Download code

Jump to: navigation, search

Back to A*_search_(JavaScript)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

astar.html

 1 <html>
 2 <head>
 3  <title>A*</title>
 4  <script type="text/javascript" src="astar.js"></script>
 5 </head>
 6 <body onload="doastar();">
 7  <h1>A* Demo</h1>
 8  <h2>Instructions</h2>
 9  'S' is the start position, 'T' is the target position and black positions are blocked.<br/>
10  Start and target positions are moved by clicking on them and then clicking on a new position. Any other position will be blocked or unblocked if clicked on.<br/>
11  The script is successfully tested on Mozilla Firefox.<br/>
12  <input type="checkbox" id="chb_paintopen" checked="1" onclick="chb_click();">Mark open positions</input>
13  <table id="grid" border="1"></table>
14  <p id="expl"></p>
15 </body>


hijacker
hijacker
hijacker
hijacker

astar.js

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/A*_search_(JavaScript)?oldid=19015
 14 */
 15 
 16 var sizex=16;
 17 var sizey=16;
 18 
 19 var start=null;
 20 var target=null;
 21 
 22 var grid=new Array();
 23 var opened=new Array();
 24 
 25 var expl_text=null;
 26 
 27 var paint_open=false;
 28 
 29 var start_moving=false;
 30 var target_moving=false;
 31 
 32 var nothing_color="#ffffff";
 33 var blocked_color="#000000";
 34 var start_color="#00ff00";
 35 var target_color="#0000ff";
 36 var route_color="#00ffff";
 37 
 38 var warn="";
 39 
 40 function pos(x, y) {
 41 	this.x=x; this.y=y;
 42 	this.cost=0;
 43 	this.totalcost=0;
 44 	this.blocked=false;
 45 	this.closed=false;
 46 	this.prev=null;
 47 
 48 	this.str=function() {
 49 		return this.x+","+this.y;
 50 	}
 51 	this.equal=function(p) {return this.x==p.x && this.y==p.y;}
 52 }
 53 
 54 
 55 function mkgrid()
 56 {
 57 	var table=document.getElementById("grid");
 58 	table.onmouseout=astar_mouseout;
 59 
 60 	var tbody=document.createElement("tbody");
 61 	table.appendChild(tbody);
 62 
 63 	var tr=document.createElement("tr");
 64 	tr.appendChild(document.createElement("th"));
 65 	tbody.appendChild(tr);
 66 
 67 	var x, y;
 68 	for(x=0; x<sizex; ++x) {
 69 		var th=document.createElement("th");
 70 		th.appendChild(document.createTextNode(x));
 71 		tr.appendChild(th);
 72 	}
 73 
 74 	for(y=0; y<sizey; ++y) {
 75 		grid[y]=new Array();
 76 		var tr=document.createElement("tr");
 77 		tbody.appendChild(tr);
 78 
 79 		var th=document.createElement("th");
 80 		th.appendChild(document.createTextNode(y));
 81 		tr.appendChild(th);
 82 
 83 		for(x=0; x<sizex; ++x) {
 84 			grid[y][x]=new pos(x, y);
 85 			var td=document.createElement("td");
 86 			td.appendChild(document.createTextNode(""));
 87 			td.id=x+","+y;
 88 			td.width=20;
 89 			td.onclick=astar_click;
 90 			td.onmouseover=astar_mouseover;
 91 			td.setAttribute("x", x);
 92 			td.setAttribute("y", y);
 93 			tr.appendChild(td);
 94 		}
 95 	}
 96 }
 97 
 98 function wipe()
 99 {
100 	var y, x;
101 
102 	warn="";
103 	opened=new Array();
104 
105 	for(y=0; y<sizey; ++y) {
106 		for(x=0; x<sizex; ++x) {
107 			grid[y][x].cost=0;
108 			grid[y][x].totalcost=0;
109 			grid[y][x].prev=null;
110 			grid[y][x].closed=false;
111 
112 			if(grid[y][x].blocked) setcolor(grid[y][x], blocked_color);
113 			else setcolor(grid[y][x], nothing_color);
114 		}
115 	}
116 	setcolor(start, start_color);
117 	setcolor(target, target_color);
118 }
119 
120 function settext(p, text)
121 {
122 	var td=document.getElementById(p.str());
123 	td.firstChild.data=text;
124 }
125 
126 function setcolor(p, color)
127 {
128 	var td=document.getElementById(p.str());
129 	td.setAttribute("bgColor", color);
130 }
131 
132 function setstart(p)
133 {
134 	if(start) {
135 		settext(start, "");
136 		setcolor(start, nothing_color);
137 	}
138 	start=p;
139 	settext(start, "S");
140 	setcolor(start, start_color);
141 }
142 
143 function settarget(p)
144 {
145 	if(target) {
146 		settext(target, "");
147 		setcolor(target, nothing_color);
148 	}
149 	target=p;
150 	settext(target, "T");
151 	setcolor(target, target_color);
152 }
153 
154 function setblock(p1, p2, block)
155 {
156 	for(var y=p1.y; y<=p2.y; ++y) {
157 		for(var x=p1.x; x<=p2.x; ++x) {
158 			if(block) {
159 				setcolor(grid[y][x], blocked_color);
160 				grid[y][x].blocked=true;
161 			} else {
162 				setcolor(grid[y][x], nothing_color);
163 				grid[y][x].blocked=false;
164 			}
165 		}
166 	}
167 }
168 
169 function opencell(p, cost, prev)
170 {
171 	if(p.blocked) return null;
172 
173 	if(prev && prev.prev && !prev.equal(start)) {
174 		if(p.x-prev.x != prev.x-prev.prev.x ||
175 			p.y-prev.y != prev.y-prev.prev.y) cost+=4;
176 	}
177 
178 	var totalcost=parseFloat(cost)+14*(Math.abs(p.x-target.x)+Math.abs(p.y-target.y));
179 
180 	/* If position is already considered: check for better cost */
181 	if(p.totalcost!=0) {
182 		if(totalcost<p.totalcost) {
183 			var nn;
184 			for(nn=0; nn<opened.length; ++nn) {
185 				if(p.equal(opened[nn])) {
186 					opened.splice(nn, 1);
187 					break;
188 				}
189 			}
190 		} else return null;
191 	}
192 
193 	p.cost=cost;
194 	p.prev=prev;
195 	p.totalcost=totalcost;
196 
197 	var n=0;
198 	for(n=0; n<opened.length; ++n) {
199 		if(p.totalcost<opened[n].totalcost) {
200 			opened.splice(n, 0, p);
201 			break;
202 		}
203 	}
204 	if(n>=opened.length) opened[n]=p;
205 
206 	grid[p.y][p.x]=p;
207 
208 	if(paint_open && !p.equal(start)) {
209 		var intensity=Math.floor(totalcost*4/5);
210 		
211 		if(intensity>255) intensity=255;
212 		setcolor(p, "#"+intensity.toString(16)+"ff"+intensity.toString(16));
213 	}
214 
215 	return p;
216 }
217 
218 function openadjacent(p)
219 {
220 	var cost=grid[p.y][p.x].cost+10;
221 	if(p.x>0) opencell(grid[p.y][p.x-1], cost, p);
222 	if(p.y>0) opencell(grid[p.y-1][p.x], cost, p);
223 	if(p.y<(sizey-1)) opencell(grid[p.y-(-1)][p.x], cost, p);
224 	if(p.x<(sizex-1)) opencell(grid[p.y][p.x-(-1)], cost, p);
225 }
226 
227 function astar()
228 {
229 	var best;
230 	var n=0;
231 
232 	var chb=document.getElementById("chb_paintopen");
233 	paint_open=chb.checked;
234 
235 	best=opencell(start, 0, start);
236 	while(best && !best.equal(target)) {
237 		best.closed=true;
238 		opened.shift();
239 		openadjacent(best);
240 
241 		if(opened.length>0) best=opened[0];
242 		else best=null;
243 
244 		if(++n>10000) {best=null; break;}	/* Catch non-stop loops (should never happen) */
245 	}
246 	if(!best) {
247 		warn="No route found";
248 		return;
249 	}
250 
251 	/* Find way back */
252 	while(!best.equal(start)) {
253 		setcolor(best, route_color);
254 		best=best.prev;
255 		if(!best) {
256 			alert("Something strange happend");	/* Should never happen */
257 			break;
258 		}
259 	}
260 }
261 
262 function astar_click(e)
263 {
264 	if(!e) var e=window.event;
265 
266 	var x=this.getAttribute("x");
267 	var y=this.getAttribute("y");
268 
269 	var p=grid[y][x];
270 
271 	if(start_moving && !p.equal(target)) {
272 		setstart(p); 
273 		start_moving=false;
274 		setblock(p, p, null);
275 	} else if(target_moving && !p.equal(start)) {
276 		settarget(p);
277 		target_moving=false;
278 		setblock(p, p, null);
279 	} else if(p.equal(start)) start_moving=true;
280 	else if(p.equal(target)) target_moving=true;
281 	else {
282 		if(grid[y][x].blocked) setblock(p, p, null);
283 		else setblock(p, p, 1);
284 	}
285 
286 	if(!start_moving && !target_moving) {
287 		wipe();
288 		astar();
289 	}
290 
291 	astar_explain(x, y);
292 }
293 
294 function chb_click()
295 {
296 	wipe();
297 	astar();
298 }
299 
300 function astar_explain(x, y)
301 {
302 	var expl=document.getElementById("expl");
303 	var p=grid[y][x];
304 	var heuristic=p.totalcost-p.cost;
305 
306 	if(start_moving) expl.innerHTML="Click to set new start position at "+p.str();
307 	else if(target_moving) expl.innerHTML="Click to set new target position at "+p.str();
308 	else if(p.blocked) expl.innerHTML=p.str()+
309 		"<br>Currently blocked. Click to unblock";
310 	else if(p.equal(start)) expl.innerHTML="Start position - Click to move";
311 	else if(p.equal(target)) expl.innerHTML="Target position - Click to move";
312 	else if(p.cost==0) expl.innerHTML=p.str()+"<br>Click to block this position";
313 	else expl.innerHTML=p.str()+
314 		"<br>Cost from start: "+p.cost+
315 		"<br>Heuristic estimate to target: "+heuristic+
316 		"<br>Total cost: "+p.totalcost+
317 		"<br>Click to block this position";
318 
319 	if(warn.length>0) expl.innerHTML+="<br><div style=\"color:red\">"+warn+"<div>";
320 }
321 
322 function astar_mouseover(e)
323 {
324 	if(!e) var e=window.event;
325 
326 	var x=this.getAttribute("x");
327 	var y=this.getAttribute("y");
328 
329 	astar_explain(x, y);
330 }
331 
332 function astar_mouseout()
333 {
334 	var expl=document.getElementById("expl");
335 	expl.innerHTML="";
336 }
337 
338 function doastar()
339 {
340 	mkgrid();
341 
342 	setstart(new pos(6, 2));
343 	settarget(new pos(9, 14));
344 	setblock(new pos(1, 3), new pos(10, 4), true);
345 	setblock(new pos(12, 4), new pos(15, 4), true);
346 	setblock(new pos(2, 6), new pos(14, 12), true);
347 	setblock(new pos(0, 6), new pos(0, 9), true);
348 	setblock(new pos(9, 6), new pos(10, 11), false);
349 	setblock(new pos(11, 11), new pos(14, 11), false);
350 
351 	astar();
352 }


hijacker
hijacker
hijacker
hijacker