3 Trace and Replay the Route
By the end of this chapter, Step doesn’t stop at the Goal. It writes the Route down, one Board per press. After that, it slides the Tiles home, one Move per press, until the parchment card says Solved.
The game as it is at the end of this chapter. Click the game to play.
If your game and this chapter part ways, here is the chapter’s finished project. Open it and compare, or start Chapter 4 from it.
To open it, start Myth Engine, choose File › Open Project... and pick the downloaded file.
3.1 The Idea
Try the game above. Press Step twenty times, the way you did in Chapter 2, and watch the count climb to 20. Press once more. This time the card doesn’t say Goal found. It says Building route...
The Tiles still sit where they were. Keep pressing. Twelve presses go by with nothing new to see. On the thirteenth, the words change to Solving...
Now press again.
Tile 1 slides up into the Blank. Press again, and Tile 8 slides right, into the Slot Tile 1 left empty. The rest follow, one Tile for each press: 1, 8, 7, 5, 4, 1, 5, 4, 1, 2, 3 and 6. After the twelfth, the card says Solved.
Your search found the Goal in Chapter 2, but it never said how to get there. What it has is a notebook of 35 lines, one for every Board it found, checked or not, in the order the Boards turned up. That isn’t a list of Moves. So how does the search find its way home?
Each line remembers one more thing, the Board it was reached from. Chapter 2 wrote that down as parentState, and promised that this chapter would follow it back. That Board is the line’s parent.
The parents are a trail of footprints. They lead only one way, backward, from where the search stopped to where it began. Start at the Goal. Its parent is the Board one Move before it, with Tile 6 one slide from home: 1, 2, 3 along the top, 4, 5 and the Blank in the middle, 7, 8, 6 along the bottom. That Board has a parent too, one Move further back. Follow the trail from parent to parent, and sooner or later you come to your own puzzle. Its parent is -1, the mark that says there’s nothing before it.
That chain, read the other way, is the Route, the Moves from your puzzle to the Goal. Each Board on it is a Route record. Twelve Moves join thirteen Boards, so there are 13 records, your puzzle and the Goal among them.
Here’s the snag. The trail starts at the Goal, and the Tiles have to start at your puzzle. So each record goes in under its Move number. That’s the movesSoFar from its line, how far it is from your puzzle. The Goal goes in as 12, the Board before it as 11, and your puzzle, last, as 0. Read them from 1 upward, and the trail plays forward.
Count the Steps, then. The search takes 20, and 1 more accepts the Goal. Copying the records takes 13, one for each, and sliding the Tiles takes 12, one for each Move. That’s 46 presses from the first to Solved.
Most of this chapter builds things you can’t see until the end. The Route is written into a table, and that table shows nothing on the screen. The Tiles move only in the last part, when Run Search learns its two new jobs.
3.2 The Plan
Here’s how the new pieces join the search you built. Read each line once for its shape, and come back to it after the last part, when every name on it is one you’ve made.
- The Goal is accepted -> Run Search starts the trail at the Goal and switches On Step Pressed to Building Route.
- Each Step in Building Route -> Copy Route Record writes one Board into Solution Route under its Move number -> its parent is the next Board to copy.
- The record whose parent is -1 -> Run Search puts Solving... on the Status Line and switches to Playing Route.
- Each Step in Playing Route -> Run Search reads the next record -> Tile For Move names the Tile that makes it -> Choose Tile sends
tileChosen, as a click does. - Hand Moves makes the Move and sends
boardChanged-> Run Search counts it as the Route’s own. On the last one, Check Goal says Solved and Run Search switches to Finished. - You slide a Tile yourself -> the search was for the old Board, so Run Search empties both tables and starts over, as in Chapter 2.
3.3 Set Up
There’s nothing to set up this time. This chapter adds no Command, no Global and no placement, so its Set up card is empty. Everything it builds lives on Puzzle Rules, which is already in the Scene.
3.4 The Route’s Page
First, the Route needs somewhere to be written.
Solution Route is a Data Table with one column, state, a Number that starts at 0. Like Search States, it starts with no rows. Run Search fills it while the game runs, one row for each record. Each row is named by its Move number, written as text, such as 12. Row 0 is your puzzle, row 1 the Board after the first Move, and so on up to the Goal.
Make it the way you made Search States. A new table’s one column is named value, so rename it state. A Data Table card on the Making page says more.
Myth makes its Data Structure with it, Solution Route Entry, as it made Search States Entry. Its one field is the column you renamed.
One row of the "Solution Route" Data Table.
3.4.1 Copy Route Record
Copy Route Record copies one record. It’s handed one Board on the trail, in board, and it does three small things with it.
It finds the Board’s line in Search States, the row named by its nine digits, and reads its movesSoFar. That’s the Board’s Move number. It keeps it in moveNumber, a Variable it declares first. Then it adds a row to Solution Route, named by that number, and writes the Board into its state.
The third thing is its answer. The Return, last in line, hands back the line’s parent, the next Board on the trail. Its Value can be a formula, and this one reads the cell straight out of Search States. The answer is a Number. So pick Number as the Return Type, as A Function card on the Making page shows.
Control Data Row works as it did in Add Search State. Leave its Operation on Add or Update, the way it starts, and its Values boxes empty.
Copies one record of the Route: a Board on the stored route to the Goal goes into the Solution Route under its Move number, which is its movesSoFar (g) in Search States. parentState is the Board its route came from: the record to copy next, or -1 after the Board the search started from.
- Name
moveNumber- Value
0
- Variable
moveNumber- Value
data('Search States', text(board), 'movesSoFar')
- Action Name
addedRow- Table
"Solution Route"- Row
text(moveNumber)
- Table
"Solution Route"- Row
text(moveNumber)- Column
"state"- Value
board
- Value
data('Search States', text(board), 'parentState')
A Board in, a record written, a parent out. Run Search will call it thirteen times in a row, once for every Board on the Route.
3.5 Which Tile Slides
Now the other half of the job. A record is only a Board. To play it, the game has to know which Tile to move.
3.5.1 Tile For Move
It looks like a hard question: which Tile turns this Board into the next one? The answer is wherever the Blank goes.
Take your puzzle, with the Blank in the center, and the first record after it, the Board after the first Move. In that Board, the Blank sits at the bottom, under the center, and Tile 1 is in the center. So Tile 1 is the one that slid. The Tile that moves is always the one that sits, on this Board, where the next Board has its Blank.
Tile For Move asks two Functions you built in Chapter 1. Slot Of Tile finds the Blank, Tile 0, in nextBoard, and Tile In Slot reads which Tile sits in that same Slot of board. The Return hands back that answer, moving.value.
It has no Variables of its own, only two Function calls and a Return.
Which Tile slides to turn a Board into the next Board of the Route: the Tile that sits in board where nextBoard has its Blank. In nextBoard it has slid into board's Blank.
- Action Name
nextBlank- board
nextBoard- tile
0
- Action Name
moving- board
board- slot
nextBlank.value
- Value
moving.value
The quiet Functions from Chapter 1 do the work again. Nobody sees them, and every Move of the Route goes through them.
3.6 All the Way Home
Last, Run Search learns what a Step does once the Goal is accepted. This is the part where the Tiles move.
Its Changes card is long, so it comes in five pieces, with the story of each between them. Take them in order.
3.6.1 Messages, Changed
First, the words. Goal found goes, because the search doesn’t stop there now. Two new rows take its place: building, for Building route..., and solving, for Solving... Type each one’s three dots as three periods, the way the card shows them.
To delete the goalFound row, click one of its cells and press Delete Selected Row, under the grid beside Add Row. The tryNew row moves up into its place. The card shows that as a Row 2 named tryNew, marked new, and the old Row 3 struck. It’s still one row, with the same words. Add the two new rows at the end.
SolvedSearching...Goal foundTry a new puzzle.Building route...Solving...3.6.2 Run Search, Changed
Run Search now has three things to remember between Steps, and they live in a Data Structure of its own, Run Search Data. On Run Search’s Data Structures card, press + and choose New Data Structure, as you did for Slide To Slot Data in Chapter 1. Myth makes it, names it after the Logic and opens it.
While the Route is built, the first field, routeBoard, holds the Board whose record is copied next. The second, movesPlayed, counts the Route’s Moves as they’re played. The last, routeNextBoard, is the Board the Route’s next Move should make, and it starts at -1. That means no Route Move is waiting.
What Run Search remembers between Steps on Puzzle Rules: routeBoard is the next Board to copy into the Route as it is built back from the Goal; movesPlayed counts the Route's Moves played so far; routeNextBoard is the Board the next Move of the Route leads to (-1 when no Route Move is under way).
Run Search reads them by names such as self.runSearchData.routeBoard, and Change Component Value changes them. Puzzle Rules already carries Run Search, so the new Data Structure arrives on it by itself, From Logic. Its card shows the new line for you to check.
Run SearchRun Search DataPuzzle RulesNext, On Step Pressed gets two more Modes, Building Route and Playing Route. Right-click the Event block and choose New Mode… for each, the way you added Searching and Finished. A new Mode joins the end of the row, after Finished. Move Left puts each one before Finished, in the card’s order. Modes on the Making page shows how. Make both before any Switch Mode that names them.
The first piece of the card shows the Data Structures line, with Not Started and Searching as they were.
Runs the A* solver one Step at a time, from the Board shown. The Step button and the Space key send stepPressed for each Step. The first Step stores that Board as the first open Search State; each Step then Expands the best open Search State (Expand Best State) until the Goal is accepted (goalAccepted). Each Step then copies one record of the Route, back along the parents (Building Route), and then plays one of its Moves (Playing Route). When the search stops (searchStopped) or the Route has been played, Step has nothing more to do (Finished). A hand Move cancels the search.
Any Objectself.runSearchData- Applies To
@self.puzzleRules- Custom Event
stepPressed
$boardState != data('Puzzle Settings', 'puzzle', 'goalBoard')- board
$boardState- movesSoFar
0- parentState
-1
- Variable
$statusLine- Value
data('Messages', 'searching', 'words')
- Event
On Step Pressed- Mode
Searching
- puzzleRules
@self.puzzleRules
- puzzleRules
@self.puzzleRules
Building Route copies one record per Step. Copy Route Record takes routeBoard and answers with its parent, as copied.value.
One If decides what comes next, and its Else is step 6. If the parent is -1, the record it copied was your puzzle, and the Route is complete. So movesPlayed starts at 0, the Status Line says Solving..., and On Step Pressed switches to Playing Route. Otherwise, the parent becomes routeBoard, and the next Step copies it.
- Action Name
copied- board
self.runSearchData.routeBoard
copied.value == (-1)- Component Value
self.runSearchData.movesPlayed- Value
0
- Variable
$statusLine- Value
data('Messages', 'solving', 'words')
- Event
On Step Pressed- Mode
Playing Route
- Component Value
self.runSearchData.routeBoard- Value
copied.value
Playing Route makes one Move per Step. It reads the record after the Moves played so far, so the first time round, that’s row 1. It holds that Board in routeNextBoard, the Board this Move should make.
Tile For Move names the Tile, as routeTile.value. Choose Tile, from Chapter 1, sends tileChosen to Puzzle Rules, the very message your click sends. Hand Moves checks the Tile is beside the Blank and makes the Move, and Slide To Slot slides it. The Route plays by the same rules your hand does.
- Component Value
self.runSearchData.routeNextBoard- Value
data('Solution Route', text(self.runSearchData.movesPlayed + 1), 'state')
- Action Name
routeTile- board
$boardState- nextBoard
self.runSearchData.routeNextBoard
- puzzleRules
@self.puzzleRules- tile
routeTile.value
Finished stays as it was. On Goal Accepted gets a new first step, and its other two change. The new step starts the trail at the Goal, setting routeBoard to the goalBoard. None of the three steps reads what another writes, so if the new one lands last, the game runs the same. Its words become Building route..., and it switches On Step Pressed to Building Route instead of Finished. On Search Stopped doesn’t change, because a search that ran out of room has no Route to build.
- Component Value
self.runSearchData.routeBoard- Value
data('Puzzle Settings', 'puzzle', 'goalBoard')
- Variable
$statusLine- Value
data('Messages', 'building', 'words')- Value
data('Messages', 'goalFound', 'words')
- Event
On Step Pressed- Mode
Building Route- Mode
Finished
- Variable
$statusLine- Value
data('Messages', 'tryNew', 'words')
- Event
On Step Pressed- Mode
Finished
3.6.3 Two Kinds of Move
On Board Changed now has two kinds of Move to tell apart, because Hand Moves sends boardChanged after every Move, the Route’s and yours alike.
A Move that makes routeNextBoard is the Route’s own. Run Search adds 1 to movesPlayed. And if that Move made the Goal, the Route has been played, and On Step Pressed switches to Finished. Check Goal says Solved in the same moment, as it does for any Move.
Any other Move is yours, and the search was for the old Board. So the Else does what On Board Changed did in Chapter 2: it empties Search States, and now Solution Route too. It sets routeNextBoard back to -1 and the count to 0, clears the Status Line unless the Board is the Goal, and switches back to Not Started.
This card has three Ifs. The outer one is step 1, and step 5 is its Else. Step 3 sits inside step 1’s Then panel, and step 10 inside its Else panel, and neither of those two has an Else of its own.
Chapter 2’s five steps all go. Twelve new ones take their place, so this last piece isn’t a Changes card at all. It’s On Board Changed whole, from Run Search’s own card. Delete the old five. Step 3, the If, takes step 4 with it when it goes. Then build the twelve you see. Each is a kind of block you’ve made before.
$boardState == self.runSearchData.routeNextBoard- Component Value
self.runSearchData.movesPlayed- Operator
+=- Value
1
$boardState == data('Puzzle Settings', 'puzzle', 'goalBoard')- Event
On Step Pressed- Mode
Finished
- Table
"Search States"
- Table
"Solution Route"
- Component Value
self.runSearchData.routeNextBoard- Value
-1
- Variable
$statesChecked- Value
0
$boardState != data('Puzzle Settings', 'puzzle', 'goalBoard')- Variable
$statusLine- Value
""
- Event
On Step Pressed- Mode
Not Started
Hand Moves, Choose Tile and Check Goal each get a new Description. It now says that a Move can come from the Route as well as from your hand. Nothing else on their cards changes, so they aren’t shown here. Run Search’s own Description is new too. Each one is yours to type or to leave.
Run the game. Press Step through the search, as in Chapter 2. Where it once said Goal found, the card now says Building route... Press on through all thirteen records, until the words change to Solving... Now press once more.
Tile 1 slides up into the Blank.
Keep pressing. One Tile after another, the Route plays out, and on the twelfth slide the card says Solved. Your search found a shortest Route, and now it walks it.
Here is what to watch for, one press at a time.
- Press Step 20 times. The count climbs to 20 and the card says Searching..., as in Chapter 2, while not a Tile moves.
- Press once more, the 21st. The card says Building route..., and the count stays at 20.
- Press 13 more times. Nothing moves and the words stay, until the 34th press changes them to Solving...
- Press once more. Tile 1 slides up into the Blank, at the same even speed as when you click it.
- Keep pressing. The Tiles slide in this order: 1, 8, 7, 5, 4, 1, 5, 4, 1, 2, 3 and 6. Each press moves one Tile, and the count stays at 20.
- On the 46th press, Tile 6 slides up into its place, and the card says Solved.
- Press Step again. Nothing happens, because the Route has been played.
- Start the game again, and press Step until a Tile or two has moved. Now click a Tile beside the Blank yourself. It slides, the count goes back to 0, and the words go. The next Step starts over, with a new search from the new Board you made.
Each line in the notebook remembers its parent. Once the Goal is accepted, Building Route follows the parents back from the Goal, one record per Step, and writes each into Solution Route under its Move number. Playing Route reads them forward, from row 1. Tile For Move finds each Tile by where the Blank goes, and Choose Tile hands it to Hand Moves, the same way your click does. A Move that isn’t the Route’s own starts the search over.
Underneath all of it is one idea. The search never stored a Route. Each line kept only one small fact, the Board before it, and the whole Route was hidden in those facts. A breadth-first search, which tries every Board in order of Moves, agrees with this one: no Route from your puzzle is shorter than 12 Moves.
3.7 If It Didn’t Work
This chapter’s pieces wait for each other, so a small slip can hide until the end. That’s normal. Press Step, watch the words on the card, and count the presses.
The card still says Goal found? Look at On Goal Accepted, where step 2’s Value should read the building row, and step 3 should switch to Building Route, not Finished.
Building route... never changes to Solving...? The trail never reaches -1. Look at step 2 of Building Route, the If, where copied.value == (-1). Then look at Copy Route Record’s Return, step 5, whose Value reads the ‘parentState’ column, quote marks and all.
Solving... appears, but no Tile moves when you press Step? Perhaps the record isn’t where Playing Route looks for it, in the row after the Moves played so far. Open Solution Route while the game runs. If it has no rows, look at Copy Route Record’s step 3, Control Data Row, and its Row, text(moveNumber). If the rows are there, look at Playing Route’s step 1 and its row, text(self.runSearchData.movesPlayed + 1).
The Tiles slide, but the wrong ones? Look at Tile For Move. Its Slot Of Tile looks in nextBoard for Tile 0, and its Tile In Slot looks in board.
One Tile slides, and then nothing moves? Perhaps movesPlayed never grows, so Playing Route reads the same record again. Look at step 2 of On Board Changed. It should add 1 to self.runSearchData.movesPlayed, with +=.
A Route Move starts the search over, so the count drops to 0 after one slide? Run Search didn’t know the Move was its own. Look at On Board Changed, step 1, $boardState == self.runSearchData.routeNextBoard, and at Playing Route’s step 1, which sets routeNextBoard.
A box the editor marks as an error? Count its quote marks and its brackets, because one may be missing.
Each of these is one small fix. Make it, run the game again, and you’re back with the chapter. The catch-up download at the top of this chapter is its finished project, if you’d like to compare.
Watch a short Route from start to finish. Open the Puzzle Settings table and type 123456708 into the puzzle row’s startBoard cell, one Move from the Goal. Run the game and count the presses. The first checks your puzzle, the second accepts the Goal, two more copy the two records, and the fifth slides Tile 8 home. Five presses in all.
Next, try a puzzle two Moves away, and three. Press Step until the count stops climbing, and read it. Then add up the Steps still to come: 1 to accept, the Moves plus 1 for the records, and the Moves again for the slides. Did the game agree?
Before Chapter 4, put 542703816 back in startBoard.
The search found the way, and now it walks it, one press at a time. In Chapter 4, it walks it on its own.