Dijkstra's algorithm in ActionScript

Dijkstra's algorithm is a useful algorithm for roguelike developers to know. It basically calculates the distance from a starting point to all other points. Once you know the distances, you can walk backwards from any point to the start. It's great for worldgen, floodfilling, ai, and pathfinding to the nearest something. Dijkstra's algorithm is also the basis for autoexplore in brogue. If you want to know "where's the nearest" of something, use Dijkstra's algorithm.

Here's an ActionScript implementation.

Note that it uses a grid to track parent nodes as well as if a cell has been visited or not. It does this for performance reasons but it's possible to keep a list or dictionary of visited nodes instead.

This implementation takes the start position, a function that verifies a cell can be entered, and a function that determines if a cell is what you're looking for. It returns an array of points from the start position to the end position or an empty array if no path was found. Using canEnter and check functions means that there's no dependancies on details of your game code - which is a very good thing. Passing in your game details means that if you want this to work with land creatures, water creatures, and amphibians, just pass different versions of canEnter depending on who's searching. And since you pass your own check function, you can search for whatever you want. Injured creatures could search for the nearest healing potion. Fleeing creatures could look for the closest tile that isn't visible from the player. Exploring creatures could look for the nearest tile that they haven't seen before. There's a lot of potential uses for this algorithm.