I have a map stored as a multidimensional array ($map[row][col]) and I'd wish to create a path from point A to point B.
Since I can have some obstacles with turns, corners, etc, etc, I'd wish to use the A* search to calculate the fastest path.
So the general function is
f(x) = g(x) + h(x)
and I have all of these values. g(x) is the cost of the move (and it's saved on the map); h(x) is the linear distance between A and B.
so I have everything I need, but I have a question: how can I organize everything?
I have no need to test for alternative paths since a square on the map can be passable or not, so when I reach the target it should be the shortest one.
how can I organize everything?
I tried with the multidimensional array, but I get lost.. :(
EDIT
I worked out some code, it's pretty a wall of text :)
//$start = array(28, 19), $end = array(14, 19) //$this->map->map is a multidimensional array, everything has a cost of 1, except for //blocking squares that cost 99 //$this->map->map == $this->radar //blocking square at 23-17, 22-18, 22-19, 22-20, 23-21, 19-17, 20-18,20-19,20-20,19-21 //they are like 2 specular mustache :P function createPath($start, $end) { $found = false; $temp = $this->cost($start, $end); foreach($temp as $t){ if($t['cost'] == $this->map->map[$end[0]][$end[1]]) $found = true; $this->costStack[$t['cost']][] = array('grid' => $t['grid'], 'dir' => $t['dir']); } ksort($this->costStack); if(!$found) { foreach($this->costStack as $k => $stack){ foreach($stack as $kn => $node){ $curNode = $node['grid']; unset($this->costStack[$k][$kn]); break; } if(!count($this->costStack[$k])) unset($this->costStack[$k]); break; } $this->createPath($curNode, $end); } } function cost($current, $target) { $return = array(); //$AIM = array('n' => array(-1, 0),'e' => array( 0, 1),'s' => array( 1, 0),'w' => array( 0, -1)); foreach($this->AIM as $direction => $offset){ $position[0] = $current[0] + $offset[0]; $position[1] = $current[1] + $offset[1]; //radar is a copy of the map if ( $this->radar[$position[0]][$position[1]] == 'V') continue; else $this->radar[$position[0]][$position[1]] = 'V'; $h = (int) $this->distance($position, $target); $g = $this->map->map[$position[0]][$position[1]]; $return[] = array('grid' => $position, 'dir' => $direction, 'cost' => $h + $g); } return $return; }
I hope you can understand everything, I tried to be clear as much as possible.
Finally, I can get to my destination, expanding only cheaper nodes, but now I have a problem.
How can I turn it into directions? I have to store a stack of orders (ie n, n, e, etc), how can I identify a path inside these values?
Back