A* search algorithm PHP

[BlackScorp]

Hello All,

iam currently selling my A* search algorithm implementation.

Features:

OOP

PSR-0 Standard Classnames with Autoloading

Including Manhattan Heursitics and Diagonal Heuristics (http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html)

Custom Blocked Types

Binaryheap

Example Implementation:

 

rquire_once 'path/to/astar.php'; 
$diagonal = true;
//Just for readability you can add any number in array
class Type{
const WALL = 1;
const FLOOR = 0;
const CHAIR = 2;
const TABLE = 3;
const CUBE = 6;
}
//y/x grid
$grid = array( 
array(Type::WALL,Type::WALL,Type::WALL,1,1,1,1,1,1), 
array(1,0,0,2,0,0,0,0,1), 
array(1,0,0,6,0,0,3,0,1), 
array(1,1,1,1,1,1,1,1,1), 
); 

$graph = new Graph($grid); //convert Array to Node Objects

$start_node = $graph->node(1,1);  //pick node x =1,y=1 as start point
$end_node = $graph->node(7,3);  //pick node x=7,y=3 as end point

if($start_node && $end_node){
   $astar = new Astar($graph); //accept only instance of Graph
   $astar->blocked(array(Type::WALL,Type::CHAIR,Type::TABLE));
   $astar->diagonal($diagonal);
   $astar->heuristic(Astar::DIAGONAL); //setup heuristics Astar::DIAGONAL || Astar::MANHATTAN
   $result = $astar->search($start_node, $end_node);
}
if(count($result) > 0){
foreach ($result as $node) { 
 echo $node->x; 
 echo $node->y; 
 echo $node->type; 
}  }else{
echo "Path not found";
}
}

 

here is a demo to test around

http://astar.blackscorp.de/

if anone is interested just PM me

Best regards BlackScorp

Edited March 26, 2013 by BlackScorp
removed singleton

[Aventro]

Doesn't look like object oriented code to me.

[BlackScorp]

you know this is just a code snippet how to use the classes, the code is fully object oriented including typhints for parameters

[Aventro]

Just because you're using classes doesn't mean you're doing object-oriented code, now I am sure you aren't.

[BlackScorp]

well a forum troll it seems. Interessting how could you sure about it?

take a look at this example http://swiftmailer.org/docs/sending.html doesnt look Object Oriented for you?

anyways iam not only using classes but in this code you dont need any design pattern just pure Classes for Typehints + calculations and a Factory Pattern to load the algorithm.

Please stop trolling

[Aventro]

I'm not trolling, I just don't see the point of stating it's object-oriented and then showing a procedural code snippet. The Script also doesn't allow - coordinates, that's usually applicable in these types of applications.

Edited March 25, 2013 by Aventro

[BlackScorp]

I'm not trolling, I just don't see the point of stating it's object-oriented and then showing a procedural code snippet.

if you would not trolling, then you would understand that this code snipped is ment to be implemented in Controller/Action of your MVC Application.

 

The Script also doesn't allow - coordinates, that's usually applicable in these types of applications.

the $grid in this case is ment to be a result set from the database or other places where you store your map.

you need to know the whole map to calculate the shortest path between 2 points

this are coordiantes.. a 2d map is nothing else like a 2d array

[Aventro]

No, I believe you misinterpret me, I meant minus coordinates.

[BlackScorp]

tbh. just because i didnt mentioned it, it doesnt mean that its not working.

i added now start rows and cols inputfields to create a map from -y/x in the demo to demonstrate it

 

$grid = array(
'-10'=>arrray('-10'=>1,'-9'=>2)
);

 

something like this is possible as grid

[Spudinski]

Is it abuse singleton day again already? Damn, I always miss the memo.

[a_bertrand]

Wasn't even aware there was such "holiday" ;) Made me laugh thanks Spudy!

[BlackScorp]

well removed singleton