Simple mechanics, complex puzzle creation - Part 4: Interesting challenges

In previous parts, we defined our game mechanics and level complexity (1), then we found a way to automatically verify that a level respects the rules of our game, presenting a fair (2) and fun challenge and rate it on a 5-star scale (3).

We are now left with the final problem of deciding which levels are worth analyzing in the first place, as a correct level can still be pretty dull to solve.

Should the designer just randomly place blocks and hope for the best, testing level after level? Is there a set of characteristics that defines an “interesting” level?

Semi-procedural generation

As a starting point, we decided to attempt a procedural generation of levels where the designer could set some desired parameters and get a set of random levels to be play tested for final approval.

As some of the parameters that influence level topology such as size, block types, can be verified during generation but other parameters related to the level’s difficulty or its star rating can only be verified after checking it (as described in previous parts) the full process is a semi-procedural generation:

Procedural block placement -> generated level -> brute-force analysis -> keep/discard level

The list of input we can set in our generator is as follows:

All the above user defined parameters are used by the generator to randomly place the necessary blocks while avoiding generating wrong levels.

This requires that for every placed block, it must respect space constraints (as some blocks require a certain amount of empty neighbor blocks to function properly) and some other position rules, defined by the game mechanics:

In this handmade test level, the top pit is useless as blocks will stop in the same spot against the corner wall (and keep this level’s rating at 3 stars). The bottom one, however, is not, because of the goal nearby. Without the pit, you couldn’t perform the perfect solution (Left, Down, Left) as one skiddy would disappear after the first left. Removing the top pit makes this a correct 5-star level (not a very interesting one though). In our procedural generation, the pit will never be placed in that position.

Should the generator fail while placing a block it will either try to reduce the blocks of that type or abort all together and start from scratch, depending on the situation.

In addition to these, Christian (the game designer) discovered an additional and very interesting parameter that is worth discussing in details.

Fearful symmetry

During the first hand-made attempts there was an easily perceivable influence of a level’s symmetry on our idea of “good level” so, after careful considerations about game mechanics, we recognized the following 4 types of symmetry as useful for our puzzle design:

Linear and diagonal symmetry are self-explanatory, the blocks are just mirrored following the symmetry’s axis.

Rotated symmetry takes the left half of the level and rotating it 180 degrees around a middle point.

Translated is just copying left inner blocks to the right while mirroring border blocks.

Depending on the size of a level, all symmetry can include some skipped blocks that are not influenced.

The effect of symmetry on a level is two-fold, not only does block placement give an ordered and cleaner look, but solutions become slightly easier for a player to visualize and being symmetric they are more forgiving, especially in starting moves

Symmetry example, either left or right are correct starting moves for a perfect solution. Even if perceptually we are inclined to go up at least on the first try.

We can add two more inputs to our generator:

Two examples of linear symmetry. On the left without color swap, on the right with color swap enabled. For the right board, perfect solutions (of course vertically symmetrical) are: Right, Up, Right, Down, Left, Up  (Yellow combo first) or Left, Up, Left, Down, Right, Up (Red combo first)

Fill in the blanks

In addition to this fully randomized mode, there’s another way we can generate a level, a “drawing mode”.

In this mode, the designer can draw some blocks (while the editor will enforce the same constraints as for randomly generated blocks) and fix them in place, set the parameters and let the generator just fill the empty parts of the level with different block configurations until the required number of pieces and the set level conditions are met.

Depending on the blocks already defined it is not always possible to get a valid level.

Whatever method of generation we used, once we have a complete level we then pass it to our checker which will solve it and analyze it with the methods we discussed before and determine if the solution is within the min/max required range and if the level rating is equal or greater than the required one. In addition, we’ll get the ratio of used level “states” over possible combinations (see part 1) and the maximum number of parents per node, both acting as a complexity indicator for the level.

A successful generation will not only create a level according to the required parameters but, because levels can be flipped and rotated, it will give us up to 8 variations of the same level, depending on its symmetry.

If we use the last generated level, we can get all 8 variations as it is not symmetrical

Batches and database

Considering how each Skiddy’s world has a fixed unique combination of blocks and each world’s level present an increasing challenge, we decided that a better usage pattern would be, after defining the required blocks for a world, to get a list of different levels after each run. To allow this, we implemented a “batch” mode that will try to generate a valid level for each size/symmetry combination while leaving other parameters untouched. To avoid getting stuck on an impossible combination or, anyway, wasting a lot of time on a particularly long set, we can set a maximum limit for retries and, should we not get a valid board within this limit, we just skip this size/symmetry combination and move to the next one.

