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:
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
