Explore Courses Blog Tutorials Interview Questions
0 votes
1 view
in AI and Deep Learning by (50.2k points)

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.. :(


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?

1 Answer

0 votes
by (108k points)

There are sites which can guide you for solving your query:

Here are some helpful sites you can refer to:



If you wish to know more about PHP MYSQL then visit this PHP and MySQL Training by Intellipaat.

Welcome to Intellipaat Community. Get your technical queries answered by top developers!

28.4k questions

29.7k answers


94.1k users

Browse Categories