Computing Degree Show 2015

Creating a new computer game using constraint programming to automatically generate and grade the difficulty of levels

When developing a puzzle game, the most time consuming part of the process is the generation of each individual level. One possible way to do this is create the levels by hand, however this method has some inherent flaws. As well as being a slow and tedious process, human error is introduced which could result in unsolvable instances of the puzzle.

One possible solution to overcome these problems in development of the puzzle levels is to harness computational power to increase the speed and accuracy of the level creation. Specifically a branch of artificial intelligence called constraint satisfaction programming. Once a precise set of constraints are generated for how to construct a level, it is possible to then find every single combination of values that abide by these constraints. This method allows for considerably faster level generation, resulting in unique and interesting puzzles that are free from human error.

With the levels generated all that remains is to export the output into a game to be played.

The game plays similar to a hybrid of Sudoku and Battleships, where the player must place ships on a grid where each equals a numerical value of one to five. Each ships occupies exactly 3 consecutive spaces on the grid and add its value to each row and column that it occupies. The goal is to place all the ships on the grid so that summed numerical values in each row and column are matched.

Upon loading the game, the player sees the title screen that links to the level select screen and a screen that explains how to play the game.


The level select screen offers 3 difficulty levels for the player to choose puzzles from ranging from easy to hard. There is a set difficulty curve in the game so levels will scale to harder puzzles effectively if the player wishes to move up to harder levels.

Screenshot_2015-04-15-14-11-32     Screenshot_2015-04-15-14-23-47     Screenshot_2015-04-15-14-23-58

To place the ships on the grid visible on the game play screen, the game allows the player to select three spaces, and if the spaces are consecutive and are on the same row or column then the ship has been successfully placed. Alternatively, the player can drag and drop ships onto positions on the grid.

Screenshot_2015-04-15-14-13-19     Screenshot_2015-04-15-14-13-35     Screenshot_2015-04-15-14-13-49     Screenshot_2015-04-15-14-14-18


Upon completion of a level the game will show a score value of 1 to 3 stars to the player based on how quickly they completed the level and they will be returned to the level select screen where they can choose to continue with more puzzles. The end goal for the game is to achieve a 3 star rating for all the levels in the game.



Developed by Adam Brown