Algorithms and data structures behind Minesweeper Battle
Tags: datastructures, algorithms, webdev
Published: 2020-06-16 23:16:36

Hi Dev.to community,

*With this blog post I'd like to start a series of blog posts dedicated to my project [Minesweeper Battle](https://minesweeper-battle.onrender.com/).*

### Intro
Data structures and algorithms is basically what every computer program consists of. Organising data in the most optimal way and using proper algorithm for a specific task make programmer's life incredibly easier. And visa versa - utilising a structure or algorithm which is not applicable for certain requirements can lead to series of workarounds, mistakes and suffering. In this post I'd like to describe in details how picking a correct data structure helped me to implement a vital part of the project in a clean and simple way.

### The game
Minesweeper Battle is a web-based variation of classical [Minesweeper](https://en.wikipedia.org/wiki/Minesweeper_(video_game)) game, where it is possible to play against another player (currently - computer player only). The goal is to "occupy" larger territory than your opponent and not to explode on a mine at the same time. At the moment tech stack of the game consists of Typescript, Vue.js and Bulma CSS framework.

The game starts on a field of NxM cells. Each player has their own starting location - for human player it is usually top left corner, for computer player - bottom right corner. Initial placing of mines is made in such a way that both players have several cells opened from the beginning, in order to avoid the situation when one should make a guesses too early. An important rule, which probably makes the whole sense of this variation of Minesweeper, is that it is possible to open or flag only those cells which border to your own territory. It prevents players from interrupting with each other and forces them to rely only on their skills (and a little bit of luck) in order to win.

### Computer player
One of the most challenging parts of the game was to implement the logic of Computer player. Computer player is the program that must be able to play the game of Minesweeper by analysing already opened cells and opening or flagging closed ones. Further I will describe how it was done step by step.

First, some context:

The game is represented by a `Game` class containing two-dimensional array of `Cell` and two methods - `openCell` and `flagCell`.
* `openCell` method sets the `Cell.opened` to `true` and checks if there is mine in that cell. If yes, then the player, who opened the cells, has exploded. If no, then it checks for cell's `neighboursMinesCount` property. If it is equal to 0, then it recursively opens all neighbours. As a result, it returns an array of Cells that have been opened.
* `flagCell` method sets `Cell.flagged` property to true.

```typescript
class Game {
    fieldWidth: number;
    fieldHeight: number; 
    cells: Cell[][] = [];

    openCell(cell: Cell): Cell[] {
        // open cell logic
    }

    flagCell(cell: Cell): void {
        // flag cell logic
    }
}

class Cell {
    x: number;
    y: number;
    neighbourMinesCount: number;
    hasMine = false;
    opened = false;
    flagged = false;
}
```
*Actually these classes contain a bit more data and logic, but we're interested only in these for now*

Before writing the code of `ComputerPlayer` let's specify some requirements for it. For this it is necessary to realise how we - humans - play Minesweeper game. A human looks at those cells that are opened and have one or more closed neighbour cells containing mines. Then they try to calculate or guess where these mines exactly are. All variations of placement of opened and closed cells with mines can be divided into three categories:
* a decision of opening/flagging certain cells can be done by analysing only one cell
* a decision of opening/flagging certain cells can be done by analysing several cells which have common closed neighbour cells
* a decision can be done by guessing

### Algorithm of Computer player

Thus high-level algorithm can be described as:
1. Identify opened cells which has closed neighbour mines.
2. Iterate through them and open/flag cells by analysing each individual cell until possible.
3. When there is no any progress in step two, try to analyse chunks of cells which has common neighbours and go to step 2 after first iteration.
4. When steps 2 and 3 didn't find any solution - try to guess one cell and go to step 2.
5. Continue this algorithm until the game is finished.

Now let's dive into details of each step.

Finding opened cells is easy - we need to iterate through all cells and take those which matches this criteria:
```typescript
cell.opened && cell.neighbourMinesCount > 0;
```
After that we need to iterate through them and analyse each cell until we stop finding any solution. That already becomes tricky. On every iteration a new cells might be (and most probably will be) opened or flagged, so we have to somehow include newly opened cells into the cycle of the fly. And if the cell has been resolved - meaning all it's neighbours either opened or flagged - then it should be removed from the list and not being taken into consideration anymore. Also it is not enough to iterate through the list only once, because if on the first iteration one particular cell couldn't be resolved, then on the second one there is a chance that it actually will.

It already becomes clear, that storing cells in a simple Array will not satisfy our needs. It will be too awkward to modify array size during iteration, and it is not possible to **conveniently** iterate throw it multiple times.

Let's list our requirements:
* we need to be able to iterate through the list multiple times
* we need to be able to add new items
* we need to be able to remove items

Which data structure would fit our needs then?

### Doubly linked list

From [Wikipedia](https://en.wikipedia.org/wiki/Doubly_linked_list):

*In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the sequence of nodes) and one data field.*

![Doubly linked list](https://dev-to-uploads.s3.amazonaws.com/i/f374fah7rvgcxw4j787k.png)

According to [Big O cheat sheet](https://www.bigocheatsheet.com/), insertion and deletion operations of Doubly linked list both has complexity of O(1). In comparison, same operations for Array has complexity of O(n).

Seems like exactly what we need! Unfortunately, Typescript doesn't have any implementation of Doubly linked list, so we need to create it ourselves.

The list consists of a nodes linked between each other. Let's define a `Node` class first:
```typescript
// to make it more independent, instead of using Cell class
// we use generic type T 
class Node<T> {
    value: T;
    next?: Node<T>;
    prev?: Node<T>;

    constructor(value: T) {
        this.value = value;
    }
}
```
... and create a DoublyLinkedList:
```typescript
class DoublyLinkedList<T> {
    private head?: Node<T>;
    private tail?: Node<T>;
}
```
For now, it contains only two properties - `head` and `tail` - references to the first and the last nodes in the list. Let's add method which adds a new node to the list - I called it `append` because it adds new node to the tail of the list.
```typescript
    append(node: Node<T>): void {
        // handle special case when the list is empty
        if (this.head === undefined) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
    }
```
Method `remove` is a little bit more complex - it is necessary to check whether references to `next` or `prev` are pointing to any `Node` class, and that node being removed isn't a current `head` or `tail` of the list:
```typescript
    remove(node: Node<T>): void {
        const prevNode = node.prev;
        const nextNode = node.next;

        if (prevNode !== undefined) {
            prevNode.next = nextNode;
        }
        if (nextNode !== undefined) {
            nextNode.prev = prevNode;
        }
        if (this.tail === node) {
            this.tail = prevNode;
        }
        if (this.head === node) {
            this.head = nextNode;
        }
    }
```
At this point we already have a structure which we can use for efficiently adding or removing nodes. What about iteration? We're going to use `Generator` for that:
```typescript
    *iterate(): Generator<Node<T>> {
        let node = this.head;
        while (node instanceof Node) {
            yield node;
            node = node.next;
        }
    }
```
Nice and simple! But wait, what about **iterate through the list multiple times** requirement? With current implementation of `iterate` method, it is possible to iterate the list only once - it will yield nodes from `head` to `tail` and then break. Can we do anything about it? Sure we can - we make our linked list **cycled**. We just link `tail` and `head` with each other:
```typescript
    private linkTailAndHead(): void {
        this.tail.next = this.head;
        this.head.prev = this.tail;
    }
```
That will make `iterate` method literally run around until the loop is interrupted outside. Of course that creates a potential for running into endless cycle issue, but we will handle that as well.
So the final implementation of the list is:
```typescript
class DoublyLinkedList<T> {
    private head?: Node<T>;
    private tail?: Node<T>;

    append(node: Node<T>): void {
        if (this.head === undefined) {
            this.head = node;
            this.tail = node;
            this.linkTailAndHead();
        } else {
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
            this.linkTailAndHead();
        }
    }

    remove(node: Node<T>): void {
        // handling the last item in the list
        if (node === this.tail && node === this.head) {
            this.tail.next = undefined;
            this.tail.prev = undefined;
            this.tail = undefined;
            this.head = undefined;
        }

        const prevNode = node.prev;
        const nextNode = node.next;

        if (prevNode !== undefined) {
            prevNode.next = nextNode;
        }
        if (nextNode !== undefined) {
            nextNode.prev = prevNode;
        }
        if (this.tail === node) {
            this.tail = prevNode;
        }
        if (this.head === node) {
            this.head = nextNode;
        }
    }

    *iterate(): Generator<Node<T>> {
        let node = this.head;
        while (node instanceof Node) {
            yield node;
            node = node.next;
        }
    }

    private linkTailAndHead(): void {
        this.tail.next = this.head;
        this.head.prev = this.tail;
    }
}
```
### Usage of Doubly linked list
At this point we've prepared a solid background for our solving algorithm. Let's utilise it!
```typescript
class ComputerPlayer {
    private game: Game;
    private cellsToAnalyze: DoublyLinkedList<Cell>;

    initialize(): void {
        this.cellsToAnalyze = new DoublyLinkedList<Cell>();
        for (let i = 0; i < this.game.fieldWidth; i++) {
            for (let j = 0; j < this.game.fieldHeight; j++) {
                const cell = this.game.cells[i][j];
                if (cell.isOpened() && cell.neighbourMinesCount > 0) {
                    this.cellsToAnalyze.append(cell);
                }
            }
        }
    }

    play(): void {
        let firstNoActionNode: Node<Cell>|undefined = undefined;
        for (let node of this.cellsToAnalyze.iterate()) {
            const cell = node.value;

            const flaggedNeighbourCellsCount = cell.getFlaggedNeighbourCellsCount();
            if (flaggedNeighbourCellsCount === cell.neighbourMinesCount) {
                for (let neighbourCell of this.game.iterateNeighbours(cell)) {
                    if (!neighbourCell.isOpened() && !neighbourCell.isFlagged()) {
                        firstNoActionNode = undefined;
                        const openedCells = this.game.openCell(new Node(neighbourCell));
                        for (let openedCell of openedCells) {
                            this.cellsToAnalyze.append(new Node(openedCell));
                        }
                    }
                }
                this.cellsToAnalyze.remove(node);

                continue;
            }

            let closedNeighbourCellsCount = 0;
            for (let neighbourCell of this.game.iterateNeighbours(cell)) {
                if (!neighbourCell.isOpened()) {
                    closedNeighbourCellsCount++;
                }
            }

            if (closedNeighbourCellsCount === cell.neighbourMinesCount) {
                for (let neighbourCell of this.game.iterateNeighbours(cell)) {
                    if (!neighbourCell.isOpened() && !neighbourCell.isFlagged()) {
                        firstNoActionNode = undefined;
                        this.game.flagCell(neighbourCell);
                    }
                }
                this.cellsToAnalyze.remove(node);

                continue;
            }

            if (node === firstNoActionNode) {
                break;
            }
            if (firstNoActionNode === undefined) {
                firstNoActionNode = node;
            }
        }
    }
}

const computerPlayer = new ComputerPlayer(game);
computerPlayer.initialize();
computerPlayer.playGame();
```
This is a complete implementation of step 2 of our solving algorithm. First we initialise the list of cells which we're going to analyse. Then in `play` method we start our loop, and on every iteration we do the following:
* if number of flagged neighbour cells equals to number of neighbour cells with mines, we open all remaining closed cells and append them to the list for further analysis
* if number of closed neighbour cells equals to number of neighbour cells containing mines, we flag these cells
*  notice the `firstNoActionNode` variable, it serves the role of loop breaker. The logic behind it can be described as "when we cycled through all nodes in the list and neither opening nor flagging of any cell has happened, then we need to break the loop"

Now we have an engine that can play the game pretty much efficiently. Let's see it in action :)
{% youtube 1_oQD6Xvpz0 %}

Awesome result! Although despite computer has stuck at the end of the video, experienced Minesweeper players could have noticed, that it is actually possible to continue the game. Unfortunately, our code isn't smart enough to analyse **combinations of cells**... yet. That is because only 2 of 5 steps of our solving algorithm has been implemented so far.

We're going to tackle remaining steps in the following posts.

Thank you for your attention!