182 lines
7.8 KiB
HTML
182 lines
7.8 KiB
HTML
|
<!DOCTYPE html>
|
|||
|
|
<html>
|
|||
|
|
|
|||
|
|
<head>
|
|||
|
|
<meta charset="utf-8" >
|
|||
|
|
<title>Slide Puzzle Description</title>
|
|||
|
|
<link rel="stylesheet" href="style/description.css">
|
|||
|
|
</head>
|
|||
|
|
|
|||
|
|
<body>
|
|||
|
|
<!-- NOTE: This page does not bother to demonstrate HTML entities, as they are mostly obsoleted by a compose key. ☺ -->
|
|||
|
|
|
|||
|
|
<h1>Video Slide Puzzle</h1>
|
|||
|
|
<p class="subtitle">
|
|||
|
|
Brandon Dyck<br>
|
|||
|
|
CS 2550-X01
|
|||
|
|
</p>
|
|||
|
|
|
|||
|
|
<p><a href="game.html">Play game</a></p>
|
|||
|
|
|
|||
|
|
<h2>Game Description</h2>
|
|||
|
|
|
|||
|
|
<figure>
|
|||
|
|
<img class="illustration" src="image/puzzleland.jpg" alt="The 14-15 Puzzle in Puzzleland">
|
|||
|
|
<figcaption>
|
|||
|
|
From Sam Lloyd's <cite>Cyclopedia of 5000 Puzzles</cite> (1915).<br>
|
|||
|
|
Public domain.
|
|||
|
|
</figcaption>
|
|||
|
|
</figure>
|
|||
|
|
|
|||
|
|
<p>
|
|||
|
|
Video Slide Puzzle is a Javascript/HTML5 implementation of the classic slide puzzle, or <a href="https://en.wikipedia.org/wiki/15_puzzle"><span style="font-style:italic">15 puzzle</span></a>, with a video, rather than a static image, as the texture for the puzzle pieces. When the game loads, a list of available videos is loaded into the "Select background" option list via AJAX, the puzzle is rendered using the first video in the list, and the player can able to select a different video at any time during gameplay using the "Select background" list.
|
|||
|
|
</p>
|
|||
|
|
|
|||
|
|
<p>
|
|||
|
|
The puzzle has fifteen pieces and one empty space arranged in a 4×4 grid. When the game loads, and subsequently whenever the player clicks the "New game" button, the pieces are shuffled to a solvable starting position, and the timer is reset to zero and starts counting upward. When the player clicks a puzzle piece adjacent to the empty space, the piece moves into the space, leaving a space in its previous position. Motion of puzzle pieces is animated. Once the pieces are in the correct positions and until a new game is started, the timer stops, the empty space in the puzzle is filled with the missing piece of the video, and clicking on the puzzle will no longer have any effect until a new game is started.
|
|||
|
|
</p>
|
|||
|
|
|
|||
|
|
<p>
|
|||
|
|
The "Undo" button is disabled when gameplay starts and is enabled as soon as the player moves a puzzle piece. When the player clicks the "Undo" button, the last piece moved moves to its previous position. This can be repeated until all moves have been reverted, at which point the "Undo" button is disabled again until the player makes another move.
|
|||
|
|
</p>
|
|||
|
|
|
|||
|
|
<p>
|
|||
|
|
You can see a non-functional <a href="gameboard.html" target="gameboard">mockup of the game board</a>. (The mockup does not show a game in progress, as that would require either a great deal of manual video editing or writing the bulk of the game's view code.) There is also a <a href="prototype.html" target="prototype">proof-of-concept</a> of rendering and moving slices of an HTML5 video element.
|
|||
|
|
</p>
|
|||
|
|
|
|||
|
|
<h2>Model Design</h2>
|
|||
|
|
<h3>Data representation</h3>
|
|||
|
|
The model represents the game board internally with the following objects:
|
|||
|
|
<dl>
|
|||
|
|
<dt><span class="var const">Rows</span></dt>
|
|||
|
|
<dd><p>A public, constant integer indicating the number of rows in the game board.</p></dd>
|
|||
|
|
|
|||
|
|
<dt><span class="var const">Columns</span></dt>
|
|||
|
|
<dd><p>A public, constant integer indicating the number of columns in the game board.</p></dd>
|
|||
|
|
|
|||
|
|
<dt><span class="var const">Empty</span></dt>
|
|||
|
|
<dd><p>A public, constant integer representing the empty puzzle piece.</p></dd>
|
|||
|
|
|
|||
|
|
<dt><span class="var">position<span></dt>
|
|||
|
|
<dd>
|
|||
|
|
<p>
|
|||
|
|
A private, zero-indexed sequence of <span class="var const">Rows</span> × <span class="var const">Columns</span> integers from 0 to <span class="var const">Rows</span> × <span class="var const">Columns</span> − 1 representing the initial game board layout. Each index corresponds to a game board position as follows (for a 4×4 grid):
|
|||
|
|
</p>
|
|||
|
|
|
|||
|
|
<table>
|
|||
|
|
<tbody>
|
|||
|
|
<tr>
|
|||
|
|
<td>0</td>
|
|||
|
|
<td>1</td>
|
|||
|
|
<td>2</td>
|
|||
|
|
<td>3</td>
|
|||
|
|
</tr>
|
|||
|
|
<tr>
|
|||
|
|
<td>4</td>
|
|||
|
|
<td>5</td>
|
|||
|
|
<td>6</td>
|
|||
|
|
<td>7</td>
|
|||
|
|
</tr>
|
|||
|
|
<tr>
|
|||
|
|
<td>8</td>
|
|||
|
|
<td>9</td>
|
|||
|
|
<td>10</td>
|
|||
|
|
<td>11</td>
|
|||
|
|
</tr>
|
|||
|
|
<tr>
|
|||
|
|
<td>12</td>
|
|||
|
|
<td>13</td>
|
|||
|
|
<td>14</td>
|
|||
|
|
<td>15</td>
|
|||
|
|
</tr>
|
|||
|
|
</tbody>
|
|||
|
|
</table>
|
|||
|
|
|
|||
|
|
<p>
|
|||
|
|
The value at each index represents the correct position of the puzzle piece currently in that position. For example, if <span class="var">position</span><sub>4</sub> = 12 in a 4×4 puzzle, then the puzzle piece at the first column and second row must be moved to the first column and fourth row in order to solve the puzzle. The exception is that the value <span class="var const">Rows</span> × <span class="var const">Columns</span> − 1 represents the empty space in the board.
|
|||
|
|
</p>
|
|||
|
|
</dd>
|
|||
|
|
|
|||
|
|
<dt><span class="var">moves</span></dt>
|
|||
|
|
<dd>
|
|||
|
|
<p>
|
|||
|
|
A private integer sequence representing the order in which pieces have been moved into the empty space. This sequence can be used together with <span class="var">position</span> to reconstruct the initial board position.
|
|||
|
|
</p>
|
|||
|
|
</dd>
|
|||
|
|
</dl>
|
|||
|
|
|
|||
|
|
<h3>Functions</h3>
|
|||
|
|
The model provides the following public functions:
|
|||
|
|
<dl>
|
|||
|
|
|
|||
|
|
|
|||
|
|
<dt>getPosition():integer[]</dt>
|
|||
|
|
<dd>
|
|||
|
|
<p>Returns a copy of <span class="var">position</span>.</p>
|
|||
|
|
</dd>
|
|||
|
|
|
|||
|
|
<dt>getPositionOf(<span class="var">piece</span>:integer):integer[]</dt>
|
|||
|
|
<dd>
|
|||
|
|
<p>Returns the current position of <span class="var">piece</span>.</p>
|
|||
|
|
</dd>
|
|||
|
|
|
|||
|
|
<dt>getMoves():integer[]</dt>
|
|||
|
|
<dd>
|
|||
|
|
<p>Returns a copy of <span class="var">moves</span>.</p>
|
|||
|
|
</dd>
|
|||
|
|
|
|||
|
|
<dt>isSolved():boolean</dt>
|
|||
|
|
<dd>
|
|||
|
|
<p>Returns a boolean value indicating whether the puzzle is in a solved position.</p>
|
|||
|
|
</dd>
|
|||
|
|
|
|||
|
|
<dt>move(<span class="var">piece</span>:integer):void</dt>
|
|||
|
|
<dd>
|
|||
|
|
<p>
|
|||
|
|
Moves <span class="var">piece</span> into the empty space. Throws an exception if <span class="var">piece</span> is not an integer, <span class="var">piece</span> < 0, <span class="var">piece</span> ≥ <span class="var const">Rows</span> × <span class="var const">Columns</span>, or <span class="var">piece</span> is not adjacent to the empty space.
|
|||
|
|
</p>
|
|||
|
|
</dd>
|
|||
|
|
|
|||
|
|
<dt>undo():void</dt>
|
|||
|
|
<dd>
|
|||
|
|
<p>
|
|||
|
|
Changes <span class="var">position</span> to its previous state and removes the last element of <span class="var">moves</span>. Throws an exception if <span class="var">moves</span> is empty.
|
|||
|
|
</p>
|
|||
|
|
</dd>
|
|||
|
|
|
|||
|
|
<dt>isSolved:boolean</dt>
|
|||
|
|
<dd>
|
|||
|
|
<p>
|
|||
|
|
A public read-only property indicating whether the puzzle is in its solved position.
|
|||
|
|
</p>
|
|||
|
|
</dd>
|
|||
|
|
</dl>
|
|||
|
|
|
|||
|
|
<h3>Initialization</h3>
|
|||
|
|
<p>Initialization of the model does the following:</p>
|
|||
|
|
<ol>
|
|||
|
|
<li>
|
|||
|
|
Initialize <span class="var">position</span> to a length of <span class="var const">Rows</span> × <span class="var const">Columns</span>, with each value equal to its index.
|
|||
|
|
</li>
|
|||
|
|
|
|||
|
|
<li>
|
|||
|
|
Randomly arrange the puzzle using the Fisher-Yates (Knuth) shuffle.
|
|||
|
|
</li>
|
|||
|
|
|
|||
|
|
<li>
|
|||
|
|
Check the puzzle for solvability using the formula described in <a href="https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html">Mark Ryan (2004)</a>, returning to Step 2 if the puzzle is not solvable.
|
|||
|
|
</li>
|
|||
|
|
|
|||
|
|
<li>
|
|||
|
|
Initialize <span class="var">moves</span> to a length of 0.
|
|||
|
|
</li>
|
|||
|
|
</ol>
|
|||
|
|
|
|||
|
|
<p>
|
|||
|
|
The Fisher-Yates shuffle delivers an even distribution of permutations in <span class="var">O</span>(<span class="var">n</span>) time. Since exactly one half of all permutations of the board are solvable (<a href="http://kevingong.com/Math/SixteenPuzzle.html#proof">Kevin Gong 2004</a>), we can expect to have to shuffle the board 1.5 times per game, on average. Checking for solvability using a naïve algorithm based on Ryan's formula will run in <span class="var">O</span>(<span class="var">n</span><sup>2</sup>) time, but this is not enough to matter on a game board small enough for human use. Overall, this seems a reasonably fast method of creating solvable games.
|
|||
|
|
</p>
|
|||
|
|
|
|||
|
|
</body>
|
|||
|
|
|
|||
|
|
</html>
|