S
S
SerYojik852017-04-17 14:24:45
Algorithms
SerYojik85, 2017-04-17 14:24:45

Is there an algorithm for testing the maze for the absence of closed spaces?

Hello, comrades, gentlemen, brothers!
I found many examples of interesting generation of labyrinths. But could not find testing it under the following requirements.
Throw, please, in RuNet a link to an example of an algorithm for testing a labyrinth for the absence of closed spaces, preferably with explanations, because I am a beginner in this matter. Those. if we do not generate (and in this case) a maze, i.e. errors are possible. The task is to check that from any of its points, one could get to any other.
I'll deal with the code, the logic is not yet clear, except how to bypass it all, marking each of the passed points as passed, and in case of inaccessible ones, give an error. But instinct tells me that this is the wrong way.
It would be great if it was possible to display a "solid wall", the passage in which would make the maze correct.

Answer the question

In order to leave comments, you need to log in

3 answer(s)
A
alex_ak1, 2017-04-17
@alex_ak1

If the labyrinth is on a grid or a graph (and how else can you set it, by the way), then a simple wave algorithm. We carry out a wave and see if there are inaccessible ones, whether it is possible to get from the end to the beginning.

A
Alexey Yeletsky, 2017-04-17
@Tiendil

You can search for the number of connected components, you can start to understand from here: https://ru.wikipedia.org/wiki/Connected_graph

G
GavriKos, 2017-04-17
@GavriKos

Well, the simplest. The labyrite is divided into cells. The number of cells is known (maze area). We go through the whole maze recursively for example (i.e. on each branch we go along each branch). And we count the number of passed unique cells. If, as a result, the number of unique cells passed is less than the area, then we have a closed space.
One can also try to represent the labyrinth as a point reachability graph. And already analyze the graph.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question