# Pathfinding AI? (Not the A* Algorithim)

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 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
: 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(!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*
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last