我一直在开发一个早期的JavaScript实现的90年代冒险游戏，并且专门绘制从英雄所处的位置到玩家点击的位置的路径。我的方法是首先确定是否可以绘制一条直线(没有障碍) , 如果不能，则使用 Brian Grinstead's出色的 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;
}
基本上，在减少相同方向上的冗余步骤之后，它会尝试通过向前查看来平滑路径，以查看是否可以消除任何步骤。
这段代码将如何与你的代码一起使用（我已经做了大部分的更改 - 我尽力了，但还有很多问题，比如绘图方式和网格舍入等 - 你必须使用网格并保持路径比例准确 - 请参见下面的假设）：
案例1:之后
案例2:之前
案例2:之后
案例3:之前
案例3:之后
案例4:之前
案例4:之后
资源: