0
\$\begingroup\$

I have an idea for a puzzle-platform game where the levels would be randomly generated. Creating a random generation is relatively simple. What's not easy is checking that randomly generated level to see if it's possible to complete, or generating a level where completion is possible. I think there are a number of different ways to do this.

Are there any games that employ something like this? How is something like this typically done, if ever?

\$\endgroup\$
  • \$\begingroup\$ There are a variety of ways to check if a puzzle is solvable. It really depends on the puzzle. If you included more specific information about your game, it would be easier to give you an answer. \$\endgroup\$ – Amplify91 May 21 '14 at 0:10
  • \$\begingroup\$ I'm not sure yet. I just think some kind of puzzle-platformer, like LIMBO, with randomly generated levels would be interesting and fun. \$\endgroup\$ – Gus May 21 '14 at 0:58
  • \$\begingroup\$ You can add things into your level generation to make sure it does not become impossible. For example don't generate a wall that is higher than a player can jump without anything else around to help. You can also use a pathfinding algorithm to check that the level is not impossible. \$\endgroup\$ – Amplify91 May 21 '14 at 1:12
  • 1
    \$\begingroup\$ Cloudberry Kingdom. Not a puzzle platformer, but a platformer none the less - this is a good read that might help: gamasutra.com/view/feature/170049/… \$\endgroup\$ – SpartanDonut May 21 '14 at 1:52
  • \$\begingroup\$ lock and key puzzle generator (definitely worth reading): reddit.com/r/proceduralgeneration/comments/1ztgcc/… \$\endgroup\$ – wes May 23 '14 at 13:50
1
\$\begingroup\$

Since I don't know the way a level is implemented in your game, I will give a general answer.

Typically, the game has a set of known rules (constraints) by which it operates. You need to apply them in your validation algorithm.

My solution for a (I assume) complex game like yours would be, as follows.

After the level has been generated, run a simulation. If the simulation solved the puzzle, you're done. Otherwise, fix the existing level or generate a new one and start over.

A simple example of this can be seen here, where he first generates a world according to a few simple rules (making corridors), places his agents on map and runs simulation to validate the level. If simulation fails, he tries to fix the level. If simulation is still failing, he generates a whole new world and starts over.

Alternatively, you could avoid the expensive game simulation by using a search algorithm like the A* algorithm, which can serve as a puzzle solver directly on your data structures. Another option might be evolutionary algorithms, although they can be quite computationally expensive and cannot guarantee valid levels.

EDIT: As DMGregory noted in the comments, you're better off generating a valid level as you go, rather than fixing it after it's been generated. This will most probably produce better levels and will be computationally cheaper. However, the implementation is naturally harder, especially when you're after complex level generation.

\$\endgroup\$
  • 2
    \$\begingroup\$ If the set of solvable/fun levels is small relative to the set of all validly-constructed levels, then the generate-and-test method can take many costly iterations to find a good level. The more of your constraints you can build into the generate step, the fewer levels you'll need to reject. As a simple example, placing platforms only in particular offsets from one another or the ground, so that the gap is always crossable, rather than placing them fully randomly. \$\endgroup\$ – DMGregory May 22 '14 at 12:45
  • \$\begingroup\$ We aren't sure of OPs programming capabilities as well as his game's complexity. But I agree, he should make use of constraints within his generation step. Updated my answer. \$\endgroup\$ – Howie May 23 '14 at 7:36
0
\$\begingroup\$

To create a concrete solution, you need to understand the movement constraints (or more so, the movement flexibility) in the platformer without the puzzle elements first. Like DMGregory said, for instance, you need to randomly place platforms within a jumping distance from one another. You also need to define a "possible jump". This jump must not be obstructed in later steps by additional platforms or elements.

After you have a valid platforming level generator, you can throw in puzzle elements without disrupting the initial constraints. For instance, add buttons that open doors, cause platforms (that were initially hidden) to appear out of thin air and so forth.

In order to provide a more specific answer, I must say that you could probably generate the platforms for a LIMBO like game but it appears to me the "puzzles" if you can call them that, are obviously hand crafted in that design.

Procedural generation is good for creating fresh, riveting new combinations of existing elements. In that specific case, it appears that it's pretty linear (the combination is not so important) and the puzzles just appear one after the other.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.