I'm using recursive backtracker or depth first fearch (correct me if it's not the same) algorithm to generate unique 2d mazes for my game. However for the gameplay I intend to implement the logic also needs to know the solution path from A,B-X,Y (to solve the maze). For that I intend to run a second process, that does that. I wonder if there is any chance to do in one run - generate and solve (to save some processing and load-times).
\$\begingroup\$
\$\endgroup\$
1
-
1\$\begingroup\$ Is there any reason you're not just generating the solution path first and generating the rest of the maze around it? That's how most puzzle generation is done: working backwards from the solution. \$\endgroup\$– Weckar E.Jul 11, 2020 at 15:15
Add a comment
|
1 Answer
\$\begingroup\$
\$\endgroup\$
1
If your depth-first search starts from the entrance or exit of the maze, then this is trivial.
Each time your generator explores/carves out a cell, store the direction you entered that cell from. This effectively gives you a map of arrows tracing out the path back to the origin of your search.
From your chosen destination point, follow those arrows until you reach the origin of the search. This gives you the path through the maze that connects the two points in linear time.
If your search starts from somewhere in the middle, then you need to build this path in two parts: start at your entrance, and backtrack along the arrows to the origin, marking the cells as "visited" as you go. Then start at your exit and do the same, until you reach a cell that's already been marked "visited". Join the two paths you've traced so far at the point where they reach this cell, forming a single path connecting the entrance and exit.
answered Jul 11, 2020 at 13:06