1
\$\begingroup\$

I am creating a maze type puzzle game where there is a grid and the user can create their own maze but I need help in writing an algorithm which finds the following things:

  1. How many dead ends are there. (It should return 4 tunnels which are marked red)
  2. How many of those dead ends don't lead to the exit. (It should return 3 tunnels as only 1 dead end leads to the END point)
  3. Which dead ends lead to the end. (*3rd dead end only)

maze

I am new to writing algorithms so I haven't written code for this yet. How can I identify dead ends, and which ones don't lead to the exit?

\$\endgroup\$
4
  • \$\begingroup\$ astrolog.org/labyrnth/algrithm.htm is my go-to resource for maze algorithms. By the way you're using the wrong terminology - I think you mean "dead end" as opposed to "tunnel". "Tunnel" implies that it connects two ends, like the chunnel going between UK and France. \$\endgroup\$ Commented Mar 18, 2016 at 6:04
  • \$\begingroup\$ @congusbongus yeah dead tunnels sorry for the confusion and link seems useful but there are way too many algorithm's can you tell me which algorithm will perfectly fit in this case and also there is also no code to create the algorithm just the concept. \$\endgroup\$ Commented Mar 18, 2016 at 11:56
  • \$\begingroup\$ The problem is a bit underspecified. If you add a red cell to the right of the 4, does that still count as a deadend or as a loop? Do you allow loops at all? \$\endgroup\$ Commented Mar 19, 2016 at 14:47
  • \$\begingroup\$ @LarsViklund that is a dead end but you got a nice point that if user selects the right cell of the 4 then it wont count as a dead end with. Need to think on that one. \$\endgroup\$ Commented Mar 21, 2016 at 6:37

3 Answers 3

Reset to default
3
\$\begingroup\$

One of many possibilities and the one I'd use is:
1. Start a Flood Fill from the start square, to find which squares are connected to it;
2. For each square marked with the flood fill verify how many walkable neighbors it has. Dead-ends should only have one walkable neighbor.
3. If said dead-end is connected to the exit of the maze, mark it as so;

A pseudo-code could look like this:

function flood_fill(square) if (square.walkable == false) return; count = 0; foreach(neighbor in square.neighbors) { if (neighbor.walkable) { count += 1; flood_fill(neighbor); } } if (count == 1) square.dead_end = true; // Or you could add it to a list //And in the required section of the code flood_fill(maze.start)

Addendum: Since you did not specify how to know if a square leads to the exit I left it out the pseudo-code.

\$\endgroup\$
2
  • \$\begingroup\$ What if we add a red cell to the right of the 4 then how will it count as a dead end? \$\endgroup\$ Commented Mar 21, 2016 at 6:38
  • \$\begingroup\$ Presumably your code will read if it's accessible by if it has a wall or not. \$\endgroup\$ Commented Apr 19, 2016 at 10:19
0
\$\begingroup\$

There are multiple way you can write this. It just depends on your personal preference and if you are wanting visuals to the implementation of the algorithm. An example is you could have all squares in the grid in an array and have a variable move throughout the array in whatever fashion you find fit. If it finds a square labeled "e" it is at the exit, if it finds one labeled "d" it could be a dead end. In this example you would have to marl the starting position as well so you know not to include it as a dead end.

So essentially you'd just have to have the algorithm move throughout the array determining if the square that it is currently in is part of the maze, if not then move back. Continue that until it has made it through the grid. Just make sure you are only mov ok no from squares adjacent to one another which is easy enough. If it finds that it cannot go any direction but back from where it came then it can mark it as "d" for dead-end unless it has made it to the exit.

\$\endgroup\$
0
\$\begingroup\$

The easiest way to do this and find the literal "end" of a dead end is to count the walls. This is presuming that you cannot have loops and you define walls for your cells.

Iterate through your cells and just find all with 3 walls as those are the only cells which are a dead end, as the can only have one exit it must have only 3 walls.

\$\endgroup\$
2
  • \$\begingroup\$ This is the inverse of Lince's awnser, where he checks wether out of 4 possible connections 1 is open, you check if 3 are closed. \$\endgroup\$ Commented Apr 19, 2016 at 14:01
  • \$\begingroup\$ With a very slight difference. Lince's makes the assumption that walls don't exist between cells and that blank cells are the walls. Mine is if the system puts walls between neighbouring cells to separate them. \$\endgroup\$ Commented Apr 21, 2016 at 11:05

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.