Dijkstra Maps implementation

[hyakugei]

Hey all.

I read about using "Dijkstra Maps" for AI (see below links). I decided to give it a try, and came up with this implementation: https://gist.github.com/hyakugei/ace116bd9ce72f2bf92c

The visualization stuff on the index.html demo page is similar to the images on the "Dijkstra Maps Visualized" page. I tried to follow the same design style as the FOV or Map bits of Rot.js (using callbacks so as to not proscribe the data storage format). I don't know if it fits into Rot.js, or is better left as a gist/project on its own, but i thought i'd ping ya'll and see what you think.

Comments, suggestions etc welcome.

Note - hex map formatting is not currently supported. I'm not sure how easy/hard it would be to do this.

--- Want to back this issue? **[Post a bounty on it!](https://www.bountysource.com/issues/27278655-dijkstra-maps-implementation?utm_campaign=plugin&utm_content=tracker%2F297828&utm_medium=issues&utm_source=github)** We accept bounties via [Bountysource](https://www.bountysource.com/?utm_campaign=plugin&utm_content=tracker%2F297828&utm_medium=issues&utm_source=github).

[ondras]

Hi @hyakugei ,

sorry for the delay. And thanks for your contribution!

I am not yet completely sure whether we shall include this in rot.js itself or not. In the meantime, I have several points to consider:

1. have you seen the ROT.Path.Dijkstra pathfinder? Would it be possible to somehow re-use this code for Dijkstra map impl? As far as I know, ROT.Path.Dijkstra does not (yet) support more than one target point, but perhaps we can improve it...
2. your _topologyOffsets look pretty similar to ROT.DIRS: https://github.com/ondras/rot.js/blob/master/src/rot.js#L18
3. instead of Number.MAX_VALUE, feel free to use 1/0 :smile:
4. calling toString in this._topologyOffsets[this._options['topology'].toString()] is not necessary. This conversion is going to take place implicitly.
5. I am not 100% sure I completely follow your Dijkstra impl at https://gist.github.com/hyakugei/ace116bd9ce72f2bf92c#file-dijkstramaps-js-L128, but it looks hugely ineffective, doing a full width*height scan every time a point with better cost is found? A Dijkstra algo shall only visit every graph node once... perhaps I am missing something here.

[hyakugei]

Hello! Thanks for the feedback!

1. I hadn't looked/known about the ROT.Path stuff before. Looking at the Dijkstra implementation, i can see how i can improve my code, but not sure how/if the existing code could be used to implement the "Dijkstra Maps". The Path code returns an array of locations, but does not compute "costs" (i know, the length is a cost) in the way that the Maps articles describe, for every empty location in the level. Still thinking about it, but at the least will use it to improve my implementation.
2. Yeah, I'll make better use of the DIR structure.
3. Heh.
4. I have been burned by Javascript's conversion/coercion rules before and it has made me overly pedantic. That is because i still do not have the rules fully internalized. If you say that it is ok, I will go with the less verbose version :)
5. Yeah, it is an sub-optimal implementation. I'm still working on improving the code for how this is done (including my understanding of it!), and am experimenting with flood-fills. This should, maybe, reduce the passes through the map to the number of sources you have. WIP.

Thanks again for the feedback, and taking the time to check it out. I'll post when I've got an update to it. I also hope to have some examples showing how you could use it. These would be much more implemenation dependant, so they are in flux, and only in my head! Thinking that I will use the "base" you have in the "addons" directory to build them from. If there is/are any other basic ROT.js "starter" code that i could leverage, would be happy to hear it :)

Peace Jos

[ondras]

I hadn't looked/known about the ROT.Path stuff before. Looking at the Dijkstra implementation, i can see how i can improve my code, but not sure how/if the existing code could be used to implement the "Dijkstra Maps". The Path code returns an array of locations, but does not compute "costs" (i know, the length is a cost) in the way that the Maps articles describe, for every empty location in the level. Still thinking about it, but at the least will use it to improve my implementation.

The Dijkstra algorithm works, by definition, by computing "cost" values for every single possible graph node (cell in our roguelike map lingo). In a pathfinding scenario, you are then interested only in a limited set of nodes with a monotonic cost values -- the (shortest) path. But even in this case, we already have all the cost values for all possible cells (see this._computed object in ROT.Path.Dijkstra), we are just not making them publicly available.

