如何在A*图搜索结果中拉直不需要的转弯？
Jas*_*ske 14 javascript algorithm graph a-star
我一直致力于90年代早期冒险游戏的JavaScript实现,并专门绘制从英雄站立位置到玩家点击位置的路径.我的方法是首先确定是否可以绘制一条海峡线(没有障碍物),如果没有,那么使用Brian Grinstead的优秀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;
}
基本上,在它减少了相同方向的冗余步骤之后,它会尝试通过向前看来平滑路径以查看它是否可以消除任何步骤.
Mic*_*dis 15
非常非常有趣的问题!谢谢你的回答!所以......首先是一些观察:
不允许对角线移动解决了这个问题,但由于你对对角线移动感兴趣,我不得不搜索更多.
我看了一下路径简化算法,如: 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代码中的所有启发式方法.不幸的是,所有的对角线允许启发式算法都有同样的问题你正在描述.
我开始使用他们的代码,因为它是一对一的网格,而你的代码正在给我绘制问题.我试图删除的simplifyPath也导致了其他问题.你必须记住,因为你正在重新映射,这可能是一个基于此的问题
- 在允许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}
- 如果您使用其他a-star实现,则第1点位置位于第1列和第2行.
- 转换为您的{x:number,y:number}但未检查所有部分:
- 我无法访问图形对象来获取障碍 - 请参阅?????
- 你必须在你做路径简化的地方用一个前瞻,例如7(几步之遥)调用我的removeZigZag
- 不可否认,与斯坦福大学的一星级实施相比,他们的代码并不是那么好,但对于我们的目的来说,它应该是相关的
- 可能代码有我不知道的错误,可以改进.此外,我只在这个特定的世界配置中进行了检查
- 我相信代码具有复杂度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:之后
资源:
- 我的代码(A*对角线运动之字形修复演示):https://github.com/zifnab87/AstarWithDiagonalsFixedZigZag
- 原始Javascript我的演示的实现可以在上面找到(第一次提交)或在这里: - http://buildnewgames.com/astar/
- A*说明:http://buildnewgames.com/astar/
- 斯坦福大学的解释:http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
- OP问题(Github)使用的JavaScript A*实现:
- Ramer Douglas Peuker算法(维基百科):http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm
- Douglas Peuker算法的Javascript实现:https://gist.github.com/rhyolight/2846020
- A*算法(维基百科):http://en.wikipedia.org/wiki/A*_search_algorithm