3 Settle One Cheapest Cell
By the end of this chapter, the search wakes. Press Step, and Dijkstra’s algorithm settles the camp, then one more cell with every Step, always the cheapest it has reached. Rings show what it has found, the Status line names each cell it settles, and Reset starts it over.
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.
Starting with this chapter? It begins where Chapter 2 ends, and Chapter 2’s Goal has that chapter’s finished project.
3.1 The Idea
The map is painted. The compass waits at the camp. Above the three buttons, the Status line still says Paint terrain. This chapter gives Step something to do.
Press Step in the game above. Inside the orange ring at the camp, a white one appears, and thin cyan rings close around two cells: the road to the camp’s right, and the forest below it. The Status line says Cell 00: cost 0. Press Step again. The white ring moves onto the road, and the line says Cell 01: cost 1.
That’s Dijkstra’s algorithm at work. For every cell it reaches, it answers one question: what’s the cheapest way there from the camp?
The answer so far is the cell’s distance. Here a distance is a cost, never a count of cells. The camp’s is 0, because you start there. The road beside it is 1, because road costs 1 to enter. The forest below is 3.
The cells the search has reached, but isn’t sure of yet, are its frontier: the thin cyan rings. Each Step takes the frontier cell with the smallest distance and makes that distance final. That’s settling the cell. Its ring turns thick, white while it’s the newest, and blue after that.
Final means final. Nothing the search finds later can beat a settled cell. Why that holds is the chapter’s one hard idea, and Cheapest first takes it slowly.
Then the settled cell makes an offer to each of its neighbors: a route through itself, at its own distance plus what the neighbor costs to enter. A neighbor takes the offer only when it’s cheaper than the best it has. That’s relaxing the neighbor, and it’s how cells join the frontier.
You might expect the search to make for the tower. It never does. When it chooses the next cell, it doesn’t ask where the tower is. It settles whatever is cheapest from the camp, whichever way that lies, and the tower’s turn comes when its cost comes.
Most of this chapter is the search’s thinking, and thinking shows nothing. So the screen won’t change at all until One Step, where the Step button wakes the search. In Rings over the map, the last part, you’ll watch it spread across the map.
3.2 The Plan
Here’s how the pieces work together. Read each line from left to right. Most of the names are new, so skim them now and come back after the rings, when you’ve built every one.
- Step is clicked, or Space is pressed -> Request Step sends
stepRequested-> Step Trial makes one Step. - Step Trial’s first Step -> Check Maze Input checks the map -> the camp gets distance 0, and Settle Cheapest Cell settles it.
- Each Step after that -> Settle Cheapest Cell asks Choose Cheapest Cell for the cheapest frontier cell, and settles it.
- A cell is settled ->
cellSettled-> Show Settled Cell writes the Status line. - The settled cell isn’t the tower -> Relax Neighbors offers each neighbor a route, through Relax Neighbor.
- A Step ends ->
searchChanged-> every Search Outline colors its ring again. - R is pressed, Reset is clicked, or a cell’s cost changes -> Reset Trial calls Clear Trial -> every record is cleared, and Clear Trial sends
trialCleared-> Step Trial is Ready again.
3.3 Set Up
This chapter’s Set up card is short.
COMMANDS adds two Button Commands, Step on Space and Reset on R, made in the Input Manager as Paint was in Chapter 2.
GLOBAL VARIABLES adds $currentCell, the cell the last Step settled. It starts at -1: no cell at all. Make it with New Global… on Reset Trial’s Globals card, as before, and type -1 into its Default.
SpaceR3.4 What the Search Writes Down
First, the search needs somewhere to write.
Everything it finds goes into Maze Cells, in three new columns beside cost. The first, distance, you’ve met. A distance of 1000000 means the search hasn’t reached the cell yet, since that’s far more than any route on this map could cost. The second, parent, holds a cell’s parent: the cell its cheapest route came through. Its -1 means none yet. The third, settled, is 1 once the cell’s distance is final, and 0 until then.
A table’s columns are the fields of its Data Structure. So open Maze Cells Entry and press Add Field for each, as you added rows to Maze Settings Entry in Chapter 2. Give each the Value its card shows.
One thing will look wrong, and isn’t. A new field fills the 120 rows already there with 0, whatever Value you type after it. So your distance and parent columns say 0 where the table’s FIRST ROWS show 1000000 and -1. Leave them. In One Step, Clear Trial writes all three columns on every row each time the game starts. Nothing reads them before then.
One row of the "Maze Cells" Data Table.
11000000-1011000000-1011000000-10Maze Settings gets two columns. The first, unreached, is the number the search writes for not reached yet, the same 1000000. The second, maxCost, is the most a cell may cost, 99. A route that entered every cell of the map at 99 would still cost far less than unreached. So no real distance is ever mistaken for not reached.
Add them to Maze Settings Entry the same way. Then type both into the rules row too, as you typed 10 for rows, because a new field gives that row 0 as well.
One row of the "Maze Settings" Data Table.
12100119991000000Run the game if you like. Nothing has changed, and nothing will for a while.
3.5 Cheapest First
Now the heart of the search: choosing which cell to settle, and settling it.
3.5.1 Choose Cheapest Cell
Choose Cheapest Cell answers one question. Which frontier cell has the smallest distance? It hands back that cell’s number, or -1 when the frontier is empty.
It does what you’d do with a price list and one finger. Read down from the top. Keep your finger on the cheapest price so far, and move it only for a lower one. Here the Repeat reads every row of Maze Cells in order, and as in Lay Out Map, local.index is the cell number. The finger is cheapest, and the price under it is cheapestDistance. The card’s first two steps make them, as Declare Variables that live only while the Function runs.
A row is a candidate only when three tests are true. The If joins them with &&, which means and: it isn’t settled, it isn’t a wall, and its distance is below cheapestDistance. Before the Repeat starts, cheapestDistance is set to unreached, so a cell the search hasn’t reached can never win.
Now look at the third test. It’s <, not <=. A price that only ties never moves your finger, so when two cells have the same distance, the first one met stays chosen. That’s always the lower number, and it decides the fourth Step, as you’ll see.
The frontier cell with the smallest distance, or -1 when the frontier is empty. The frontier is every cell that is not a Wall, not settled, and already reached (its distance is less than Maze Settings unreached). On equal distances the lowest cell number wins.
- Name
cheapest- Value
-1
- Name
cheapestDistance- Value
0
- Variable
cheapest- Value
-1
- Variable
cheapestDistance- Value
data('Maze Settings', 'rules', 'unreached')
dataCount('Maze Cells')timesdata('Maze Cells', local.index, 'settled') == 0 && data('Maze Cells', local.index, 'cost') != data('Terrains', 'Wall', 'cost') && data('Maze Cells', local.index, 'distance') < cheapestDistance- Variable
cheapest- Value
local.index
- Variable
cheapestDistance- Value
data('Maze Cells', local.index, 'distance')
- Value
cheapest
3.5.2 Settle Cheapest Cell
Settle Cheapest Cell turns that choice into a certainty. Watch $currentCell. It’s the Global the Function keeps the chosen cell in, so the rest of the game can find it. When the frontier is empty, it’s -1, and the card’s If lets nothing else happen. Otherwise the cell is settled, and the Function sends cellSettled to say so.
Two names on its card need a word. The call’s Action Name is cheapest. That’s the word for the finger in Choose Cheapest Cell, but here it names the call. So cheapest.value is the number the call hands back, the cell under the finger. On the block it shows as cheapest alone. And Set Data Cell finds the row by its name. The formula dataRow('Maze Cells', $currentCell) gives the name of the row at that number, such as Cell 12.
Set Data Cell is back from Chapter 2, in the Action List while Advanced Mode is on.
Visited, down on the sidebar, has said 0 ever since Chapter 1. It was waiting for this. It counts settled cells, and only those. A cell the search has reached but not settled, with only a thin cyan ring, isn’t counted.
Here is the chapter’s one hard idea, so take it slowly. Why can a settled cell’s distance never change again?
Say the cheapest frontier cell has distance 3. Any other way to it, one the search hasn’t found yet, must leave the settled cells somewhere. Where it leaves, it passes through a frontier cell. Every frontier cell’s distance is already 3 or more. That’s what cheapest means.
From there the way on can only add, because no cost on the map is below 0. So no way round comes in under 3. The cell is settled at 3, for good.
That’s why the search never goes back to fix a settled cell. It’s also why every cost must stay at 0 or above, and Check Maze Input, in The map is checked first, sees to that.
Nothing listens for cellSettled yet. In One Step, the Status line will.
Settles the cheapest frontier cell (Choose Cheapest Cell): marks it settled, adds 1 to Visited, and sends cellSettled, so the Status line can name it. The cell settled becomes the current cell (the Project Global currentCell), which is -1 when the frontier was empty and nothing was settled; cell gives the same number.
- Action Name
cheapest
- Variable
$currentCell- Value
cheapest.value
$currentCell >= 0- Table
"Maze Cells"- Row
dataRow('Maze Cells', $currentCell)- Column
"settled"- Value
1
- Variable
$visited- Operator
+=- Value
1
- Custom Event
cellSettled
- Value
$currentCell
3.6 A Cheaper Way In
A settled cell has one more job: it offers each of its neighbors a route through itself.
3.6.1 Relax Neighbor
Relax Neighbor makes one offer, to one neighbor. It asks Find Grid Neighbor, your Function from Chapter 2, which cell lies in its direction. The answer comes back as next.value, and goes into the Variable neighbor.
The offer goes only to a neighbor that can take it: one on the map, not a wall, and not settled. A settled cell is final, so it’s never offered anything. The price comes next, newDistance: this cell’s distance, plus the neighbor’s cost. If that’s below the neighbor’s distance so far, the neighbor takes it, and two Set Data Cells write its new distance, and this cell as its parent.
Count the camp’s offers. The camp settles at 0, and its neighbors are asked in turn. Up is off the map, so Find Grid Neighbor answers -1, and nothing is offered. Right is road, cost 1. The offer is 0 plus 1, far below 1000000, so the road takes it: distance 1, with the camp as its parent. Below is forest, and it takes 0 plus 3. Left is off the map again, so that’s two thin cyan rings from one settled cell.
An offer that only ties is turned down, because the second If asks <. So a cell keeps the parent it found first. The parent column has no reader yet. In Chapter 4, the route is found by following parents home from the tower.
Offers one neighbor of a settled cell a route through it. The neighbor is the cell next to cell in direction (a row of Directions). A neighbor on the map that is not a Wall and not settled gets distance (cell's distance plus the neighbor's cost) and cell as its parent, but only when that is strictly smaller than its distance so far, so an equal route keeps the parent it found first.
- Name
neighbor- Value
-1
- Name
newDistance- Value
0
- Action Name
next- cell
cell- direction
direction
- Variable
neighbor- Value
next.value
neighbor >= 0 && data('Maze Cells', neighbor, 'cost') != data('Terrains', 'Wall', 'cost') && data('Maze Cells', neighbor, 'settled') == 0- Variable
newDistance- Value
data('Maze Cells', cell, 'distance')
- Variable
newDistance- Operator
+=- Value
data('Maze Cells', neighbor, 'cost')
newDistance < data('Maze Cells', neighbor, 'distance')- Table
"Maze Cells"- Row
dataRow('Maze Cells', neighbor)- Column
"distance"- Value
newDistance
- Table
"Maze Cells"- Row
dataRow('Maze Cells', neighbor)- Column
"parent"- Value
cell
3.6.2 Relax Neighbors
Relax Neighbors makes all four offers, one after another. A Repeat runs once for each row of Directions, and dataRow hands Relax Neighbor that row’s name: Up, Right, Down, then Left.
That’s the order Chapter 2 asked you to keep. Here it is in use. The search looks around each cell up, right, down and left.
Offers every neighbor of one settled cell a route through it (Relax Neighbor), in the order of Directions: Up, Right, Down, Left.
dataCount('Directions')times- cell
cell- direction
dataRow('Directions', local.index)
Nothing calls these yet. Step Trial will, in One Step.
3.7 The Map Is Checked First
One more piece comes before the first Step: a check that the map can be searched at all.
3.7.1 Check Maze Input
A search of a broken map couldn’t be trusted. So Check Maze Input looks at the map and Maze Settings before anything is settled. It hands back one word, problem. That’s the name of a row of Messages, or nothing at all when every rule holds.
It catches your own slips, too. The likeliest is a rules row that still holds Add Field’s 0s, and If it didn’t work shows what the Status line says then.
There are five rules, in the order of the card’s Description. The map must have as many cells as columns times rows, and the settings maxCost and unreached must make sense together. The camp and the tower must be cells of the map. Every cost must be a wall, or a whole number from 0 up to maxCost. Last, the camp and the tower may not be walls. The game’s words call those two S and G, for start and goal, as in Unblock S and G.
The check takes two limits from Step Trial, which calls it. The first, maxCostLimit, is 99. That’s the most maxCost may be, so every cost stays within two digits. The second, unreachedLimit, is the most unreached may be: 1000000000. They’re Step Trial’s Shared Variables, not numbers typed into the check, so you can see them and change them without opening it.
The rule about costs is the one the search rests on. A cost below 0 would let a longer route look cheaper, and a settled distance wouldn’t be final any more. The wall’s -1 is the one exception, because a wall is never offered anything.
The card is long. But most of it is one shape five times: an If with one Change Variable inside. The If for the costs sits in a Repeat, which visits every cell. Each If’s condition joins its tests with ||, which means or, so any true test breaks the rule.
The rules are asked from the last to the first. Each broken rule writes its row’s name over the one before, so when several are broken, the first rule is written last. That’s the one the player reads.
A few pieces are new. Step 8 multiplies: with the Operator *=, the Value multiplies what the Variable held, so mapCells becomes columns times rows. A number that isn’t whole differs from its own floor(), and that’s what each test with floor() asks. And problem is words, so its Declare Variable’s Type is Text. Step 9 empties it with "", two double quote marks with nothing between. The Function’s Return Type is Text too, and the Return at the bottom hands problem back.
Checks the map and Maze Settings before a search begins. problem is the Messages row of the first rule that is broken, or empty when every rule holds: the map has columns times rows cells (wrongMapSize); maxCost is a whole number from 0 to maxCostLimit, and unreached is larger than any route can cost and at most unreachedLimit (wrongSettings); the Camp and the Tower are cells of the map (wrongEndpoints); every cost is a Wall or a whole number from 0 to maxCost (wrongCost); neither the Camp nor the Tower is a Wall (blockedEndpoint).
- Type
Text- Name
problem
- Name
camp- Value
0
- Name
tower- Value
0
- Name
mapCells- Value
0
- Variable
camp- Value
data('Maze Settings', 'rules', 'startCell')
- Variable
tower- Value
data('Maze Settings', 'rules', 'goalCell')
- Variable
mapCells- Value
data('Maze Settings', 'rules', 'columns')
- Variable
mapCells- Operator
*=- Value
data('Maze Settings', 'rules', 'rows')
- Variable
problem- Value
""
data('Maze Cells', camp, 'cost') == data('Terrains', 'Wall', 'cost') || data('Maze Cells', tower, 'cost') == data('Terrains', 'Wall', 'cost')- Variable
problem- Value
'blockedEndpoint'
dataCount('Maze Cells')timesdata('Maze Cells', local.index, 'cost') < data('Terrains', 'Wall', 'cost') || data('Maze Cells', local.index, 'cost') > data('Maze Settings', 'rules', 'maxCost') || data('Maze Cells', local.index, 'cost') != floor(data('Maze Cells', local.index, 'cost'))- Variable
problem- Value
'wrongCost'
- Action Name
isCampOnMap- Table
"Maze Cells"- Row
camp
- Action Name
isTowerOnMap- Table
"Maze Cells"- Row
tower
isCampOnMap.value == false || camp != floor(camp) || isTowerOnMap.value == false || tower != floor(tower)- Variable
problem- Value
'wrongEndpoints'
data('Maze Settings', 'rules', 'maxCost') < 0 || data('Maze Settings', 'rules', 'maxCost') > maxCostLimit || data('Maze Settings', 'rules', 'maxCost') != floor(data('Maze Settings', 'rules', 'maxCost')) || data('Maze Settings', 'rules', 'unreached') <= (dataCount('Maze Cells') * data('Maze Settings', 'rules', 'maxCost')) || data('Maze Settings', 'rules', 'unreached') > unreachedLimit- Variable
problem- Value
'wrongSettings'
mapCells != dataCount('Maze Cells') || data('Maze Settings', 'rules', 'columns') < 1 || data('Maze Settings', 'rules', 'columns') != floor(data('Maze Settings', 'rules', 'columns')) || data('Maze Settings', 'rules', 'rows') != floor(data('Maze Settings', 'rules', 'rows'))- Variable
problem- Value
'wrongMapSize'
- Value
problem
Its answers are rows of Messages, and Messages gets seven new rows. Six are words for a search that can’t begin or can’t go on: one for each rule, and No route. The seventh, cellSettled, goes between a cell’s name and its distance on the Status line. It starts with a colon and ends with a space after cost.
The card can’t show that space. Type it anyway: without it, the Status line runs the word and the number together.
Paint terrain.: costNo route.Fix columns and rows.Check search settings.Check start and goal.Use costs 0 to maxCost.Unblock S and G.3.8 One Step
Now the pieces come together, and the search wakes.
3.8.1 Step Trial
Step Trial, on Maze Rules, makes one Step each time stepRequested arrives. What a Step does depends on where the trial is, and Step Trial keeps that in its Event’s Modes. It has three: Ready, Searching and Finished. Only one answers at a time. Switch Mode turns on another one and turns the rest off, ready for the next Step. So one press is always exactly one Step.
Ready answers the first Step of a trial: it calls Check Maze Input, and when problem is empty, the search begins. The camp’s distance becomes 0, and Settle Cheapest Cell settles it, the only cell reached so far. If the camp is also the tower, the search is over at once, and the trial is Finished. Otherwise the camp makes its offers, and Step Trial switches to Searching. When a rule is broken instead, the Status line shows that rule’s words, nothing is settled, and the trial is Finished.
Searching answers every Step after that. It settles the cheapest frontier cell, and that cell makes its offers. When the cell it settles is the tower, though, the search is over: the tower’s distance is final, and that’s the cost of the cheapest route. When there’s no cell left to settle before the tower, nothing more can be reached, and the Status line says No route. Either way, the trial is Finished.
Finished has no Actions. A Step there does nothing, until Reset or a painted cell starts a new trial.
Step Trial has a second Event, for trialCleared. That message comes from Clear Trial, the next piece. When it arrives, Reset Modes puts On Step Requested back to Ready, its Starting Mode.
Build it in this order. Make Step Trial, and give it the card’s two Shared Variables, Numbers that stay Constant. It hands them to Check Maze Input as @self.maxCostLimit and @self.unreachedLimit. Add its Event, a Custom Event, stepRequested. Nothing sends that yet, so make it with Add Custom Event…, as you made paintRequested.
Its one Mode is named Step Trial. Rename it Ready, and add Searching, then Finished, with New Mode…. If they don’t stand in the card’s order, Move Left and Move Right put them there. Ready should be the Starting Mode. Then add the trialCleared Event, with Add Custom Event… again, since nothing sends it yet either. Only now add the Actions. Switch Mode and Reset Modes pick the Event and the Mode from lists, and the lists need them first. Modes on the Making page shows each move.
A few spots need care. Ready’s step 10 sends searchChanged from the end of step 2’s True line, after the If inside it. So right-click step 2’s If, and choose Add inside Then. Searching’s step 10 is different. It’s on the Mode’s own line, after its If, so right-click the Searching block and choose Add unattached Action here. Either way, Connect to sequence joins it at the end of its line.
And three Elses here hold two Actions each. Add Else, on the If’s right-click menu, makes the Else. Then right-click the Else and choose Add inside Else for each of its two Actions, and join each with Connect to sequence.
Ready’s step 2 asks whether inputCheck is empty. Its right side is "", two double quote marks with nothing between them: no problem at all.
On the card, the first Event’s heading and its When bar come three times, one above each Mode. It’s still one Event, with three Modes standing in a row to its right.
Makes one Step of the trial each time stepRequested arrives (the Step button or the Step Command). What a Step does depends on the trial's phase, the Mode of stepRequested: Ready begins the search and settles the Camp, Searching settles the next cheapest cell, and Finished does nothing. Before the first settle, Ready checks the map and Maze Settings (Check Maze Input); maxCostLimit and unreachedLimit are the largest maxCost and unreached that check allows. A cleared trial (trialCleared, from Clear Trial) starts again from Ready.
Any Object- Action Name
inputCheck- maxCostLimit
@self.maxCostLimit- unreachedLimit
@self.unreachedLimit
inputCheck.value == ""- Table
"Maze Cells"- Row
dataRow('Maze Cells', data('Maze Settings', 'rules', 'startCell'))- Column
distance- Value
0
- Action Name
firstSettle
firstSettle.value == data('Maze Settings', 'rules', 'goalCell')- Event
On Step Requested- Mode
Finished
- cell
firstSettle.value
- Event
On Step Requested- Mode
Searching
- Custom Event
searchChanged
- Variable
$status- Value
data('Messages', inputCheck.value, 'words')
- Event
On Step Requested- Mode
Finished
- Action Name
settle
settle.value >= 0settle.value == data('Maze Settings', 'rules', 'goalCell')- Event
On Step Requested- Mode
Finished
- cell
settle.value
- Variable
$status- Value
data('Messages', 'noRoute', 'words')
- Event
On Step Requested- Mode
Finished
- Custom Event
searchChanged
- Event
On Step Requested
The card for Maze Rules adds Step Trial. Yours lands at the bottom of the list. As in Chapter 2, that’s fine: no two of them wait for the same Event.
3.8.2 Clear Trial
Every trial needs a clean start, and Clear Trial gives it one. It wipes the search’s records from every row of Maze Cells, puts the sidebar back to its first words, and hides every ring. Watch its last step. It sends trialCleared to Maze Rules, and Step Trial puts its Event back to Ready. The next Step begins a new search.
Why doesn’t Clear Trial switch the Mode itself? It can’t. Only the Logic whose Event it is can change that Event’s Modes, and Clear Trial is a Function, with no Event at all. So it sends word, and Step Trial does the rest.
It never touches cost. A Reset keeps your terrain.
This is what the 0s in Maze Cells were waiting for. Clear Trial runs as the game starts. Every row is written fresh before the search reads it.
Its one Parameter, rules, is the Maze Rules it tells, and no other kind of Object will do. It’s an Object Parameter, so open its Settings, choose Nominal, and pick Maze Rules. In Trigger Custom Event on Object, the Applies To list then offers rules · Maze Rules.
Puts the trial back to Ready, keeping the terrain: every cell of Maze Cells gets distance unreached (Maze Settings), no parent (-1) and settled 0, Visited goes back to 0, no cell is current (currentCell -1), Status asks the learner to paint terrain (the Messages ready words), and searchChanged clears every Search Outline. Last, trialCleared tells Step Trial on rules (Maze Rules) that the trial was cleared, so the next Step starts from Ready.
dataCount('Maze Cells')times- Table
"Maze Cells"- Row
dataRow('Maze Cells', local.index)- Column
"distance"- Value
data('Maze Settings', 'rules', 'unreached')
- Table
"Maze Cells"- Row
dataRow('Maze Cells', local.index)- Column
"parent"- Value
-1
- Table
"Maze Cells"- Row
dataRow('Maze Cells', local.index)- Column
"settled"- Value
0
- Variable
$visited- Value
0
- Variable
$currentCell- Value
-1
- Variable
$status- Value
data('Messages', 'ready', 'words')
- Custom Event
searchChanged
- Applies To
rules- Custom Event
trialCleared
3.8.3 Reset Trial
In Chapter 1, Reset Trial set the Status line and nothing more. Its name promised more, though. From Chapter 3, a Reset would put the search back where it started, and this would be the piece that does it.
Now four things call for a clean start, and each Event calls Clear Trial. The Scene starts. The Reset Command comes, when R is pressed. The Reset button sends resetRequested when it’s clicked. Or terrainChanged comes after a painted cell, because a search of the old map wouldn’t be true of the new one.
Painting a cell with the cost it already has sends nothing. The search goes on. Any other cost starts the trial over, back at Ready.
Its old step goes. Clear Trial sets the Status line now, along with everything else. Right-click that block and choose Delete. Each call hands Clear Trial self as rules: the Maze Rules that Reset Trial is on. Clear Trial takes nothing else. So Reset Trial must promise to be on a Maze Rules. Open its Logic Component card, and set Attach to Maze Rules, as its card shows. Then each call’s rules box reads self · Maze Rules. There’s nothing to change.
The Add Event window lists terrainChanged already, but not resetRequested, since nothing sends it yet. Add Custom Event… makes that one.
Puts the trial in its Ready state, keeping the terrain, with the Function Clear Trial: when the Scene starts, when the learner presses Reset (the Reset Command, R in the Input Manager) or the Reset button (resetRequested), and whenever a cell's terrain changes (terrainChanged), so a search never mixes two maps.
Maze RulesAny Object- Variable
$status- Value
data('Messages', 'ready', 'words')
- rules
self
- rules
self
- rules
self
- rules
self
3.8.4 Show Settled Cell
Remember cellSettled, which Settle Cheapest Cell has been sending with no one listening? This is who it was for.
Show Settled Cell, on Status, hears it each time a cell is settled. It writes the line in three moves: the row’s name for $currentCell, then the cellSettled words, then the cell’s distance. So Cell 12, then the colon and cost, then 3. The second and third moves use the Operator +=, which adds to the end of the words.
Why not let Settle Cheapest Cell write the line itself? It could. But then the search would carry the player’s words as well as the search. Kept apart, Settle Cheapest Cell does Dijkstra’s algorithm and nothing else, and the Status line tells you what happened.
The Status line while the search settles cells: each time Settle Cheapest Cell settles a cell (cellSettled), Status names the cell by its Maze Cells row and gives its distance, as in "Cell 52: cost 8".
Any Object- Variable
$status- Value
dataRow('Maze Cells', $currentCell)
- Variable
$status- Operator
+=- Value
data('Messages', 'cellSettled', 'words')
- Variable
$status- Operator
+=- Value
data('Maze Cells', $currentCell, 'distance')
Window / UIUI{$status}16Semibold#203F43CenterVector3.8.5 Request Step
The Step Button has kept its UI Interaction since Chapter 1, waiting for this. Request Step makes a click send stepRequested, and the Step Command does the same for Space. The button and the key only ask. Maze Rules decides what a Step is.
Lets the learner ask for one Step with a click or a touch on the Step button, or with the Step Command (Space in the Input Manager): each sends stepRequested, which Step Trial on Maze Rules answers.
Any Object- Custom Event
stepRequested
- Custom Event
stepRequested
Window / UIUIX 108, Y 48Step18Bold#203F43CenterVector-1PanelX 108, Y 48#EEE3CC3.8.6 Request Reset
Request Reset is Request Step again, for the other button, with one Event: a click sends resetRequested.
Lets the learner ask for a Reset with a click or a touch: activating the Reset button sends resetRequested, which Reset Trial on Maze Rules answers.
Any Object- Custom Event
resetRequested
Window / UIUIX 254, Y 48Reset18Bold#203F43CenterVector-1PanelX 254, Y 48#EEE3CCRun the game, and press Step. The Status line says Cell 00: cost 0, Visited says 1, and the search has woken at the camp.
Press Step again: Cell 01: cost 1. Cell 02: cost 2 comes next, then Cell 03: cost 3, and the fifth Step says Cell 12: cost 3. Cells 3 and 12 both had distance 3, and the lower number went first, the price list and the finger.
Press R, and it all goes back to Paint terrain. The map hasn’t shown you any of it yet. That’s the last part’s job.
3.9 Rings Over the Map
Last, the search becomes something you can watch.
Each cell gets a ring of its own, a Search Outline, made by Lay Out Map along with the cell. A ring hides until the search reaches its cell. Reached, it’s a thin cyan ring, on the frontier, and settled, a thick blue one. The cell the last Step settled has a thick white ring, the newest certainty.
Thin means not final yet, and thick means final. So the search reads the same even if cyan and blue look alike to you, and the Status line says it in words as well.
3.9.1 Color Search Outline
Color Search Outline decides one ring’s look. It asks from the weakest look to the strongest, so the last question that’s true wins. First it hides the ring. If the cell is reached, its distance below unreached, it shows the thin ring in frontierTint. If the cell is settled, it shows the thick ring in settledTint. If the cell is $currentCell, the ring takes currentTint, white, on the thick ring it already has.
Its outline is made the way you made Highlight Terrain Choice’s button in Chapter 2: an Object Parameter that stays Structural, with the Sprite as a Required Component. Pick it in each Applies To list. Set Visible is new. In a Function its Visible box is typed, so type true or false, as the card has it. Set Frame picks one of the Cell Outline’s two frames. Frame 0 is the thin ring, and frame 1 the thick one.
Shows one cell's place in the search on its Search Outline: hidden while the search has not reached the cell, a thin ring in frontierTint once it is reached, a thick ring in settledTint once it is settled, and currentTint while it is the current cell (the one the last Step settled). A later rule wins: current over settled over frontier. The thin and the thick ring are frames 0 and 1 of the Cell Outline picture, so a settled cell shows by its shape as well as by its color.
spriteSprite- Applies To
outline- Visible
false
data('Maze Cells', cell, 'distance') < data('Maze Settings', 'rules', 'unreached')- Applies To
outline- Visible
true
- Applies To
outline- Frame
0
- Applies To
outline- Value
frontierTint
data('Maze Cells', cell, 'settled') == 1- Applies To
outline- Visible
true
- Applies To
outline- Frame
1
- Applies To
outline- Value
settledTint
cell == $currentCell- Applies To
outline- Visible
true
- Applies To
outline- Value
currentTint
3.9.2 Show Search Outline
Show Search Outline is the ring’s own Logic, and it works like Paint Map Cell, which began in Chapter 1 as Show Map Cell. When placedOnMap arrives, it asks Cell Screen Position where its cell stands. It goes there, Screen and all, and colors itself. When searchChanged arrives, it colors itself again. Step Trial and Clear Trial already send searchChanged, so it’s waiting in the Add Event window.
Its Data Structures card takes Map Place, under Existing Data Structures, as Paint Map Cell’s does. Its Components card needs the Sprite. The three colors are Shared Variables, Colors that stay Constant, with the card’s codes as their Starting Values. Each call’s outline box starts at self, the ring itself, so leave it there.
One cell's ring that shows where the search is: whenever the search changes, it is hidden, a thin cyan ring (frontier), a thick blue ring (settled) or a thick white ring (the current cell), with Color Search Outline. Its cell is its Map Place cell, which Lay Out Map gives it. frontierTint, settledTint and currentTint are the three colors.
Any Objectself.mapPlaceSprite- Action Name
place- cell
self.mapPlace.cell
- Position Relative To
Screen- X
place.x- Y
place.y
- outline
self- cell
self.mapPlace.cell- frontierTint
@self.frontierTint- settledTint
@self.settledTint- currentTint
@self.currentTint
- outline
self- cell
self.mapPlace.cell- frontierTint
@self.frontierTint- settledTint
@self.settledTint- currentTint
@self.currentTint
The Search Outline is a Screen UI Object showing the Cell Outline at 64 by 64. Remove its UI Interaction. A Scene Depth Draw Order of 1 puts it over the cells and under the orange ring, which has 4. Attach Show Search Outline, and its Map Place arrives From Logic.
Window / UIUIX 64, Y 6411Cell OutlineX 64, Y 64Show Search OutlineMap PlaceMap Place’s card changes only its Description, which now names the Search Outlines too. A Changes card never marks its Description, so nothing on this one is green or struck. Type the new one in if you like.
The cell a piece of the map stands on. cell is its number: 0 is the top-left cell, and the numbers grow to the right, then down (its row of Maze Cells). Lay Out Map gives each Map Cell and each Search Outline its cell right after creating it.
3.9.3 Lay Out Map
Lay Out Map makes the rings in the same Repeat that makes the cells. Three new steps follow the old three. They work the same way. Create Instance makes a Search Outline as newOutline, newOutline.cell gets local.index, and placedOnMap goes to newOutline only. Add each with Add inside Repeat, on the Repeat’s right-click menu.
The Object it makes comes from a new Shared Variable, searchOutline, an Object that stays Constant and starts at None, like mapCell.
Lays out the map when the Scene starts: for each row of Maze Cells it creates a Map Cell and a Search Outline, gives each the cell number (its Map Place cell) and tells it, with placedOnMap, that it is placed; the piece then stands on its cell and shows itself. mapCell and searchOutline are the Objects it makes.
Any ObjectdataCount('Maze Cells')times- Object to Create
@self.mapCell- X
0- Y
0- Created As
newCell
- Variable
newCell.cell- Value
local.index
- Applies To
newCell- Custom Event
placedOnMap
- Object to Create
@self.searchOutline- X
0- Y
0- Created As
newOutline
- Variable
newOutline.cell- Value
local.index
- Applies To
newOutline- Custom Event
placedOnMap
On the Map, set the new searchOutline the way you set mapCell: under Variables, pick Search Outline as its Value. The Map’s card comes whole this time, with no marks. Its new line is the last one.
Map CellSearch OutlineRun the game, and press Step. Inside the orange ring at the camp, a white one appears, and thin cyan rings close around the road to its right and the forest below. Step again. The white ring moves onto the road, and the camp’s turns blue.
Keep going. The thick blue spreads out from the camp like a ripple, quick along the road and slow into the forest. The thin cyan edge stays a cell ahead of it. Each white ring is the newest certainty, and none is ever taken back.
Watch for each of these.
- Before the first Step, no ring shows. Visited says 0, and the Status line says Paint terrain.
- Press Step. Visited says 1, and the Status line says Cell 00: cost 0. Inside the orange ring at the camp is a thick white ring. Thin cyan rings stand on the road to its right and the forest below it.
- Press Step again: Cell 01: cost 1, and Visited 2. The road beside the camp has the thick white ring now, and the camp’s is thick and blue.
- The third Step settles Cell 02 at cost 2, and the fourth Cell 03 at cost 3. The fifth says Cell 12: cost 3. Cells 3 and 12 tied at 3, and the lower number went first.
- Press R, or click Reset. Every ring hides, Visited goes back to 0, and the Status line says Paint terrain.
- Step a few times, then paint a cell with a new terrain. The search clears, as if you had pressed Reset. Paint a cell with the terrain it already has, and the search goes on.
- Wall the camp in: paint walls on the road to its right and the forest below it. The first Step settles the camp alone. The second says “No route.” Visited stays at 1, and Steps after that change nothing.
- Press D to bring the map back. If you have the patience, keep pressing Step: after 78 Steps the tower settles, Cell 119: cost 24, and Step does nothing after that.
- Cost still shows two dashes. It learns the route’s cost in Chapter 4.
Each Step settles the cheapest frontier cell, and its distance is final. The cell offers its neighbors a route, and a neighbor takes it only when it’s cheaper. The rings show it all: thin cyan for the frontier, thick blue for settled cells, thick white for the newest. Reset, or a painted cell, clears the search. The next Step begins again at the camp.
Underneath all of it is one plain fact about the map you painted: no cost on it is below 0. A route never gets cheaper as it goes, so the cheapest cell on the frontier can’t be beaten by any way round. That’s why the search never goes back. It settles cells in order of their cost from the camp, each one once, and each one for good.
Edsger Dijkstra described this search in 1959, in a paper called “A note on two problems in connexion with graphs.” The game’s title, Weighted maze (Dijkstra), names him for it.
3.10 If It Didn’t Work
Something may be off the first time, and that’s all right. This chapter has more moving parts than the last two, so there’s more to check. Run the game, watch the Status line, and follow the chain one piece at a time.
Step does nothing at all? Follow the message. Request Step, on the Step Button, sends stepRequested. Step Trial’s Event must name it the same way, capital R and all. Is Step Trial on Maze Rules? Then open it, and look along Ready’s line for a block standing apart, with no arrow into it. Join it with Connect to sequence.
Every cell says cost 0, or every cell has a thin cyan ring before the first Step? The distances are still the 0s from Add Field. Clear Trial never ran. Look at Reset Trial’s When the Scene Starts: it should call Clear Trial, with self as its rules.
Does the first Step say “Check search settings.”? The rules row of Maze Settings still holds 0 under maxCost and unreached. Type 99 and 1000000, and step again. If it says “Use costs 0 to maxCost.” instead, it’s the same row: maxCost is still 0.
Does the second Step already say “No route.”? The camp’s offers never landed, then, and perhaps Relax Neighbors never runs at all. Look at Ready’s step 8, under the Else of step 5’s If. Or look in Relax Neighbor for a block standing apart, since both Set Data Cells sit inside its second If.
The Status line runs the word into the number, as in cost3? The cellSettled words need a space after cost. Double-click that cell in Messages, and type it.
After R, does the next Step say “No route.” at once, or do nothing at all? Then Step Trial never went back to Ready. Clear Trial’s last step should send trialCleared to rules. And Step Trial’s On Trial Cleared should Reset Modes on On Step Requested.
Cell 12 comes before Cell 03? Look at the third test in Choose Cheapest Cell’s If. It should say <. With <=, a tie moves your finger, and the higher number wins.
Status names the cells, but no ring shows? Perhaps the rings were never made. Look at Lay Out Map’s three new steps, inside the Repeat. Then open the Map. Under Variables, searchOutline should say Search Outline. Or perhaps they never hear searchChanged: look at Show Search Outline’s second Event. Or perhaps they stand off the screen: in its first Event, Set Position should say Screen.
The rings show, but never turn thick? Look at Color Search Outline’s step 8, whose Frame should be 1.
R does nothing? In the Input Manager, the Reset Command needs its key. And Reset Trial needs its Command Pressed Event, set to Reset.
Each of these is one small fix. Make it, run the game again, and you’re back with the chapter. The catch-up download in the Goal is this chapter’s game, finished, to compare with yours.
The search is yours to test now. Play a game against it. Before each Step, put your finger on the screen, on the cyan cell you think it settles next. Then press Step and see. The rule is the one Choose Cheapest Cell follows: the smallest distance, and the lower number on a tie. Paint a few cells of your own first, maybe a road through the forest below the camp, and see whether your finger keeps up.
The search is awake, and it stops when the tower settles. The compass still waits at the camp. In Chapter 4, a yellow line runs home from the tower, and the compass walks it.