A* Algorithm

[Liquidedust]

Well since I am going to need to pass some stuff through a pathfinder in something I code currently I started to look around and see if there were any pre-built A* algorithm libraries for PHP out there and pretty much came up with silch (A* is an evil term to search for just so you know ).

 

So really just wondering if someone knows of a pre-made library that implements A* or that I will be stuck in making my own library for it? This since it feels kind silly to recreate the wheel if it has already been made.

http://en.wikipedia.org/wiki/A*_algorithm

 

Thanks in advance

 

(realized this might be in the wrong section, but just move as you seem fit in that case - this is math after all)

[Mark Baker]

I can offer you Djikstra's graph search algorithm implemented in PHP, but not A* I'm afraid.

[Liquidedust]

I can offer you Djikstra's graph search algorithm implemented in PHP, but not A* I'm afraid.

 

Well never really implemented something like A* or Djikstra's myself so would be good to how someone else went about implementing it to get the basics framework down, and even Djikstra is a great start for what I am doing (though Djikstra can act pretty stupid at times which is why I was primarily interested in A*).

 

So most certainly interested in seeing how you implemented Djikstra's if that you'd be willing to show me

[Liquidedust]

Odd cannot seem to edit my posts in this thread, what I meant with Djikstra acting stupid is not due to the path it takes (since its almost optimal if the path exists) meant more that it does cycles that aren't really needed.

[Mark Baker]

Djikstra BFS example attached, using the London Underground map

 

Note that it's not OO code, just a simple function, but would be easy enough to convert to OO

 

[attachment deleted by admin]

[Liquidedust]

Djikstra BFS example attached, using the London Underground map

 

Note that it's not OO code, just a simple function, but would be easy enough to convert to OO

 

Quite diffrent from what I need to apply this to myself but yeah nice with a practical application of code, oh and remind me to never go from Liverpool to Heathrow via the tube.

 

Also thanks

[Liquidedust]

Its pretty simple so far, but this is how far I have gotten so far:

 

Any input and suggestions appreciated 

 

function reconstruct_path( $came_from , $current_node , $failsafe ) {

if( $failsafe < 1000 ){

	if( isset( $came_from[ $current_node ] ) ) {

		$new_failsafe = $failsafe+1;
		$p = reconstruct_path( $came_from , $came_from[ $current_node] , $new_failsafe  );
		return $p." =>\r\n".$current_node;

	} else {

		return null;

	}

} else {

	return null; // killed pathfinding, infinite loop or more then 1000 iterations

}

}

function h_distance( $current , $target ) {

$this_current = explode("," , $current);
$this_target = explode("," , $target);

$H_score = 10 * ( abs($this_current[0]-$this_target[0]) + abs($this_current[1]-$this_target[1]) );

return $H_score;

}

function min_F_score( $openset , $f_score) {

foreach( $openset as $value) {

	if( isset( $lowest_f ) ) {

		if( $f_score[$value] < $lowest_f ) {

			$lowest_f = $f_score[$value];
			$lowest_key = $value;

		}

	} else {

		$lowest_f = $f_score[$value];
		$lowest_key = $value;

	}

}

return $lowest_key;

}

function neighbor_nodes($pos) {

$pos = explode( "," , $pos );

$neighbors = array();

if( $pos[0] != 1 ) {
	$neighbors[] = ($pos[0]-1).",".$pos[1];
}

if( $pos[0] != 10 ) {
	$neighbors[] = ($pos[0]+1).",".$pos[1];
}

if( $pos[1] != 1 ) {
	$neighbors[] = $pos[0].",".($pos[1]-1);
}

if( $pos[1] != 10 ) {
	$neighbors[] = $pos[0].",".($pos[1]+1);
}

return $neighbors;

}

///////////////////////////////////////////////////////////////////////////////
////   $start_coords and $goal_coords are in 'x,y' format                  ////
////   $grid_g_scores is an array with all possible co-ordinates and how   ////
////   hard each grid is to traverse                                       ////
////   $infinity is the variable that defines if a certain value           ////
////   in $grid_g_scores is impossible to pass                             ////
///////////////////////////////////////////////////////////////////////////////

