Building a Map

Edsger W. Dijkstra was one of the great minds behind modern computer science. He created many of the algorithms and theories that drive modern software development. One of his creations was a pathfinding algorithm that can reliably find a path between any two points in a graph. This, in turn, spawned many other algorithms. We’ll occasionally use Dijkstra maps, also called flow maps.

Dijkstra maps are incredibly useful. We can use them for everything from AI to making our game automatically play itself. They power a large part of the popular roguelike, Brogue. We’ll start by using them to help the monsters find the player.

A Dijkstra map represents our map as a grid of numbers. We indicate starting points, set to zero. The rest of the map is set to a large number indicating that we can’t go there. Each starting point is scanned, and tiles to which we can travel from that point are given a value of one. On the next iteration, open tiles that we haven’t already visited receive a value of two. This is repeated until every available tile on the map has a value, and that value tells us how far away we are from the starting point: