Как выправить ненужные повороты в результатах поиска A* графа?
Я работал над реализацией JavaScript приключенческих игр начала 90-х годов и специально строил путь от места, где стоит герой, до места, на которое нажал игрок. Мой подход заключается в том, чтобы сначала определить, можно ли провести прямую линию (без препятствий), а если нет, то искать путь четких путевых точек, используя превосходный javascript-astar Брайана Гринстеда. Однако проблема, с которой я сталкиваюсь, заключается в том, что путь (хотя оптимальное будет отклоняться от пробелов, которые могут показаться пользователю непреднамеренными. Вот классический пример того, о чем я говорю (зеленый путь - это сгенерированный путь, красные точки). каждый поворот, где направление пути меняется):
Теперь я знаю, что A * гарантированно возвращает только путь, который не может быть проще (с точки зрения шагов), но я изо всех сил пытаюсь реализовать эвристику, которая взвешивает повороты. Вот изображение, на котором показаны два других пути, которые также можно квалифицировать как простые (с равным количеством шагов)
Синий путь будет содержать одинаковое количество шагов и поворотов, в то время как красный путь будет иметь такое же количество шагов и меньше поворотов. В моем коде у меня есть simplifyPath() функция, которая удаляет шаги, где меняется направление, поэтому, если бы я мог получить все возможные пути от astar тогда я мог бы выбрать тот с наименьшим количеством оборотов, но это не так A* фундаментально работает, поэтому я ищу способ включить простоту в эвристику.
Вот мой текущий код:
var img,
field = document.getElementById('field'),
EngineBuilder = function(field, size) {
var context = field.getContext("2d"),
graphSettings = { size: size, mid: Math.ceil(size/2)},
engine = {
getPosition: function(event) {
var bounds = field.getBoundingClientRect(),
x = Math.floor(((event.clientX - bounds.left)/field.clientWidth)*field.width),
y = Math.floor(((event.clientY - bounds.top)/field.clientHeight)*field.height),
node = graph.grid[Math.floor(y/graphSettings.size)][Math.floor(x/graphSettings.size)];
return {
x: x,
y: y,
node: node
}
},
drawObstructions: function() {
context.clearRect (0, 0, 320, 200);
if(img) {
context.drawImage(img, 0, 0);
} else {
context.fillStyle = 'rgb(0, 0, 0)';
context.fillRect(200, 100, 50, 50);
context.fillRect(0, 100, 50, 50);
context.fillRect(100, 100, 50, 50);
context.fillRect(0, 50, 150, 50);
}
},
simplifyPath: function(start, complexPath, end) {
var previous = complexPath[1], simplePath = [start, {x:(previous.y*graphSettings.size)+graphSettings.mid, y:(previous.x*graphSettings.size)+graphSettings.mid}], i, classification, previousClassification;
for(i = 1; i < (complexPath.length - 1); i++) {
classification = (complexPath[i].x-previous.x).toString()+':'+(complexPath[i].y-previous.y).toString();
if(classification !== previousClassification) {
simplePath.push({x:(complexPath[i].y*graphSettings.size)+graphSettings.mid, y:(complexPath[i].x*graphSettings.size)+graphSettings.mid});
} else {
simplePath[simplePath.length-1]={x:(complexPath[i].y*graphSettings.size)+graphSettings.mid, y:(complexPath[i].x*graphSettings.size)+graphSettings.mid};
}
previous = complexPath[i];
previousClassification = classification;
}
simplePath.push(end);
return simplePath;
},
drawPath: function(start, end) {
var path, step, next;
if(this.isPathClear(start, end)) {
this.drawLine(start, end);
} else {
path = this.simplifyPath(start, astar.search(graph, start.node, end.node), end);
if(path.length > 1) {
step = path[0];
for(next = 1; next < path.length; next++) {
this.drawLine(step, path[next]);
step = path[next];
}
}
}
},
drawLine: function(start, end) {
var x = start.x,
y = start.y,
dx = Math.abs(end.x - start.x),
sx = start.x<end.x ? 1 : -1,
dy = -1 * Math.abs(end.y - start.y),
sy = start.y<end.y ? 1 : -1,
err = dx+dy,
e2, pixel;
for(;;) {
pixel = context.getImageData(x, y, 1, 1).data[3];
if(pixel === 255) {
context.fillStyle = 'rgb(255, 0, 0)';
} else {
context.fillStyle = 'rgb(0, 255, 0)';
}
context.fillRect(x, y, 1, 1);
if(x === end.x && y === end.y) {
break;
} else {
e2 = 2 * err;
if(e2 >= dy) {
err += dy;
x += sx;
}
if(e2 <= dx) {
err += dx;
y += sy;
}
}
}
},
isPathClear: function(start, end) {
var x = start.x,
y = start.y,
dx = Math.abs(end.x - start.x),
sx = start.x<end.x ? 1 : -1,
dy = -1 * Math.abs(end.y - start.y),
sy = start.y<end.y ? 1 : -1,
err = dx+dy,
e2, pixel;
for(;;) {
pixel = context.getImageData(x, y, 1, 1).data[3];
if(pixel === 255) {
return false;
}
if(x === end.x && y === end.y) {
return true;
} else {
e2 = 2 * err;
if(e2 >= dy) {
err += dy;
x += sx;
}
if(e2 <= dx) {
err += dx;
y += sy;
}
}
}
}
}, graph;
engine.drawObstructions();
graph = (function() {
var x, y, rows = [], cols, js = '[';
for(y = 0; y < 200; y += graphSettings.size) {
cols = [];
for(x = 0; x < 320; x += graphSettings.size) {
cols.push(context.getImageData(x+graphSettings.mid, y+graphSettings.mid, 1, 1).data[3] === 255 ? 0 : 1);
}
js += '['+cols+'],\n';
rows.push(cols);
}
js = js.substring(0, js.length - 2);
js += ']';
document.getElementById('Graph').value=js;
return new Graph(rows, { diagonal: true });
})();
return engine;
}, start, end, engine = EngineBuilder(field, 10);
field.addEventListener('click', function(event) {
var position = engine.getPosition(event);
if(!start) {
start = position;
} else {
end = position;
}
if(start && end) {
engine.drawObstructions();
engine.drawPath(start, end);
start = end;
}
}, false);#field {
border: thin black solid;
width: 98%;
background: #FFFFC7;
}
#Graph {
width: 98%;
height: 300px;
overflow-y: scroll;
}<script src="http://jason.sperske.com/adventure/astar.js"></script>
<code>Click on any 2 points on white spaces and a path will be drawn</code>
<canvas id='field' height
='200' width='320'></canvas>
<textarea id='Graph' wrap='off'></textarea>Покопавшись в отличном ответе Michail Michailidis, я добавил следующий код в свой simplifyPath() функция) ( демо):
simplifyPath: function(start, complexPath, end) {
var previous = complexPath[1],
simplePath = [start, {x:(previous.y*graphSettings.size)+graphSettings.mid, y:(previous.x*graphSettings.size)+graphSettings.mid}],
i,
finalPath = [simplePath[0]],
classification,
previousClassification;
for(i = 1; i < (complexPath.length - 1); i++) {
classification = (complexPath[i].x-previous.x).toString()+':'+(complexPath[i].y-previous.y).toString();
if(classification !== previousClassification) {
simplePath.push({x:(complexPath[i].y*graphSettings.size)+graphSettings.mid, y:(complexPath[i].x*graphSettings.size)+graphSettings.mid});
} else {
simplePath[simplePath.length-1]={x:(complexPath[i].y*graphSettings.size)+graphSettings.mid, y:(complexPath[i].x*graphSettings.size)+graphSettings.mid};
}
previous = complexPath[i];
previousClassification = classification;
}
simplePath.push(end);
previous = simplePath[0];
for(i = 2; i < simplePath.length; i++) {
if(!this.isPathClear(previous, simplePath[i])) {
finalPath.push(simplePath[i-1]);
previous = simplePath[i-1];
}
}
finalPath.push(end);
return finalPath;
}
По существу, после того, как он уменьшает избыточные шаги в одном и том же направлении, он пытается сгладить путь, заглядывая в будущее, чтобы увидеть, может ли он устранить какие-либо шаги.
6 ответов
Очень очень интересная проблема! Спасибо за этот вопрос! Итак... сначала несколько замечаний:
Отсутствие диагонального перемещения решает эту проблему, но так как вы заинтересованы в диагональном движении, мне пришлось искать больше.
Я взглянул на алгоритмы упрощения пути, такие как: Ramer Douglas Peuker ( http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm) и реализация: https://gist.github.com/rhyolight/2846020. Я добавил реализацию к вашему коду без успеха. Этот алгоритм не учитывает препятствия, поэтому его было сложно адаптировать.
Интересно, каково было бы поведение (для диагональных перемещений), если бы вы использовали Dijkstra вместо A* или если вы использовали алгоритм "все кратчайшие пути между парой узлов", а затем сортировали их, увеличивая изменение направления.
Прочитав немного об A* здесь http://buildnewgames.com/astar/ я подумал, что используемая вами реализация A-star - это проблема или эвристика. Я перепробовал все эвристики на звездочке вашего кода, включая евклидову, которую я сам кодировал, и попробовал также всю эвристику в коде http://buildnewgames.com/astar К сожалению, все диагонали, допускающие эвристику, имели ту же проблему, что и вы описываю.
Я начал работать с их кодом, потому что это один-к-одному, а у вас проблемы с рисованием. Ваш simpifyPath, который я пытался удалить, также вызывал дополнительные проблемы. Вы должны иметь в виду, что, поскольку вы делаете переназначение, это может быть проблемой, основанной на том, что
- На квадратной сетке, которая допускает 4 направления движения, используйте расстояние Манхэттена (L1).
- На квадратной сетке, которая допускает 8 направлений движения, используйте диагональное расстояние (L∞).
- На квадратной сетке, которая допускает любое направление движения, вы можете или не хотите евклидово расстояние (L2). Если A* находит пути на сетке, но вы разрешаете движение не на сетке, вы можете рассмотреть другие представления карты. (из http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html)
Какой у меня алгоритм псевдокода:
var path = A-star();
for each node in path {
check all following nodes till some lookahead limit
if you find two nodes in the same row but not column or in the same column but not row {
var nodesToBeStraightened = push all nodes to be "straightened"
break the loop;
}
skip loop index to the next node after zig-zag
}
if nodesToBeStraightened length is at least 3 AND
nodesToBeStraightened nodes don't form a line AND
the resulting Straight line after simplification doesn't hit an obstruction
var straightenedPath = straighten by getting the first and last elements of nodesToBeStraightened and using their coordinates accordingly
return straightenedPath;
Вот визуальное объяснение того, что сравнивается в алгоритме:
Визуальное объяснение: 
Как этот код будет использоваться с вашим (я сделал большинство изменений - я старался изо всех сил, но есть так много проблем, как то, как вы рисуете, из-за округления сетки и т. Д.), Вы должны использовать сетку и сохранить точный масштаб путей - см. также предположения ниже):
var img,
field = document.getElementById('field'),
EngineBuilder = function(field, size) {
var context = field.getContext("2d"),
graphSettings = { size: size, mid: Math.ceil(size/2)},
engine = {
//[...] missing code
removeZigZag: function(currentPath,lookahead){
//for each of the squares on the path - see lookahead more squares and check if it is in the path
for (var i=0; i<currentPath.length; i++){
var toBeStraightened = [];
for (var j=i; j<lookahead+i+1 && j<currentPath.length; j++){
var startIndexToStraighten = i;
var endIndexToStraighten = i+1;
//check if the one from lookahead has the same x xor the same y with one later node in the path
//and they are not on the same line
if(
(currentPath[i].x == currentPath[j].x && currentPath[i].y != currentPath[j].y) ||
(currentPath[i].x == currentPath[j].y && currentPath[i].x != currentPath[j].x)
) {
endIndexToStraighten = j;
//now that we found something between i and j push it to be straightened
for (var k = startIndexToStraighten; k<=endIndexToStraighten; k++){
toBeStraightened.push(currentPath[k]);
}
//skip the loop forward
i = endIndexToStraighten-1;
break;
}
}
if (toBeStraightened.length>=3
&& !this.formsALine(toBeStraightened)
&& !this.lineWillGoThroughObstructions(currentPath[startIndexToStraighten], currentPath[endIndexToStraighten],this.graph?????)
){
//straightening:
this.straightenLine(currentPath, startIndexToStraighten, endIndexToStraighten);
}
}
return currentPath;
},
straightenLine: function(currentPath,fromIndex,toIndex){
for (var l=fromIndex; l<=toIndex; l++){
if (currentPath[fromIndex].x == currentPath[toIndex].x){
currentPath[l].x = currentPath[fromIndex].x;
}
else if (currentPath[fromIndex].y == currentPath[toIndex].y){
currentPath[l].y = currentPath[fromIndex].y;
}
}
},
lineWillGoThroughObstructions: function(point1, point2, graph){
var minX = Math.min(point1.x,point2.x);
var maxX = Math.max(point1.x,point2.x);
var minY = Math.min(point1.y,point2.y);
var maxY = Math.max(point1.y,point2.y);
//same row
if (point1.y == point2.y){
for (var i=minX; i<=maxX && i<graph.length; i++){
if (graph[i][point1.y] == 1){ //obstacle
return true;
}
}
}
//same column
if (point1.x == point2.x){
for (var i=minY; i<=maxY && i<graph[0].length; i++){
if (graph[point1.x][i] == 1){ //obstacle
return true;
}
}
}
return false;
},
formsALine: function(pointsArray){
//only horizontal or vertical
if (!pointsArray || (pointsArray && pointsArray.length<1)){
return false;
}
var firstY = pointsArray[0].y;
var lastY = pointsArray[pointsArray.length-1].y;
var firstX = pointsArray[0].x;
var lastX = pointsArray[pointsArray.length-1].x;
//vertical line
if (firstY == lastY){
for (var i=0; i<pointsArray.length; i++){
if (pointsArray[i].y!=firstY){
return false;
}
}
return true;
}
//horizontal line
else if (firstX == lastX){
for (var i=0; i<pointsArray.length; i++){
if (pointsArray[i].x!=firstX){
return false;
}
}
return true;
}
return false;
}
//[...] missing code
}
//[...] missing code
}
Допущения и несовместимости приведенного выше кода:
- препятствием является 1, а не 0
- оригинальный код, который я имею в демоверсии, использует массив вместо {x: number, y:number}
- в случае использования другой реализации типа "звезда" точка 1 находится в столбце 1 и строке 2.
- преобразован в ваш {x: номер, y: номер}, но не проверил все части:
- Я не мог получить доступ к графическому объекту, чтобы получить препятствия - понимаете?????
- Вы должны позвонить моему removeZigZag с предвкушением, например, 7 (несколько шагов) в том месте, где вы делали упрощение пути
- по общему признанию их код не так хорош по сравнению с реализацией a-star из Стэнфорда, но для наших целей он должен быть неуместным
- возможно, в коде есть ошибки, о которых я не знаю, и которые можно улучшить. Также я делал свои проверки только в этой конкретной конфигурации мира
- Я полагаю, что код имеет сложность O(N x lookahead)~O(N), где N - количество шагов во входном A* кратчайшем пути.
Вот код в моем репозитории github (вы можете запустить демо) https://github.com/zifnab87/AstarWithDiagonalsFixedZigZag
- на основе этой реализации A* Javascript, загруженной отсюда: http://buildnewgames.com/astar/
Их код clickHandling и код мировой границы нарушен, так как при нажатии правой стороны карты расчет пути иногда не работает. У меня не было времени, чтобы найти их ошибку. В результате мой код имеет ту же проблему. Вероятно, это потому, что карта, которую я поставил из вашего вопроса, не является квадратной - но в любом случае мой алгоритм не должен изменяться. Вы увидите, что это странное поведение происходит, если не выполняется мой код удаления ZigZag. (Изменить: это было на самом деле, потому что карта не была квадратной - я обновил карту, чтобы быть квадратной на данный момент)
Не стесняйтесь поиграть, раскомментировав эту строку, чтобы увидеть до-после:
result = removeZigZag(result,7);
Я приложил 3 ранее после набора изображений, чтобы результаты можно было визуализировать: (Имейте в виду, чтобы соответствовать старт и цель, если вы попробуете их - направление имеет значение;))
Случай 1: До 
Случай 1: После 
Случай 2: До 
Случай 2: После 
Случай 3: До 
Случай 3: После 
Случай 4: До 
Случай 4: После 
Ресурсы:
- Мой код (демонстрация исправления диагонального движения Z * Zag): https://github.com/zifnab87/AstarWithDiagonalsFixedZigZag
- Оригинальный Javascript * Реализация моей демонстрации может быть найдена выше (первый коммит) или здесь: - http://buildnewgames.com/astar/
- * Объяснение: http://buildnewgames.com/astar/
- * Объяснение из Стэнфорда: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
- Реализация JavaScript A*, используемая в вопросе OP (Github):
- Алгоритм Рамера Дугласа Пейкера (Википедия): http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm
- Реализация алгоритма Дугласа Пейкера на Javascript: https://gist.github.com/rhyolight/2846020
- Алгоритм A* (Википедия): http://en.wikipedia.org/wiki/A*_search_algorithm
Вы можете использовать модифицированный алгоритм A* для учета изменений в направлении. Хотя упрощение результата стандартного алгоритма A* может дать хорошие результаты, оно может быть неоптимальным. Этот модифицированный алгоритм A* вернет путь минимальной длины с наименьшим числом витков.
В модифицированном алгоритме A* каждая позиция соответствует восьми различным узлам, каждый со своим собственным заголовком. Например, должность (1, 1) соответствует восьми узлам
(1,1)-up, (1,1)-down, (1,1)-right, (1,1)-left,
(1,1)-up-left, (1,1)-up-right, (1,1)-down-left, а также (1,1)-down-right
Эвристическое расстояние от узла до цели - это эвристическое расстояние от соответствующей точки до цели. В этом случае вы, вероятно, захотите использовать следующую функцию:
H(point) = max(abs(goal.xcor-point.xcor), abs(goal.ycor-point.ycor))
Узлы, которые соответствуют определенной позиции, связаны с узлами соседних позиций с соответствующим заголовком. Например, узлы, соответствующие позиции (1,1) все подключены к следующим восьми узлам
(1,2)-up, (1,0)-down, (2,1)-right, (0,1)-left,
(0,2)-up-left, (2,2)-up-right, (0,0)-down-left, а также (2,0)-down-right
Расстояние между любыми двумя соединенными узлами зависит от их курса. Если они имеют одинаковую голову, то расстояние 1иначе мы сделали поворот, поэтому расстояние 1+epsilon, epsilon представляет произвольно малое значение / число.
Мы знаем, что нужно иметь особый случай как для начала, так и для цели. Начало и цель представлены в виде одного узла. В начале у нас нет заголовка, поэтому расстояние между начальным узлом и любым подключенным узлом 1,
Теперь мы можем запустить стандартный алгоритм A* на модифицированном графике. Мы можем отобразить возвращенный путь к пути в исходной сетке, игнорируя заголовки. Общая длина возвращаемого пути будет иметь вид n+m*epsilon, n общая длина соответствующего пути в исходной сетке, и m это количество оборотов. Поскольку A* возвращает путь минимальной длины, путь в исходной сетке - это путь минимальной длины, который делает наименьшее количество поворотов.
Я придумал что-то вроде исправления, которое является простым дополнением к вашему исходному коду, но оно не работает во всех ситуациях (см. Изображение ниже), потому что мы ограничены тем, что возвращает нам *. Вы можете увидеть мой jsfiddle здесь
Я добавил следующий код в ваш simplifyPath функционировать прямо перед возвращением. Что он делает, так это убирает дополнительные шаги, проверяя, есть ли четкий путь между несмежными шагами (сначала смотря на большие промежутки). Это может быть оптимизировано, но вы должны понять суть того, что у меня есть.
do{
shortened = false;
loop:
for(i = 0; i < simplePath.length; i++) {
for(j = (simplePath.length - 1); j > (i + 1); j--) {
if(this.isPathClear(simplePath[i],simplePath[j])) {
simplePath.splice((i + 1),(j - i - 1));
shortened = true;
break loop;
}
}
}
} while(shortened == true);
Ниже вы можете видеть, что это удаляет путь, который идет слева (как в вопросе), но также и то, что удаляются не все лишние повороты. Это решение использует только точки, предоставленные из A*, а не точки между ними на пути - например, потому что у 2-й точки нет прямой прямой линии до 4-й или 5-й точек, она не может оптимизировать точку 3 из. Это происходит намного меньше, чем в исходном коде, но иногда дает странные результаты.
В редакции для узлов, имеющих ссылки на свои родительские узлы. Также сохраните внутри переменной направление, из которого пришел этот узел. В моем случае было только две возможности горизонтально или вертикально. Поэтому я создал две общедоступные статические константы для каждой возможности. И вспомогательная функция с именем «toDirection», которая принимает два узла и возвращает, какое направление следует выбрать, чтобы перейти от одного к другому:
public class Node {
final static int HORIZONTALLY = 0;
final static int VERTICALLY = 1;
int col, row;
boolean isTravelable;
int fromDirection;
double hCost;
double gCost;
double fCost;
Node parent;
public Node(int col, int row, boolean isTravelable) {
this.col = col;
this.row = row;
this.isTravelable = isTravelable;
}
public static int toDirection(Node from, Node to) {
return (from.col != to.col) ? Node.HORIZONTALLY : Node.VERTICALLY;
}
}
Затем вы можете изменить функцию расчета веса, чтобы учитывать повороты. Теперь вы можете дать небольшое наказание за повороты, такие как:
public double calcGCost(Node current, Node neighbor) {
if(current.fromDirection == Node.toDirection(current, neighbor)) {
return 1;
} else{
return 1.2;
}
}
Полный код: https://github.com/tezsezen/ASarAlgorithm
На риск возможного понижающего голосования, я сделаю все возможное, чтобы предложить ответ. Если вы не используете сторонний плагин, я бы предложил создать простой объект pop / push-стека, однако, поскольку вы используете чей-то плагин, может быть лучше попробовать работать параллельно с ним, а не против него.
При этом я мог бы просто сделать что-то простое, например, отследить свои выходные результаты и попытаться логически определить правильный ответ. Я хотел бы сделать простой объектный тип объекта литерала для хранения в массиве всех возможных путей? Таким образом, весь срок службы объекта - только хранение информации о местоположении. Затем вы могли бы позже проанализировать этот массив объектов в поисках наименьшего количества оборотов.
Кроме того, поскольку этот сторонний плагин будет выполнять большую часть работы за кулисами и, по-видимому, не очень доступен для извлечения, вам может потребоваться указать критерии самостоятельно. Например, если он добавляет больше оборотов, чем вы хотите, то есть внутри двери, выглядящей квадратной, то, возможно, отправив ему координаты начала и конца, не достаточно. Возможно, лучше останавливаться на каждом повороте и отправлять новые координаты, чтобы увидеть, возможна ли прямая линия. Если бы вы сделали это, то каждый ход имел бы изменение, чтобы посмотреть и увидеть, есть ли препятствие, останавливающее движение по прямой линии.
Я чувствую, что этот ответ слишком прост, поэтому он должен быть неправильным, но я все же попробую...
//Entity Type Object Literal
var pathsFound = function() {
//Path Stats
straightLine: false,
turnCount: 0,
xPos: -1, //Probably should not be instantiated -1 but for now it's fine
yPos: -1,
//Getters
isStraightLine: function() { return this.straightLine; },
getTurnCount: function() { return this.turnCount; },
getXPos: function() { return this.xPos; },
getYPos: function() { return this.yPos; },
//Setters
setStraightLine: function() { this.straightLine = true; },
setCrookedLine: function() { this.straightLine = false; },
setXPos: function(val) { this.xPos = val; },
setYPos: function(val) { this.yPos = val; },
//Class Functionality
incrementTurnCounter: function() { this.turnCount++; },
updateFullPosition: function(xVal, yVal) {
this.xPos = xVal;
this.yPos = yVal.
},
}
Таким образом, вы могли бы сообщать все данные на каждом этапе пути, и прежде чем рисовать на экране, вы могли бы перебрать массив этих литералов объекта и найти правильный путь по наименьшему turnCount,
var img,
field = document.getElementById('field'),
EngineBuilder = function(field, size) {
var context = field.getContext("2d"),
graphSettings = { size: size, mid: Math.ceil(size/2)},
engine = {
getPosition: function(event) {
var bounds = field.getBoundingClientRect(),
x = Math.floor(((event.clientX - bounds.left)/field.clientWidth)*field.width),
y = Math.floor(((event.clientY - bounds.top)/field.clientHeight)*field.height),
node = graph.grid[Math.floor(y/graphSettings.size)][Math.floor(x/graphSettings.size)];
return {
x: x,
y: y,
node: node
}
},
drawObstructions: function() {
context.clearRect (0, 0, 320, 200);
if(img) {
context.drawImage(img, 0, 0);
} else {
context.fillStyle = 'rgb(0, 0, 0)';
context.fillRect(200, 100, 50, 50);
context.fillRect(0, 100, 50, 50);
context.fillRect(100, 100, 50, 50);
context.fillRect(0, 50, 150, 50);
}
},
simplifyPath: function(start, complexPath, end) {
var previous = complexPath[1], simplePath = [start, {x:(previous.y*graphSettings.size)+graphSettings.mid, y:(previous.x*graphSettings.size)+graphSettings.mid}], i, classification, previousClassification;
for(i = 1; i < (complexPath.length - 1); i++) {
classification = (complexPath[i].x-previous.x).toString()+':'+(complexPath[i].y-previous.y).toString();
if(classification !== previousClassification) {
simplePath.push({x:(complexPath[i].y*graphSettings.size)+graphSettings.mid, y:(complexPath[i].x*graphSettings.size)+graphSettings.mid});
} else {
simplePath[simplePath.length-1]={x:(complexPath[i].y*graphSettings.size)+graphSettings.mid, y:(complexPath[i].x*graphSettings.size)+graphSettings.mid};
}
previous = complexPath[i];
previousClassification = classification;
}
simplePath.push(end);
return simplePath;
},
drawPath: function(start, end) {
var path, step, next;
if(this.isPathClear(start, end)) {
this.drawLine(start, end);
} else {
path = this.simplifyPath(start, astar.search(graph, start.node, end.node), end);
if(path.length > 1) {
step = path[0];
for(next = 1; next < path.length; next++) {
this.drawLine(step, path[next]);
step = path[next];
}
}
}
},
drawLine: function(start, end) {
var x = start.x,
y = start.y,
dx = Math.abs(end.x - start.x),
sx = start.x<end.x ? 1 : -1,
dy = -1 * Math.abs(end.y - start.y),
sy = start.y<end.y ? 1 : -1,
err = dx+dy,
e2, pixel;
for(;;) {
pixel = context.getImageData(x, y, 1, 1).data[3];
if(pixel === 255) {
context.fillStyle = 'rgb(255, 0, 0)';
} else {
context.fillStyle = 'rgb(0, 255, 0)';
}
context.fillRect(x, y, 1, 1);
if(x === end.x && y === end.y) {
break;
} else {
e2 = 2 * err;
if(e2 >= dy) {
err += dy;
x += sx;
}
if(e2 <= dx) {
err += dx;
y += sy;
}
}
}
},
isPathClear: function(start, end) {
var x = start.x,
y = start.y,
dx = Math.abs(end.x - start.x),
sx = start.x<end.x ? 1 : -1,
dy = -1 * Math.abs(end.y - start.y),
sy = start.y<end.y ? 1 : -1,
err = dx+dy,
e2, pixel;
for(;;) {
pixel = context.getImageData(x, y, 1, 1).data[3];
if(pixel === 255) {
return false;
}
if(x === end.x && y === end.y) {
return true;
} else {
e2 = 2 * err;
if(e2 >= dy) {
err += dy;
x += sx;
}
if(e2 <= dx) {
err += dx;
y += sy;
}
}
}
}
}, graph;
engine.drawObstructions();
graph = (function() {
var x, y, rows = [], cols, js = '[';
for(y = 0; y < 200; y += graphSettings.size) {
cols = [];
for(x = 0; x < 320; x += graphSettings.size) {
cols.push(context.getImageData(x+graphSettings.mid, y+graphSettings.mid, 1, 1).data[3] === 255 ? 0 : 1);
}
js += '['+cols+'],\n';
rows.push(cols);
}
js = js.substring(0, js.length - 2);
js += ']';
document.getElementById('Graph').value=js;
return new Graph(rows, { diagonal: true });
})();
return engine;
}, start, end, engine = EngineBuilder(field, 10);
field.addEventListener('click', function(event) {
var position = engine.getPosition(event);
if(!start) {
start = position;
} else {
end = position;
}
if(start && end) {
engine.drawObstructions();
engine.drawPath(start, end);
start = end;
}
}, false);#field {
border: thin black solid;
width: 98%;
background: #FFFFC7;
}
#Graph {
width: 98%;
height: 300px;
overflow-y: scroll;
}<script src="http://jason.sperske.com/adventure/astar.js"></script>
<code>Click on any 2 points on white spaces and a path will be drawn</code>
<canvas id='field' height
='200' width='320'></canvas>
<textarea id='Graph' wrap='off'></textarea>