Myth Engine: 8-Puzzle Solver
Learn A* Search by Building a Sliding Puzzle Game, Step by Step
Welcome
This is 8-Puzzle Solver. Play it first. You’ll make every piece of it yourself.
Click a Tile beside the Blank, or press Solve.
Eight Tiles sit out of order on the Board, and the card beside them shows the Goal. The empty square among the Tiles is the Blank. These are your keys:
- Click a Tile beside the Blank, and it slides in. Or press its number, 1 to 8.
- Step, or Space, takes one Step of the search.
- Solve, or A, takes the Steps by itself, and pauses when you press it again or press Escape.
- New puzzle, or N, mixes the Tiles. Reset, or R, puts that puzzle back the way it began.
- The Estimate button on the card, or E, switches between Manhattan and Misplaced Tiles.
Slide a Tile or two first, then press Solve and keep your eyes on the card.
The Story
A worktable of dark wood. A brass ring-sphere stands at one corner, and a lantern burns at the other. Star charts curl at the edges, with a compass and a spyglass among them. In the middle sits a brass frame around a square of navy velvet, and on the velvet lie eight cream Tiles, out of order. They read 5 4 2 across the top, 7, the Blank and 3 across the middle, and 8 1 6 across the bottom.
A parchment card beside the frame shows where they belong: 1 2 3, 4 5 6, 7 8, and the Blank last. That’s the Goal.
You can put them in order by hand, and every slide is one Move. Or you can press Step and watch a search work it out.
The Tiles stay still while it works. On the card, “Searching…” appears, and a count climbs: States checked 1, 2, 3. On the 21st Step, the search picks the Goal itself as its best Board, and accepts it. It has checked 20 Boards to get there. Now it writes down the Route, one Board per Step, from the Goal back to the start. At last the Tiles begin to slide. Twelve Moves later, the Board matches the card, and no Route from this Board is shorter.
That search has a name: A* Search. By the end of Chapter 3, you’ll have built it yourself.
What You’ll Build
All of it, chapter by chapter.
- The table, set. The Board, the Goal on its card and the title plate are all there. Click a Tile beside the Blank, and it glides there in 0.22 seconds and lands square. Put them all in order, and the card says Solved.
- The search. A Step button joins the table, and each press checks one more Board while the Tiles stay still. It picks the open Board with the lowest Moves so far plus Estimate. The Estimate is a guess at how many Moves are left. From this puzzle, the search checks 20.
- The Route. Keep pressing Step. The search follows the Route back from the Goal to the start, a Board at a time. Then it plays the Route forward, one slide per Step, and the Tiles go home in 12 Moves.
- The search on its own. The gold Solve button takes the Steps for you, up to 8 every 0.05 seconds. Press it again, and the work holds still.
- New puzzles and two Estimates. New puzzle mixes the Tiles with 12 random Moves from the Goal, and Reset puts that puzzle back. The Estimate button switches between two guesses. Solve the first puzzle both ways: 20 Boards checked with Manhattan, 84 with Misplaced Tiles, and the same 12 Moves. A Message Line under the buttons says what each Step does.
Five chapters, one for each of those. Each chapter opens with a box called Goal, and in it is the game as that chapter leaves it, ready to play. So you see where you’re going before you start.
How Each Chapter Teaches
Every piece of the game comes to you as a story and a card. The story puts the piece in your head: what it does, and roughly how. The card gives every exact name and number. Read the story, then build from the card with that picture in mind. Run your game, and watch it happen.
A* Search comes to you the same way. You’ll watch each part of it work on the screen before you learn its name.
Making what a card shows is the page for the cards. It shows how to make each kind of card, in the editor’s own words. Start there before Chapter 1, and come back whenever a card shows you something you haven’t made yet.
Every chapter’s Goal box also has a catch-up download. It’s that chapter’s finished project. If your game and the chapter part ways, open it and compare the two. Or start the next chapter from it.
Get the Starter Kit
The game uses two pictures, and the Starter Kit holds both. One is the whole worktable: the brass frames, the velvet, the parchment card, the lantern and the star charts. The other is a tiny white square. Every Tile, every cell of the Goal picture and every button is that square, tinted. The game has no sounds, so there are none to install.
You’ll build the game in Myth Engine. If it isn’t on your computer yet, Get Myth Engine is where to find it.
Once Myth Engine is open, make a new Blank 2D project and install the Starter Kit into it. Choose File > Install Myth Pack…, pick the file, and press Install. Chapter 1 starts there.
To install it, open Myth Engine, choose File › Install Myth Pack... and pick the downloaded file.
Get the Finished Game’s Project
The game at the top of this page is a project too, and you can open it in Myth Engine. It’s the same file as Chapter 5’s catch-up download. Open it with File > Open Project… whenever you want to see how a finished piece fits together.
To open it, start Myth Engine, choose File › Open Project... and pick the downloaded file.