How to efficiently implement Dijkstra's path finding algorithm?

Question

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:

Answer 1

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.