A* pathfinding in 2D?

Not for 'how-to' coding questions but PHP theory instead, this forum is here for those of us who wish to learn about design aspects of programming with PHP.

Moderator: General Moderators

Post Reply
ballhead
Forum Newbie
Posts: 2
Joined: Fri Jul 14, 2006 12:57 am

A* pathfinding in 2D?

Post by ballhead »

Anyone know/has a script that does the A* pathfinding?
My needs are quite low:
Got a maze (size could be various). There are only fields You can go throught (1) and fields You can`t (0). You got to go from starting point A to ending point B. No diagonales are allowed.

Code: Select all

A
10000
11111
01010
01011
00101
11111
B
The script should give out "true" (meaning there is a way to go from A to B). No need to output the correct way (of course if it`s possible, it could be good). Perfect would be that I can change the A's and B's coordinates.

Read some basic tutorials but even they are too hard fro me. :oops:

Searched the forum and found this one:
http://www.artplastique.free.fr/nrx/PHP ... php?code=1
But don`t know how it works and how to implement it.
User avatar
Ambush Commander
DevNet Master
Posts: 3698
Joined: Mon Oct 25, 2004 9:29 pm
Location: New Jersey, US

Post by Ambush Commander »

You'd have to build a parser for whatever maze format you define (I assume what you pasted) to turn it into the format that the astar algorithm could process it.

I think it'd be an interesting project.
santosj
Forum Contributor
Posts: 157
Joined: Sat Apr 29, 2006 7:06 pm

Post by santosj »

Damn, I did this project in School in C++! Really fun and good stuff. It would be a lot better if you solved it yourself instead of depending on others.


However, I could post my C++ code for you and you could convert it to PHP. I think I'll do the PHP code for myself, but I'm not going to do any school work for anyone. If it isn't a project, then let me know and I'll see about posting some sample code.

--------------------

The trick is that without AI, you really need to parse the map into an array or vector. Using Numbers is easy because you only do comparsions.

Code: Select all

// After Parsing
$map[0] = array('A', NULL, NULL, NULL, NULL);
$map[1] = array(1, 0, 0, 0, 0);
$map[2] = array(1, 1, 1, 1, 0);
$map[3] = array(0, 1, 0, 1, 0);
$map[4] = array(0, 1, 0, 1, 1);
$map[5] = array(0, 0, 1, 0, 1);
$map[6] = array(1, 1, 1, 1, 1);
$map[7] = array('B', NULL, NULL, NULL, NULL);
Is your array, which you are transverse and I'm guessing that you won't be using any AI techniques to record the weight of the length of the 'bot' going through the maze. It is easier without AI.

All you do is start where at $map[0][0] and and go down, unless 'A' is at another position.
  1. Check where 'A' is in the 0 position array.
  2. Down is the only direction, but check to see if the 'bottom' position is '1' and return error if it is '0'
  3. Once in the maze, check all positions for '1', first checking the down position, then the right position, then the left.
  4. Repeat Step 3 until 'B' is reached.
If you would be better practice to 'record' the path you take, so that you can reverse your step if you reach a dead end.

The Maze PHP Code

It appears to me that they took either C++ code and converted it to PHP. You don't have to have such an complex code example. My code was all in a while loop.

EDIT

I realized that my C++ code had different and far easier specifications. A* path finding is a AI technique, in which you record all possible routes and choose the one that has the 'shortest' one. I think it would be a nice fun project to try to do.
ballhead
Forum Newbie
Posts: 2
Joined: Fri Jul 14, 2006 12:57 am

Post by ballhead »

Thank You for the suggestions, but they didn`t help me a lot. I do understand that I have to process all the possible ways till the B is reached, but I Don`t understand how to do that with PHP...
Read the http://www.policyalmanac.org/games/aStarTutorial.htm tutorial, but I don`t understand. That`s too difficualt to me.
Maybe someone could explain me the basics to make such a script?
santosj
Forum Contributor
Posts: 157
Joined: Sat Apr 29, 2006 7:06 pm

Post by santosj »

Yeah, it is what I said. You want to record all possible paths and place the ones that 'complete' in another array. I don't think it is all that difficult. I started to create some code, but I'm busy with another project.

I do have the string parser for creating the array if you would like to see that.
Post Reply