My pathfinding algorithm

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

screenshot!

Yay spaceships!

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

*edit*

Decent as in I liked it and... oh nevermind.

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 make mazes using a recursive algo.

Quote:

---

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.

./edit

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;
                                }
                        }
        }

---

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)