# How to efficiently implement Dijkstra's path finding algorithm?

As per this answer: How to devise an algorithm for a person being on a walk? I tried to implement a simple path finding algorithm.

The map is 60x60 tiles total, and walkable tiles are even fewer:

(The reddish tiles are walkable and have weight of 1 (road), the greenish tiles have weight of 2 (grass), the white tiles are unwalkable)

I hoped that for such a small map there shouldn't be any performance issues. I was wrong. The game is supposed to run at 60fps. With the profiler enabled path finding can take up to 50ms! This means a few frames. Even with the profiler disabled the jitter is very visible. In this case I believe the algorithm would be unusable on any larger map. What am I doing wrong?

Here is the code for one character (The engine: RPG Maker MV):

GZKM.P1MomWalkMovement = function() {
var getTileWeight = function(tagId) {
return 1+((tagId&0x10)>>1)
}

$gameVariables._data[3] =$gameVariables._data[3] || {}
var state = ($gameVariables._data[3].P1MomWalkMovement =$gameVariables._data[3].P1MomWalkMovement || {})
state.goal = state.goal || null

var findgoal = function() {
var arr = []
for(var x = 0; x < $gameMap.width(); x++) for(var y = 0; y <$gameMap.height(); y++) if($gameMap.regionId(x,y)&0x1) arr.push({x:x,y:y}) state.goal = arr[Math.floor(Math.random()*arr.length)] } var setMomMovement = function() { var mom = this; var evs = [] for(var x = 0; x <$gameMap.width(); x++) {
evs[x] = []
for(var y = 0; y < $gameMap.height(); y++) { evs[x][y] = [] } }$gameMap.events().filter(function(ev){return ev.isNormalPriority() && !ev.isThrough()}).forEach(function(ev){evs[ev.x][ev.y].push(ev)})

// Optimization attempt. RPGMaker's default checks for passability seem to be linear in the number of all events on map per tile.
// I tried to bring this down to O(1) per tile.
// No, I didn't profile this, b/c I don't have many events yet - but
// I plan to have more, so I wanted to be on a safe side.
var isCollidedWithEventsOld = Game_CharacterBase.prototype.isCollidedWithEvents;
Game_CharacterBase.prototype.isCollidedWithEvents = function(x, y) {
return evs[x][y].length
}

var h = new GZKM.Heap()
var map = []
for(var x = 0; x < $gameMap.width(); x++) for(var y = 0; y <$gameMap.height(); y++) if($gameMap.regionId(x,y)&0x1) if(x != mom.x || y != mom.y) map[[x,y]] = h.push(Infinity, {x:x,y:y}) map[[mom.x, mom.y]] = h.push(0, {x:mom.x, y:mom.y}) var curr; while((curr = h.pop()) !== undefined && curr.priority != Infinity && !(curr.elt.x == state.goal.x && curr.elt.y == state.goal.y)) { for(var d = 2; d <= 8; d+=2) { // directions var nx =$gameMap.roundXWithDirection(curr.elt.x, d)
var ny = $gameMap.roundYWithDirection(curr.elt.y, d) if([nx,ny] in map && mom.canPass(curr.elt.x, curr.elt.y, d)) { var candPriority = curr.priority + getTileWeight($gameMap.regionId(curr.elt.x,curr.elt.y))
if(candPriority < map[[nx,ny]].priority) {
h.reprioritize(map[[nx,ny]], candPriority)
map[[nx,ny]].elt.prev = curr
}
}
}
}

Game_CharacterBase.prototype.isCollidedWithEvents = isCollidedWithEventsOld;

if(!('prev' in map[[state.goal.x, state.goal.y]].elt))
state.goal = null
else {
var t = map[[state.goal.x, state.goal.y]]
while(!(t.elt.prev.elt.x == mom.x && t.elt.prev.elt.y == mom.y))
t = t.elt.prev
var dir;
if(t.elt.x == mom.x+1) dir = 6
else if(t.elt.x == mom.x-1) dir = 4
else if(t.elt.y == mom.y+1) dir = 2
else if(t.elt.y == mom.y-1) dir = 8
this.moveStraight(dir)
}

}.bind(this)

if(state.goal === null) findgoal()

setMomMovement()
}


