Я работаю над реализацией 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>
Случай 1: после
Случай 2: До
Случай 2: После
Случай 3: До
Случай 3: После
Случай 4: До
Случай 4: После
Ресурсы: