Алгоритм Дейкстры медленный. (Для петель)

Я попытался добавить алгоритм Дейкстры в js-игру. Сначала, когда я заставил его работать, он был очень медленным (5-10 кадров в секунду), и браузер вылетал из строя. После добавления множества улучшений я добился 50-60 кадров в секунду с 200 плитками (см. GRID_SPREADING в скрипте ниже). Когда я выключаю этот алгоритм, у меня получается 120–144 кадров в секунду, но я пытаюсь получить как минимум 60+ кадров в секунду при использовании 800–1000 плиток (см. GRID_SPREADING в сценарии ниже, я хочу, чтобы максимальное значение было не менее 800). Я пока не так хорош в кодировании, поэтому буду очень благодарен, если вы поможете мне достичь этой цели … (вот видео, которое я следил, чтобы создать это: https://www.youtube.com/watch?v=0faPPgOT—E&t=934sправда, делал это с нуля).

Вот отрывистая часть:

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();

Я провел много исследований, но не могу найти решение, чтобы устранить эту задержку. Есть ли другой способ сделать это лучше?

Поскольку большая часть деталей, необходимых для тренировки того, что происходит, отсутствует (см. Мой комментарий к вопросу), можно только просмотреть то, что можно увидеть.

Ваш запрос на устранение лагов в коде невозможно решить, не делая много предположений.

Ошибки.

Нет пути через функцию pathfindLoop это не называет себя. Это вызовет у вас проблемы, однако ваше намерение неясно, а точный характер проблемы зависит от вашего намерения.

Неясное ожидание

Когда вы вызываете сон, вы его ждете.

Однако рекурсивный вызов pathfindLoop() не ожидается. Совершенно непонятно, является ли это ошибкой только вашей стороны (ошибка) или преднамеренной (проблема).

О … бесконечность всего этого

Ваша функция приведет к сбою страницы, поскольку ваш код не позволяет стеку вызовов выдавать вызовы при выходе pathfindLoop

Звонить pathfindLoop означает бесконечный список обращений к себе.

Догадавшись о вашем намерении, можно было бы увидеть в этом способ создания непрерывной системы, подобной опросу (похожей на setInterval или цикл анимации с использованием requestAnimationFrame). Подождите 10 (сколько угодно), затем обработайте данные и повторите.

Если это ваше намерение, это очень ошибочно, поскольку вы не учитываете стек вызовов.

Каждый звонок pathfindLoop добавляет новый контекст в стек вызовов. Каждое обещание создает новую запись в стеке обещаний.

Поскольку функция async контекст не может быть удален из стека до тех пор, пока контекст async звонки, которые он сделал, разрешены. Этого никогда не произойдет и в конце концов позвонит pathfindLoop приведет к сбою страницы, задолго до этого она перестанет отвечать (зависает).

Возможно, это задержка, о которой вы упомянули в своем вопросе. Хотя без дальнейших подробностей можно только догадываться.

Общие моменты

Дополнительные моменты, замеченные при просмотре кода.

• Плохое название.

• Соглашение JS не использовать snake_case для имен переменных. Обычно он используется только в js при определении имен в UPPERCASE_SNAKE

• Непоследовательное использование точек с запятой.

• Нечетное размещение точки с запятой. У вас есть точка с запятой в конце if пункт. например if (foo); {... точка с запятой игнорируется, но остается задаться вопросом, каковы ваши намерения здесь?

• Слишком сильно зависит от более высокого прицела. В частности, потому что вы мутируете pgrids, а также realPgrids. Это может быть, а может и не плохо, но опять же без дополнительной информации можно только догадываться.

• Неясное использование переменных с более высоким ограничением или неопределенных переменных. Переменная build определенный??? Будет добавлено "use strict" к вашему коду вызвать его сбой ??

• Небезопасное использование для … в петли. В современном JS действительно нет причин использовать для … в петли. Скорее использовать для … из петля

  Пример использования for of скорее, чем for in. Из вашего кода …

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

  Предполагая builds это объект

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

  Или предполагая builds это массив

    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);
  

  ссылка на Array.every

Переписать ??

Я не могу полностью переписать ваш код, так как не могу закодировать неизвестные детали.

Перезапись решит проблему стека вызовов и предполагает, что pathfindLoop быть сродни функции опроса.

"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
}

Ссылки

• strict_mode
• setTimeout