path finding

Im trying to make a function that takes an array of tiles, start tile and end tile, and returns an array of tiles from the start tile to the end tile.

basically:

Code:

---


struct map
{
    int x, y;
    bool bBlocked;
};

struct tile
{
    int x, y;
};

tile *getTilePath(map *maptiles, tile tileStart, tile tileEnd)
{
    //do something to figure out the shortest
    //distance between [tileStart] and [tileEnd]
    //in [maptiles] and return this path as an array
}

---

i need to figure this out for a 2d topdown RPG-style game im working on. so far i managed to make it move from tileStart to tileEnd, but lets say there was a tile that blocked the path, it would just go right through it.

an example of using the function would be, providing it a map of 3x3 tiles, with say the center tile blocked, it would look something like this:

00E
01C
SAB

1 means blocked. 0 is nonblocked.
If i wanted to find the way from S to E, it would return {A, B, C} etc..

could anyone post any links that might help or if possible a snippet that i might be able to use, im not sure where to start.

thanks in advance

You will need a stack for this. Pick any tile in the direction of the target and push these onto the stack. Follow tiles till you hit one you are surrounded by tiles you cannot move over - hence a dead end. Back up in the stack and try all tiles again. If you cannot move, back up again, if you can move start sticking tiles into the stack again and move towards the target.

This will not only create mazes, it will also solve them.

i see how that might work for a maze game (sorry i should have mentioned its similar to a maze game, my bad)..

the closest thing i can compare it to (other than a maze) is a 2d topdown RPG kind of game, where theres trees .. etc.. and if you click on a tile, it should be able to walk the right tiles and avoid the trees.

would the stack work for this? but how would i know which way to go, in my first post i used the 3x3 map example, how would i know if i should go up instead of right?

Quote:

---

but how would i know which way to go, in my first post i used the 3x3 map example, how would i know if i should go up instead of right?

---

You would not now , that is why Bubba said you could do it with a stack, because you will keep moving untill you find a dead end or untill you have reached E. When you would find a dead end, you would go back on the stack untill theres another way to go to.

Then again in your example it would be possible to move first to the upper left and then turn right to reach E. Both are actually the same in your example as in the amount of moves you have to do to reach E. But in some cases one way might be longer then the other so then its up to you to take the shortest way, allthough when trying to find the shortest way you would have to go back and forth all the time, thus it will take longer before you would have the right track to move on.

::edit::
thats just the way i see it, im not into game programming but this seems to me the best approach.

Here is a link to an explanation of the A* pathfinding algorithm. It is similar to what bubba is suggesting but goes into a lot more detail. Enjoy.

http://www.policyalmanac.org/games/aStarTutorial.htm

The Sticky 'Post Your Games Here' has a nice pathfinding program by kashikoi3 on page three, near the end of the page.

Hope this helps :)

If you're all new to pathfinding or AI programming, i would advice you not to try and implement an A* solution, it involves some concepts that might be too much to handle as a beginner.

If you're searching a 2d maze, a brute force search like the one Bubba suggested in his first post might work for you.

If you want something faster / more reliable and have knowledge of graphs, try out Breadth first search and/or depth first search.

Breadth first search@CBoard

They do not guarantee to find the shortest path, but neither is the bruteforce alternative.

If you want guaranteed shortest paths i suggest you first look into Dijkstras shortest path algorithms and then move on to A* which could be considered a refined version of Dijkstras.

I don't see anything difficult about A*. Each tile simply has a value that indicates how much work it is to move to that tile (as in uphill or something) and the algorithm decides the path based on that and how much closer it gets to the target.

A* is just a variation on what I posted. It uses an associated 'cost' with each tile or area and takes the path that has the least 'cost' in it.

However most of these algorithms are far too slow for real-time games. I've learned through much mission creation and editing for several games that - most of the AI is stupid and the level editor and script is really what brings it to life.

In fact some levels have nodes that all NPCs and players can use to get from point to point. The node system works very well because once you find the shortest distance to the next node, you know where to go next.

