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

  1. #1
    Registered User harryP's Avatar
    Join Date
    Sep 2002
    Posts
    124

    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
    Draco dormiens nunquam titallandus.
    Console Graphics Library: http://www.geocities.com/steve_alberto/cgl.html

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User harryP's Avatar
    Join Date
    Sep 2002
    Posts
    124
    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
    Draco dormiens nunquam titallandus.
    Console Graphics Library: http://www.geocities.com/steve_alberto/cgl.html

  4. #4
    Comment your source code! Lynux-Penguin's Avatar
    Join Date
    Apr 2002
    Posts
    533
    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
    Asking the right question is sometimes more important than knowing the answer.
    Please read the FAQ
    C Reference Card (A MUST!)
    Pointers and Memory
    The Essentials
    CString lib

  5. #5
    Registered User harryP's Avatar
    Join Date
    Sep 2002
    Posts
    124
    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?

    Brendan
    Draco dormiens nunquam titallandus.
    Console Graphics Library: http://www.geocities.com/steve_alberto/cgl.html

  6. #6
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    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.
    Away.

  7. #7
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    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.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  8. #8
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    bah too quick blackrat
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  9. #9
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.
    Last edited by PJYelton; 07-30-2003 at 04:17 PM.

  10. #10
    Comment your source code! Lynux-Penguin's Avatar
    Join Date
    Apr 2002
    Posts
    533
    [Edit]: So it does repeat...
    so then do what he said, add a bool, table or something. Be creative...


    -LC
    Last edited by Lynux-Penguin; 07-30-2003 at 04:35 PM.
    Asking the right question is sometimes more important than knowing the answer.
    Please read the FAQ
    C Reference Card (A MUST!)
    Pointers and Memory
    The Essentials
    CString lib

  11. #11
    Registered User harryP's Avatar
    Join Date
    Sep 2002
    Posts
    124
    Thanks everyone, I'm working on it.

    Brendan
    Draco dormiens nunquam titallandus.
    Console Graphics Library: http://www.geocities.com/steve_alberto/cgl.html

  12. #12
    Comment your source code! Lynux-Penguin's Avatar
    Join Date
    Apr 2002
    Posts
    533
    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
    Asking the right question is sometimes more important than knowing the answer.
    Please read the FAQ
    C Reference Card (A MUST!)
    Pointers and Memory
    The Essentials
    CString lib

  13. #13
    Registered User harryP's Avatar
    Join Date
    Sep 2002
    Posts
    124
    Heh now you know how I feel . I'll post the code when I finally get it working...

    Brendan
    Draco dormiens nunquam titallandus.
    Console Graphics Library: http://www.geocities.com/steve_alberto/cgl.html

  14. #14
    the_spcst
    Guest
    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;

  15. #15
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    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*

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. pathfinding ai problems
    By ichijoji in forum C++ Programming
    Replies: 0
    Last Post: 08-18-2003, 06:14 PM
  2. AI (Pathfinding)
    By jdinger in forum Game Programming
    Replies: 7
    Last Post: 04-16-2003, 10:20 AM
  3. Game Design Topic #1 - AI Behavior
    By TechWins in forum Game Programming
    Replies: 13
    Last Post: 10-11-2002, 10:35 AM
  4. Technique of all board-like games?
    By Nutshell in forum Game Programming
    Replies: 28
    Last Post: 04-24-2002, 08:19 AM
  5. AI (pathfinding) tutorial
    By dirkduck in forum Game Programming
    Replies: 3
    Last Post: 02-09-2002, 12:04 PM