2
\$\begingroup\$

I develop a (really) simple puzzle game that asks you to join a point A to a B (enter/exit) using a ball and mechanisms that you can rotate to give the correct direction to the ball in order to join the exit.

Here is screenshots of a simple level, showing clearly the purpose of the game:

1) New level started, the mechanisms are rotated in a random way:

New level started, the mechanisms are rotated in a random way

2) Level is completed, all the mechanisms are rotated properly to give the ball the right path to join the exit:

Level is completed, all the mechanisms are rotated properly to give the ball the right path to join the exit

Question:

How can I create an algorithm allowing me to automatically generate levels by taking into account the rotations and leaving only one possibility for the player to complete the level?

I'd also like to add more complexity by adding more mechanisms (to create creating difficulty levels).

I don't think it's necessary to talk about tech, but I'm using C# and Unity.

Let me know if you need more information.

Thank you!

\$\endgroup\$
4
  • \$\begingroup\$ Does the ball only bounce in 90 degrees? \$\endgroup\$
    – Bálint
    Commented Mar 30, 2017 at 9:51
  • \$\begingroup\$ @Bálint Yes! But sometimes I add a new mechanism: a "plate" which gives the ability to the ball to bounce back (it only changes the direction of the ball, eg: from left -> right to right -> left) \$\endgroup\$
    – Hadrien
    Commented Mar 30, 2017 at 9:58
  • \$\begingroup\$ but if a ball hits a plane, then it will go back to the start position no matter what \$\endgroup\$
    – Bálint
    Commented Mar 30, 2017 at 10:48
  • \$\begingroup\$ @Bálint yes, indeed. Do you have a start of solution to generate the levels? \$\endgroup\$
    – Hadrien
    Commented Mar 30, 2017 at 10:56

1 Answer 1

Reset to default
1
\$\begingroup\$

Backtracking.

  1. Place a mechanism which aims at the goal from a random direction and a random distance. Have it face randomly so the ball needs to come from either the right or the left to get directed to the goal.
  2. Then another one at a random distance which aims at the previously placed mechanism's input, again with its own input randomly facing right or left.
  3. Repeat step two. The number of iterations depends on the desired difficulty.
  4. Place the start so it faces the last placed mechanism. You now have a solved puzzle.
  5. (optional) place some more random mechanism which aim at the opposite of the output of a random one of the existing mechanisms. These are "red herrings" which are not needed to solve the puzzle and only serve the purpose to confuse the player.
  6. Then rotate each rotator into a random direction so the player has to guess how to rotate them.
\$\endgroup\$
2
  • \$\begingroup\$ Really nice explanation and approach, I'm currently developing a basic generator to try this. Thank you! \$\endgroup\$
    – Hadrien
    Commented Mar 30, 2017 at 11:22
  • 2
    \$\begingroup\$ Minor quibble: the solution presented isn't really "backtracking" in the algorithmic sense described by the link. A backtracking algorithm tries to solve a problem incrementally but naively, making occasional missteps that it doesn't detect until some time later, when it realises it's in a dead end and abandons that trial solution, "backtracking" or undoing steps back to an earlier choice and trying a different decision. The algorithm described here always proceeds with placing and never second-guesses its work — in fact it works equally well proceeding forward from the start to the goal. \$\endgroup\$
    – DMGregory ♦
    Commented Mar 30, 2017 at 12:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .