A* Проблема с следопытом

Спасибо, что позволили мне присоединиться к вашим форумам.

У меня есть вопрос относительно сценария поиска пути A*, над ответом на который я ломал голову последние пару дней.

Я разобрался с большей частью этого, но мои навыки программирования недостаточно хороши, чтобы понять некоторые его части.



Я понимаю, что он выбирает начальную и конечную точку при первой загрузке программы или когда пользователь щелкает мышью и вызывает функцию findPath(). и я могу проследить его до функции CalculatePath() и разобраться с большей частью остального кода, но есть пара строк, которые я просто не понимаю:

Эта линия.

Как он может выполнить этот оператор условия, если переменной length еще не присвоено значение:

362 while(длина = открытая.длина)

{...}

Кроме того, что, черт возьми, означает индекс массива [0] в конце:

375 myNode = open.splice(мин, 1)[0];

Вот сценарий:

// элемент холста игры

вар холст = ноль;

// контекст холста 2d

вар ctx = ноль;

// изображение, содержащее все спрайты

вар спрайтшит = ноль;

// true, когда таблица спрайтов загружена

вар spritesheetLoaded = ложь;

// мировая сетка: двухмерный массив тайлов

вар мир = [[]];

// размер в мире в тайлах спрайтов

вар worldWidth = 16;

вар worldHeight = 16;

// размер тайла в пикселях

вар tileWidth = 32;

вар tileHeight = 32;

// начало и конец пути

вар pathStart = [worldWidth,worldHeight];

вар pathEnd = [0,0];

вар currentPath = [];

// гарантируем, что concole.log не вызывает ошибок

if (typeof console == «неопределено») var console = { log: function() {} };

// html-страница готова

функция загрузки()

{

console.log('Страница загружена.');

холст = document.getElementById('gameCanvas');

Canvas.width = worldWidth * tileWidth;

Canvas.height = worldHeight * tileHeight;

Canvas.addEventListener("клик", CanvasClick, false);

if (!canvas) alert('Бла!');

ctx = Canvas.getContext("2d");

if (!ctx) alert('Хмм!');

спрайт-таблица = новое изображение();

spritesheet.src = 'spritesheet.png';

// изображение выше было преобразовано в URL-адрес данных

// чтобы для этого не требовались никакие внешние файлы

// эта веб-страница — полезна для включения в

// страница "gist" или "jsfiddle"

//spritesheet.src = 'данные:изображение/png;......

spritesheet.onload = загружено;

}

// спрайт-лист готов

функция загружена()

{

console.log('Спрайт-таблица загружена.');

spritesheetLoaded = правда;

создатьМир();

}

// заполняем мир стенами

функция createWorld() //********************************************

{

console.log('Создание мира...');

// создаем пустоту

for (var x=0; x {

мир[х] = [];

for (var y=0; y {

мир[х][у] = 0;

}

}

// разбросать несколько стен

for (var x=0; x {

for (var y=0; y {

если (Math.random() > 0,75)

мир[х][у] = 1;

}

}

// вычисляем начальный возможный путь

// примечание: маловероятно, но возможно никогда его не найти...

текущийПуть = [];

в то время как (currentPath.length == 0)

{

pathStart = [Math.floor(Math.random()*worldWidth),Math.floor(Math.random()*worldHeight)];

pathEnd = [Math.floor(Math.random()*worldWidth),Math.floor(Math.random()*worldHeight)];

если (мир[pathStart[0]][pathStart[1]] == 0)

currentPath = findPath(мир,pathStart,pathEnd);

}

перерисовать();

} // завершение createWorld()****************************************** ****

функция перерисовки()

{

if (!spritesheetLoaded) return;

console.log('перерисовка...');

вар spriteNum = 0;

// очищаем экран

ctx.fillStyle = '#000000';

ctx.fillRect(0, 0, холст.ширина, холст.высота);

for (var x=0; x {

for (var y=0; y {

// выбираем спрайт для рисования

переключатель (мир [x] [y])

{

Дело 1:

спрайтнум = 1;

перерыв;

по умолчанию:

спрайтнум = 0;

перерыв;

}

// Нарисуй это

// ctx.drawImage(img,sx,sy,width,height,x,y,width,height);

ctx.drawImage(таблица спрайтов,

spriteNum*tileWidth, 0,

ширина плитки,

x*tileWidth, y*tileHeight,

tileWidth, tileHeight);

}

}

// рисуем путь

console.log('Текущая длина пути: '+currentPath.length);

для (rp=0; rp {

переключатель (рп)

{

случай 0:

спрайтнум = 2; // начинать

перерыв;

случай currentPath.length-1:

спрайтнум = 3; // конец

перерыв;

по умолчанию:

спрайтнум = 4; // узел пути

перерыв;

}

ctx.drawImage(таблица спрайтов,

spriteNum*tileWidth, 0,

ширина плитки,

currentPath[rp][0]*tileWidth,

currentPath[rp][1]*tileHeight,

tileWidth, tileHeight);

}

}

// обрабатываем события кликов на холсте

функция CanvasClick(e)

{

вар х;

отличаться;

// захватываем координаты html-страницы

if (e.pageX != не определено & & e.pageY != не определено)

{

х = е.страницаX;

y = e.pageY;

}

еще

{

x = e.clientX + document.body.scrollLeft +

документ.documentElement.scrollLeft;

y = e.clientY + document.body.scrollTop +

document.documentElement.scrollTop;

}

// делаем их только относительно холста

х -= холст.offsetLeft;

y -= холст.offsetTop;

// возвращаем плитку x,y, на которую мы нажали

вар ячейка =

[

Math.floor(x/tileWidth),

Math.floor(y/tileHeight)

];

// теперь мы знаем, когда нажали на плитку

console.log('мы нажали плитку '+cell[0]+','+cell[1]); //@@@@@@@@@@@@

pathStart = pathEnd;// в этот момент pathEnd = [0,0], поэтому pathStart = [0,0]

Конец пути = ячейка; // например, pathEnd = [5,6]

// вычисляем путь

currentPath = findPath(мир,pathStart,pathEnd);

перерисовать();

}

// мир — это двумерный массив целых чисел (например, world[10][15] = 0)

// pathStart и pathEnd — это массивы типа [5,10]

функция findPath(world, pathStart, pathEnd)//@@@@@@@@@@@найти путь

{

// ярлыки для скорости

вар абс = Math.abs;

вар макс = Math.max;

вар pow = Math.pow;

вар sqrt = Math.sqrt;

// мировые данные являются целыми числами:

// все, что превышает это число, считается заблокированным

// это удобно, если вы используете пронумерованные спрайты, более одного

// из которых пешеходная дорога, трава, грязь и т. д.

вар maxWalkableTileNum = 0;

// отслеживаем размеры мира

// Обратите внимание, что эта реализация A-star ожидает, что мировой массив будет квадратным:

// он должен иметь одинаковую высоту и ширину.

Если ваш игровой мир прямоугольный,

// просто заполните массив фиктивными значениями, чтобы заполнить пустое пространство.

вар worldWidth = мир [0].length;

вар worldHeight = world.length;

вар worldSize = worldWidth * worldHeight;

// какую эвристику нам следует использовать?

// по умолчанию: без диагоналей (Манхэттен)

вар distanceFunction = ManhattanDistance;

вар findNeighbours = функция () {}; // пустой

// функции distanceFunction

// они возвращают расстояние от одной точки до другой

функция ManhattanDistance(Точка, Цель)

{ // линейное движение – никаких диагоналей – только стороны света (NSEW)

вернуть abs(Point.x - Goal.x) + abs(Point.y - Goal.y);

}

функция DiagonalDistance(Точка, Цель)

{ // диагональное движение - предполагается, что Diag Dist равен 1, как и кардиналы

return max(abs(Point.x - Goal.x), abs(Point.y - Goal.y));

}

функция EuclideanDistance(Точка, Цель)

{ // диагонали считаются немного дальше сторон света

// диагональное движение с помощью Евклида (AC = sqrt(AB^2 + BC^2))

// где AB = x2 - x1 и BC = y2 - y1 и AC будет [x3, y3]

return sqrt(pow(Point.x - Goal.x, 2) + pow(Point.y - Goal.y, 2));

}

функция Neighbours(x, y) //myNeighbours = Neighbours(myNode.x, myNode.y);

//myNode.xy = плитка из открытого массива

{

вар N = y - 1,

S = у + 1,

Е = х + 1,

Ш = х - 1,

myN = N > -1 & & canWalkHere(x, N), myS = S myE = E myW = W > -1 & & canWalkHere(W, y), результат = []; если (мойN) result.push({x:x, y:N}); если (myE) result.push({x, y:y});

если (myS)

result.push({x:x, y:S});

если (myW)

result.push({x:W, y:y});

findNeighbours(myN, myS, myE, myW, N, S, E, W, результат);

вернуть результат;

}

// возвращает логическое значение (мировая ячейка доступна и открыта)

функция canWalkHere(x, y)

{

return ((world[x] != null) & &

(мир[x][y] != ноль) & &

(world[x][y] <= maxWalkableTileNum));

};

// Функция Node, возвращает новый объект со свойствами Node

// Используется в функции CalculatePath для хранения стоимости маршрута и т. д.

// 1-й вызов, var mypathStart = Node(null, {xathStart[0], yathStart[1]});

функция Node(Parent, Point) // Point = {xathStart[0], yathStart[1]}

{

вар newNode = {

// указатель на другой объект Node

Родитель,

// индекс массива этого узла в мировом линейном массиве

valueoint.x + (Point.y * worldWidth),

// координаты местоположения этого узла

xoint.x,

йоинт.й,

// эвристическая оценка стоимости

// всего пути с использованием этого узла

ф:0,

// стоимость distanceFunction, которую нужно получить

// от начальной точки до этого узла

г:0

};

вернуть новыйузел;

}

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

// Функция пути, выполняет операции алгоритма AStar@@@@@@@@@@@

функция расчетаПути()

{

// создаем узлы по координатам начала и конца x,y

var mypathStart = Node(null, {xathStart[0], yathStart[1]});

var mypathEnd = Node(null, {xathEnd[0], yathEnd[1]});

// создаем массив, который будет содержать все мировые ячейки

вар AStar = новый массив (worldSize);

// список открытых в данный момент узлов

вар open = [mypathStart]; // массив объектов

// список закрытых узлов

вар Закрыто = []; // массив объектов

// список итогового выходного массива

вар результат = [];

// ссылка на узел (который находится рядом)

вар мои соседи;

// ссылка на Node (который мы сейчас рассматриваем)

вар myNode;

// ссылка на узел (с которого начинается рассматриваемый путь)

вар myPath;

// временные целочисленные переменные, используемые в вычислениях

длина var, max, min, i, j;

// перебираем открытый список, пока ничего не останется

в то время как (длина = открытая длина)

{

Макс = WorldSize;

мин = -1;

for(i = 0; i < length; i++) // притворяемся, что длина = 1 { если (открыть.f <макс)
{
макс = открыто.ф;
мин = я;
}
}
// захватываем следующий узел и удаляем его из открытого массива
myNode = open.splice(мин, 1)[0];

// это целевой узел?
if(myNode.value === mypathEnd.value)
{
myPath = Closed[Closed.push(myNode) - 1];
делать
{
result.push([myPath.x, myPath.y]);
}
в то время как (myPath = myPath.Parent);
// очищаем рабочие массивы
AStar = Закрыто = открыто = [];
// мы хотим вернуть начало и конец
результат.обратный();
}
else // или это не целевой узел
{
// находим, какие ближайшие узлы доступны для прохода
myNeighbours = Neighbours(myNode.x, myNode.y);
// проверяем каждый из них, который еще не был опробован
for(i = 0, j = myNeighbours.length; i {
myPath = Node(myNode, myNeighbours); // myNode является родительским
если (!AStar[myPath.value])
{
// предполагаемая стоимость этого конкретного маршрута на данный момент
myPath.g = myNode.g + distanceFunction(myNeighbours, мойУзел);
//оценочная стоимость всего предполагаемого маршрута до пункта назначения
myPath.f = myPath.g + distanceFunction(myNeighbours, mypathEnd);
// запомните этот новый путь для тестирования выше
open.push(мойПуть);
// отмечаем этот узел в мировом графе как посещенный
AStar[myPath.value] = правда;
}
}
// запоминаем этот маршрут как не имеющий непроверенных опций
Closed.push(myNode);
}
} // продолжаем итерацию, пока список Open не станет пустым
вернуть результат;
}

// фактически вычисляем путь со звездочкой!
// это возвращает массив координат
// пусто, если путь невозможен
вернуть расчетный путь();

} // конец функции findPath()