Dijkstra's algorithm is slow. (For loops)

Question

I tried to add Dijkstra's algorithm to a js game. First when I got it working it was very very Laggy (5-10 fps) and the browser would crash.. After adding a lot more improvements I got it to like 50-60 fps with 200 tiles (see GRID_SPREADING in script bellow). When I turn off this algorithm I have 120-144 fps, but I am trying to at least get 60+ fps while using 800-1000 tiles (see GRID_SPREADING in script below, I want max to be at least 800). I am not that good at coding yet so I would really be thankfull if you can help me achieve this goal... (here is the video I followed to create this: https://www.youtube.com/watch?v=0faPPgOT--E&t=934s, though, he was doing it in scratch).

Here is the laggy part:

var GRID_SPREADING = {
 dist: 80,
 b_col: 100,
 max: 400,
 show: false
}
// the main player will look and move to the direction of the nearest tile (not the direction to the nearest tile, but the dir property of the nearest tile)
const pathfindLoop = async () => { // pgrids is an object of arrays that holds all dijkstra algorithm's tiles
 if(!doPathfind || !nearestEnemy || dist4(nearestEnemy[1], nearestEnemy[2], enemyMovedPath[0], enemyMovedPath[1]) < 10) {
 await sleep(10);
 pathfindLoop();
 return;
 }
 if(Object.keys(pgrids).length > GRID_SPREADING.max){
 enemyMovedPath[0] = nearestEnemy[1];
 enemyMovedPath[1] = nearestEnemy[2];
 realPgrids = pgrids;
 pgrids = {};
 } else {
 let makeFirstP = true;
 for(let mfp in pgrids) {
 if(dist4(pgrids[mfp].x, pgrids[mfp].y, nearestEnemy[1], nearestEnemy[2]) < 50); {
 makeFirstP = false;
 }
 }
 if(makeFirstP) {
 createPathObj(nearestEnemy[1], nearestEnemy[2], 90);
 }
 for(let o in pgrids) {
 if(!(pgrids[o].checked)) {
 for(let i = 0; i < 4; i++) {
 if(i == 3) {
 pgrids[o].checked = true;
 }
 let res1 = locwxda(pgrids[o].x, pgrids[o].y, i*90, -GRID_SPREADING.dist);
 let res = {x: res1.x, y: res1.y};
 let go = true;
 for(pgrid in pgrids) {
 if(dist4(res.x, res.y, pgrids[pgrid].x, pgrids[pgrid].y) < GRID_SPREADING.dist/2.5) {
 go = false;
 break;
 }
 }
 if(go) {
 
 for(build in builds) { // builds is a large object of arrays: 50-300 properties, but removing this for loop doesn't improve much at all
 if(dist4(builds[build][1], builds[build][2], res.x, res.y) < GRID_SPREADING.b_col) {
 go = false;
 break;
 }
 }
 
 }
 if(go) {
 createPathObj(res.x, res.y, i*90) // a simple short function, adds an array property to object pgrids
 }
 }
 }
 }
 }
 await sleep(10);
 pathfindLoop();
 } 
 pathfindLoop();

I've done many research but I can't find the solution to solve this lag. Is there a completely different and better way to do this?

• Blindman67: There is too much missing from the code to do a meaningful review. Variables doPathfind, nearestEnemy, enemyMovedPath, realPgrids, pgrids, builds and functions sleep, dist4, createPathObj, locwxda are not defined
• radarbob: I have seen a performance hit when the JS interpreter has to transit scopes looking for definitions or declarations. And conversely, a significant performance gain when we moved global scoped things into the executing scope. Just speculating of course (see @Blindman67 comment), and it seems scope nesting / (dis)encapsulation / wading in the global gunk, are driving factors not complexity metrics.
• BCdotWEB: The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How do I ask a good question?.

Answer 1

As most of the detail needed to workout what is going on, is missing, (See my comment on question) one can only review what one can see.

