-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathpathfinding.js
125 lines (118 loc) · 3.87 KB
/
pathfinding.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
console.log('--------------Pathfinding start------------');
const BY_A = 1;
const BY_B = 2;
const NO_ONE = 0;
const generateVisited = (maze) => {
return maze.map((row, y) =>
row.map((ele, x) => ({
opened_by: NO_ONE,
closed: ele === 1,
length: 0,
x,
y,
}))
);
};
function findShortestPathLength(maze, [xA, yA], [xB, yB]) {
let visited = generateVisited(maze);
visited[yA][xA].opened_by = BY_A;
visited[yB][xB].opened_by = BY_B;
// coordinates provided in the form [x,y] will be accessed as [y][x]
let aQueue = [visited[yA][xA]];
let bQueue = [visited[yB][xB]];
let iteration = 0;
while (aQueue.length && bQueue.length) {
iteration++;
let aNeighbours = [];
// get A neighbours
while (aQueue.length) {
let coordinate = aQueue.shift();
aNeighbours = aNeighbours.concat(
getNeighbours(visited, coordinate.x, coordinate.y)
);
}
//process B neighbours
for (let neighbour of aNeighbours) {
if (neighbour.opened_by === BY_B) return iteration + neighbour.length;
else if (neighbour.opened_by === NO_ONE) {
neighbour.length = iteration;
neighbour.opened_by = BY_A;
aQueue.push(neighbour);
}
}
let bNeighbours = [];
// get A neighbours
while (bQueue.length) {
let coordinate = bQueue.shift();
bNeighbours = bNeighbours.concat(
getNeighbours(visited, coordinate.x, coordinate.y)
);
}
//process B neighbours
for (let neighbour of bNeighbours) {
if (neighbour.opened_by === BY_A) return iteration + neighbour.length;
else if (neighbour.opened_by === NO_ONE) {
neighbour.length = iteration;
neighbour.opened_by = BY_B;
bQueue.push(neighbour);
}
}
}
return -1;
}
// the coordinates are in (x,y) format but they translate into [y][x]. think of it in that way
function getNeighbours(visited, x, y) {
const neighbours = [];
if (x - 1 >= 0 && !visited[y][x - 1].closed) {
neighbours.push(visited[y][x - 1]);
}
if (x + 1 < visited[y].length && !visited[y][x + 1].closed) {
neighbours.push(visited[y][x + 1]);
}
if (y - 1 >= 0 && !visited[y - 1][x].closed) {
neighbours.push(visited[y - 1][x]);
}
if (y + 1 < visited.length && !visited[y + 1][x].closed) {
neighbours.push(visited[y + 1][x]);
}
return neighbours;
}
const fifteenByFifteen = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 2, 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, 0, 0],
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0],
[0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0],
[0, 0, 1, 0, 1, 0, 1, 1, 2, 1, 0, 1, 0, 1, 0],
[0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0],
[0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
];
const eightByEight = [
[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 2, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 1, 2],
];
const sixBySix = [
[0, 0, 0, 0, 0, 0],
[0, 2, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0],
[0, 0, 2, 0, 0, 0],
];
console.log(findShortestPathLength(sixBySix, [1, 1], [2, 5]) == 7);
console.log(findShortestPathLength(eightByEight, [1, 6], [7, 7]) == 15);
console.log(findShortestPathLength(fifteenByFifteen, [1, 1], [8, 8]) == 78);
console.log('----------------pathfinding end------------');