A* and Dijkstra can easily work with a node system with great results. If your world is a set of tiles, you already have a node mesh to work with. They are time consuming, and may need to be given a "time slice" so that a path can be determined after several frames, but only try that out if it proves to be a big slowdown. Also, depending on your world, both of those may be a waste of time. You could very well get away with a "best first" algorithm," which simply says "I'm at this spot, which spot next to me will bring me closer to my target?"

Basicly what I'm saying is the simplest solution to give you the desired results is the best.

I don't entirely understand A*, and I'm not sure what this method is called, if it is original, or if it works all of the time. In fact, this is just something I adopted from something I learned in 10th grade about using matrices when you have systems of competition to see who would win the matches. I'm not sure how useful it is or how it can be adopted and modified to be useful for other things.


You create a square matrix whose dimension is equal to the number of tiles. Each row of the matrix represents the tile you are in, and each column represents whether or not you can get to the adjacent tile in a single move from the current tile. If you can get to the adjacent tile you put a 1, otherwise a 0, and for itself put a zero because you cannot move to the same tile in a single step (you need at least two steps to get back to the current tile) . So, lets say you have four tiles A B C D.

-From A you can get to B C D
-From B you can get to A C
-From C you can get to A B D
-From D you can get to A C

The matrix will look like this:

Code:

---

    A  B  C  D
    _______
A| 0  1  1  1
B| 1  0  1  0
C| 1  1  0  1
D| 1  0  1  0

---

Then, when you raise this matrix to a power (multiply it by itself) it gives you the number of different ways to get from one tile to any other tile in the number of moves (the power).

Raise the above matrix to the third power gives you the number of connections between tiles in three moves. Obviously, because this is such a small example, the connections involve a lot of crossing over the same tiles. But, if you have several thousand tiles where sometimes it isn't clear . Here's a program I just wrote demonstrating this idea:

Code:

---

#include <iostream>
#include <fstream>
#include <conio.h>
using namespace std;

#define        NUM_TILES        4

//This does not modify the original matrix unless you put the original matrix as the output matrix
//assumes it is a square matrix and that the input matrix is a two dimensional array
void        Multiply(int ** inputmatrix1,int ** inputmatrix2,int        size,int ** outputmatrix);

void        PrintMatrix(int        **        inputmatrix,int size)
{
        for(int row = 0; row < size; row++)
        {
                for(int col = 0; col < size; col++)
                {
                        cout        <<        inputmatrix[row][col] << "  ";
                }
                cout        <<        endl;        //done with the line
        }
}

void        WriteMatrixToFile(int        **        inputmatrix, int size,ofstream        &        fout)
{
        for(int row = 0; row < size; row++)
        {
                for(int col = 0; col < size; col++)
                {
                        fout        <<        inputmatrix[row][col]        <<        "  ";
                }
                fout        <<        "\n";
        }
}

void        MakeMatrixIdentity(int        **inputmatrix,int size)
{
        for(int x = 0; x < size; x++)
        {
                inputmatrix[x][x] = 1;       
        }
}