As far as "multiple target cells" goes, this might be even easier. The ROT.Path.Dijkstra constructor accepts only one pair of target coordinates, but we might introduce another public method (addTarget comes to mind) that would add another target cell. Its implementation would be trivial, basically the same as _add: target cells are specific only because they already have a computed cost value (zero).

This being said, I would look for ways to improve the current implementation so it offers the API necessary for Dijkstra maps.

If there is/are any other basic ROT.js "starter" code that i could leverage, would be happy to hear it :)

I am not aware of any. However, if you manage to create a suitable Dijkstra map demo/app, it might make sense to include it in the "addons" directory as well.

[hyakugei]

Ok, I went back and threw out my implementation and tried to use the existing ROT.Path.Dijkstra stuff. I copy/pasted most of the underlying ROT.Path, and the ROT.Path.Dijkstra code as the base. I then changed the API a bit (removing a bunch of to/from vars) and added the 'addTarget()' method. Compute and _compute changed a bit, and i tweaked the obj{} to include a 'cost'(int) and 'target'(bool). Anyway, i was able to use a fair bit of the original functionality of the ROT.Path stuff.

It is also way faster. I don't know what i did wrong in my initial attempt, but this is like an order of magnitude improvement. The "flee" map is still quite a bit slower then the regular one. It has to compute the regular map, then multiply all the costs by -1.2, then re-compute the map. The only way i could get the second computation to work properly was by adding all the locations on the map back into the _todo array. I tried to add only the original target locations, but that didn't work. More experimentation/thought required here. However, even with this less-then-ideal setup, it is faster then the original "regular" map creation speed.

And i improved the debug colour output, a lot.

Please check out the updated code at the original url - https://gist.github.com/hyakugei/ace116bd9ce72f2bf92c

One next step might be to look at how it could be re-integrated into the ROT.Path.* object? Either in its own namespace or replacing the existing ROT.Path.Dijkstra object? Maybe different compute methods - one for simple paths, one for full maps... I don't know.

Another is for me to build some AI demos which use these. That sounds like the most fun option! ;)

Thanks again for your comments! Peace J

[ondras]

Several questions for better code understanding:

1) what is the meaning of the cost value for addTarget?

2) how is the "flee" feature supposed to work, high-level speaking?

Reminder: a regular Dijkstra algorithm will populate every cell with a numerical value -- the (shortest) distance to the (nearest) zero-point. Zero-points are defined using addTarget (so they are, by definition, closest to the nearest zero-point).

[hyakugei]

1) The cost is if you are making a "combined" map with multiple targets, but you want some of the targets to be "more desirable" then others. In this way you can assign different "costs" to those items. Ie. If you have a monster that likes gold more then attacking the player, and you add gold and the player to a map, you can give the player a cost of 0 but gold a cost of -5. This make the Gold "closer", and so, if using the map for decision making, the monster will go for the gold in cases where the player may be closer, thus simulating a higher desire for gold. See the "variable strengths" part of the article for more details.

I should, however, make cost have a default value of 0, so you don't have to provide it in the normal case of adding targets of equal value.

2) The flee behaviour makes an "inverted" map. The targets you add become the points that are the least desirable, and so the map is how one would flee from those targets, toward the most distant points from them (which become the most desirable). The process is to create a normal map, then multiply the costs by a negative value (-1.2 by default), then re-run the re-costing over the map. This gives a map which will not move NPCs (or whoever uses it) into the corners of room, but towards the points that are farthest away from the targets. See the "Fleeing AI" section of this article and/or "Section 1) Safety Maps" of this one for more examples and explanations.

I really had to play around with the flee stuff to see the difference the different multipliers make. I'm still not happy with how the code woks for this use, since i have to add every location back into the _todo list to ensure that each one gets checked and "re-costed". This is the weakest part of the code, since i don't feel confident that this is the only way to ensure that the map gets properly re-costed. However, i have not been able to find another way that does make it work, with less calls/cycles.

Thanks again for the feedback! Jos

[ondras]

1) The cost is if you are making a "combined" map with multiple targets, but you want some of the targets to be "more desirable" then others. In this way you can assign different "costs" to those items. Ie. If you have a monster that likes gold more then attacking the player, and you add gold and the player to a map, you can give the player a cost of 0 but gold a cost of -5. This make the Gold "closer", and so, if using the map for decision making, the monster will go for the gold in cases where the player may be closer, thus simulating a higher desire for gold. See the "variable strengths" part of the article for more details.

