Tuesday, February 19, 2013

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.

3 comments:

  1. This is incredibly useful for AI and a lot of things. Thank you for the AS3 implementation. Do you have performance tests for this?

    ReplyDelete
    Replies
    1. I don't have any performance tests for this. I used to use an array instead of a grid to track visited cells though. That was much slower because checking to see if a cell had been visited had to traverse the array - an O(n) operation. Checking a 2d array to see if the cell is empty is constant time. I noticed a big improvement when I switched away from the array.

      I'm sure there are other ways to improve performance but this works well enough for me so I haven't looked into it any further.

      Delete
  2. Thanks for the sharing :)

    ReplyDelete