A few things jump out to me:
- Your goal selection can choose any tile as a goal, even ones that are not walkable.
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.
- 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.
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. 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.
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 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.
- 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.