Pathfinding AI? (Not the A* Algorithim)

Printable View

07-30-2003
harryP

Pathfinding AI? (Not the A* Algorithim)

Alright, I honestly spent 6 hours last night working on a pathfinding system for my maze game because I'd like to implement AI into it. Well, I hadn't been sure where to start so I did a search on this message board and found an interesting method someone described about determining where the destination point is and storing prioritised (is that even a word -snorts-) directions in an array. Well, I tried this and that won't work for me it seems because in mazes, you won't always have "set" priorities, they'd always be different. So then I came online and did some more searching, and to make a long story short, A* is not what I'm looking for...in all honesty, it was way too complicated for me, at least in the example I looked at. I have used linked lists and stuff before, but I don't think I can implement that into my game which uses arrays. So my question is, how can I find a path, using arrays, from one point to another? Any help would be greatly appreciated, honestly, I'm so stumped with this right now...Thanks!

Brendan
07-30-2003
quzah

What exactly are you looking for in your pathfinding? Just a single path from start to finish? Multiple paths? A path from each cell to every other cell?

If all you want is a single path, tha'ts easy enough. Simply move (usually done recursively, though it doesn't have to be) through room by room until you reach the end.

If you want paths from every room to the end, you can apply the same method.

Is this time critical or anything? Or just a simple "find the exit" with no time constraints? Is it supposed to be "AI"-like, ie: wander around randomly somewhat until you reach the end, or is it supposed to just be the shortest path?

Quzah.
07-30-2003
harryP

Basically, I'm just looking for a path from start to finish, which would be easy enough if there weren't obstacles in the way. But there are walls and things that will be blocking a direct path, so I need a way to make it find a way around these obstacles and get back onto its path. This has proven to be difficult for me, because I can't just say "if you can't continue right, move up, and if you can't do that, move down, and as a last resort, move left" like I tried doing earlier, because it usually doesn't end up that way. There were times when it couldn't go right so it went up, and then, since the exit was down and to the left, it went down again, then back up, then down, forever. So I need some way for it to like, analyze the situation and determine a good route from there.

Brendan
07-30-2003
Lynux-Penguin

first set boundaries on the maze when you move so you don't go where ur not supposed to

Code:

int move(int dir, int mypos) //where move returns the new position { ... if(mypos<2) return mypos; ... }

something like that for boundaries
and also make sure move bounds the 'piece' so that it has to follow the paths in the maze
and then for the ai, after you have move implemented....

Code:

int follow(int mypos) { int up = 1,down=2,left=3,right=4; if(mypos==finalPos) return 0; //0 for success follow(move(mypos,up)); follow(move(mypos,right)); follow(move(mypos,down)); follow(move(mypos,left)); return -1; //for failure }

or something like that on the basis of the recursion.

-LC
07-30-2003
harryP

Thanks very much, Lynux-Penguin, but the problem is persisting where it will move up, then down, then up, and just do that over and over. Any ideas on how to prevent this from occuring? :confused:

Brendan
07-30-2003
confuted

How about a variable storing the last move's direction? IE. If the last move was up, the current move can not be down UNLESS there are no other possible moves.
07-30-2003
HybridM

How are you generating the numbers the 'piece' uses to determine the direction to move?

You could set some sort of flag preventing a move back in the opposite direction, unless it's a dead end.
07-30-2003
HybridM

bah too quick blackrat :)
07-30-2003
PJYelton

The easiest way is to simply keep an array of bools which mirrors the maze. Set it all to false and everytime you enter a new spot set the corresponding bool array true. Then every time you move to a new spot, first check to see if it is already true, and if so, skip it. That way no spot will ever be checked twice. Just checking to make sure you don't go back the way you came isn't enough because that doesn't take into account going in a circle.

To find the shortest distance, the easiest way is to use a queue. You first enter the spot where you start into the queue, and then from then on you always work with the front of the queue, adding on the spot that exists in each direction (N,S,E,W) making sure to never enter in the same spot twice into the queue (either add a visited bool to the spot struct or use the array I talked about above). When you add all directions in, pop the queue and continue doing the same with whats next in line. Keep doing this until the queue is empty (meaning that is impossible to get from A to B) or you add a spot to the queue which is the end point, in which case your done. This will always find the shortest path to the end.
07-30-2003
Lynux-Penguin

[Edit]: So it does repeat...
so then do what he said, add a bool, table or something. Be creative...

-LC
07-30-2003
harryP

:) Thanks everyone, I'm working on it.

Brendan
07-30-2003
Lynux-Penguin

