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
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210 | //class.pathfinder.php
<?php
//EXAMPLE OF USE
/*
$map=getMap(); //You can use whatever function you need for this purpose
require('class.pathfinder.php');
$path=new PathFinder(); //Create new pathfinder object
$path->setOrigin($valuestring['ox'],$valuestring['oy']); //Set the start location
$path->setDestination($valuestring['dx'],$valuestring['dy']); //Set the destination
$path->setMap($map); //Assign the map to use for calculations
$result=$path->returnPath(); //Returns an array of all the walked steps
*/
//Example of the map-array generating function
//This pathfinder example assumes that a square map is used. To use rectangular map you need to tweak the pathfinder a bit
//Here we assign one tile in four as 'unpassable'
//Map is an associative array which has a key of the tile's coordinates as the base. Only required array value is 'weight' but
//you can store additional information in the array for, say, public purposes, such as tile graphic data.
/*
function getMap(){
$map=array();
for($x=1;$x<=20;$x++){
for($y=1;$y<=20;$y++){
$rand=rand(1,4);
if($rand==1){
$map[$x.'x'.$y]=array('weight'=>'10.0');
} else {
$map[$x.'x'.$y]=array('weight'=>'1.0');
}
}
}
return $map;
}
*/
class PathFinder{
//stores the map data array
private $map=array();
//stores origin and destination locations
private $origX=0;
private $origY=0;
private $destX=0;
private $destY=0;
//this is used to store the returned path
private $path=array();
//this stores locations already looked at, this is temporary and is cleared if pathfinding gets stuck
private $walked=array();
//internal storage of squares count and map width
private $mapSquares=0;
private $mapWidth=0;
//flag used to determine if path has been found
private $found=0;
//this is a failsafe if the calculation takes too long. It is limited to 100 solves by default
//Should failsafe be unsuccessful then only partial path will be returned
private $failSafe=0;
public $failSafeLimit=100;
//function to set the map, it needs to be an array
public function setMap($map){
$this->map=$map;
$this->mapSquares=count($this->map);
$this->mapWidth=sqrt($this->mapSquares);
}
//set origin location
public function setOrigin($origX,$origY){
$this->origX=$origX;
$this->origY=$origY;
}
//set destination location
public function setDestination($destX,$destY){
$this->destX=$destX;
$this->destY=$destY;
}
//calculates and returns path
public function returnPath(){
if($this->origX!=0 && $this->origY!=0 && $this->destX!=0 && $this->destY!=0 && !empty($this->map)){
//this function runs recursively within itself until path is found or failSafe is reached
$this->findPath($this->origX,$this->origY);
return $this->path;
} else {
echo 'Insufficient pathfinder data, please define origin and destination points and a map';
die();
}
}
//main function for path calculation
private function findPath($curX,$curY){
//failsafe check here
$this->failSafe++;
if($this->failSafe>=$this->failSafeLimit){
$this->found=1;
}
if($this->found!=1){
//resetting the default values for this current square
$lowestEstimatedCost=0;
$shortestX=0;
$shortestY=0;
//looping through all the nearby squares
for($x=-1;$x<=1;$x++){
if($this->found==0){
for($y=-1;$y<=1;$y++){
if($this->found==0){
$checkX=$x+$curX;
$checkY=$y+$curY;
//making sure the checked square is within map boundries
if($checkX>=1 && $checkY>=1 && $checkX<=$this->mapWidth && $checkY<=$this->mapWidth){
if($checkX==$curX && $checkY==$curY){
//this is the current square we are on, so ignore for now
} else if($checkX==$this->destX && $checkY==$this->destY){
//we have found the destination!
$this->found=1;
$this->path[]=$this->destX.'x'.$this->destY;
} else {
//if this square has not been 'walked' yet, then consider it as one of the next step
if(!in_array($checkX.'x'.$checkY,$this->walked)){
$weight=$this->map[$checkX.'x'.$checkY]['weight'];
$weight=(($x==-1 && $y==-1) || ($x==-1 && $y==1) || ($x==1 && $y==-1) || ($x==1 && $y==1))?$weight*1.4:$weight;
$estimatedCost=$this->estimatedCost($checkX,$checkY,$weight);
//this makes sure the lowest cost square is used for next step
if($estimatedCost<$lowestEstimatedCost || $lowestEstimatedCost==0){
$lowestEstimatedCost=$estimatedCost;
$shortestX=$checkX;
$shortestY=$checkY;
}
}
}
}
}
}
}
}
}
if($this->found!=1){
if($shortestX==0 || $shortestY==0){
//if the shortest locations are 0 then calculation must have gotten stuck and we clear the walked path
//and try to find a new path from where we got stuck, essentially a re-solve
$this->walked=array();
$this->walked[]=$curX.'x'.$curY;
$this->findPath($curX,$curY,$this->destX,$this->destY);
} else {
//we store the next step into walked array (so it is not checked again during this path)
$this->walked[]=$shortestX.'x'.$shortestY;
//storing the location into path array
$this->path[]=$shortestX.'x'.$shortestY;
$this->findPath($shortestX,$shortestY,$this->destX,$this->destY);
}
}
}
//this is used to calculate estimated distance between two points
private function estimatedCost($curX,$curY,$weight){
$dx=$this->destX-$curX;
$dy=$this->destY-$curY;
$value=sqrt(($dx*$dx)+($dy*$dy));
return $value*$weight;
}
}
?>
//example.php
<?php
//Example of the map-array generating function
//This pathfinder example assumes that a square map is used. To use rectangular map you need to tweak the pathfinder a bit
//Here we assign one tile in four with a heavier weight and it is less favored for finding the path
//Map is an associative array which has a key of the tile's coordinates as the base. Only required array value is 'weight' but
//you can store additional information in the array for, say, public purposes, such as tile graphic data.
function getMap(){
$map=array();
for($x=1;$x<=20;$x++){
for($y=1;$y<=20;$y++){
$rand=rand(1,4);
if($rand==1){
$map[$x.'x'.$y]=array('weight'=>'3.0');
} else {
$map[$x.'x'.$y]=array('weight'=>'1.0');
}
}
}
return $map;
}
//Currently getMap is dynamic and changes with each try, but you can send a pre-generated maps here just as easily
//as long as the weight is set for each map tile element and the array key is in XxY format
$map=getMap();
require('class.pathfinder.php');
$path=new PathFinder(); //Create new pathfinder object
$path->setOrigin(1,1); //Set the start location
$path->setDestination(20,20); //Set the destination
$path->setMap($map); //Assign the map to use for calculations
$result=$path->returnPath(); //Returns an array of all the walked steps
echo '<pre>';
print_r($result);
echo '</pre>';
?>
|
Comments
You need to be logged in to comment on snippets.