Альтернатива Javascript pathfinding.js - PullRequest
Новая
       47

Альтернатива Javascript pathfinding.js

0 голосов
/ 29 сентября 2019

Я использую библиотеку pathfinding.js , чтобы найти ближайший путь.На входе у меня есть мои координаты в качестве объекта {x: x, y: y} и массив объектов с координатами пунктов назначения [{x: x, y: y}].

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

Перед циклом я устанавливаю столкновения, которые также являются массивом объектов, таких как координаты пунктов назначения [{x: x, y: y}]. 

const PF = require('pathfinding');

const getClosestMonsterData = (page, heroCoords, destinationCoords, mapData, range) => {
    return new Promise(resolve => {

        let currentGrid, currentPath,
            closestPathLength = range,
            closestPath = [],
            closestPathFormatted = [],
            closestCoords = {},
            softGrid = new PF.Grid(mapData.dimensions.x, mapData.dimensions.y),
            finder = new PF.AStarFinder();

        //set collisions
        for(let i = 0; i < mapData.collisions.length; i++) {
            softGrid.setWalkableAt(mapData.collisions[i].x, mapData.collisions[i].y, false);
        }

        //find actual closest coordinate and its path
        for(let i = 0; i < destinationCoords.length; i++) {
            currentGrid = softGrid.clone();
            currentPath = finder.findPath(heroCoords.x, heroCoords.y, destinationCoords[i].x, destinationCoords[i].y, currentGrid);

            if(currentPath && currentPath.length !== 0 && currentPath.length <= closestPathLength) {
                closestPathLength = currentPath.length;
                closestPath = currentPath;
                closestCoords = destinationCoords[i];
            }
        }

        resolve({ coord: closestCoords, path: closestPathFormatted });
    });
};

export { getClosestMonsterData }

Эта библиотека вынуждает меня клонировать сетку вцикл каждый раз, когда я использую findPath метод.Моя приборная панель не большая - она ​​размером около 100х100.Кроме того, около половины из них - столкновения.Массив адресатов содержит около 100 элементов.

Моя проблема в том, что этот алгоритм работает так медленно.Настолько медленный, что я могу буквально увидеть человеческим глазом, что программа ждет этой функции. Иногда для этого требуется даже 1 секунда (так!).Это, вероятно, из-за клонирования этой сетки каждый раз ... Я ищу альтернативу для этой библиотеки, мои требования:

  • Я могу установить размер сетки двумя числами x, y
  • Я могу установить координаты, которые нельзя пройти (столкновения), двумя числами x, y
  • Я могу найти координаты пути, кратчайшие x, y, двумя числами
  • Быстрее, чем этот pathfinding.js
...