.:: Bots United ::. - View Single Post - a much faster version of waypoint checking code.

Whistler · **Re: a much faster version of waypoint checking code. -** 08-12-2004

here's a bit of explanations on the code above...
the original POD-Bot uses Floyd-Warshall algorithm to find all paths between all nodes... but this is just not necessary:
1. we needn't find the shortest path, finding a random path is enough
2. have you noticed that POD-Bot only reports "path broken from 0 to n" or "from n to 0" ? so actually we only need to verify connections between waypoint nr. 0 and the other waypoints
I just do a traverse in the waypoint graph with Depth-first Search.
because I'm lazy, I used the std::vector. you can try using a linked list instead if you don't want to use standard library.

	(#3)
Whistler Summoner Status: Offline Posts: 1,499 Join Date: Feb 2004 Location: Mist Village	Re: a much faster version of waypoint checking code. - 08-12-2004 here's a bit of explanations on the code above... the original POD-Bot uses Floyd-Warshall algorithm to find all paths between all nodes... but this is just not necessary: 1. we needn't find the shortest path, finding a random path is enough 2. have you noticed that POD-Bot only reports "path broken from 0 to n" or "from n to 0" ? so actually we only need to verify connections between waypoint nr. 0 and the other waypoints I just do a traverse in the waypoint graph with Depth-first Search. because I'm lazy, I used the std::vector. you can try using a linked list instead if you don't want to use standard library.