In the end, we get a simple list of levels with their data and requested parameter and we can easily complete the skipped entries by either repeating the batch run (as they are fully randomized) or just generating the single missing size/symmetry combination in normal mode.

To reach a final collection of “interesting” levels, we have already generated a lot of random or pseudo-random levels and checked them, consuming a significant amount of time so, it would be nice to avoid wasting this pre-existing work, re-generating and checking combinations we already know are either valid or wrong, so we implemented a simple database organized by rating, size, and type to keep track of the results, even between different runs of the editor.

In this database, we save both correct and wrong levels with their analysis result and all the parameters requested at creation (this is useful for debugging the generator), using the level’s name (which is a unique encoding of all the blocks) as the key for storage and retrieval. This avoids repeated checks as we can immediately retrieve the results by querying for the block encoding.

All level data are in simple and compact text files so the full database can be zipped and copied to other computers together with the editor so the designer can work on any machine just by copying one small executable and a zip file.

The Human Touch

After implementing all these features, we are now at a point where most of the grunt work of level generation can be performed automatically by our editor. We can now easily create thousands of levels according to our specification with the reassurance that they are correct and up to our required rating, freeing the designer from a workload that not only would have required an impossible amount of time but, after a certain point, would have been impossible for the complexity involved.

By implementing as much as possible the designer ideas, the rules, and mechanics discovered while observing and playtesting simpler handmade levels, computer-aided puzzle design is indeed helping us create fair, fun and interesting challenges.

Yet, there is still a final and important ingredient missing before we can be satisfied with a level set and use it in our game. Handpicking the best levels and arranging them in significant progressions like we showed in the natural tutorial example still requires a human “touch”, a “feeling” both in aesthetics and gameplay satisfaction for the level being played that we are not yet able to condense in some automated process.

The difference that our editor brings to the table is that now the designer’s complete attention can be focused on this quality filtering, choosing of the best levels of the crop, the most diverse, graphically pleasing, a focus on quality, choosing from a wider selection of possibilities, without any doubt about correctness or the possibility of mistakes.

To conclude, we feel that not only the time we devoted to this aspect of our development paid off but it was also a huge lesson, helping us to discover other sides of our simple game and the importance of developing every part of it with a tight cooperation between designer and programmer.

Our hope is that this recollection of our journey can help other beginning developers find the same positive opportunity.

References and thanks

The idea for this blog series was inspired by Jonah Wallerstein’s blog: Just a level solver: Why my simple puzzle game took me over a year to complete which deals with a very similar problem to the one we faced and uses an approached we also considered before successfully developing our own editor.

While writing part 3 I stumbled upon Jonathan Blow’s AIIDE 2016 talk: How do you make an AI that designs video games? That deals with level design, game mechanics and meaning, which is a much deeper and more professional look into the idea of natural learning and hidden tutorials in game levels and structure. As any talk by Jonathan Blow, this is highly recommended.

Finally, thanks to my friends Colin Cowpe and Alex Jermy for reviewing my ramblings and helping me present them in a hopefully clear and interesting fashion.

As stated in part 1 introduction, this blog series is a companion piece to talks given at Codemotion 2012 in Rome (http://roma2012.codemotion.it/talk/skiddy-esperienza-un-primo-progetto-serio-nel-mondo-dei-videogiochi/index.html) and at Politecnico di Milano on October 31^st, 2014 (https://www.youtube.com/watch?v=8_UeywA68kA). Those talks are more design/gameplay oriented but will help get a complete picture of the reasoning and choices behind the game.

Disclaimer: As a first experience in designing/programming a video game, we are aware our methods might not be the best but they served the purpose and aided the design and the code to evolve and complement each other.  If readers have questions or suggestions regarding the subject matter and how to improve it, we at BigBangPixel would sincerely like to discuss it, so write us at [email protected]

License: Skiddy and all related assets including levels and editors are Copyright 2012 by BigBangPixel and all rights are reserved. The information published in this article can be used by anyone for non-assignable, non-transferable, non-commercial use or educational purposes.  Any other use, including any redistribution in whole or in part, requires explicit, written permission from BigBangPixel.