//if matrix element row,col is 1, then matrix element col,row is also 1
//make the initial matrix the zero matrix
int main(void)
{
        int        ** m;
        int **        m_to_2; //connections when walked two steps
        int        ** m_to_3;  //connections when walked three steps
        int        ** m_to_4;  //connections when walked four steps

        m = new int*[4];
        for(int i = 0; i < 4; i++)
        {
                m[i] = new int[4];
                m[i][0] = m[i][1] = m[i][2] = m[i][3] = 0;
        }

        m_to_2        =        new int*[4];
        for(i = 0; i < 4; i++)
        {
                m_to_2[i] = new int[4];
                m_to_2[i][0] = m_to_2[i][1] = m_to_2[i][2] = m_to_2[i][3] = 0;
        }

        m_to_3        =        new int*[4];
        for(i = 0; i < 4; i++)
        {
                m_to_3[i] = new int[4];
                m_to_3[i][0] = m_to_3[i][1] = m_to_3[i][2] = m_to_3[i][3] = 0;
        }

        m_to_4        =        new int*[4];
        for(i = 0; i < 4; i++)
        {
                m_to_4[i] = new int[4];
                m_to_4[i][0] = m_to_4[i][1] = m_to_4[i][2] = m_to_4[i][3] = 0;
        }

       
        m[0][0]=0;        m[0][1]=1; m[0][2]=1; m[0][3]=1;
        m[1][0]=1;        m[1][1]=0; m[1][2]=1; m[1][3]=0;
        m[2][0]=1;      m[2][1]=1; m[2][2]=0; m[2][3]=1;
        m[3][0]=1;        m[3][1]=0; m[3][2]=1; m[3][3]=0;
       

        std::ofstream        fout("MatrixData.txt");
        if(fout.fail())
        {
                cout        <<        "Could not create matrix data file" << "\a\n";
                getch();
        }

        Multiply(m,m,4,m_to_2);
        PrintMatrix(m_to_2,4);
        fout        <<        "M squared" << "\n";
        WriteMatrixToFile(m_to_2,4,fout);
        fout        << "\n\n";
        cout << endl << endl;
        getch();

        Multiply(m,m_to_2,4,m_to_3);
        PrintMatrix(m_to_3,4);
        fout << "M cubed" << "\n";
        WriteMatrixToFile(m_to_3,4,fout);
        fout        << "\n\n";
        cout << endl << endl;
        getch();

        Multiply(m,m_to_3,4,m_to_4);
        PrintMatrix(m_to_4,4);
        fout << "M to fourth power" << "\n";
        WriteMatrixToFile(m_to_4,4,fout);
        fout        << "\n\n";
        cout << endl << endl;
        getch();

        return        0;
}


//Note that when doing the matrix math out on paper, I usually traverse down the rows staying in the same column
//(i.e making the outer for loop 'column' instead of 'row') but the results are the same
void        Multiply(int ** inputmatrix1,int ** inputmatrix2,int size,int ** outputmatrix)
{
        for(int col = 0; col < size; col++)
        {
                for(int row = 0; row < size; row++)
                {
                        for(int x = 0; x < size; x++)
                        {
                                outputmatrix[row][col]        +=        inputmatrix1[row][x] * inputmatrix2[x][col];
                        }
                }
        }
}

---

Here is the output written to file:

Code:

---

M squared
3  1  2  1 
1  2  1  2 
2  1  3  1 
1  2  1  2 


M cubed
4  5  5  5 
5  2  5  2 
5  5  4  5 
5  2  5  2 


M to fourth power
15  9  14  9 
9  10  9  10 
14  9  15  9 
9  10  9  10

---

and I posted a drawing of what the arrangement of such tiles might look like


I'm trying to come up with a more complicated example that involves about 100 tiles and also a way to 'solve' for the path. I'm not sure how computationall expensive it will be. The work I've shown above can be pre computed, but it doesn't actually solve for the path as of yet, just shows if there is a connection and how many ways you can get there (but, once it is computed, the only real problem is a memory foot pritn which can be combated by using a smaller sized variable, or just use bitfields which will say yes or no there's a connection but will not say how many ways it can be done)

I hardly think raising a matrix to a power is going to be faster.

Try using nodes. As your objects pass a node, keep track of it in a pointer. That way if they do get off of the 'highway' you can get back on it by going back to the last node.

Based on this diagram you can see what I'm talking about. At each node you store the normalized vector to the connecting nodes - you could even store the angle and compare that with what you really need to get to where you are going. Once you have chosen a node, rotate to the new vector and head towards it.

You can see in my image how this would enable you to navigate around complex objects. It does require and editor that allows you to place navigation nodes - no nodes = no pathfinding. If on the chance that something does get in your way on the way to a node, drop down to a bump and grind algorithm to navigate around the object and get back on the vector to the next node.

If you use an acceptable or random margin of error for each vector, each unit would head towards the next node, but would not need to take the same exact path.

You can also set a radius for each node and store the square of the distance in the node structure. When your unit reaches this square of the distance from the node, you need to choose another node because you have reached the current one. I would work in terms of the square of the distance so you can avoid the nasty sqrt().

It is my opinion that this system should only be used for player controlled vehicles since that is the main area of concern. All NPCs, patrolling vehicles, etc, should have numbered waypoints set by the script controlling the level.

There should be some rudimentary follow code for units to use when they are grouped with a player - like a group of units moving to a node, etc. This can be accomplished with the bump and grind system - if they run into each other - just get back on track with the vector to the node.

Speed is hardly an issue in a 2D rpg game, so even if you were doing that in real time with big matrices it likely wouldn't matter, especially with integer based math. Also, what I posted is just conceptual and all that stuff is precomputed, and it only requires a lookup to get a value which just tells you

a) if there's a path
and (more importantly)
b) how many ways you can get from tile X to tile Y and
c) in how many steps it takes (represented by the matrix power)

