Алгоритм поиска пути Jump Point Search

[mikser]

http://habrahabr.ru/post/162915/
Поигрался с их очень юзабельными визуализатором на HTML5 http://qiao.github.com/PathFinding.js/visual/ (для сравнения там завизуализированы и другие алгоритмы поиска пути)

По субьеткивным ощущениям работает на порядок быстрее A* и ему подобных

[lamo386]

хм миксер умеет интересное чтиво подбросить

[goodvin1709]

Да быстро А* работает.Я много читал про него но мне страшновато то что если у нас матрица 32766*32766 вроде как кусок карты. а не 27*27 то будет плоховато дело.В принципе вот что получилось с вводом лабиринта:
Оффтоп

13 ms очень даже не плохо ну учитывая то что нужно будет подгрузить геодату,вбить ее в матрицу[x,y,I]
i=1,i=0 если 1 то проходимо если 0 преграда.И что бы добежать от ГК Гирана до ДВ просчет будет занимать возможно пару минут(смотря какой код).
Ну вот тестим самый быстрый под бота:
A*-Manhattan - 2 ms.Operation:1425.
A*-Euclidean - 4 ms.Operation:1426.
A*-Chebyshev - 1 ms.Operation:1426.
Breadth-First-Search -4 ms.Operation:1443.
Best-First-Search -Manhattan - 4 ms.Operation:1232.
Best-First-Search -Euclidean - 9 ms.Operation:1229.
Best-First-Search -Chebyshev - 2 ms.Operation:1242.
Dijkstra- 2 ms.Operation:1433.
Jump Point Search-Manhattan - 9 ms.Operation:184.
Jump Point Search-Euclidean - 5 ms.Operation:184.
Jump Point Search-Chebyshev - 1 ms.Operation:184.
Топ 1:Jump Point Search-Chebyshev - 1 ms.Operation:184.
Теперь вопрос:Подойдет ли он для поиска пути в Lineage 2.?Как его засунуть в .dll или в исходный кусок?
Дальше посидев чуток я нашел его код на .js
Оффтоп

var Heap = require('../core/Heap');
var Util = require('../core/Util');
var Heuristic = require('../core/Heuristic');

/**
* Path finder using the Jump Point Search algorithm
* @param {object} opt
* @param {function} opt.heuristic Heuristic function to estimate the distance
* (defaults to manhattan).
*/
function JumpPointFinder(opt) {
opt = opt || {};
this.heuristic = opt.heuristic || Heuristic.manhattan;
}

/**
* Find and return the the path.
* @return {Array.<[number, number]>} The path, including both start and
* end positions.
*/
JumpPointFinder.prototype.findPath = function(startX, startY, endX, endY, grid) {
var openList = this.openList = new Heap(function(nodeA, nodeB) {
return nodeA.f - nodeB.f;
}),
startNode = this.startNode = grid.getNodeAt(startX, startY),
endNode = this.endNode = grid.getNodeAt(endX, endY), node;

this.grid = grid;


// set the `g` and `f` value of the start node to be 0
startNode.g = 0;
startNode.f = 0;

// push the start node into the open list
openList.push(startNode);
startNode.opened = true;

// while the open list is not empty
while (!openList.empty()) {
// pop the position of node which has the minimum `f` value.
node = openList.pop();
node.closed = true;

if (node === endNode) {
return Util.backtrace(endNode);
}

this._identifySuccessors(node);
}

// fail to find the path
return [];
};

/**
* Identify successors for the given node. Runs a jump point search in the
* direction of each available neighbor, adding any points found to the open
* list.
* @protected
*/
JumpPointFinder.prototype._identifySuccessors = function(node) {
var grid = this.grid,
heuristic = this.heuristic,
openList = this.openList,
endX = this.endNode.x,
endY = this.endNode.y,
neighbors, neighbor,
jumpPoint, i, l,
x = node.x, y = node.y,
jx, jy, dx, dy, d, ng, jumpNode,
abs = Math.abs, max = Math.max;

neighbors = this._findNeighbors(node);
for(i = 0, l = neighbors.length; i < l; ++i) {
neighbor = neighbors[i];
jumpPoint = this._jump(neighbor[0], neighbor[1], x, y);
if (jumpPoint) {

jx = jumpPoint[0];
jy = jumpPoint[1];
jumpNode = grid.getNodeAt(jx, jy);

if (jumpNode.closed) {
continue;
}

// include distance, as parent may not be immediately adjacent:
d = Heuristic.euclidean(abs(jx - x), abs(jy - y));
ng = node.g + d; // next `g` value

if (!jumpNode.opened || ng < jumpNode.g) {
jumpNode.g = ng;
jumpNode.h = jumpNode.h || heuristic(abs(jx - endX), abs(jy - endY));
jumpNode.f = jumpNode.g + jumpNode.h;
jumpNode.parent = node;

if (!jumpNode.opened) {
openList.push(jumpNode);
jumpNode.opened = true;
} else {
openList.updateItem(jumpNode);
}
}
}
}
};

