Существует довольно много стандартных алгоритмов поиска путей, которые вы можете использовать для этого.
Это не относится к javascript.
Вы можете использовать один алгоритм без эвристики, и вам не следует останавливатьсяпо первому решению.
Вот как вы можете это сделать:
Хитрость в том, что вам нужно сохранить уже посещенные квадраты в списке и проверить, не посещаете ли вы один из них.на каждом шагу.
Другой трюк в том, что вам нужен определенный порядок между соседними квадратами.(Как сверху / справа / снизу / слева. Это действительно глупый алгоритм, но он подходит для этого конкретного случая.)
Также вам нужно иметь возможность идентифицировать квадраты (это возможно по их положению)
Рассмотрим рекурсивную функцию (например, назовите ее Visit):
function visit(square) {
add the square to the pathlist //pathlist is not a list of paths but a list of squares which is the current path
if (square is the goal) {
add a copy of the pathlist to the goalslist
}
else {
for (each adjacency in square.adjacencies) { // this can be calculated by adding +1 and -1 to the coordinates, and checking if its overflowing (less then one/more than five)
if (adjacency is in pathlist) {
//do nothing we have already been here
}
else {
visit(adjacency)
}
}
}
remove square from the pathlist!!
}
Запустите этот алгоритм при посещении (начало).Вы получите свой результат в goallist, который, как мы надеемся, представляет собой список путей.
Кроме того, это всего лишь половина псевдокода javascript-half, но из него легко написать javascript.
РЕДАКТИРОВАТЬ: Наслаждайтесь решением:
<script type="text/javascript">
var start = [1,1],
goal = [5,5],
pathList = [],
solutionList = [],
solutionCount = 0,
width = 5,
height = 5;
function squareInArray(square, array) {
var i = 0,
x = square[0],
y = square[1];
for (i = 0; i < array.length; i++) {
if (x == array[i][0] && y == array[i][1]) {
return true;
}
}
return false;
}
function visit(square) {
var i = 0,
x = square[0],
y = square[1],
adjacencies = [[x-1,y],[x+1,y],[x,y+1],[x,y-1]];
pathList.push(square);
if (x == goal[0] && y == goal[1]) {
var solution = pathList.slice(0); //copy trick
solutionList.push(solution);
solutionCount++;
//alert(solution);
}
else {
for (i = 0; i < adjacencies.length; i++) {
if (adjacencies[i][0] < 1 || adjacencies[i][0] > width || adjacencies[i][1] < 1 ||adjacencies[i][1] > height) {
//overflow
}
else {
if (squareInArray(adjacencies[i], pathList)) {
//do nothing we have already been here
}
else {
visit(adjacencies[i]);
}
}
}
}
pathList.pop();
}
visit(start);
alert(solutionCount);
</script>
8512 голов.Также кто-то должен проверить, правильный ли мой код.
Проверьте эту скрипку: http://jsfiddle.net/SoonDead/rd2GN/3/