I'm making matrices on my ti83 and looking at ways to build the path, I'm finding some pretty quick methods that actually seem faster but I'm trying to make sure it works all of the time and then I'm going to put it into code and make a simple 3D app with it.

edit:
The original poster was talking about tiles, sort of like a grid of small blocks, where you can only move in six directions to adjacent tiles. What you posted, while is interesting, doesn't seem as pertinent as what I posted. What you have posted seems more pertinent to something more complex, i.e with arbitrary geometry in a first person shooter style game. The OP specifically said '2d rpg' which is supposed to be relatively simple.

Quote:

---

Code:

---

//Note that when doing the matrix math out on paper, I usually traverse down the rows staying in the same column
//(i.e making the outer for loop 'column' instead of 'row') but the results are the same
void        Multiply(int ** inputmatrix1,int ** inputmatrix2,int size,int ** outputmatrix)
{
        for(int col = 0; col < size; col++)
        {
                for(int row = 0; row < size; row++)
                {
                        for(int x = 0; x < size; x++)
                        {
                                outputmatrix[row][col]        +=        inputmatrix1[row][x] * inputmatrix2[x][col];
                        }
                }
        }
}

---

---

These three for loops will kill you. The inner loop is extremely slow. Try using a linear approach to the array.

Your method might work, however it does necessitate a ton of multiplies - which is not good. And I mean a ton.

And no offense but you can use vectors in a 2D RPG as well. Just because you have tiles does not mean everything in the game is tile based. And I'm working on an RTS with someone and I think we are going to use this approach - even with a tile based map. The tiles for the map are simply for rendering purposes - nothing else.

Bubba, that is pre computed. You don't do that in real time. Please re-read my posts. To quote myself:

Quote:

---

Also, what I posted is just conceptual and all that stuff is precomputed, and it only requires a lookup to get a value which just tells you

a) if there's a path
and (more importantly)
b) how many ways you can get from tile X to tile Y and
c) in how many steps it takes (represented by the matrix power)

---

I haven't actually decided the best way to actually find the pathway, I just wanted to throw that stuff out there because it does seem useful but it is so far incomplete work (I'm still working on it).

edit:

Quote:

---

And no offense but you can use vectors in a 2D RPG as well. Just because you have tiles does not mean everything in the game is tile based. And I'm working on an RTS with someone and I think we are going to use this approach - even with a tile based map. The tiles for the map are simply for rendering purposes - nothing else.

---

Well, I see what you are saying. I mean, of course you need vector math. But, the difference in our ideas is that in yours you have what appears to be a scenario where the user can move in an arbitrary direction, where my scenario was simpler (you can only move from the middle of one tile to the middle of another), which is what I thought the OP had setup.

So you are going to store a ton of matrices on disk just for this? I'm not seeing the point.

Do yourself a favor and load up some professional editors for retail games and you will see how some of them accomplish path finding. It will give you a lot of insight into how it works.

