Algorithm to find two points furthest away from each other

Question

Im looking for an algorithm to be used in a racing game Im making. The map/level/track is randomly generated so I need to find two locations, start and goal, that makes use of the most of the map.

• The algorithm is to work inside a two dimensional space
• From each point, one can only traverse to the next point in four directions; up, down, left, right
• Points can only be either blocked or nonblocked, only nonblocked points can be traversed

Regarding the calculation of distance, it should not be the "bird path" for a lack of a better word. The path between A and B should be longer if there is a wall (or other blocking area) between them.

Im unsure on where to start, comments are very welcome and proposed solutions are preferred in pseudo code.

Edit: Right. After looking through gs's code I gave it another shot. Instead of python, I this time wrote it in C++. But still, even after reading up on Dijkstras algorithm, the floodfill and Hosam Alys solution, I fail to spot any crucial difference. My code still works, but not as fast as you seem to be getting yours to run. Full source is on pastie. The only interesting lines (I guess) is the Dijkstra variant itself on lines 78-118.

But speed is not the main issue here. I would really appreciate the help if someone would be kind enough to point out the differences in the algorithms.

• In Hosam Alys algorithm, is the only difference that he scans from the borders instead of every node?
• In Dijkstras you keep track and overwrite the distance walked, but not in floodfill, but thats about it?

Answer 1

Assuming the map is rectangular, you can loop over all border points, and start a flood fill to find the most distant point from the starting point:

bestSolution = { start: (0,0), end: (0,0), distance: 0 }; for each point p on the border     flood-fill all points in the map to find the most distant point     if newDistance > bestSolution.distance         bestSolution = { p, distantP, newDistance }     end if end loop 

I guess this would be in O(n^2). If I am not mistaken, it's (L+W) * 2 * (L*W) * 4, where L is the length and W is the width of the map, (L+W) * 2 represents the number of border points over the perimeter, (L*W) is the number of points, and 4 is the assumption that flood-fill would access a point a maximum of 4 times (from all directions). Since n is equivalent to the number of points, this is equivalent to (L + W) * 8 * n, which should be better than O(n²). (If the map is square, the order would be O(16n^1.5).)

Update: as per the comments, since the map is more of a maze (than one with simple obstacles as I was thinking initially), you could make the same logic above, but checking all points in the map (as opposed to points on the border only). This should be in order of O(4n²), which is still better than both F-W and Dijkstra's.

Note: Flood filling is more suitable for this problem, since all vertices are directly connected through only 4 borders. A breadth first traversal of the map can yield results relatively quickly (in just O(n)). I am assuming that each point may be checked in the flood fill from each of its 4 neighbors, thus the coefficient in the formulas above.

Update 2: I am thankful for all the positive feedback I have received regarding this algorithm. Special thanks to @Georg for his review.

P.S. Any comments or corrections are welcome.

Answer 2

Follow up to the question about Floyd-Warshall or the simple algorithm of Hosam Aly:

I created a test program which can use both methods. Those are the files:

• maze creator
• find longest distance

In all test cases Floyd-Warshall was by a great magnitude slower, probably this is because of the very limited amount of edges that help this algorithm to achieve this.

These were the times, each time the field was quadruplet and 3 out of 10 fields were an obstacle.

 Size         Hosam Aly      Floyd-Warshall (10x10)      0m0.002s       0m0.007s      (20x20)      0m0.009s       0m0.307s (40x40)      0m0.166s       0m22.052s (80x80)      0m2.753s       - (160x160)    0m48.028s      - 

The time of Hosam Aly seems to be quadratic, therefore I'd recommend using that algorithm. Also the memory consumption by Floyd-Warshall is n², clearly more than needed. If you have any idea why Floyd-Warshall is so slow, please leave a comment or edit this post.

PS: I haven't written C or C++ in a long time, I hope I haven't made too many mistakes.