# Blocky

Authors: Diane Horton (dianeh@cs.utoronto.ca) and David Liu (david@cs.utoronto.ca)

## Description

A visual game in which players apply operations such as rotations to a recursive structure in order to work towards a goal. The main data structure is a quad-tree, so this assignment provides lots of practise with recursion and trees. Students also implement some interesting and challenging algorithms.

Game assignments may be less appealing to female than male students [1], so we designed a game that is puzzle-like, with simple rules, but that is challenging to play. We think the game board is attractive, bearing a resemblance to a Mondrian painting, and the colour scheme can easily be configured by students - this is surprisingly satisfying!

## The Game

Blocky is played on a randomly-generated game board made of squares of four different colours. We call the game board a "block." A block is either:
• a square of one colour, or
• a square that is subdivided into 4 equal-sized blocks.

Each player is randomly assigned their own goal to work towards: either to create the largest connected "blob" of a given colour or to put as much of a given colour on the outer perimeter as possible.

There are three kinds of player moves:

• rotating a block (clockwise or counterclockwise),
• swapping the two halves of a block (horizontally or vertically), and
• "smashing" a block (giving it four brand-new, randomly generated, sub-blocks).

What makes moves interesting is that they can be applied to any block at any level. For example, on the board on the left below, the user has chosen a block (highlighted) that is two levels below the top level. Rotating it clockwise would result in the board on the right.

## Data Structures

Blocks are represented using quad-trees. For example, suppose we set the maximum depth to just 2, and had this simple game board:

Its quad-tree would have this structure, where the children represent the upper-right, upper-left, lower-left, and lower-right sub-blocks, in that order:

Our implementation stores additional information in each node, including the size and position of the square, and includes a rich set of invariants that express, for instance, that:

• Each node has either 0 or 4 children.
• Only leaf nodes have a colour.
• If a node has children, their height and width is half of its height and width.

When scoring a player who has a "blob goal", we need to find the largest connected blob of the target colour. This is much easier to do on a 2-D representation than on a quad-tree, so students derive a 2-D representation from the quad-tree. The algorithm is tricky, because a block of uniform colour may need to be treated as 1 square, or 4 squares, or 16 squares, etc. depending on how finely divided the game board is. The board above, for example, is 4-by-4 in the 2-D representation, since a maximum depth of 2 allows the board to be divided into up to 16 squares. We implement the 2-D representation as a list of lists of colours.

## Assignment Materials

For the benefit of the community, we ask that adopters of the assignment do not post solutions or more of the starter code than we are providing here.