You don't have to be rude about it. This isn't a professional game, this is an amateur 2D rpg game. I just had an idea that I thought was original and if nothign else, neat, and while incomplete I thought a group of programmers would give a better reception to some potentially new innovations but clearly I was wrong. I will restate, again, exactly what my idea accomplishes. When you pre-compile these matrices it gives you this information (I've already stated this):

Quote:

---

a) if there's a path
and (more importantly)
b) how many ways you can get from tile X to tile Y and
c) in how many steps it takes (represented by the matrix power)

---

Thats it!!!

I'm not being rude....just do some research - and games and editors are the best place to start.

But I am stating facts here - your editor might be done processing a matrix by the end of next year for the game. Would work ok for small maps, but not large ones unless you could break it down into cells - but then you have the problem of finding which cell you are in to match the matrix on disk.

I did some timings to see how long it takes to square a matrix of various sizes using my code (these are approximate).

100 = .015 seconds
500 = 1.7 seconds
1000 = 16 seconds
1500 = 55 seconds
2000 = 132 seconds

I actually expected it to be a bit slower, but I think a more reasonable criticism is the memory footprint. a five hundred to one thousand tile map is a good size for a 2d rpg level, but to store an integer of any size, even if is just a byte, takes up a lot of space in those matrices (because you would need to store the matrix for multiple steps for it to be useful), even if you just store true/false in bit fields (a byte holding true/false information for 8 tiles, etc). So, you're probably right it won't end up being the best method, but I maintain it was an interesting idea and tonight or tomorrow I might make a simple 3D top-down pacman type game using that information and post it, just for the sake of it.
I've used the empire earth 2 editor, worldcraft editor, q3radiant, to make maps for EE2, half life, counter strike, quake3 and doom3.

Is that 500 by 500 or 500 spaces total? Oh and something seems funny because the 500 one is 113 times slower than the 100 one. You have optimization turned on?

Because its an O(N^3) , or worse, algorithm.

Anyway, the concept of preprocessed lookup tables is not something to be disregarded because you do not think it looks professional bubba :)
Several modern games have used preprocessed pathfinding in some way, with great success.
A hierachial approach will solve the potentially huge matrices and building times, as you pointed out yourself.

Quote:

---

Anyway, the concept of preprocessed lookup tables is not something to be disregarded because you do not think it looks professional bubba

---

If retail games use different approaches then why wouldn't you want to use what they are since after all they are the ones making money from their efforts. I for one dont want to waste my time on classroom algos that look and sound great but offer little practicality.

I don't care if it's professional, but the method proposed is not even rational. You act as if I've never attempted to do this in my game programming efforts.

Frankly I find your lack of respect rude. And no they dont pre-process the path - the level editor is usually what the path comes from and those nodes are placed by people, not by the computer.

In all my days of gaming I've never seen any pathfinding that I thought was really good except maybe in games like Sims and Sims 2 where you have a dynamic environment and yet the characters can still find the toilet, bathtub, etc., etc. But even that falls apart when you have multiple ways to get to the area - sometimes they will go out the kitchen door, in the front door and then to the bathroom. Not exactly brilliant.

Half life had a very good pathfinding system but again I cannot say they did not used human placed nodes or hints in the level for the NPCs to follow. Command and Conquer is ludicrous pathfinding in all generations of the game, Medieval Total War is basically find the guy and hack and slash until he is dead - all the while ingoring directional orders from you the player. SWAT 4 has horrid pathfinding problems - stairways suck, Delta Force 1, 2, BHD, Extreme and Joint Operations: Typhoon Rising as well as Escalation rely solely on waypoints - if an enemy is detected they go to alert status and well...based on pre-set variables might run towards the enemy firing - accuracy determined by the level editor, etc., etc. Flight Simulator 9 actually has some very good pathfinding for the air traffic control system as well as did Flight Unlimited 2. SWAT 2 and 3 both had horrid pathfinding as did Rainbow Six, Ghost Recon, etc. Hidden and dangerous 1 had laughable path finding.