I should, however, make cost have a default value of 0, so you don't have to provide it in the normal case of adding targets of equal value.

I see. There is, probably, no need to use negative numbers, right? The most important cell can be 0, other potential targets can be >0...

I looked a bit more into the current ROT.Path.Dijkstra impl and I see now that the code is not really prepared to handle multiple targets, as it stores just the "closest neighbor" / "largest slope" value for every cell instead of a numeric score. This will have to be greatly refactored for Dijkstra maps with multiple targets to work properly.

2) The flee behaviour makes an "inverted" map. The targets you add become the points that are the least desirable, and so the map is how one would flee from those targets, toward the most distant points from them (which become the most desirable). The process is to create a normal map, then multiply the costs by a negative value (-1.2 by default), then re-run the re-costing over the map. This gives a map which will not move NPCs (or whoever uses it) into the corners of room, but towards the points that are farthest away from the targets. See the "Fleeing AI" section of this article and/or "Section 1) Safety Maps" of this one for more examples and explanations.

I am not sure we need completely new values for this behavior. You see, the current numerical values mean "you are X cells away from your closest target". We can maintain this (using the map you already have), but reverse the decision procedure that follows afterwards; instead of "pick the lowest number", the decision procedure can do "pick the largest number" (fleeing in the opposite direction) or something more advanced. Say, "pick the number that is closest to 3", as in "move to a range of 3 from your target" -- suitable for an Archer AI or similar.

[hyakugei]

I'm not sure about limiting the target cost to greater then or equal to 0 because I don't know why you would limit it that like? If it works as is, why limit the designer/programmer?

I agree that the existing API would have to change quite a bit to work with this style of map, and the way I have programmed it. There may be ways to make it "fit" the existing API more easily, by taking a different direction in the implementation.

About the flee map, I don't understand what, or what part, of the code you would change, specifically. You can't do a simple "move to greater values when fleeing" - the map will then push NPCs into corners. By applying the -1.2 value to all costs, and then "re-smoothing" the maps costs, the map's costs move smoothly towards the farthest away points, rather then the corners. You get NPCs moving towards passage ways and doors to get away. I don't see a way to do this without an initial computation of the map's costs, the negative multiplication of all the map's costs, then a "re-smoothing" of those costs. On the article page , there are the 2 example flee maps which show the subtile difference between a simple "negation" of the costs vs. the multiplication version. Also, I'd be wary of losing polymorphism, when thinking about how the AI could work. This would most "break" when wanting to implement AI in the following way, making use of multiple Dijkstra maps. Each would have a different set of Targets. One for $, one for Swords, one for Health Potions, for example. You can then give each map a "desire" value (per NPC), sum each map's cost values (multiplied by their "desire") and then simply find the lowest cost neighbour.

The "find a range" thing works with the maps for sure. Again, this is fine if you are not using the multiple maps style of AI as described above. Otherwise, you'd take all those 3 value locations and create a new map, with each one of the '3s' set as a target. You would then use that new map as your "3 range" map, and if you are an NPC which really likes to use ranged weapons, you'd have a high "desire" value to multiply that maps values, increasing the likelihood of it influencing the final direction that NPC might choose to move.

[ondras]

I'm not sure about limiting the target cost to greater then or equal to 0 because I don't know why you would limit it that like? If it works as is, why limit the designer/programmer?

I do not want to limit the user; I am just trying to simplify the case in order to understand it better. If we decide to have a full impl in rot.js, you will be free to use any values for default costs.

About the flee map, I don't understand what, or what part, of the code you would change, specifically. You can't do a simple "move to greater values when fleeing" - the map will then push NPCs into corners. By applying the -1.2 value to all costs, and then "re-smoothing" the maps costs, the map's costs move smoothly towards the farthest away points, rather then the corners.

You are right, I was mistaken. This part of the Dijkstra map feature is still somewhat puzzling for me; I will have to think about it more (with respect to leveraging an existing ROT.Path.Dijkstra or the new DijkstraMap feature).

Generally speaking, I think that a Dijkstra map feature would be a welcome addition to rot.js. We can start with a well-designed API backed by your current implementation and delegate some parts to ROT.Path.Dijkstra afterwards (refactoring, API-compatible).

[airstruck]

