Jump to content

A* Algorithm


Liquidedust

Recommended Posts

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 :P).

 

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)

Link to comment
Share on other sites

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 :)

Link to comment
Share on other sites

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 :)

Link to comment
Share on other sites

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]

Link to comment
Share on other sites

This thread is more than a year old. Please don't revive it unless you have something important to add.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.