Good examples of path finding though are believe it or not Grand Theft Auto series - very good - the cops are unreal, Mafia, Need for Speed Underground 1 and 2, etc.

Quote:

---

Is that 500 by 500 or 500 spaces total? Oh and something seems funny because the 500 one is 113 times slower than the 100 one. You have optimization turned on?

---

That is 500 spaces (or tiles) total, I did that in debug mode but it is essentially just slow

Quote:

---

Because its an O(N^3) , or worse, algorithm.

---

Yeah


Bubba you very clearly know what you are talking about, but you also very clearly have an elitist attitude. WE ARE AMATEURS AND ARE TRYING NEW THINGS. I sincerely hope that your own personal projects are particularly advanced and that you can back up your arrogantness. It is true my idea is not great, but I just wish you had said something along the lines of "well bud I am a fellow game programmer and I know how hard it is to innovate new ideas, but your algorithm isn't that great because of these following reasons" instead of "do yourself a favor" and blah blah blah.

I already have the shame of putting too much time into an idea that won't work...you could at least show some respect by being nice about it.

Quote:

---

Quote:
Anyway, the concept of preprocessed lookup tables is not something to be disregarded because you do not think it looks professional bubba


If retail games use different approaches then why wouldn't you want to use what they are since after all they are the ones making money from their efforts. I for one dont want to waste my time on classroom algos that look and sound great but offer little practicality.

---

I'm not sure if you meant that retail games do not use look up tables, but if you did you are mistaken Bubba. If you mean that you probably won't find the proposed algorithm used, you're probably right. Although it is a pretty interesting algorithm in my opinion. Instead of logic, you're using pure math! I am quite interested to hear the results of your pac man demo BobMcGee.

You're very right about how node meshes are created for 3D games, however in 2D you rarely need a node mesh. Especially if it's a tile lay out (it's already a node mesh by some definitions).

Not to start a war, but the AI in GTA is a complete hack. They spawn around corners so you can't see them, and ram into you lol.

Skorman I really appreciate the encouragement. I will fiddle around with my idea a little bit more. The pre processing doesn't matter to me because the results can just be saved to a file, but I will see if I can think of any way to perhaps cut down the memory footprint and make sure that any calculations that do need to be done realtime can be done reasonably quickly. i might make my pacman thing 3D so it might take a little bit longer, and it won't be a game per se just a mechanism for showing the functionality of the path finding. If you have any ideas feel free to share :)

Quote:

---

Not to start a war, but the AI in GTA is a complete hack. They spawn around corners so you can't see them, and ram into you lol.

---

They do, but not when you are chasing another car or another car of thugs is chasing you. Those cars are AI objects and they are chasing you. The cops, however, do cheat and just re-spawn at the nearest intersection.

Mafia had very good pathfinding and I'd like to know how they did it. The cops would respawn but it was not as evident as GTA. The cops would follow you literally for mile after mile through winding streets, etc, etc. It was very good. Somehow I think they tracked the streets you took and simply followed the same route. I don't remember if they actually tried to take a crossroad to cut you off. Now that would be a very good algorithm but I wouldn't want to to code it.

And no I'm not saying they don't use look-up tables, but I am saying this is overkill for what needs to be done at this time.

And for Bob:
To say I'm an elitist when you don't even know me is really not a good thing. I've helped a lot of people here and made a lot of friends, supplied all kinds of code, screenshots, algos, etc, etc. I hardly think elitist is the word for it. My advice for when you code algos is keep it simple stupid - anything else is either going to be a mess or cause the whole thing to never get done.
So basically use the easiest thing that gets the job done well, perhaps not the best job, but it still works.

Well then I'm sorry, I was angry.

sorry for the delayed reply, the link MrWizard posted a page back was perfect for what i wanted, it even had 2 examples and its surprisingly fast... about 2 ms for a 70x70 tiled map (i only needed 1 for about 10x10 to 15x15)

once again, thanks to everyone for all the help

edit: wow.. only 4 or 5 posts in this topic are actually related to my question :)