I currently have a random-walk algorithm used to generate a series of boxes on a grid. The grid boxes are used as a map to create levels for my game. An example of the generated grids below:

I need a way to find the furthest pair of boxes on the grid. For example, in the image it would be `(11, 21)`

and `(24, 16)`

. I’m not sure what algorithm I need to learn in order to do this. Any help appreciated.

Maybe if you let yourself reinterpret this grid as an undirected graph, create it’s **Minimum Spanning Tree**

MSP approximation:

you could solve for the so called **longest path problem** ?

Did you try using A* pathfinding ?

You can calculate the path from every node to every other node , and only keep the one with the maximum numbers of nodes in the path.

There are also a lot of cases that can be skipped , for example :

let’s say you calculate the path to go from **C** to **F** , and it gives you : [ C - D - E - F] , you take that result and save it as the result of going from C to F.

Then , you calculate the path from **A** to **F** , you wont have to calculate it all the way to the end , all you have to do is go through [A - B - C] , then you stop at C since the rest of it ( C to F ) is already calculated , so you just take [A - B] and add the pre-cacluated result ([C - D - E - F]) which will give [ A - B - C - D - E - F].

As you can see , most of the paths will end up as (small section + pre-calculated section) so a lot of skips will occur.

if you don’t wanna do the skipping thing , you can just brute-force the whole thing and save it everytime you update the map.