Finding Path

[Ultima]

Hi guys, Guys im new in cpp and I need help with a function.
I have imported a maze.. into a double array :: map[8][16]
This is a sample map:

***************
*A            *
*             *
**** **********
*             *
*             *
*            B*    
***************

(Not to scale, supposed to be 8 x 15)

I need a function to find a path from A to B (not using vector or algoritihm).

Can any1 give me a clue on how to start? Currently, I have the position of A and B. Thanks in advance =)

[mahlerfive]

One way to approach this is to use recursion. Essentially the function will take the current position and then call recursively on the positions up, right, down, and left of the current position. Your base cases are if you hit a wall or find the target. You will need to store or print some info along the way assuming you have to output the correct path or the whole path taken (including dead ends).

[helios]

It'd be easier if the maze was a set of corridors with intersections, rather than a set of rooms. Then you would use some of the well known maze-solving algorithms, such as Treamux's algorithm (http://en.wikipedia.org/wiki/Maze#Tremaux.27s_algorithm ).
If you really want to have the maze as a matrix, you should add more data, such as a value to represent a door:
WWWWWWWWWWWWWWW
WA W
W W
WWWWDWWWWWWWWWW
W W
W W
W BW
WWWWWWWWWWWWWWW
Now it's very easy to detect a single room, and from there you can build a graph and reduce the problem to my original suggestion.

[Ultima]

I used http://micromouse.cannock.ac.uk/maze/fastfloodsolver.htm
as a reference to find my path =)

needed a really short code for it, but thanks guys ^^ i appreciate your help

[seymore15074]

Just follow the wall on the right until you find the endpoint.

[matrebatre]

I wrote a script for this. This is what I did:

- Make a copy of the maze using type 'unsigned char' (works faster than double). The walls and starting point should be 1, the end point 2 and everything else 0.
- Create a list of coordinates, with one entry: the starting point.
- Create a new (empty) list.
- while(true) {
- For every entry in the list, check if adjacent points are free (value 0). If they are, set them to 11/12/13/14 (corresponding to up/down/left/right) and add their coordinates to a new list. If you reach the end point (value 2), stop the while loop.
- If the list is empty, return 0 (no path found).
- Copy the contents of the new list to the old list, clear the new list.
- }
- Follow the path back to the starting point (11/12/13/14).
- Reverse the path.

You can also try to find a path in the opposite direction, so you don't have to reverse the path.

This method will always find the shortest path.