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?

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.

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:

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:

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.