Home
Alphabetical
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Minehunt: Concepts that can be demonstrated

 

Apart from the easier programming ideas, the algorithms and strategies may be used as examples of some basic concepts:

 Human perception

The reason why the game has some difficulty for humans is that we cannot easily perceive the square of eight cells that surround a given cell.  We may be able to see such a square for one cell, but then have difficulty switching to the square corresponding to a neighbouring cell (e.g. when both show the same bombcount and in fact share the bombs, as is often the case).

Probability

The program sets out the bombs on the grid, but the player starts seeing everything covered.  When some parts have been uncovered, the player's strategy should be based on probabilities, which strangely do have a meaning even though in fact the bombs will not be moved by the program.  (Hey! what about a version that does move the bombs around, but without changing the known bombcounts.  Is it more difficult? No, it is not, but why not?)

Graphics

Propagating a zero-bomb cell to uncover a sea is an algorithm also used in computer hardware graphic cards.

Optimisations

The plain math algorithm works, but is so impractical that we are forced into optimisation from the start.

User interface design

There is little of it, but enough to show that attention to detail is necessary

Parameterising

The size of the grid is the most important parameter.  The player can resize the grid but this means redrawing the entire window.  A number of drawing issues come up here:  the way I did it in Revolution with a grid of text fields is very expensive in redrawing time.  Reducing this time leads to some graphics concepts again.

Keeping track

Computing the set of possible configurations is not trivial to do:  a brute-force approach is not good enough.  We can consider the area between the uncovered "sea" and the still covered "Island":  the narrow strip of covered cells bordering on uncoverd cells is the best place to generate combinations that allow us to make fast progress, leaving the majority of covered cells for later.  A pruned binary tree that is constantly rearranged as one proceeds through generating the possible positions is one way of doing it.

Choosing the next move

In an ambiguous situation we have to choose a cell to uncover but should pick one that is most likely to be a safe one, yet at the same time likely to yield the most information.  Computing these probabilities is again not trivial.

Valid XHTML 1.0 StrictValid CSS

next planned revision: 2005-06-01