Would it make sense for DijkstraMap to share the same interface as the other path modules (extend Path), and add a few functions to manage goals and access the map?

• In constructor, add a single goal, don't build map yet, set dirty flag
• Add a method create(callback), just like Map has.
• In compute, if dirty, rebuild map with create.
• Add two methods to add/remove goals.

Pseudocode:

DijkstraMap (goalX, goalY, passableCallback, options)
    addGoal(goalX, goalY)

DijkstraMap:compute (fromX, fromY, callback)
    create()
    roll downhill, invoking callback

DijkstraMap:create (callback?)
    if dirty, rebuild the map and unset dirty
    if callback, invoke it on all visited cells

DijkstraMap:addGoal (goalX, goalY)
    push { goalX, goalY } onto goals
    set dirty

DijkstraMap:removeGoal (goalX, goalY)
    remove { goalX, goalY } from goals
    set dirty

I'm trying this in a Lua port of rot.js and it seems to work pretty nicely. Passes tests for A* and Dijkstra with a similar implementation to the one posted here.

[ondras]

Would it make sense for DijkstraMap to share the same interface as the other path modules (extend Path), and add a few functions to manage goals and access the map?

Yes, I think that would make sense. I have never actually used Dijkstra Maps before, but I assume people would want to have them at the very same place they have a regular pathfinder now?

[airstruck]

It definitely fits the same use cases as existing path finders. Create an object with a goal, then use it to compute paths from other points to the goal.

It also fits other use cases that might make the Path interface a little awkward. It can have multiple goals, so you might not want to pass the initial goal to the constructor if you want to add a bunch of goals later in a loop. So you might end up instantiating it with DijkstraMap(null, null, cb) in some cases.

Topology is a little tricky also. You can generate the map with either 4- or 8-topology, and you can traverse either one with either 4- or 8-topology paths. So if you have a game that's mostly all 4-topology, but one mob can move diagonally, you should be able to let it pathfind using the 4-topology map you already generated. This means compute should probably take an optional argument to override the topology the map was generated with, or it should have special methods for that like compute4 and compute8, or something.

For the sake of organization, uniformity, and easy testing, it still seems worth putting with the other pathfinders.

[Gerhard-Wonner]

Are there any news on this issue? Being able to compute Dijkstra Maps would be very beneficial for my game which is a racing game where the position of the goal never changes. The AI-runners sometimes need to recalculate their paths if opponents are blocking their way. Thus I will still have to calculate paths by the A method every now and than. So you might ask what the benefit of a precalculated Dijkstra Map would be in this case. The reason is that in my racing game it is necessary to calculate and display the ranking of all runners in every turn. In the moment I do this by sorting all runners according to the length of their paths to the goal. This works but it has a strange effect if one runner has to recalculate its path in order to avoid an obstacle blocking its way. In this case it is possible that the new path is significantly longer than before. If this happens that runner might lose 3 positions in the rankings during a single turn. This looks silly and is very difficult to communicate to the player. In the moment I communicate it by a message like "Runner A is confused and lost 3 positions." but this sounds quite awkward. If I had a precalculated Dijkstra Map I would sort the rankings according to the distances the runners have on this map. A runner following a disadvantageous path would then gradually lose positions when following that path. This behavior would be much more understandable for the player compared to the behavior described above. Thus all I need is a method to precalculate a Dijkstra Map where I can look up the distance to a single goal that never changes its position. Is this already possible in rot.js? A second question: In which cases would I prefer the Dijkstra's algorithm over the A algorithm and vice versa?

[ondras]

Thus all I need is a method to precalculate a Dijkstra Map where I can look up the distance to a single goal that never changes its position. Is this already possible in rot.js?

So, for every map cell in your game, you want to pre-compute and store the distance from this cell to a common goal cell? Sounds like a textbook case for the Dijkstra algorithm. I suggest doing this yourself, because it is almost trivial to implement. Re-using the rot.js implementation would be awkward and somewhat sub-optimal here, because the rot.js pathfinder would give you redundant information that is costly to compute and useless for your case.

Give your goal cell the distance of 0. While there are unranked cells:

1. pick cells with the highest ranked value (only the goal cell in the first iteration)
2. take their unranked neighbors
3. rank their neighbors by adding 1 to the cell value (these will now form the set for step 1)

[Gerhard-Wonner]

