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
|
var jaws = (function(jaws) {
/**
* A-Star pathfinding
*
* Takes starting and ending x,y co-ordinates (from a mouse-click for example),
* which are then translated onto the TileMap grid.
*
* Does not allow for Diagonal movements
*
* Uses a very simple Heuristic [see crowFlies()] for calculating node scores.
*
* Very lightly optimised for speed over memory usage.
*
* Returns a list of [col, row] pairs that define a valid path. Due to the simple Heuristic
* the path is not guaranteed to be the best path.
*/
jaws.TileMap.prototype.findPath = function(start_position, end_position, inverted) {
if (typeof inverted == 'undefined') { inverted = false }
var start_col = parseInt(start_position[0] / this.cell_size[0])
var start_row = parseInt(start_position[1] / this.cell_size[1])
var end_col = parseInt(end_position[0] / this.cell_size[0])
var end_row = parseInt(end_position[1] / this.cell_size[1])
if (start_col === end_col && start_row === end_row) {
return [{x: start_position[0], y:start_position[1]}]
}
var col = start_col
var row = start_row
var step = 0
var score = 0
//travel corner-to-corner, through every square, plus one, just to make sure
var max_distance = (this.size[0]*this.size[1] * 2)+1
var open_nodes = new Array(this.size[0])
for(var i=0; i < this.size[0]; i++) {
open_nodes[i] = new Array(this.size[1])
for(var j=0; j < this.size[1]; j++) {
open_nodes[i][j] = false
}
}
open_nodes[col][row] = {parent: [], G: 0, score: max_distance}
var closed_nodes = new Array(this.size[0])
for(var i=0; i < this.size[0]; i++) {
closed_nodes[i] = new Array(this.size[1])
for(var j=0; j < this.size[1]; j++) {
closed_nodes[i][j] = false
}
}
var crowFlies = function(from_node, to_node) {
return Math.abs(to_node[0]-from_node[0]) + Math.abs(to_node[1]-from_node[1]);
}
var findInClosed = function(col, row) {
if (closed_nodes[col][row])
{
return true
}
else {return false}
}
while ( !(col === end_col && row === end_row) ) {
/**
* add the nodes above, below, to the left and right of the current node
* if it doesn't have a sprite in it, and it hasn't already been added
* to the closed list, recalculate its score from the current node and
* update it if it's already in the open list.
*/
var left_right_up_down = []
if (col > 0) { left_right_up_down.push([col-1, row]) }
if (col < this.size[0]-1) { left_right_up_down.push([col+1, row]) }
if (row > 0) {left_right_up_down.push([col, row-1])}
if (row < this.size[1]-1) { left_right_up_down.push([col, row+1]) }
for (var i=0 ; i<left_right_up_down.length ; i++) {
var c = left_right_up_down[i][0]
var r = left_right_up_down[i][1]
if ( ( (this.cell(c, r).length === 0 && !inverted) ||
(this.cell(c, r).length > 0 && inverted) ) &&
!findInClosed(c, r) )
{
score = step+1+crowFlies([c, r] , [end_col, end_row])
if (!open_nodes[c][r] || (open_nodes[c][r] && open_nodes[c][r].score > score)) {
open_nodes[c][r] = {parent: [col, row], G: step+1, score: score}
}
}
}
/**
* find the lowest scoring open node
*/
var best_node = {node: [], parent: [], score: max_distance, G: 0}
for (var i=0 ; i<this.size[0] ; i++) {
for(var j=0 ; j<this.size[1] ; j++) {
if (open_nodes[i][j] && open_nodes[i][j].score < best_node.score) {
best_node.node = [i, j]
best_node.parent = open_nodes[i][j].parent
best_node.score = open_nodes[i][j].score
best_node.G = open_nodes[i][j].G
}
}
}
if (best_node.node.length === 0) { //open_nodes is empty, no route found to end node
return []
}
//This doesn't stop the node being added again, but it doesn't seem to matter
open_nodes[best_node.node[0]][best_node.node[1]] = false
col = best_node.node[0]
row = best_node.node[1]
step = best_node.G
closed_nodes[col][row] = {parent: best_node.parent}
}
/**
* a path has been found, construct it by working backwards from the
* end node, using the closed list
*/
var path = []
var current_node = closed_nodes[col][row]
path.unshift({x: col*this.cell_size[0], y: row*this.cell_size[1]})
while(! (col === start_col && row === start_row) ) {
col = current_node.parent[0]
row = current_node.parent[1]
path.unshift({x: col*this.cell_size[0], y: row*this.cell_size[1]})
current_node = closed_nodes[col][row]
}
return path
}
jaws.TileMap.prototype.lineOfSight = function(start_position, end_position, inverted) {
if (typeof inverted == 'undefined') { inverted = false }
var x0 = start_position[0]
var x1 = end_position[0]
var y0 = start_position[1]
var y1 = end_position[1]
var dx = Math.abs(x1-x0)
var dy = Math.abs(y1-y0)
var sx, sy
if (x0 < x1) {sx = 1} else {sx = -1}
if (y0 < y1) {sy = 1} else {sy = -1}
var err = dx-dy
var e2
while(! (x0 === x1 && y0 === y1) )
{
if (inverted) { if (this.at(x0,y0).length === 0) {return false} }
else { if (this.at(x0,y0).length > 0) {return false} }
e2 = 2 * err
if (e2 > -dy)
{
err = err - dy
x0 = x0 + sx
}
if (e2 < dx)
{
err = err + dx
y0 = y0 + sy
}
}
return true
}
return jaws;
})(jaws || {});
|
