Generating Arrow Maze puzzles

Question

I have picked this puzzle shown here as training in programming games.

In these mazes you follow the arrows. From each arrow you can move to any of the arrows it's pointing to, in the same row, column, or diagonal.

More explanation can be found here.

As you can see the Arrow on a yellow background in the top-left corner marks the beginning of the maze. Since this arrow is pointing to the right, the player can move from here to either of the two spaces to the right. The player then chooses which arrow to should move to. If they choose the Down arrow in the top-middle, then for their next move they can travel to any of the spaces in the column below it. If they choose the diagonal arrow, then they can move diagonally.

In short, the arrow direction indicates the path direction the player can move. The player continues making these moves until they arrive at the bulls-eye which marks the end of the maze. Here is a solution to this maze:

What I want is to generate a brand new puzzle each time the player starts the game, so they will have to find a different solution path. The player then makes their choices of moves to solve the puzzle. Then they can generate a new puzzle to solve.

Unfortunately, I'm stuck on this step. How can I generate this kind of puzzle? Do I need some path finding methods and which one will help me to achieve this goal?

I'm using the C# language.

Thanks!

Answer 1

Here's a way I'd try:

1. Pick a cell in the maze where you want to start. Add it as the first step in our solution.

2. Pick a random direction for that arrow. For cells on one or more edge of the maze, that direction can't point outside the maze.

3. Pick one cell in the direction of that arrow to be the next step in the solution.

4. Mark all cells in the direction of the starting arrow as "reachable on step 1" - we'll use this to avoid accidentally creating trivial shortcuts.

5. From the next solution cell we chose, pick a new random direction, again being careful not to point outside the maze.

6. Find a cell in that direction that's not yet marked reachable (so we couldn't have gotten there at an earlier step even if we tried) and add it as the next step in our solution, marking all thus-far-unmarked cells in the direction we chose as "reachable on step 2" (or step 3, 4... depending on how many times we've looped) Then continue from 5.

7. If there are no non-reachable cells in that direction, choose a new random direction from those remaining.

8. If no direction lets you continue further, then mark this cell as the destination instead. Now our solution is done.

9. Now, we fill in the remaining cells. Starting with those reachable in step 1, choose directions that don't point to any cell in our solution later than the first. Then we proceed to those reachable in step 2, choosing directions that don't point to any cell in the solution later than the second, and so on. This way we ensure these cells never short-cut the solution.

10. You can fill in any remaining non-reachable cells randomly - they can even all point straight to the goal, it won't matter, since the player can't reach them.

11. If in step 9 you run into a situation where no direction avoids shortcuts, oops, we messed up, try starting over from 1. (I currently don't have a better idea for how to avoid this, but on small maps this should still run fast enough even with this naive guess-and-check approach).

Answer 2

For storage, use N by M array of enums: ARROW_UP, ARROW_UP_LEFT and so on. If field is 3 by 3 with arrow pointing to up-left in the middle, then you'll need an 3 by 3 array, and middle field will have value ARROW_UP_LEFT.

Now, regarding the puzzle, let me confirm: player can set an arrow to any direction he wants, or he can only swap fields?

For first option, there is no need for you to check anything, it'll be always possible for a player to find a way. There should be more than one 'correct way' - just shuffle and don't confirm anything.

For second option, You can just randomize all fields and then backtrack from goal to starting position. Also, you can try to implement some kind of maze generation algorithm (https://stackoverflow.com/questions/22305644/how-to-generate-a-maze-with-more-than-one-success-full-path seems to be somewhat related).