I want to add puzzles to my game by adding indestructable blocks that the player must move away to progress. What kind of heuristic/algorithm can I use to create those patterns?

Context:



Home: Where bunny starts, where the carrots need to go
Bunny: The player's character
Tree: An obstacle that cannot move
Rock: An obstacle that can be pushed forward
Carrot: Can be pushed and dragged, including around a corner

In this example, if the player pushes the rock to the carrot at C6, the rock will cover the carrot and the player cannot win and must restart the level.


Q: How do I randomly generate this kind of map, where the player must move rocks to get to carrots?

The basic idea to make computer generated puzzles, is to make a lot of random puzzles and make the computer solves these puzzles and keep only the ones that are solvable and not too easy.
It is better explained in the following page :

http://www.puzzlebeast.com/about/index.html

(sorry i don't know how to make url clickable :-( )

The bottom line is : you have to make a solver for your type of puzzle, which is another problem :-)

Have your maze-generator solve levels in reverse. (pulling blocks, starting at exit, etc.)

It can take more or less random steps to reverse the final state and you should be able to generate reasonable puzzles. At least you'll know that all of them are solvable.

Re:

I took the route of starting with a solution and do some reverse movements on the rocks. To have a higher chance that the solution corresponds to a maze where some carrots are trapped, I started with a maze with two layers of trees for the border. I added more paths to the puzzle so that there is room for chasing and other actions.

Result:



/joy