iDevGames Forums
Preprocessed Waypoints - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Programming Fundamentals (/forum-7.html)
+--- Thread: Preprocessed Waypoints (/thread-1550.html)



Preprocessed Waypoints - NelsonMandella - Mar 25, 2009 06:01 PM

I'm working on implementing a pathfinding/navigation system for my 2d game engine.

After researching a variety of options I've decided to go with a preprocessed waypoint system.

How it works:

example:

(the () numbers represent waypoints, the numbers represent the cost to get from one to the other)

(0)-----22------(1)----10--(2)
|
7
|
(3)





data structures:

N is the number of waypoints.


NSPoint waypoint_list[N] -this is an array containing all of the waypoints.

int cost_table[N][N] - this is an array containing defining which points are connected(meaning you can walk to one from another). This array consists of ints defining the cost to get from one waypoint to another, if the cost is greater than 999 then you can not get from one node to the other.

for the above example cost_table[0][1] would 22.

int solution_table[N][N].


for the above example solution_table[0][2] would be 1 because 1 is the next waypoint that 0 must traverse in order to reach the goal of 2.

so the value of solution_table[start][end] would give me the nearest waypoints connected to start which will eventually lead me to end.

The solution table is preprocessed and stored in a file(or perhaps even calculated upon startup). An all-pair shortest path algorithm is required to fill the solution table and requires access only to the cost_table[N][N] array to do so.

I'm trying to use Floyd's algorithm(an all-pair shortest path algorithm), in my implementation but am having trouble.

Here is what my floyd's algorithm looks like using a three-dimensional solution_table[N][N][N] instead of the above two-dimensional, for simplicity's sake.

int counter;
for ( k = 0; k < n; k++)
{
counter = 0;
for ( start = 0; start < n; start++)
{
for (end = 0; end < n; end++ )
{

if (start == end)
solution_table[counter][start][end] = end;
else if (cost_table[i][j] > (cost_table[start][k] + cost_table[k][end]))
{
solution_table[counter][start][end]= k;
counter++;
}
}
}
}


This is overkill because the only element I would need in this array is solution_table[0][start][end (or maybe [1][start][end]- im not really sure).

I've been trying for over a week and I cannot find a way to properly implement Floyd's algorithm- I know I'm doing something horribly wrong but I can't figure out what. Trying to implement this algorithm is just way way above my head at the moment(even though it looked simple to me at first).

Perhaps somebody here has a better grasp of Floyd's algorithm or what I'm doing wrong in my attempted implementation of it.


Preprocessed Waypoints - NelsonMandella - Mar 26, 2009 07:06 PM

please, I'm desperateHuh


Preprocessed Waypoints - Ingemar - Mar 27, 2009 02:16 AM

NelsonMandella Wrote:please, I'm desperateHuh
Are your waypoints in a grid, or a connected network of aribtrary points? The grid is a lot easier.

As long as you don't have weird things like negative costs on some branches, you can propagate movement costs over the grid, starting at one of the endpoints until you get to the goal. You can optimize it with a heuristics function, that is A*.

How slow is your current approach? If it works, use it.

I somewhat question the use for this in a "game engine". It doesn't seem like something that is universally applicable, but rather a feature that depends on the representation. And there are different path finding methods for different kinds of game entities. The shortest path is very often not the right one.