Nun, der Titel sagt mehr oder weniger alles aus. Das Problem ist das Folgende:
Der richtige Weg wird gefunden, jedoch nicht für alle Tiles. Folgendes ist der Code (abgewandelt von http://tonypa.pri.ee/tbw/tut22.html):
Das Problem liegt vermutlich an der "cost" Variable, die verwendet wird, um den günstigesten Weg zu finden (nicht unbedingt kürzesten) sofern dieser Schritt nämlich nicht vorgenommen wird und das Script einfach alle Tiles ausprobiert, funktioniert es einwandfrei.
HTML (Javascript Tag funktioniert nicht):
// path finding module
var path = (function () {
// nodes which still have to be checked, this array is being filled up
// constantly while processing all the possible tiles for the path
var toBeChecked = [];
// this object contains all the nodes which have already been processed
// the naming convention for the key is as follows: node_y_x
var checked = {};
// map reference
var tiles = [];
// array containing the ID's of the walkable nodes
var walkableTiles = [];
// checks whether it is possible to step (walkable === true) onto a certain tile
function walkable (y, x) {
len = walkableTiles.length;
while (len--) {
if (tiles[y][x] === walkableTiles[len]) {
return true;
}
}
return false;
}
// adds a node to the to-check list
function addNode (node, y, x, endY, endX) {
var name = 'node_' + y + '_' + x;
var cost = Math.abs(y - endY) + Math.abs(x - endX);
if (table[y][x] === 0) {
// check whether the node has not been visited already
if (checked['node_' + y + '_' + x] === undefined) {
// check whether there is any node with higher costs within
// the toBeCheck array, in case there is, replace it because
// there is a better option now
var len = toBeChecked.length;
while (len--) {
if (cost < toBeChecked[len].cost) {
delete toBeChecked[len];
toBeChecked[len] = {
y: y,
x: x,
parentY: node.y,
parentX: node.x,
cost: cost
}
break;
}
}
// this tile is the most expensive to get at now
if (len) {
toBeChecked.push({
y: y,
x: x,
parentY: node.y,
parentX: node.x,
cost: cost
});
}
}
}
}
// returns the path as an array
// note: parameter node is the final node, the path still is returned in
// correct order
function generatePath (node) {
var way = [];
while (node.parentY) {
way.push({
y: node.y,
x: node.x
});
node = checked['node_' + node.parentY + '_' + node.parentX];
}
return way.reverse();
}
return {
init: function (tilesRef, walkableRef) {
tiles = tilesRef;
walkableTiles = walkableRef;
},
find: function (startY, startX, endY, endX, tilesRef, walkableRef) {
// reset
toBeChecked = [];
checked = {};
// just for (type)safety reasons
startY *= 1;
startX *= 1;
endY *= 1;
endX *= 1;
var cost = Math.abs(startY - endY) + Math.abs(startX - endX);
// new object on the to-check list
toBeChecked.push({
y: startY,
x: startX,
parentY: null, // marks the end of the path
parentX: null,
cost: cost
});
// process list
while (toBeChecked.length > 0) {
var node = toBeChecked.shift();
// node has been checked
checked['node_' + node.y + '_' + node.x] = node;
if (node.y === endY && node.x === endX) {
alert('got');
return generatePath(node);
} else {
addNode(node, node.y + 1, node.x, endY, endX);
addNode(node, node.y, node.x + 1, endY, endX);
addNode(node, node.y - 1, node.x, endY, endX);
addNode(node, node.y, node.x - 1, endY, endX);
}
}
// no path
return false;
}
};
}());
HTML:
findPath
http://code.jquery.com/jquery-1.5.1.min.js">
// 1 === wall, 0 === ground
var table = [
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
];
// character
var character = {
y: 1,
x: 1,
walking: false
};
// draw map
function generateMapGrid () {
var size = 20, map = '';
for (var y = 0; y < table.length; y++) {
for (var x = 0; x < table[y].length; x++) {
var top = size * y, left = size * x;
map += '';
}
}
$('#game').append(map);
// event handlers for path finding
$('#game').children().click(function () {
var parts = $(this).attr('id').split('_'), y = parts[1], x = parts[2];
var way = path.find(character.y, character.x, y, x);
if (way) {
markPath(way);
}
});
}
// generate character and attach event handlers to it
function generateCharacter () {
var top = character.y * 20, left = character.x * 20;
var html = '';
$('#game').append(html);
}
// color path
function markPath (way) {
way.forEach(function (node) {
$('#tile_' + node.y + '_' + node.x).css('background', '#40d510');
});
}
$(function () {
path.init(table, [0]);
generateMapGrid();
generateCharacter();
});
CSS:
body {
margin: 0px;
padding: 0px;
}
.tile {
position: fixed;
height: 20px;
width: 20px;
}
.tile_0 {
background: #ffffff;
}
.tile_1 {
background: #000000;
}
.character {
background: #32a303;
}