Preprocessed Waypoints

Member
Posts: 194
Joined: 2009.02
Post: #1
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.
Member
Posts: 194
Joined: 2009.02
Post: #2