Hello @ondras, thank you for the quick response! So I will implement it myself according to your proposal. I would be pleased if you could also answer my other question. Since there are two pathfinding algorithms implemented in rot.js (A* and Dijkstra) I wonder which one is better? Or does it depend on certain cases? How can I decide which one to use? Kind regards Gerhard

[ondras]

Hi @Gerhard-Wonner,

it depends on use cases. The A is generally faster when trying to find one solution, but the Dijkstra implementation is caching all discovered values, so repeated Dijkstra calls with a common target cells are often more faster than multiple individual A calls.

I am actually not sure why is the caching implemented only in ROT.Path.Dijkstra; perhaps it could be added to the A* implementation as well.

For your use case (compute distance for every cell, but only once), there is no difference between these two, because you want to scan all cells. The main difference (performance-wise) between A* and Dijkstra is how many cells need to be visited until a solution (shortest path) is found.

[airstruck]

Interesting conversation here!

I think you could actually piggyback most of Dijkstra on A* by switching out the heuristic function. There's some discussion of that here -- https://stackoverflow.com/questions/13031462/difference-and-advantages-between-dijkstra-a-star

But, yeah, DijkstraMap is a bit different, because it caches everything on the map with respect to some goal points. It's like Dijkstra, but you start at the goal(s), flood-fill outward, and you don't stop when you find a path to anywhere, you just keep going until you've filled the whole map.

Did I say I was going to port some Lua code back to JS? I guess I never found time for it, but I do have DijkstraMap in Lua here if you want to port it @Gerhard-Wonner.

[Gerhard-Wonner]

@ondras and @airstruck Thank you for your informative responses! I did the implementation today and I am quite happy with the result: Of course it is not as general as your solution @airstruck but it meets my needs quite well. I agree, it would be better to port your general solution. Unfortunately I will also not have the time to do it since I am a full time worker and father of 3 kids. In addition, I am still quite new to JS and not confident to meet the quality of rot.js. But this might be an interesting project once I have a little more practice.

[TimAstier]

Joining up the conversation here. Has anyone come up with a performant way to generate dijkstra maps in JS? Or is there a way to use Rot.js to generate full maps (not only the result path)?

Like @hyakugei I'm also trying to generate dijkstra maps on every round, to try and do applications as explained in these articles. If I understand well, generating the map only once would allow things to scale easily, with many creatures on the map for example.

EDIT: Something with my function must be very wrong as frontier.lenght on distance 31 logs 102949 😅.

I made a first attempt at writing my own implementation that passed this test:

it('works on basic map', () => {
    const map: TileType[][] = [
      ['#', '#', '#', '.', '.'],
      ['.', '.', '.', '.', '#'],
      ['.', '.', '.', '.', '#'],
      ['.', '#', '.', '.', '.'],
    ];
    const target: Position = [0, 2];
    const expectedResult = [
      ['#', '#', '#', '5', '6'],
      ['1', '2', '3', '4', '#'],
      ['0', '1', '2', '3', '#'],
      ['1', '#', '3', '4', '5'],
    ];
    const dijkstraMap = getDijkstraMap(map, target);
    expect(dijkstraMap).toEqual(expectedResult);
  });

One concern I have is that my getDijkstraMap function seems to scale very poorly with map dimensions increasing. This is pretty bad as in order to do exciting things as explained in the "Incredible power of dijkstra maps" article, you are supposed to be able to generate several maps every round. In my current implementation, performances starts degrading very vast around 25x20 maps:

// Performance degrades very fast on bigger maps:
// 5x4 ~ 0.23ms
// 25x21 ~ 32ms
// 30x30 ~ 926ms
// Will reach several seconds beyond these (and explodes around 35x35, ~ 10 sec)

Since the maps I currently use are 60x38, I'm worried that I won't be able to use dijkstra maps, unless I improve performance drastically or maybe only run the function on a subset of the map (like what shows in the viewport), but that's not quite ideal... I wonder how it works in other projects. Are you able to generate several of these maps on larger grids within milliseconds? I'm thinking that I might have missed something, as the function starts taking several full seconds beyond 30x30.

[TimAstier]

I found my mistake, I had duplicates in some arrays 🎉 New performance:

// 5x4 ~ 0.24ms
// 25x21 ~ 1.21ms
// 30x30 ~ 2.21ms
// 60x38 ~ 6.96ms (can go up to about 16 sometimes)