Thread: Pathfinding AI? (Not the A* Algorithim)

To clarify the way I talked about above using a queue to find the shortest route, here is an example that should explain better what I meant.

Create a struct named room or spot or whatever that includes the coordinates as well as a pointer to another room. This pointer points to the room you came from. When I mean room, I just mean a particular (x,y) location.

Code:

struct room
{
    int roomNum;
    room *previous;
};

Then create a queue of room pointers. Also create an array of bools that keep track of which rooms you have tried.

Now say this is your map, you want to get from room A to room B. The X's are walls that cannot be traveled over.

Code:

A...
..X.
.X..
...B

For my description, we'll label these rooms 1-16, with rooms 1-4 on top etc and room 1 being the start and room 16 being the end. Rooms 7 and 10 are walls. Okay, first you put room 1 onto the queue with its previous pointer pointing to NULL since you didn't come from anywhere. Now you just continue in an infinite loop working with the front of the queue until either it is empty (no solution) or you reach the ending point. Heres what would happen:

Top of queue - room 1. Check all four directions. Can't go north or west, out of bounds. Add rooms 2 and 5 to end of queue, both having previous pointers pointing to room 1. Set rooms 2 and 5 to being checked in the bool array. Pop queue.

Top of queue - room 2. Check all four directions. Can't go north, out of bounds. Can't go west, room already checked. Add rooms 3 and 6 to end of queue, both having previous pointers pointing to room 2. Check bool array. Pop queue.

Top of queue - room 5. Check all four directions. Can't go west, out of bounds. Can't go north or east, rooms already checked. Add 6 to end of queue, previous pointer pointing to room 5. Check bool array. Pop queue.

Top of queue - room 3. Check all four directions. West, already checked, north out of bounds, south wall. Add 4 to end of queue, previous pointer pointing to room 3. Check bool array. Pop queue.

Top of queue - room 6. Check all four directions. North and west already checked. South and east are walls. Add nothing to queue. Pop queue.

etc etc

Top of queue - room 15. Check all four directions. Notice that east is starting point. Set room 16 previous pointer to room 15, exit the overall loop, you're finished!

Now all you have to do to print the shortest distance is use a while loop which prints the rooms from 16 to 1:

Code:

room *current=endingRoom;
while (current->previous!=NULL)
{
     cout<<current->roomNum<<" ";
     current=current->previous;
}
// prints 16 15 14 13 9 5 1

or if you need to have it print from beginning to end use a recursive function:

Code:

void backTrack(room* current)
{
    if (current->previous!=NULL)
        backTrack(current->previous);
    cout<<current->roomNum<<" ";
}

backTrack(endingRoom);  // prints 1 5 9 13 14 15 16

Of course this was an extremely simple maze but it works on even the most complex, always giving the quickest route between two points.

To repeat an earlier statement, this is *not* AI, just a search. Anyways, moving on to how to solve it, I still am not sure if what you are looking for is a shortest path solution or any path solution. Either way, here are three ways I would solve the problem.

First:
If you know ahead of time that there is no way to go in a circle in the maze, and your solution doesn't need to be the shortest path, then a very easy way to find the destination is to simply follow a wall. What do I mean by "follow a wall" ? Well, imagine that you are in the maze, you take your right hand and place it on the wall to your right, then you continue to walk in whatever direction allows you to keep your hand on the wall and eventually you'll hit the end. Another way to picture this is:

If you can move right -- turn right and move forward.
ElseIf you can move forward -- move forward.
ElseIf you can move left -- turn left and move forward
Else turn around -- move forward.
Repeat:

If you are skeptical this will not work, try it out on paper in a simple maze. The idea is that you will never walk into the same place in the same direction twice. Therefore if an exit exists, you'll get to it eventually.

Second:
If you want to just find "any path". You'll note that this method is similar to the first, but uses memory to remember how to backtrack to make sure it doesn't hit a loop.Use the same algorithm as above, however, you'll need the help of one more EXPLORE boolean and a structure to store the locations you've been to. I'd recommend a hash if you've got lots of cells and run-time matters. Otherwise, any container with a search method works given the time. Now, as you start exploring the maze, set EXPLORE true. Follow the same algorithm as above except each time after you check if you *can* move somewhere, also check that you haven't been there before. If at any point you turn around, set EXPLORE to false (as you are now backtracking). Continue the same algorithm as the above, until you enter a place you haven't been at which time you set EXPLORE back to true. I suppose this was a bit confusing, so i'll write a pseudo code for it.

START:
If you can move right AND ((not EXPLORE) OR (have not been to the place on the right))
Turn right, and move forward,
If you can move forward AND ((not EXPLORE) OR (have not been to the place in front))
Move forward, add this place to your memory.
If you can move left AND ((not EXPLORE) OR (have not been to the place on the left))
Turn left, and move forward, add this place to your memory.
Else
Set EXPLORE to false.

If have not been to this place
add this place to your memory
set EXPLORE true
LOOP:

The above is obviously not the cleaniest way to do it. As you can see there are several repetative steps taken, however without more time to explain, I think these steps illustrate the idea the best. Feel free to ask if you've got further questions on it.

Now, if you don't know for a fact that there is no way to make a loop inside then you'll have to use some sort of data structure to remember where you've been and where you've yet to go. I seriously recommend the use of a tree (graph) structure for solving the problem because that is the nature of the problem, a graph search. I don't know if you are familiar with graphs in CS terms, but they're pretty much a set of nodes connected to each other by a set of edges (paths). You can see how this means you could easily represent your maze as a graph and even build up that representation while traversing it. If you insist on using an array to hold the data in a way that looks more like a maze, you'll find yourself doing lots of extra work to get this algorithm working because an array simply doesn't lend itself easily to this type of search. Anyhoo, I won't describe this search at the moment in much detail unless someone actually needs it. The general idea is to construct the graph of the maze while traversing it. To find the shortest path through it, use a BFS (breadth first search). You were saying an A* search was too complex, but really, from the postings I've read, it looks like you are close to implementing a DFS (depth first search), which is very similar to a BFS and A* is simply a very very very small tweak on BFS that results in (sometimes) much better search time.

Hope this helps a little at least...

~SK