2 views

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][\$end]) \$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 = \$current + \$offset; \$position = \$current + \$offset; //radar is a copy of the map if ( \$this->radar[\$position][\$position] == 'V') continue; else \$this->radar[\$position][\$position] = 'V'; \$h = (int) \$this->distance(\$position, \$target); \$g = \$this->map->map[\$position][\$position]; \$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?

by (108k points)

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

Here are some helpful sites you can refer to:

https://www.thoughtco.com/simple-site-search-2694116

Simple-search-using-PHP-MySQL

PHP-MySQL-search-algorithm

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