I got COMPLETELY stumped and just gave up, but for the sake that I'm trying to help you, here is wat I came up with before my mind Seg-Faulted and gave up...

Code:

#include <iostream.h> #define up 1 #define down 2 #define left 3 #define right 4 struct pos { int x, y; }; const char maze[][] = { "#########", "# S#", "# #######", "# #", "# #######", "# E#", "#########" }; const pos start = {7,1}; const pos end = {7,6}; bool move(int dir, pos &mypos) { switch(dir) { case left: if(maze[mypos.x+1][mypos.y]=='#') return false; mypos.x++; return true; case right: if(maze[mypos.x-1][mypos.y]=='#') return false; mypos.x--; return true; case up: if(maze[mypos.x][mypos.y+1]=='#') return false; mypos.y++; return true; case down: if(maze[mypos.x][mypos.y-1]=='#') return false; mypos.y--; return true; }; } int follow(int x, int y, int dir) { if(x==end.x && y==end.y) return 1; //found switch(dir) { case left: if(maze[x-1][y]=='#') return 0; return follow(x-1,y); case right: if(maze[x+1][y]=='#') return 0; return follow(x+1,y); case up: if(maze[x][y-1]=='#') return 0; return follow(x,y-1 int main() {

Sorry I couldn't be of more help...
I did this thing for a project for my old class but I can't remember what I did or where it is. I know I did something recursive like this though....

When you figure it out, post the code plz, I'd like to see it.

-LC
07-30-2003
harryP

Heh now you know how I feel :) . I'll post the code when I finally get it working...

Brendan
07-30-2003
the_spcst

The main idea is to go forward (whichever direction that is at the moment), and as soon as you encounter an obstacle, you make a choice, right or left. If there is now no obstacle, move forward, otherwise, turn in the same direction. This is hardly AI. Just a simple 'winding path' concept.

while(1)
if(!advance())
if(!turn(clockwise))
break;
07-30-2003
vasanth

i would use some kind of backtracking here.... Hope you have solved the problem where you have to place some n number of queens on a chess board such that none of the queens are under attack by other queens...

Here when a particular position is not possible you back track untill you get the right on...

Hmmm... looks interesting..

* Off to create a Mouse in the Maze Program*
07-31-2003
funkydude9

Hmm...I tried to implement this exact concept in my Pacman game, but it took too long so I said the heck with it and that's why the AI sucks. :D
07-31-2003
vasanth

Well.. wrote a program in 20 minutes now... please check it out
maze.zip

You can build your own maze and ask the computer to solve it.... I have included the exe..

bye
Vas
07-31-2003
harryP

:) 20 minutes...hah way to show me up. Well, it could probably use some work on it's path stuff, because it went around the whole maze like 6 times even though it could have just gone in a straight line :). but hey, no complaints here, because it's a lot farther than I'v gotten...my maze guy is determined to have his little directional crises evertime I run the maze...-sigh- but thanks for that, it really did help. This must've been what Lynux-Penguin was talking about, using recursion to solve it. Alright, I'll work on it. Thanks everyone, you've all been a big help!

Brendan
07-31-2003
PJYelton

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.
07-31-2003
harryP

Oh alright, I'll try that out, then, too. Because I've got a method that KIND OF works, but it needs more work on it. I'll try out the queue then, as well. Thanks for clarifying that :).

Brendan
07-31-2003
SereneKaos

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
07-31-2003
Lynux-Penguin

Code from vasanth's maze prog:

Code:

//in move(): move(x,y+1); move(x,y-1); move(x+1,y); move(x-1,y);

There's that recursion I was talking about. Btw: nice job, I love what you did with the graphics and everything.

-LC
08-01-2003
Helix

Oh my ... look at all the fuss that's been made about pathfinding:p (not that it's not worthit).
The algorithm the man needs is called FILL - used in pathfinding when the terrain is entirely known. It's most simple AND it generates the shortest path, so ... :cool: You're done.
It's been said, though >>> use recursion and a boolean matrix.

... ... ... ... ... ...

There are mainly two types of pathfinding > pathfinding when you know the "map" and pathfinding when you don't. From what has been posted so far it's obvious that you're after type #1 - pathfinding with the terrain entirely known. And that's toujours solved by the fill algorithm.

If by any chance you need type #2 also or maybe you're getting curious about it check out EVBF:
http://www.visualbasicforum.com/show...ght=mazetracer
http://www.visualbasicforum.com/show...ght=mazetracer
They ran a really tough contest about it up until March this year.