A Dijkstra map is a pathfinding tool that, in its most basic sense, marks a 2D grid of cells with distance values according to the number of cells a particular cell is away from a target cell, navigating around wall cells. When used properly, however, it is a powerful data structure that, when combined with other Dijkstra maps, allows multiple A.I. agents to intelligently navigate towards targets, biasing one set of targets over another based on specified weights.
Dijkstra maps operate on very basic principles. The implementation I chose (and the one described by Brian Walker) is relatively naive but simple to implement and does the job well enough.
Start with a grid of floating point values. These floats represent your map. Target cells are marked with a low number, usually 0. Wall cells are marked with a very high number (I've indicated walls with an X instead for readability). All other cells are marked with some arbitrary high number in between. You choose this number based on the maximum distance you can expect from a cell to a target. When working with very small maps, 99 works well. For other maps, 999 will work well.
In order to mark each tile with its distance from a target, we could employ a system of queues and nodes, starting from target cells and expanding outwards. For this naive implementation, however, we'll just loop through each cell. In each cell, provided it is not a wall cell, we apply a simple rule: a cell's value cannot be more than one greater than the lowest value in adjacent cells. Thus, we check all adjacent cells for the lowest possible value (whether we check walls or not is irrelevant - wall cells have an absurdly high value and thus are very unlikely to be the lowest possible value). We then set the current cell's value to the minimum of its value and the lowest adjacent value plus one. If the value has changed, then we should flag it as such.
We can repeat this for every cell in the grid. We end up with something much closer to our target. This algorithm is biased, however, towards values nearer where we start our search through the map.
This process should be repeated until no more changes are made.
As we can see, the map in the lower right-hand corner of my fancy illustration is complete. Each cell contains the number of steps it needs to take in order to reach the nearest target. At this point, it would be very simple to find a path from an arbitrary non-wall cell on the map to the nearest target by rolling downhill. From the given cell, one merely has to find the adjacent cell with the lowest value (if several share the lowest value, pick one at random) and move towards it. If the cell has the lowest value of all adjacent values, then the path should stay put. This prevents a path from rapidly fluctuating between two neighboring cells if one is a target cell.
Pathfinding away from target nodes is slightly more complicated. Slightly. Rolling uphill on the map (or multiplying every non-wall cell's value by negative one and rolling downhill) will result in slightly weird behavior. Walker suggests multiplying by a negative value slightly greater than one (say, 1.2). Run through the scanning process again, this time using the negated values.
From a set of target nodes, empty nodes, and walls, we have now generated two maps. One, when followed, traces a path from any arbitrary cell towards a target cell (the Approach map). The other traces a path from an arbitrary cell away from any goal (the Flee map). What's great about these maps is that they are entirely dependent on the location of walls and targets. They only need to be updated when either of these parameters change (updating involves resetting all non-target, non-wall cells to the start value and running through the calculations described above). This means they can be reused for many entities. Not every enemy has to own a copy of pathfinding data - it can simply pull from a collective map.
By themselves, Dijkstra maps are great pathfinding tools, but combined, they can emulate more complicated A.I. concepts. Goal-based A.I. is focused on picking actions that satisfy goals without relying on state machines. A good goal-based A.I. relies on a set of goals, actions, and knowledge about the current world state to make its decisions. Dijkstra maps can, in combination, be used to simulate this decision-making process. Actions are replaced with movement in a certain direction, knowledge of the world state is replaced with a collection of maps, and goals are replaced with weights and targets for these maps. A positive weight indicates a desire to move towards a target, while a negative one indicates a desire to move away from targets.
Combining Dijkstra maps together is fairly simple. Start with a Dijkstra map with all its cells set to a value of zero. For each cell in each map to combine together, multiply the map's weight by the cell's value and add it to the combined map. If the weight is negative, multiply the absolute value of the weight by the cell's Flee map value and add that value to the combined map instead. We can then use this map to navigate around a map according to the desires of an A.I. agent. We could also apply this combination to only a small portion of the map to avoid calculations on other areas. If an A.I. agent wants to move on the map, it may only be concerned with its next target cell rather than the contents of the entire map. By applying this weighted sum and using it to guide an agent around the map, said agent will appear to intelligently make decisions. Walker offers an excellent description of what this looks like: "can't stay near the queen because the player is too powerful for that to be a useful fight, and while east is a slightly more efficient escape route, west will take me past water (I am very thirsty) and also toward another of my compatriots -- so I'll go west". By changing these weights - for example, increasing the weight of a food map as a character grows hungrier - the directions of movement will vary and appear to be intelligent.
There are some drawbacks to using this technique as a shortcut to goal-based A.I. Weights can occasionally balance one another out, leaving minimum values that are nowhere near a goal yet represent areas into which AI agents may roll downhill. These situations require a lot of tuning of weight values to ensure such situations are rare. It is also limited in the range of actions it can represent. A Dijkstra map query will only output the desired direction of movement. This works if all actions are based on movement, but more abstract or localized actions will not be easily simulated with this technique.
As I mentioned, my implementation of Dijkstra maps is not ideal. Sidney Durant's article on vector field pathfinding reveals several optimizations and enhancements to the Dijkstra map technique. Instead of finding the least-valued neighbor cell at query time, I could cache this information within the map when it is updated, reducing later performance costs. I would essentially turn the map's distance values (referred to as a heatmap) into a vector field by using neighbor values to calculate the vector's components. I could also make use of a breadth-first search algorithm to generate the distance values instead of a multiple-pass system of comparisons, turning this part into a modified Dijkstra's algorithm and thus allowing for non-grid graphs of nodes and connections instead of just 2D grids of cells.
I put together a short demonstration of this technique in action. I have two separate A.I. characters maneuvering around a randomly-generated continuous region. Each desires to move towards unexplored open tiles with a constant weight. Their desire to seek out money increases as they collect money. Their desire to seek out food items increases with time, as does their desire for water.
Dijkstra maps, in isolation, have great potential for pathfinding both towards some set of targets and away from said targets. They might be suitable for strategy games, herding games, and games featuring large collections of A.I. agents navigating in a shared environment. They are reusable for multiple entities, as they depend on the location of the target, not on the starting location. One could easily make a Dijkstra map for some set of desirable locations and have 100 entities pathing from random cells to target cells without duplicating the map or recalculating it. As Tyler Glaiel pointed out in his blog post on pathfinding, while the setup may be a bit longer due to caching the entire map rather than simply finding a path from one point to another, it allows a great amount of entities to utilize it for pathfinding at the cost of a short lookup on neighboring tiles instead of performing their own pathing algorithms. When combined, Dijkstra maps are able to imbue A.I. characters with simulated desires expressed through movement. Games featuring independent A.I. characters that need to appear intelligent in their motion could benefit from the technique; Brian Walker's rogue-like game Brogue made extensive use of them.
My naive implementation of Dijkstra maps works fine on PC, but on other platforms it may not fare so well. Depending on the size of the map, amount of target nodes, and the location of the target nodes, the algorithm could make hundreds of passes in one update. It is a time-intensive process rather than a memory-intensive one and may not be suitable for platforms with heavy restrictions on CPU time. The technique in general, however, given the proper optimizations, should be suitable for most platforms.
References:
Walker, Brian. The Incredible Power of Dijkstra Maps. RogueBasin. 10 March 2010. Web.
Durant, Sidney. Understanding Goal-Based Vector Field Pathfinding. Tuts+. Envato Pty Ltd, 5 July 2013. Web.
Glaiel, Tyler. Some experiments in pathfinding + AI. Gamasutra. 7 October 2012. Web.
No comments:
Post a Comment