My heap implementation is here: https://codereview.stackexchange.com/questions/177124/binary-heap-priority-queue-implementation-in-javascript

What am I doing wrong? How to fix the code and remove the jitter?

Edit: Sorry, I forgot to tell you. According to the profiler the game spends an unacceptably high amount of time in setMomMovement. 1/2 - 1/3 of this time is the function's self time, the rest is mainly Game_CharacterBase.canPass (RPG Maker's function... will I have to try to optimize it even more?) Around 1-2 ms is spent in my heap implementation:

• Does your profiler tell you where exactly the bottleneck in above code might be? – Philipp Oct 17 '17 at 11:36
• @Philipp Yes, of course, I'm sorry. Please see my edited question. – gaazkam Oct 17 '17 at 12:12

A few things jump out to me:

1. Your goal selection can choose any tile as a goal, even ones that are not walkable.

(Oops, this is not the case, I'd just misread the method. I'll leave the remainder of this point in for others' reference)

You can terminate Dijkstra's Algorithm early when it reaches the goal, but if the goal is unreachable then it has no choice but to explore the entire reachable area trying to find some way in. Ensuring the goal is reachable should avoid this worst-case search most of the time.

2. It's been a while since I used RPGMaker (it wasn't using js back then), but it looks like you re-plan the entire path every time you need to take one step, take that step, then throw out the rest of the path and re-plan on the next update. Am I reading this right?

I understand that maintaining complex state from frame to frame is somewhat challenging in scripting environments like this, but it could be well worth the investment to cache this path so it can be re-used until it needs to be invalidated.

Even without threads, you can spread this re-planning work over multiple frames to avoid any periodic hitches whenever a new path is needed.

3. The same goes for your data structures like the passability map and heap. Re-allocating (and re-filling the passability) frequently can be a big time sink. Especially since your profiling shows gathering the passability information is one of your biggest time sinks.

Investing in a way to cache and re-use these structures instead of always re-creating them from scratch could be a big win, and might even let you have multiple agents sharing this pathfinding investment together, so you get more gameplay bang for your programming buck.

4. You can add a heuristic estimate to your Dijkstra implementation to turn it into A*, prioritizing the direct route to the goal and spending less time exploring less-promising side branches (provided the goal is reachable)

The heuristic needn't be complicated; even a simple Manhattan distance heuristic will help.

• Thank you for your answer. re 1) Actually I think not: if(\$gameMap.regionId(x,y)&0x1) - this ensures the goal must be a passable tile ("passable tiles" are defined by tags, this is because I'd like Mom to move in a much narrower set of tiles than the player; my picture above shows tiles passable by Mom only, not by player); – gaazkam Oct 17 '17 at 13:14
• re 2 and 3) You're right of course, but: my thinking was, either the performance overhead is acceptable or not, and if it is, then it won't hurt to add it every step as the fps won't decline, or if it's not, then this optimizatinon would only make the jitter less frequent, which would still be unacceptable; re 4) But how? The simple distance function? I'm not sure. Precalculating Dijsktra for all tiles? This might go in MBs of additional data to download. All that comes to my mind is to laborously define the heuristic by hand ;/ Guess I'd better start working on it, then ;/ Have an upvote! – gaazkam Oct 17 '17 at 13:16
• Ahh, thanks. I'd missed that on mobile since only the first part of the line fits on the screen. Please consider putting line breaks between different statements in your code to keep it easy to read. ;) – DMGregory Oct 17 '17 at 13:16
• 2: No, you can incrementally pathfind a little over multiple frames, so you don't need to take a hitch all at once when the re-pathfinding kicks off. 3: No, this setup needs to be done only once on map load or incrementally updated if something on the map changes, not re-created from scratch periodically. 4: Yes, a simple distance function is a standard choice for an A* heuristic. In this case you'd probably use Manhattan distance — it's fast to calculate on demand, and is admissible (never over-estimates distance for an agent that moves in 4 cardinal directions). – DMGregory Oct 17 '17 at 13:20
• The benefit of Dijkstra's over A* is that with Dijkstra's you get (as a side-effect) all the closest paths to or from a goal node, so you can re-use the same results, especially if there some tiles that are often interesting. And regarding the calculating it every frame or not you can spread out the load by not completing the entire algorithm in one frame. – pelle Oct 18 '17 at 17:07