Your request to resolve laggy code is impossible to address without makes a lot of guesses.

Bugs.

There is no path through the function pathfindLoop that does not call its self. This will cause you problems, however your intent is unclear and the exact nature of the problem depends on your intent.

Unclear awaiting

When you call sleep you await it.

However the recursive call pathfindLoop() is not awaited. It is completely unclear if this is an error only your part (a bug) or deliberate (a problem).

Oh... the infinity of it all

Your function will crash the page as your code does not allow the call stack to pop calls when exiting pathfindLoop

To call pathfindLoop means an infinite list of calls to self.

Guessing your intention one could see this as a way of creating an ongoing polling like system (similar to setInterval or an animation loop using requestAnimationFrame). Wait 10 (what ever's) then process data and repeat.

If this is your intention it is very flawed as you fail to take into account the call stack.

Each call to pathfindLoop adds a new context to the call stack. Each promise creates a new entry on the promise stack.

As the function is async the context can not be removed from the stack until the context of async calls it has made, are resolved. This will never happen and eventually calling pathfindLoop will crash the page, well before that the page will become very unresponsive (laggy).

Maybe this is the lag you mention in your question. Though without further details one can only guess.

General points

Further points noticed when reviewing the code.

• Poor naming.

• JS convention is not to use snake_case for variable names. It is generally only used in js when defining names in UPPERCASE_SNAKE

• Inconsistent use of semicolons.

• Odd placement of semicolon. You have a semicolon at the end of an if clause. eg if (foo); {... the semi colon is ignored, but one is left to wonder as to your intent here?

• Too heavily reliant on higher scope. Particularly because you mutate pgrids, and realPgrids. This may or may not be bad but again without further information one can only guess.

• Unclear use of higher scoped or undefined variables. Is the variable build defined??? Will adding "use strict" to your code cause it to crash??

• Unsafe use of for...in loops. In modern JS there really is no reason to use for...in loops. Rather use for...of loop

  Example of using for of rather than for in. From your code...

  for (build in builds) {
   if (dist4(builds[build][1], builds[build][2], res.x, res.y) < GRID_SPREADING.b_col) {
   go = false;
   break;
   }
   }
  

  Assuming builds is an object

   for (const build of Object.values(builds)) {
   if (dist4(build[1], build[2], res.x, res.y) < GRID_SPREADING.b_col) {
   go = false;
   break;
   }
   }
  

  Or assuming builds is an array

   for (const build of builds) {
   if (dist4(build[1], build[2], res.x, res.y) < GRID_SPREADING.b_col) {
   go = false;
   break;
   }
   }
   // OR
   go = builds.every(build => dist4(build[1], build[2], res.x, res.y) >= GRID_SPREADING.b_col);
  

  ref to Array.every

Rewrite??

I can not fully rewrite your code as I can not code unknown details.

The rewrite will address the call stack problem and assumes pathfindLoop to be akin to a polling function.

"use strict"; // Always use this directive. 
const pathfindLoop = () => { // do not use async here
 // ... the rest of your code here
 setTimeout(pathfindLoop, 10); // assumes 10 from sleep(10); is ms
}

Refs

• strict_mode
• setTimeout

• A. Arh: Hey. Thanks for everything. I will try fix the bugs and bad code.. But I've tried many other things (It used to be setInterval and the performance is the same) and nothing seems to help. In the end, is it possible to have this algorithm with like 1000 tiles with good performance at all? Edit: Is there any better way that I can check if some coordinates are very near one of the property x and ys from a large object than just looping the object and checking every item one by one - I hope this is clear
• Blindman67: @A.Arh This answer codereview.stackexchange.com/a/257681/120556 has an example that has deliberately slowed down as a visualization, it handles about 16000+ tiles at a reasonable rate (though I can not remember how quick it was). 1000 tiles should be no problem.
• A. Arh: Thanks! I will take a look