Computing Degree Show 2016

Creating a new computer game using constraint programming

The Knight’s Escape

by Christopher Dunlop

Implementing a computer game has many challenges one of which is ensuring that the difficulty increases consistently throughout the game. The difficulty curve of the game corresponds directly to the player’s enjoyment as the player should be challenged when progressing through the game without reaching the point where the gameplay becomes repetitive or they reach a level which they cannot complete. This project involved creating a brand new computer game where all levels were generated automatically using constraint satisfaction problems; a technique within a branch of Artificial Intelligence called Constraint Programming. The difficulty of each level was then calculated automatically based on statistics given by the solver and was set to be the closest representation of what a player might perceive as difficult. The game was then tested to ensure the difficulty set by the grader adhered to the perceptions of the participants. After testing, the algorithm was shown to be successful, but could be improved and suggestions are explored in detail within this report.

The “Knights Escape” is a puzzle game based on a common mathematical problem called the Knight’s Tour. This is where the knight on a chessboard has to visit each square on the board only once. The level is complete when the player has moved to every square on the board once. Once the player has moved onto a square the player cannot move onto that square again. In the Knights Escape gameplay this is shown by the square changing to look like lava to indicate the square is no longer available to the knight, as shown below.


Just like the Knights Tour the player is restricted to the moves a knight can make in chess. The knight can only complete a move that is two squares vertically and one square horizontally, or two squares horizontally and one square vertically.


Unlike the knights tour the playable board differs in size between levels. The playable area grows as the game progresses and it will not always be square like a chessboard. There are 5 non playable squares at the start of each level which are shown as lava from the beginning (figure 3). This is to allow more variations of levels within the same board size to produce a better gameplay experience. The player completes the level when they have collected all the gems which are on each square. When the player reaches a point where they have either collected all the gems, or are stuck with no moves left to make the game will display a menu to either restart the level or continue to the next level.