1 | "use strict";
|
2 |
|
3 | var BinaryHeap = require("./binary-heap");
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
10 |
|
11 | function AStar(isWalkable) {
|
12 | this.destX = 0;
|
13 | this.destY = 0;
|
14 | this.scaleX = 1;
|
15 | this.scaleY = 1;
|
16 | this.openNodes = {};
|
17 | this.closedNodes = {};
|
18 | this.openHeap = new BinaryHeap(function(a, b) {
|
19 | return a.f - b.f;
|
20 | });
|
21 | this.isWalkable = isWalkable;
|
22 | }
|
23 |
|
24 |
|
25 |
|
26 |
|
27 |
|
28 | AStar.prototype.heuristic = function(x, y) {
|
29 |
|
30 | var dx = Math.abs(x - this.destX) / this.scaleX;
|
31 | var dy = Math.abs(y - this.destY) / this.scaleY;
|
32 | return dx + dy;
|
33 | };
|
34 |
|
35 |
|
36 |
|
37 |
|
38 |
|
39 |
|
40 |
|
41 |
|
42 | AStar.prototype.makeNode = function(x, y, parent, g) {
|
43 | g += parent.g;
|
44 | var h = this.heuristic(x, y);
|
45 |
|
46 | return {
|
47 | x: x,
|
48 | y: y,
|
49 | parent: parent,
|
50 | f: g + h,
|
51 | g: parent.g + g,
|
52 | h: h
|
53 | };
|
54 | };
|
55 |
|
56 |
|
57 |
|
58 |
|
59 |
|
60 |
|
61 |
|
62 | AStar.prototype.updateOpenNode = function(key, parent, g) {
|
63 | var node = this.openNodes[key];
|
64 | if (!node) {
|
65 | return false;
|
66 | }
|
67 |
|
68 | var newG = parent.g + g;
|
69 |
|
70 | if (newG >= node.g) {
|
71 | return true;
|
72 | }
|
73 |
|
74 | node.parent = parent;
|
75 | node.g = newG;
|
76 | node.f = node.g + node.h;
|
77 |
|
78 | var pos = this.openHeap.indexOf(node);
|
79 | this.openHeap.bubbleUp(pos);
|
80 |
|
81 | return true;
|
82 | };
|
83 |
|
84 |
|
85 |
|
86 |
|
87 |
|
88 |
|
89 |
|
90 |
|
91 |
|
92 | AStar.prototype.insertNeighbor = function(key, x, y, parent, g) {
|
93 | var node = this.makeNode(x, y, parent, g);
|
94 | this.openNodes[key] = node;
|
95 | this.openHeap.insert(node);
|
96 | };
|
97 | AStar.prototype.tryNeighbor = function(x, y, parent, g) {
|
98 | var key = makeKey(x, y);
|
99 | if (this.closedNodes[key]) {
|
100 | return;
|
101 | }
|
102 | if (!this.isWalkable(x, y)) {
|
103 | return;
|
104 | }
|
105 | if (!this.updateOpenNode(key, parent, g)) {
|
106 | this.insertNeighbor(key, x, y, parent, g);
|
107 | }
|
108 | };
|
109 | AStar.prototype.getNeighbors = function getNeighbors(parent) {
|
110 | var diagonalCost = 1.4;
|
111 | var straightCost = 1;
|
112 | this.tryNeighbor(parent.x - this.scaleX, parent.y - this.scaleY, parent, diagonalCost);
|
113 | this.tryNeighbor(parent.x, parent.y - this.scaleY, parent, straightCost);
|
114 | this.tryNeighbor(parent.x + this.scaleX, parent.y - this.scaleY, parent, diagonalCost);
|
115 |
|
116 | this.tryNeighbor(parent.x - this.scaleX, parent.y, parent, straightCost);
|
117 | this.tryNeighbor(parent.x + this.scaleX, parent.y, parent, straightCost);
|
118 |
|
119 | this.tryNeighbor(parent.x - this.scaleX, parent.y + this.scaleY, parent, diagonalCost);
|
120 | this.tryNeighbor(parent.x, parent.y + this.scaleY, parent, straightCost);
|
121 | this.tryNeighbor(parent.x + this.scaleX, parent.y + this.scaleY, parent, diagonalCost);
|
122 | };
|
123 |
|
124 | function generatePath(node) {
|
125 | var path = [];
|
126 | while (node.parent) {
|
127 | var ix = node.x;
|
128 | var iy = node.y;
|
129 | while (ix !== node.parent.x || iy !== node.parent.y) {
|
130 | path.unshift({ x: ix, y: iy });
|
131 |
|
132 | var dx = node.parent.x - ix;
|
133 | if (dx > 0) {
|
134 | ix++;
|
135 | } else if (dx < 0) {
|
136 | ix--;
|
137 | }
|
138 | var dy = node.parent.y - iy;
|
139 | if (dy > 0) {
|
140 | iy++;
|
141 | } else if (dy < 0) {
|
142 | iy--;
|
143 | }
|
144 | }
|
145 | node = node.parent;
|
146 | }
|
147 | return path;
|
148 | }
|
149 |
|
150 | function makeKey(x, y) {
|
151 | return x + "," + y;
|
152 | }
|
153 |
|
154 |
|
155 |
|
156 |
|
157 |
|
158 |
|
159 |
|
160 |
|
161 |
|
162 | AStar.prototype.search = function aStar(srcX, srcY, destX, destY) {
|
163 | function scale(c, s) {
|
164 | var downscaled = Math.floor(c / s);
|
165 | return downscaled * s;
|
166 | }
|
167 | srcX = scale(srcX, this.scaleX);
|
168 | srcY = scale(srcY, this.scaleY);
|
169 | this.destX = scale(destX, this.scaleX);
|
170 | this.destY = scale(destY, this.scaleY);
|
171 |
|
172 | if (!this.isWalkable(this.destX, this.destY)) {
|
173 | return [];
|
174 | }
|
175 |
|
176 | var srcKey = makeKey(srcX, srcY);
|
177 | var srcNode = {
|
178 | x: srcX,
|
179 | y: srcY,
|
180 | g: 0,
|
181 | h: this.heuristic(srcX, srcY)
|
182 | };
|
183 | srcNode.f = srcNode.h;
|
184 | this.openNodes = {};
|
185 | this.openNodes[srcKey] = srcNode;
|
186 | this.openHeap = new BinaryHeap(function(a, b) {
|
187 | return a.f - b.f;
|
188 | });
|
189 | this.openHeap.insert(srcNode);
|
190 | this.closedNodes = {};
|
191 |
|
192 | var node = this.openHeap.deleteRoot();
|
193 | while (node) {
|
194 | var key = makeKey(node.x, node.y);
|
195 | delete this.openNodes[key];
|
196 | this.closedNodes[key] = node;
|
197 | if (node.x === this.destX && node.y === this.destY) {
|
198 | return generatePath(node);
|
199 | }
|
200 | this.getNeighbors(node);
|
201 | node = this.openHeap.deleteRoot();
|
202 | }
|
203 | return [];
|
204 | };
|
205 |
|
206 | module.exports = AStar;
|