function A_star( $start_coords , $goal_coords , $grid_g_scores , $infinity ) {
     
// The set of nodes already evaluated.
$closedset = array();
     
// The set of tentative nodes that still need to be evaluated
$openset = array($start_coords => $start_coords);
     
// Distance from start along the optimal path.
$g_score = array($start_coords => 0 );
     
// the heuristic for each grid based of the Manhattan Method
$h_score = array($start_coords=>h_distance($start_coords,$goal_coords));
     
// Estimated total distance from start to goal through y.
$f_score = array($start_coords => $h_score[$start_coords] );
     
// array used to store the optimal path
$came_from = array();

while( !empty( $openset ) ) {
         
    // Set $x to the node in openset having the lowest f_score[] value
	$x = min_F_score( $openset , $f_score );
         
	// Check if we are at the goal co-ordinates end if so return the path
	if( $x == $goal_coords ) {
             
		return $start_coords
				.reconstruct_path($came_from,$goal_coords,0);

	}
         
	unset( $openset[$x] );
	$closedset[$x] = $x;
         
	foreach( neighbor_nodes($x) as $y ) {

		// if $y isn't in closed set run the following
		if( !array_key_exists( $y , $closedset ) ) {

			$tentative_g_score = $grid_g_scores[$x] +h_distance($x,$y);
			$tentative_is_better = false;

			// if this grid is traversable continue
			if( $tentative_g_score < $infinity ) {

				// if $y isn't in $openset add it and give it a
				// h_score(based off Manhattan Method)
				if( !array_key_exists( $y , $openset ) ) {

					$openset[$y] = $y;
					$h_score[$y] = h_distance( $y , $goal_coords );
					$tentative_is_better = true;

				} elseif( $tentative_g_score < $g_score[$y] ) {

					$tentative_is_better = true;

				}

				if( $tentative_is_better == true ) {

					$came_from[$y] = $x;
					$g_score[$y] = $tentative_g_score;
					$f_score[$y] = $g_score[$y] + $h_score[$y];

				}

			}

		}

	}

}

     return "no path to target can be found!";

}

$the_map = array(

'1,10' => 4, '2,10' => 4, '3,10' => 4, '4,10' => 400, '5,10' => 4, '6,10' => 4, '7,10' => 4, '8,10' => 400, '9,10' => 4, '10,10' => 4,
'1,9' => 4,  '2,9' => 400,  '3,9' => 4,  '4,9' => 400,  '5,9' => 4,  '6,9' => 400,  '7,9' => 4,  '8,9' => 400,  '9,9' => 4,  '10,9' => 400,
'1,8' => 4,  '2,8' => 400,  '3,8' => 4,  '4,8' => 400,  '5,8' => 4,  '6,8' => 400,  '7,8' => 4,  '8,8' => 400,  '9,8' => 4,  '10,8' => 400,
'1,7' => 4,  '2,7' => 400,  '3,7' => 4,  '4,7' => 400,  '5,7' => 4,  '6,7' => 400,  '7,7' => 4,  '8,7' => 400,  '9,7' => 4,  '10,7' => 400,
'1,6' => 4,  '2,6' => 400,  '3,6' => 4,  '4,6' => 400,  '5,6' => 4,  '6,6' => 400,  '7,6' => 4,  '8,6' => 400,  '9,6' => 4,  '10,6' => 400,
'1,5' => 4,  '2,5' => 400,  '3,5' => 4,  '4,5' => 400,  '5,5' => 4,  '6,5' => 400,  '7,5' => 4,  '8,5' => 400,  '9,5' => 4,  '10,5' => 400,
'1,4' => 4,  '2,4' => 400,  '3,4' => 4,  '4,4' => 400,  '5,4' => 4,  '6,4' => 400,  '7,4' => 4,  '8,4' => 400,  '9,4' => 4,  '10,4' => 400,
'1,3' => 4,  '2,3' => 400,  '3,3' => 4,  '4,3' => 400,  '5,3' => 4,  '6,3' => 400,  '7,3' => 4,  '8,3' => 400,  '9,3' => 4,  '10,3' => 400,
'1,2' => 4,  '2,2' => 400,  '3,2' => 4,  '4,2' => 400,  '5,2' => 4,  '6,2' => 400,  '7,2' => 4,  '8,2' => 400,  '9,2' => 4,  '10,2' => 400,
'1,1' => 4,  '2,1' => 400,  '3,1' => 4,  '4,1' => 4,  '5,1' => 4,  '6,1' => 400,  '7,1' => 4,  '8,1' => 4,  '9,1' => 4,  '10,1' => 400

);

///////////////////////////////////////////////////////////////////////////////
/////////    start position , end position , map_array , infinity     /////////
/////////       (infinity = grid value impossible to traverse)        /////////
///////////////////////////////////////////////////////////////////////////////

echo "<pre>\r\n";
print_r ( A_star('1,1','10,1',$the_map,400) );
echo "</pre>\r\n";

 

[attachment deleted by admin]

[Liquidedust]

hmmm, there as some odd behaviour in the pathfinder need to locate what I did wrong (if you spot anything poke me about it)