In general, longest path is an NP-hard problem (except for trees, which our perfect graphs are).
However, we don't exactly want longest path: what we want is to find the maximum length shortest path, which can be done via a BFS at each node, keeping track of the pair of cells that are the furthest apart. Ultimately, these can be used for the start and the goal position to presumably make the maze more challenging.
This should be calculable in time O(w2h2) simply by starting at each cell, of which there are at most w * h, and running a BFS, which will take at most w * h steps.
By implementing BFS for each maze type, we will be able to do this easily, as well as find the connected components easily, and possibly have enough information to generalize solutions to AbstractMaze.
In general, longest path is an NP-hard problem (except for trees, which our perfect graphs are).
However, we don't exactly want longest path: what we want is to find the maximum length shortest path, which can be done via a BFS at each node, keeping track of the pair of cells that are the furthest apart. Ultimately, these can be used for the start and the goal position to presumably make the maze more challenging.
This should be calculable in time
O(w2h2)simply by starting at each cell, of which there are at mostw * h, and running a BFS, which will take at mostw * hsteps.By implementing BFS for each maze type, we will be able to do this easily, as well as find the connected components easily, and possibly have enough information to generalize solutions to
AbstractMaze.