/**
Search recursively in the direction (parent -> child), stopping only when a
* jump point is found.
* @protected
* @return {Array.<[number, number]>} The x, y coordinate of the jump point
* found, or null if not found
*/
JumpPointFinder.prototype._jump = function(x, y, px, py) {
var grid = this.grid,
dx = x - px, dy = y - py, jx, jy;

if (!grid.isWalkableAt(x, y)) {
return null;
}
else if (grid.getNodeAt(x, y) === this.endNode) {
return [x, y];
}

// check for forced neighbors
// along the diagonal
if (dx !== 0 && dy !== 0) {
if ((grid.isWalkableAt(x - dx, y + dy) && !grid.isWalkableAt(x - dx, y)) ||
(grid.isWalkableAt(x + dx, y - dy) && !grid.isWalkableAt(x, y - dy))) {
return [x, y];
}
}
// horizontally/vertically
else {
if( dx !== 0 ) { // moving along x
if((grid.isWalkableAt(x + dx, y + 1) && !grid.isWalkableAt(x, y + 1)) ||
(grid.isWalkableAt(x + dx, y - 1) && !grid.isWalkableAt(x, y - 1))) {
return [x, y];
}
}
else {
if((grid.isWalkableAt(x + 1, y + dy) && !grid.isWalkableAt(x + 1, y)) ||
(grid.isWalkableAt(x - 1, y + dy) && !grid.isWalkableAt(x - 1, y))) {
return [x, y];
}
}
}

// when moving diagonally, must check for vertical/horizontal jump points
if (dx !== 0 && dy !== 0) {
jx = this._jump(x + dx, y, x, y);
jy = this._jump(x, y + dy, x, y);
if (jx || jy) {
return [x, y];
}
}

// moving diagonally, must make sure one of the vertical/horizontal
// neighbors is open to allow the path
if (grid.isWalkableAt(x + dx, y) || grid.isWalkableAt(x, y + dy)) {
return this._jump(x + dx, y + dy, x, y);
} else {
return null;
}
};

/**
* Find the neighbors for the given node. If the node has a parent,
* prune the neighbors based on the jump point search algorithm, otherwise
* return all available neighbors.
* @return {Array.<[number, number]>} The neighbors found.
*/
JumpPointFinder.prototype._findNeighbors = function(node) {
var parent = node.parent,
x = node.x, y = node.y,
grid = this.grid,
px, py, nx, ny, dx, dy,
neighbors = [], neighborNodes, neighborNode, i, l;

// directed pruning: can ignore most neighbors, unless forced.
if (parent) {
px = parent.x;
py = parent.y;
// get the normalized direction of travel
dx = (x - px) / Math.max(Math.abs(x - px), 1);
dy = (y - py) / Math.max(Math.abs(y - py), 1);

// search diagonally
if (dx !== 0 && dy !== 0) {
if (grid.isWalkableAt(x, y + dy)) {
neighbors.push([x, y + dy]);
}
if (grid.isWalkableAt(x + dx, y)) {
neighbors.push([x + dx, y]);
}
if (grid.isWalkableAt(x, y + dy) || grid.isWalkableAt(x + dx, y)) {
neighbors.push([x + dx, y + dy]);
}
if (!grid.isWalkableAt(x - dx, y) && grid.isWalkableAt(x, y + dy)) {
neighbors.push([x - dx, y + dy]);
}
if (!grid.isWalkableAt(x, y - dy) && grid.isWalkableAt(x + dx, y)) {
neighbors.push([x + dx, y - dy]);
}
}
// search horizontally/vertically
else {
if(dx === 0) {
if (grid.isWalkableAt(x, y + dy)) {
if (grid.isWalkableAt(x, y + dy)) {
neighbors.push([x, y + dy]);
}
if (!grid.isWalkableAt(x + 1, y)) {
neighbors.push([x + 1, y + dy]);
}
if (!grid.isWalkableAt(x - 1, y)) {
neighbors.push([x - 1, y + dy]);
}
}
}
else {
if (grid.isWalkableAt(x + dx, y)) {
if (grid.isWalkableAt(x + dx, y)) {
neighbors.push([x + dx, y]);
}
if (!grid.isWalkableAt(x, y + 1)) {
neighbors.push([x + dx, y + 1]);
}
if (!grid.isWalkableAt(x, y - 1)) {
neighbors.push([x + dx, y - 1]);
}
}
}
}
}
// return all neighbors
else {
neighborNodes = grid.getNeighbors(node, true);
for (i = 0, l = neighborNodes.length; i < l; ++i) {
neighborNode = neighborNodes[i];
neighbors.push([neighborNode.x, neighborNode.y]);
}
}

return neighbors;
};

module.exports = JumpPointFinder;

Сам алгоритм тут:-->llllllllllll<--
Дерзаем товарищи!

[alexteam]

вбить ее в матрицу[x,y,I]

вот тут то и начнуться проблемы. главная их них - память. т.к. алгорит требует площадь с одинаковой стоимостью перехода между ее соседними ячейками. т.е. надо квантовать "одинаковыми квадратиками"

Добавлено через 14 минут
а вообще, квантовать плохо. особенно если игровое пространство "непрерывно". пусть даже и псевдонепрерывно.
догадаетесь почему?


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

[supernewbie]

alexteam, можно с каждой точки проверять можно ли двигаться напрямую и удалять промежуточные точки

[goodvin1709]

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

[Zergatul]

Все равно бот будет двигаться подозрительно