-
Notifications
You must be signed in to change notification settings - Fork 0
/
aStar.js
138 lines (113 loc) · 4.01 KB
/
aStar.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
126
127
128
129
130
131
132
133
134
135
136
137
138
// ----- ----- ----- ----- ----- -----
// A* algorithm
// Adapted from this article:
// http://www.policyalmanac.org/games/aStarTutorial.htm
// ----- ----- ----- ----- ----- -----
var aStar = {
search: function(graph, startNode, endNode) {
var openList = [];
var closedList = [];
openList.push(startNode);
while (openList.length > 0) {
// Grab node with lowest finalCost to process next
// Index of openList pointing to node with lowest finalCost
var lowInd = 0;
for (var i = 0; i < openList.length; i++) {
if (openList[i].finalCost < openList[lowInd].finalCost) { lowInd = i; }
}
var currentNode = openList[lowInd];
// Base case: endNode found; return directions
if (currentNode.end) {
var node = currentNode;
var directions = [];
var route = [];
while (node.parent) {
route.push(node);
node = node.parent;
}
// Nodes are pushed from last to first
route.reverse();
_(route).each(function(node) {
_(node.directions).each(function(value, key) {
if (value && value.id === node.parent.id) {
if (key === 'N') { directions.push('S'); }
if (key === 'S') { directions.push('N'); }
if (key === 'E') { directions.push('W'); }
if (key === 'W') { directions.push('E'); }
}
});
});
directions = directions.join(' ');
console.log('Directions:', directions);
}
// Default case: move currentNode from openList into closedList,
// and process its neighbors.
// Simultaneously drop currentNode from openList and push into closedList
for (node in openList) {
if (openList[node].id === currentNode.id) {
closedList.push(openList.splice(node, 1)[0]);
}
}
// using 'aStar' instead of 'this', just to be safe
var neighbors = aStar.neighbors(graph, currentNode);
for (var i = 0; i < neighbors.length; i++) {
var neighbor = neighbors[i];
// Don't want to process walls or prev. traversed nodes
if (_(closedList).contains(neighbor) || neighbor.token === '|') { continue; }
var grossCost = currentNode.grossCost + 10;
var lowestGrossCost = false;
if (!_(openList).contains(neighbor)) {
// First encounter of this node, so it must be best choice
lowestGrossCost = true;
// Calculate its heuristicCost, since it hasn't been done yet
neighbor.heuristicCost = aStar.heuristic(neighbor, endNode);
openList.push(neighbor);
} else if (grossCost < neighbor.grossCost) {
lowestGrossCost = true;
}
if (lowestGrossCost) {
// Optimal path (thus far) to this node,
// so we set the neighbor's parent to be the currentNode
neighbor.parent = currentNode;
neighbor.grossCost = grossCost;
neighbor.finalCost = neighbor.grossCost + neighbor.heuristicCost;
}
}
}
// No path found
return [];
},
heuristic: function(neighbor, endNode) {
// Manhattan method
var dist1 = Math.abs(endNode.y - neighbor.y);
var dist2 = Math.abs(endNode.x - neighbor.x);
return dist1 + dist2;
},
neighbors: function(graph, currentNode) {
var neighbors = [];
var x = currentNode.x;
var y = currentNode.y;
// Gather neighbors (above, below, left, and right of currentNode)
// North
if (y > 0 && graph[y - 1][x].token === ' ') {
neighbors.push(graph[y - 1][x]);
}
// South
if (y < graph.length - 1 && graph[y + 1][x].token !== '|' &&
currentNode.token !== '_') {
neighbors.push(graph[y + 1][x]);
}
// East
if (x < graph[y].length - 1 &&
y > 0 &&
graph[y][x + 1].token !== '|') {
neighbors.push(graph[y][x + 1]);
}
// West
if (x > 0 && y > 0 &&
graph[y][x - 1].token !== '|') {
neighbors.push(graph[y][x - 1]);
}
return neighbors;
}
};