Improve Generator Unit Test

[john-science]

The generator unit tests are pretty good. But they need one more test feature for each generator type: test if the maze is solvable?

One way to solve this would be to put a start and end point in the corner of the maze and solve it.

This is easy in theory, but not all mazes are solvable using the same solving Algorithm.

[geneshki]

Would just solving the generated maze from a particular run be enough of a check? If the test should ensure that the generator always generates a solvable maze checking a single maze doesn't seem the right approach.

Finding the solution could be implemented as finding a path in a graph, which is implemented at least in ShortestPath solver (Perhaps the others do a similar thing). Right now I know very little about mazes to see how one such solver wouldn't find a path if it exists. Do you have a resource that I can read to understand better the problem?

[john-science]

Hey @geneshki !

Sure, if you look in our maze-generating docs, you'll see each algorithm is listed as "perfect" or "imperfect":

Results

perfect, unbiased

(A "perfect" maze has one, and only one, solution.)

And if you look in the maze-solving docs, each algorithm listed says whether it can solve perfect/imperfect mazes:

Results

    1 solution
    not the shortest solution
    works against imperfect mazes

So, that's certainly a place to start.

Most (all?) of our maze-generating algorithms should generate a maze that is solvable by an algorithm that can solve imperfect mazes.

Of course, you're right that:

Would just solving the generated maze from a particular run be enough of a check?

Though, to date, our unit tests don't run millions of mazes through the algorithms. They need to be faster than that.