MakeWebGames

A* search algorithm PHP

Recommended Posts

Hello All,

iam currently selling my A* search algorithm implementation.

Features:

OOP

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;
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{
}
}
```

here is a demo to test around

if anone is interested just PM me

Best regards BlackScorp

Edited by BlackScorp
removed singleton
Share on other sites

Doesn't look like object oriented code to me.

Share on other sites

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

Share on other sites

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

Share on other sites

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.

Share on other sites

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 by Aventro
Share on other sites

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

Share on other sites

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

Share on other sites

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

Share on other sites

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

Share on other sites

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

Share on other sites

well removed singleton

Join the conversation

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

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.