Thread: My pathfinding algorithm

  1. #1

    Join Date
    May 2005
    Posts
    1,042

    My pathfinding algorithm (download!)

    I wrote a pathfinding algorithm which reduces the number of calculations required realtime by precompiling some data using connectivity matrices. The speedup comes from the fact that you do not need to know the entire path in order to make the next move. I started it on a whim and never thought it would work at all, much less be fast and use little memory. Subsequently I'd like to share it, have people tested it and all of that fun touchy programming garbage.


    I wrote a paper detailing how it works and stuff so that if you don't care you don't have to see it in this post (it is .rtf though). You can get the link to that here:

    Paper

    The actual demo and the pertinent code can be found here:

    Linky

    controls:

    wasd = increase velocity
    g = hit brakes
    click mouse1 to select the start/end node

    mouse2 renders view from actors point of view


    mouse looks around and stuff



    tell me what you think and any issues you have run into
    Last edited by BobMcGee123; 09-13-2005 at 11:57 AM.
    I'm not immature, I'm refined in the opposite direction.

  2. #2

    Join Date
    May 2005
    Posts
    1,042
    screenshot!
    I'm not immature, I'm refined in the opposite direction.

  3. #3
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    Yay spaceships!

    The algorithm is really decent dude, and the Paper was entertaining.

    *edit*

    Decent as in I liked it and... oh nevermind.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  4. #4

    Join Date
    May 2005
    Posts
    1,042
    Well, any comments are welcome. Please point out any criticisms...perhaps I should have made it so that it does a better job of actually making a maze? Maybe the mazes should be larger? I was thinking of making it so that you make a texture with repeating tiles so you can essentially draw your own maze then have the program load it in.

    I don't know whether or not I'll end up using this in a computer game, I can use everything I wrote but I'd have to package stuff better to make it more reusable.
    I'm not immature, I'm refined in the opposite direction.

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I make mazes using a recursive algo.

    1. Pick a starting point.
    2. Push current cell on stack.
    3. Pick one of four neighbor cells.
    4. If cell is empty, move to cell, increment cell count and goto 2, else goto 5
    5. Pop cell from stack.
    6. goto 3

    7. Repeat above till cell count reaches total number of cells.
    This will generate a 100x100 maze in about 1 second.

  6. #6

    Join Date
    May 2005
    Posts
    1,042
    ./edit
    I'm not immature, I'm refined in the opposite direction.

  7. #7

    Join Date
    May 2005
    Posts
    1,042
    I viewed your response in this thread Bubba, Thantos informed me it was very on topic and very constructive. I've just tried implementing something similar to what you've suggested. It works a bit better than what I had previously coded, but I keep getting mazes in which it is not very dispersed. It 'clumps' together in certain areas. Here's my current working implementation. I am right now trying to add a bias such that the maze generator is biased towards heading away from the original starting location (top right).

    Tell me what you think

    EDIT: well, doesn't matter now I'm off to programming other things more important than this.

    Code:
    /*
    	-While the number of cells required for the demo has not been reached
    	
    	1 Choose a neighbor of the current cell (the current cell is the last one successfully added to the maze)
    	2 If this neighor is a valid cell (doesn't fall outside of the tilemap) and hasn't already been added, add this cell
    		set this cell as the current cell
    	 else 
    		make sure the generator isn't blocked, if it is randomly choose a better current cell
    
    
    	other:
    	rand()%4	returns numbers between 0 and 3
    	0	=	North
    	1	=	South
    	2	=	East
    	3	=	West
    */
    
    	for(i = 0; i < NUM_TILES; i++)
    	{
    		gTileData[i].SetState(INACCESSIBLE);
    	}
    
    	int	LastDirection(0);
    	int	LastDirectionIterations(0);
    
    	int	CurrentCellIndex	=	0;	
    	int	CurrentCellRow(0),CurrentCellCol(0);
    
    	gTileData[0].DisableState(INACCESSIBLE);
    	
    	int	CellsAdded	=	1;
    	int	CellsLeft	=	NUM_ACCESSIBLE_TILES	-	1;
    	
    	unsigned	int	Random		=	0;
    
    	int	temp_row(0),temp_col(0),temp_index(0);
    
    	srand(GetTickCount());
    
    	while(CellsAdded <	NUM_ACCESSIBLE_TILES)
    	{
    		//The direction is very biased for going south and east, and against going west and north
    		Random	=	rand()%16;	
    
    		/*	
    			Find which cardinal direction we are going to so we can get the row/col and then the index and then see if we can 
    				even use the god damn thing
    		*/
    	
    		switch(Random)	
    		{
    			/*
    				North
    			*/
    			case	0:
    			{
    				temp_row	=	CurrentCellRow	-	1;
    				temp_col	=	CurrentCellCol;
    				break;
    			}
    			
    			/*
    				South
    			*/
    			case	1:
    			{
    				temp_row	=	CurrentCellRow	+	1;
    				temp_col	=	CurrentCellCol;
    				break;
    			}
    
    			/*
    				East
    			*/
    			case	2:
    			{
    				temp_row	=	CurrentCellRow;
    				temp_col	=	CurrentCellCol	+	1;
    				break;
    			}
    			/*
    				West	
    			*/
    			case	3:
    			{
    				temp_row	=	CurrentCellRow;
    				temp_col	=	CurrentCellCol	-	1;
    				break;
    			}
    		}
    
    			/*
    				Get the index for the current cell we are trying
    			*/
    			
    			temp_index	=	IndexFromRowCol(temp_row,temp_col);
    
    			if(temp_index	!=	-1	&&	gTileData[temp_index].IsStateTrue(INACCESSIBLE) && LastDirectionIterations	<	5)
    			{
    					gTileData[temp_index].DisableState(INACCESSIBLE);	
    					CurrentCellRow	=	temp_row;	CurrentCellCol	=	temp_col;	CurrentCellIndex	=	temp_index;
    					++CellsAdded;
    					--CellsLeft;
    					if(Random	==	LastDirection)
    						++LastDirectionIterations;
    					else
    					{
    						LastDirection = Random;
    						LastDirectionIterations	=	0;
    					}
    			}
    			
    			/*
    				Check to see if you are stuck, if you are stuck randomly choose a new starting point
    				You are stuck when you are surrounded by tiles that are either already accessible or have 
    					invalid locations (outside bounds of tilemap)
    				You don't want to do this check all of the time so it's probably better to only do it
    					when you've been stuck trying to move from the currentindex for at least 16 iterations or so
    			*/
    			else
    			{
    				//check to see if we are stuck, if we are randomly choose a new starting cell to start from
    				if(IsPathGeneratorBlocked(CurrentCellIndex,CurrentCellRow,CurrentCellCol))
    				{
    					CurrentCellIndex	=	PathGeneratorNewCellStart();
    					RowColFromIndex(CurrentCellIndex,&CurrentCellRow,&CurrentCellCol);
    					LastDirection	=	-1;
    					LastDirectionIterations	=	0;
    				}
    			}
    	}
    Last edited by BobMcGee123; 09-23-2005 at 08:29 AM.
    I'm not immature, I'm refined in the opposite direction.

  8. #8

    Join Date
    May 2005
    Posts
    1,042
    Besides, I posted an intermediate version of my code subsequently parts of it don't even make sense(rand()%16, then I switch for options 0-3...not what I meant to post in the first place)
    I'm not immature, I'm refined in the opposite direction.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. All-angle pathfinding algorithm?
    By TriKri in forum Game Programming
    Replies: 6
    Last Post: 06-20-2007, 07:26 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM