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[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.

anyone(please I'm desperate)?

Hum, with waypoint, the simplest I know of is A*
Have you tried it?

If you already have all your waypoints, and the cost to go to each of them. You are all setup for a fast A* search :)

The reason I tried to avoid a* is because it looks too hard for me to implement. I'm a really horrible programmer when it comes to algorithms of any mild type of complexity. I looked at both floyd's and dijkstra's and thought floyd's looked easier. There is no speed consideration at all because I'm not searching in real time- I don't care how inefficient it is as long as it's simple.

I tried implementing Dijkstra's today but that didn't go well either. Might anybody have some old code from either Dijkstra's or Floyd's algorithm implemented in such a way so that it creates a list of path nodes(not just the distance) for every pair of nodes(though I really only need the node after the start node)?

Here is the pseudo-code I found in a book for what I'm trying to do.


POINTS waypoints[n];
int cost_table[n];
int solution_table[n][n];



void create_solution_table(void)
{
for (each start node)
{
for (each end node)
{
if (start == end)
solution_table[start][end] = end;
else
{
list = dijkstra(start, end);
first_node = find_first_node(list);
solution_table[start][end] = firts_node;
}
}

@Daivuk: Floyd-Warshall has the same algorithmic complexity as running Dijkstra or A* on every pair of points, so you might as well use whichever method is easier -- which is probably Floyd-Warshall.

@ari556655: There's a nice description of the algorithm here and C source code here. The Wikipedia article is also ok, but it sometimes says "shortest path" when it should say "cost of shortest path" or "length of shortest path."

Also, a suggestion: When you post code here, put it between [code] and [\code] tags.

Ok, now I'm looking at your code...

1. Why are you doing this?

if (start == end)   solution_table[counter][start][end] = end;

This says that the cost to go from a node to itself is equal to its id number... Why would that be?

Quote: 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).

Actually, you need "solution_table[n-1][start][end]" in the end, for all possible values of 'start' and 'end.' In other words, you can throw out "solution_table[k][start][end]" for all k less than n-1 and all values of 'start' and 'end.'

Quote: Original post by Emergent
1. Why are you doing this?

if (start == end)   solution_table[counter][start][end] = end;

This says that the cost to go from a node to itself is equal to its id number... Why would that be?

POINT waypoint_list[n];

cost_table[n][n] (the same as edge_weight[n][n], the cost to go between two points, if the points are not traversable the cost is some really high number 9999 or something)

int solution_table[N][N][N] is intended to store the entire path(indexes to the waypoint list) between each pair of points. Though really I only need one node from this path(the node after the start node) so I could really use solution_table[n][n] and store the path( a list of node indexes leading from start to end) in a seperate temporary array(path_node_indexes[n or something like that]).

As far as I can tell by reading implementations of floyd's and dijkstra's such as the one you linked above, they don't include a way to keep track of every node traversed between a pair of points, they only track the distance which I don't need.

For precalculated pathfinding, you're looking for THIS

Hope it helps
Cheers
Dark Sylinc

Yes that's exactly what I'm trying to do. The article however does not explain exactly how to implement an all-pair shortest path algorithm(floyd's or dijkstra's) in such a way as to save the path of nodes(not distances) for every pair(in order to extract the second element).

Quote: Original post by ari556655
Yes that's exactly what I'm trying to do. The article however does not explain exactly how to implement an all-pair shortest path algorithm(floyd's or dijkstra's) in such a way as to save the path of nodes(not distances) for every pair(in order to extract the second element).

The thing is, that the distances implicitly encode the path. Every step, the best thing to do is to move to whichever of your neighbors has the shortest distance to the goal. Your path always just follows the steepest descent direction.