Procedural Generation for "Hopper"

One of my current projects is a mobile version of a simple Flash game I made years ago called Three Blind Mice. I'm referring to the new game as "Hopper" for now. Here's how it works:

• You enter a sequence of moves by swiping up, down, left or right.
• After each swipe you have a couple seconds to add another move to your sequence. Swiping up, up, and left will enter the moves up, up, and left.
• When you finish swiping, your character hops according to the moves you entered.
• The goal is to collect stars, the more stars you collect in one sequence, the higher your score.
• Land on the grey stone tile to finish the level.
• Avoid hopping off screen or into water.

The strategy of the game involves keeping track of the sequence of moves you entered. It's a simple concept that I wanted to revisit after having grown as a designer and programmer.

One of the things I hoped to improve for the mobile version was the procedural level generation. I had a few goals in mind:

• The levels should be interesting to play and varied from one another.
• The levels' complexity should be influenced by a parameter so I can escalate their difficulty.
• Each level should have at least one perfect solution, meaning a single sequence of moves that collects all the stars and reaches the goal.

Let's take a look at the methods I've tried so far.

Method #1: Two Bridges

1) Create two grass shorelines separated by water.

 2) Pick a random position on each shoreline and connect them by a bridge. Repeat for a second bridge.

3) Place some dirt and grass tiles randomly.

4) Place the player, goal, and stars.

My first attempt was the "two bridges" method. I started by filling the grid with water tiles, which are impassable by the player. Then I placed a line of grass tiles along the top and bottom edges of the grid. I was thinking of these as shorelines and the water in between as a river the player was attempting to cross via a bridge.

To generate the bridge, I first selected a random horizontal position on each shoreline. I also selected a random vertical position between the two shorelines out in the water where the bridge would bend. I then placed dirt tiles in a vertical line out from the random shoreline positions to the bend position in the river. Finally, I connected the ends of those two lines with a horizontal line. Now I had a bridge generation function that let me connect any two shoreline positions using something resembling taxicab geometry.

Single bridge generation.

However, I didn't like how the single bridge felt like such an obvious solution, so I drew a second bridge overtop of it using new random positions (hence "two bridges"). I also placed some dirt and grass tiles at random positions to visually break up the obvious paths and provide possibilities for shortcuts.

I placed the player start position and goal on the opposing shorelines, and the stars were spawned on random dirt tiles. That latter bit compromised the goal of ensuring a perfect solution, because occasionally the stars would be spawned on an unreachable dirt tile "island" surrounded by impassable water.

Method #2: Weighted Drunken Walk

1) Fill with water.

 2) Randomly scatter dirt and grass tiles.

3) Draw the drunken path with dirt and grass.

4) Place the player, goal tile, and stars along the path.

In order to fix the unreachable star problem, I decided I should start by generating a perfect solution path and then building the level to accommodate it. That way I could place all the stars along that path and know they could be reached. To generate the path, I first tried a weighted drunken walk:

1. Define a start position and end position.
2. Randomly choose a neighboring tile from the start position to "walk" to.
3. Check if the new position is the end position. If so, you're done. If not, repeat step 2.

Instead of "pure" random walking, I assigned weighted values to the four possible directions: 0.75 for up, 0.25 for down, and 0.5 for left and right. So each time a random direction is picked for step 2, it's 3 times more likely to pick up than down, which encourages the path to progress upwards towards the goal.

Once I've recorded the move sequence for the perfect solution path, I drew it to the grid with dirt and grass tiles. Dirt tiles turn into water once the character has stepped on them, so I only place these on positions that are only visited once in the perfect solution path. 

Weighted drunken walk path.

I also added the randomly placed dirt and grass like in the first method, but when it came time to place stars I only placed them on positions along the perfect solution path. That way, I knew all the stars could be reached by following the path and levels always had at least one perfect solution.

Unfortunately, the drunken walk algorithm frequently doubles back on itself by random chance. This prevented me from placing as many dirt tiles as I wanted because I couldn't determine that a position was revisited needlessly due to the drunken walking or if the retracing was necessary to get back after collecting a star on a peninsula. The levels also just looked ugly, which was reason enough on its own to try something else.

Method #3: Waypoints

1) Fill with water.

 2) Randomly place a few waypoints.

3) Draw a path that connects the waypoints in sequence with dirt and grass.

 4) Randomly scatter dirt and grass tiles.

5) Place the player, goal tile, and stars along the path.

My third and current method for producing a perfect solution path is to randomly place a few waypoints-- arbitrary positions that the path must pass through-- between the start and end positions. Then I draw connecting bridges between each pair of waypoints in sequence. The connecting bridges work much like ones in my "two bridges" method but they consist of a maximum of two lines instead of three. I also randomly selected if a bridge's horizontal line should be drawn before its vertical line.

Flipping between horizontal-first and vertical-first.

This bridge flipping works well because it produces paths that sometimes retrace themselves and sometimes don't. If I wanted to control the amount of retracing, I could probably weight the random choice between horizontal-first and vertical-first so it was more or less likely to match the choice made for the previous bridge, which is typically when the retracing occurs.

So far, the waypoint method of generating the perfect solution is working well. The resulting solution is much more deliberate in its progress towards the goal and retraces itself less than the drunken walk, which allows me to place many more dirt tiles. I've also added arrow tiles, which slide your character one tile when they are landed on. Like with dirt tiles, I only place these at positions that are only visited once by the perfect solution path since they block movement in any direction other than what the arrow allows. Again, the waypoint method allows for more of these occurrences.

Another plus of the waypoint method is that it provides a good way to control the complexity of a level, which was one of my original goals for the procedural generation. By adjusting the number and placement of the starting waypoints, I can vary how long and convoluted the perfect solution path is. 

I've added a difficulty parameter which controls those waypoint placement properties as well as the odds of dirt and arrow tiles appearing. It still needs tuning, but so far I'm pretty happy with the results:

left: 0% difficulty, center: 50% difficulty, right: 100% difficulty

Placeholder art courtesy of Daniel Cook's Miraculously Flexible Prototyping Tiles.