Randomized puzzle generator – How it works!

Posted by (twitter: @zanzlanz)
December 14th, 2014 9:51 am

Hey again!

Recently I’ve made a post – http://ludumdare.com/compo/2014/12/06/puzzle – where I show off progress on the random puzzle generator I created for LD31. A few of you were interested in how I created it, so here I am to explain it!

First of all, here’s the newest gif of me playing the first couple randomly generated levels, and an image of one of the higher levels:

 

Puzzle generator with coins!Sometimes things get complicated dundundun

 

If you want to try it out yourself, here’s my submission:
http://ludumdare.com/compo/ludum-dare-31/?action=preview&uid=11407

 

The idea is simple:

Create a random level generator that provides the player with a challenging, yet always solvable, sliding puzzle.

 

Here’s the trick!

I programmed a simple noise generator (loops through all tiles on the screen and sets them to a random tile). Then I made a pathfinding algorithm that starts at the spawn point and finds all possible moves. It’s kind of like A*, where if a move gets you to a spot quicker than a different move, it over-writes it. Then I simply determine which spot took the highest number of moves to get to, and place the end there! If the spot with the highest number of moves isn’t “hard” enough, I generate another level from scratch and try again, until the level meets a certain difficulty.

The water.

You die when you touch the water. That was pretty easy to put into the generator. Basically I tell it the same thing as I do to the snowman: if there is water along the path, you can’t go down that path (restart the player). The generator has no problem dealing with that.

The coins… oh the coins.

I really wanted to give the player something to collect as an added challenge, as they solve the puzzle. The goal here is not to place coins in the middle of the path to the end. That would be way too easy for the player. So basically I created another algorithm that tells me if Point A can lead to Point B (or pass through it, even). I found the best way to make coins was to check these:

– You can pass through the coin safely from the start.
– Wherever you land next, you can pass through the start, AND reach the end (if you can’t reach the end, it’s in an unsolvable position!)
– If you can get from wherever you land after you pass through the start BACK to the coin (basically, if it’s possible to get other coins).

I’m kind of worried that there are very specific “corner cases” where this generator doesn’t make every coin collectable. But I’ve never seen it happen, so maybe it is flawless! :)

How fast does it generate?

Fast for the small levels, and quite slow for the end levels (30 seconds some times).  So what I did is make the generator create the rest of the levels while the player is solving the first ones! It can create all 20 of them by the time you reach level 5. Also, I did a lot of fooling around with the density of water and blocks, and found some densities are better for the generator to quickly create harder levels, quicker.

 

Alright! Well I hope you enjoyed the post! I also hope this inspires you to try out random generation – it’s not all that hard once you get the concept down. 😀

Thanks for reading,
– Zanz

 


4 Responses to “Randomized puzzle generator – How it works!”

  1. pht59x says:

    Some pretty good ideas in here.

  2. tudd says:

    I like generating the later levels as you play the easy ones, that’s a good idea :)

    • Zanzlanz says:

      Thanks! Yeah I give it 1/8 of the time in each frame to generate later levels, so unless the player is experiencing lag on the rendering, it’s virtually unnoticeable :) If someone is really fast and beats the level generator to a level, it’ll just show the usual generating screen.

Leave a Reply

You must be logged in to post a comment.

[cache: storing page]