Myth Engine: Weighted Maze
Learn Dijkstra’s Algorithm by Building a Pathfinding Game, Step by Step
Welcome
This is Weighted Maze. Play it first. Every piece of it, you’ll make yourself.
Click the game, then press Find route.
The camp is in the top-left corner and the tower in the bottom-right, and everything between them is yours to paint. These are your keys:
- Choose Road, Forest, Mud or Wall in the sidebar, or press 1, 2, 3 or 4, and click a cell to paint it.
- The arrow keys walk the orange ring from cell to cell. Enter paints the cell inside it.
- Step, or Space, takes one step of the search.
- Find route, or F, takes the steps by itself, and pauses when you press it again or press Escape.
- Reset, or R, clears the search but keeps your terrain.
- D brings back the map you started with.
Try it once as it is. Then paint a wall across the road and press Find route again.
The Story
A map lies on a table, twelve cells across and ten down. Pale stone road. Pines along a dirt track, brown mud with puddles in it, gray rubble walls. A canvas tent with a lantern stands in the top-left corner. That’s the camp. A stone tower flies an orange flag in the bottom-right. A teal compass waits at the camp.
Every cell has a price for stepping onto it: road costs 1, forest 3 and mud 6, and nothing enters a wall. The game asks for the cheapest route.
Press Step and the search wakes at the camp, and rings spread out from it, one cell at a time, cheapest first. A thin cyan ring marks a cell the search has reached. A thick blue one marks a cell whose cost is final. When the tower’s cost is final, a yellow line runs back from the tower to the camp, and the compass walks it.
On the map you start with, that route costs 24, in 24 moves. Straight across the top and down the right side is only 20 moves, but it costs 53. On this map, the cheapest route isn’t the one with the fewest moves.
That search has a name. It’s Dijkstra’s algorithm. By Chapter 4, you’ll have built it yourself.
What You’ll Build
All of it. Here it is, in the order the chapters build it.
- The map on the table. Its 120 cells are laid out by the game itself when it starts, with the camp in one corner and the tower in the other. Beside it stand the sidebar’s four terrains and three buttons, and the compass waits at the camp. Everything is there, and nothing answers yet.
- The land answers your hands. Choose Forest and click the road beside the camp, and pines grow there. The arrow keys walk the orange ring, Enter paints, and D puts the first map back.
- The search. Step settles the camp at cost 0, and each Step after it settles one more cell: the cheapest one the search has reached. The thin cyan edge creeps outward, and the Status line names each cell as it settles.
- The route. When the tower settles, the Cost reads 24. Each Step then marks one more cell of the route, from the tower back to the camp, and a yellow line joins them. After that, each Step slides the compass one cell along it, until it stands on the tower.
- The search on its own. Find route takes a Step every 0.045 seconds, and the rings spread across the map while you watch. Pause holds it still, and Find route goes on from the same cell.
Five lines, five chapters. Each chapter ends with a game you can play. Its Goal lets you play it right there on the page, so you can 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, and run your game to watch it happen.
Dijkstra’s algorithm comes the same way. Each chapter shows one more part of it on the screen before it names what you’re seeing.
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. Read its first two passages before Chapter 1, and come back whenever a card shows you something you haven’t made yet.
Every chapter also has a catch-up download in its Goal. 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
Every picture the game uses comes in one Myth Pack. It holds the terrain tiles with the camp and the tower, the ring that marks a cell, and the compass. It also holds the plain panel that the sidebar and the route line are made from. That’s the Starter Kit. The game has no sounds, so there are none to install.
You’ll build it all in Myth Engine. If it isn’t on your computer yet, Get Myth Engine is where to find it.
Then make a new Blank 2D project, and install the Starter Kit into it: choose File > Install Myth Pack… and pick the file. 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. It’s the same file as Chapter 5’s catch-up download. Open it whenever you want to see how a finished piece was put together.
To open it, start Myth Engine, choose File › Open Project... and pick the downloaded file.
If your own project has changes you haven’t saved, Myth Engine asks first, and offers to save it before it opens this one.
In Chapter 1, the compass waits at the camp, and nothing answers it yet. Five chapters from now, it’s the game you played above.