-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
194 lines (153 loc) · 6.42 KB
/
index.html
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
<!DOCTYPE html>
<html>
<head>
<title>Jan-Eric Duden's Code-Portfolio</title>
<link href="style.css" rel="stylesheet" type="text/css">
</head>
<body>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.6.4/jquery.min.js" type="text/javascript"></script>
<h1>A* search algorithm demonstration</h1>
<div>
<p>
This code demonstrates the A* path finding algorithm.
</p>
<p>
It displays a map with random obstacles.
A click on an empty tile on the map sets the start point.
A second click on an empty tile determines the end point of the path.
</p>
<p>
The A* implementation is written in client-side JavaScript
with a heap as priority queue. The implementation is not optimized for speed.
</p>
<p>
Please view the source of the html and js files for code comments.
</p>
<div id="legend">
Legend:
<dl>
<dt class="openset">g/h</dt>
<dd>node in open set with the current path cost g (from start to node) and
estimated path cost (h) to the goal.</dd>
<dt class="closedset">g/h</dt>
<dd>node in the closed set with the current path cost g (from start to node) and
estimated path cost (h) to the goal.</dd>
<dt class="start"><span class="block"></span></dt>
<dd>Start</dd>
<dt class="goal"><span class="block"></span></dt>
<dd>Goal</dd>
<dt class="path"><span class="block"></span></dt>
<dd>Shortest Path</dd>
<dt class="obstacle"><span class="block"></span></dt>
<dd>Obstacle</dd>
</dl>
</div>
</div>
<script src="map.js" type="text/javascript"></script>
<script src="tile.js" type="text/javascript"></script>
<script src="priorityqueue.js" type="text/javascript"></script>
<script src="astar.js" type="text/javascript"></script>
<script type="text/javascript">
$(document).ready(function() {
/*
Creates an square map in div with id "map".
Map tiles will be tagged with the the class "maptile".
Map tiles that are obstacles will also get the class "obstacle".
Empty tiles get the class "empty".
Map tiles that are part of the path that a-star calculated
get in addition class "path".
The map tile that is the start title gets the class "start".
The goal tile the "goal" class.
All map are linked with their corresponding dom-element to easliy update the
dom elements if the map view changes.
*/
var map = new Map();
map.size(20,20,function(x,y) {
var tile = new Tile();
if( Math.random() < 0.2 )
tile.type(tile.obstacleType);
return tile;
});
// create dom from map
$("#map").append(function() {
var tableElement = $("<table></table>");
for(var y=0; y<map.tiles.length; y++) {
var rowOfTiles = map.tiles[y];
var rowElement = $("<tr></tr>");
tableElement.append(rowElement);
for(var x=0; x<rowOfTiles.length; x++ ) {
var tile = rowOfTiles[x];
var cellElement = $(document.createElement("td"));
cellElement.addClass("maptile").data("coord",{x:x,y:y});
//tool tip with coordinates of cell
cellElement.attr("title",x.toFixed()+","+y.toFixed());
tile.domElement = cellElement;
rowElement.append(cellElement);
cellElement.append($(document.createElement("div")));
if( tile.type() === tile.obstacleType ) {
cellElement.addClass("obstacle");
}
else {
cellElement.addClass("empty");
}
}
}
return tableElement;
});
/**
* Computes the manhattan distance between the coordinates.
*/
function manhattanDistance(fromCoord,toCoord) {
return Math.abs(fromCoord.x-toCoord.x)+Math.abs(fromCoord.y-toCoord.y);
};
var astar = null;
var mapElement = $("#map");
$(".maptile.empty").click(function(){
var clickedCoordinates = $(this).data("coord");
if( astar == null ) {
// Initialize AStar with manhattan distance and
// visualize the open and close set.
astar = new AStar(map,manhattanDistance,function () {
var astar = this;
$("#map .openset",mapElement).removeClass("openset");
$(".maptile.empty",mapElement).each(function() {
var coord = $(this).data("coord");
var node = astar.tryGetNode(coord);
if( node !== undefined && node !== null )
{
if( node.closed )
$(this).addClass("closedset");
else
$(this).addClass("openset");
$(this).empty();
$(this).html("<div>"+node.g.toFixed()+"/"+node.h.toFixed() +"</div>");
}
});
});
astar.start = clickedCoordinates;
// Reset all classes that are used to display the state of a-star
$(".start",mapElement).removeClass("start");
$(".goal",mapElement).removeClass("goal");
$(".path",mapElement).removeClass("path");
$(".openset",mapElement).removeClass("openset");
$(".closedset",mapElement).removeClass("closedset");
$(".maptile.empty",mapElement).html("<div></div>");
$(this).addClass("start");
}
else {
astar.goal = clickedCoordinates;
$(this).addClass("goal");
var pathNodes = astar.searchPath();
//add path class to all nodes betwen start and goal
for(var i = 1; i<pathNodes.length-1; i++) {
map.tiles[pathNodes[i].y][pathNodes[i].x].domElement.addClass("path");
}
astar = null;
}
});
});
</script>
<div id="map">
</div>
</body>
</html>