Algorithms Explained : Minesweeper Game

This blog post explains most critical algorithms for well-known windows oriented game, minesweeper:

Game Rules:

1. The board is a two dimensional space, which has a predetermined number of mines.
2. Cells has two states, opened and closed.
3. If you left-click on a closed cell:
1. Cell is empty and opened. 
1. If neighbour cell(s) have mine(s), this opened cell shows neighbour mine count.
2. If neighbour cells have no mine, all neighbour cells are opened automatically.
2. Cell has a mine, game ends with FAIL.
4. If you right-click on a closed cell, you put a flag which shows that "I know that cell has a mine".
5. If you multiclick (both right and left click) on a cell which is opened and has at least one mine on its neighbours:
1. If neighbour cells' total flag count equals to this multi-clicked cell's count and predicted mine locations are true, all closed and unflagged neighbour cells are opened automatically.
2. If neighbour cells' total flag count equals to this multi-clicked cell's count and at least one predicted mine location is wrong, game ends with FAIL.
6. If all cells (without mines) are opened using left clicks and/or multi-clicks, game ends with SUCCESS.

Data Structures:

We may think each cell as a UI structure (e.g. button), which has following attributes:

• colCoord = 0 to colCount
• rowCoord = 0 to rowCount
• isOpened = true / false   (default false)
• hasFlag    = true / false    (default false)
• hasMine  = true / false    (default false)
• neighbourMineCount  0 to 8  (default 0, count of total of mines on neighbour cells)

So, we have a two dimensional "Button[][] cells" data structure to handle game actions.

Algorithms:

Before Start:

1. Assign mines to cells randomly (set hasMine=true) .
2. Calculate neighbourMineCount values for each cell, which have hasMine=false. (this step may be done for each clicked cell while game continues but it may be inefficient)

Note1: Neighbour cells should be accessed with {(colCoord-1, rowCoord-1),(colCoord-1, rowCoord),(colCoord-1, rowCoord+1),(colCoord, rowCoord-1),(colCoord, rowCoord+1),(colCoord+1, rowCoord-1),(colCoord+1, rowCoord),(colCoord+1, rowCoord+1)} coordinates. And don't forget that, neighbour cell counts may be 3 (for corner cells), 5 (for edge cells) or 8 (for middle cells).

Note2: It's recommended to handle mouse clicks with "mouse release" actions instead of "mouse pressed/click" actions, otherwise left or right click may be understood as multi-clicks or vice versa.

Right Click on a Cell:

• If cell isOpened=true, do nothing.
• If cell isOpened=false, set cell hasFlag=true and show a flag on the cell. 

Left Click on a Cell:

• If cell isOpened=true, do nothing.
• If cell isOpened=false:
• If cell hasMine=true, game over.
• If cell hasMine=false:
• If cell has neighbourMineCount > 0, set isOpened=true, show neighbourMineCount on the cell. If all cells which hasMine=false are opened, end game with SUCCESS.
• If cell has neighbourMineCount == 0, set isOpened=true, call Left Click on a Cell for all neighbour cells, which hasFlag=false and isOpened=false.

Note: Last step may be implemented with recursive call or using a stack data structure.

Multi Click (both Left and Righ Click) on a Cell:

• If cell isOpened=false, do nothing.
• If cell isOpened=true:
• If cell neighbourMineCount == 0, no nothing.
• If cell neighbourMineCount > 0:
• If cell neighbourMineCount != "neighbour hasFlag=true cell count", do nothing.
• If cell neighbourMineCount == "neighbour hasFlag=true cell count":
• If all neighbour hasFlag=true cells are not hasMine=true, game over.
• If all neighbour hasFlag=true cells are hasMine=true (every flag is put on correct cell), call Left Click on a Cell for all neighbour cells, which hasFlag=false and isOpened=false.

Note: Last step may be implemented with recursive call or using a stack data structure.

Software Version Controlling Best Practices

Always use version controlling
Use version controlling/source control even if one developer exists. This issue brings change tracking and versioning of the application continuously. For multi developers, it brings more benefits like co-working on same files and fast codebase updates.

Do not commit halfdone work
Each commit should consist of a complete task (issue, bugfix, etc.). Partial commits may cause unfunctionality, crash of application or even compilation errors.

Full Update -> Build -> Run -> Full Commit rule

For having no trouble, a stable version controlling process should be applied. According to this process, you should full update the code, then build and run your application. If application runs correctly, you should commit all of your updated files. While committing, inspect all of your changed files and changes. If all team members apply this process, application will always continue to run and no one will prevent others work. 

Commit atomicity/granularity

Do not use version controlling system to backup each single file separately and do not commit hundreds of files after days or weeks of development. Commits should be atomic, and as a best practice, should include files which are related with only one task. Late commits also brings more conflicts.

Use descriptive commit messages

Commit messages are important for tracking changes. Descriptive commit messages help developers to control old versions of code within a functional context, instead of date and time only.

Don't commit generated files

Use "ignore" funcionalities of your version controlling tool to ignore commiting and updating of generated files (e.g. target folders, user settings, IDE generated files, generated classes after each build etc.) By doing this, you will not waste your time for managing those unstable/unimportant files.

Continuous integration

Use continuous integration along with version controlling. By doing that, perform automated builds and deploys to a specific location. Also, configure the tool to create a separate version number (with a predefined versioning algorithm, e.g. <major_changes>.<minor_changes>.<bug_fixes>) for each build. This will be useful to trace tests and deployments.

Use qualified version controlling tools and plugins (especially for merge)

Version controlling tool quality is also important. It must at least show changed files clearly, give ability to merge conflicted files easily and view old versions of files. Besides, it will be better to have a branching function to manage versions and and issue tracking system synchronization to manage issue-related code file matchings.

Use branches for testing and different lines of code

You should use different code branches for development, testing and also production. If a version of code is being tested, development should not continue on that branch. Development can continue on another branch and when a new version will be tested after fixing some bugs and adding new properties, a new test branch should be provided with a new version. When a stable test branch is reached, it may be released as a production branch.

You can also take a look at the below link for version controlling basics:
http://betterexplained.com/articles/a-visual-guide-to-version-control/

A Theorical Look into Object/Resource Pool Pattern

Definition:

Sometimes our software projects need costly object creations (database connections, socket connections, large graphical objects etc.). This cost may be about time and/or memory. Those objects may also be needed to be created frequently. At that moment, Object/Resource Pool pattern comes to help.

Object Pool pattern:

• Reuses unused costly objects without re-creating those objects (e.g. books in a library).
• May create objects eagerly before they are needed, to manage application performance.
• May limit created number of objects to manage application performance and user access.

Working principle:

Object Pool Class Diagram

Client requests an object (Reusable) from object pool. Object pool has a list of predefined reusables and gives an available one from pool. For the client's point of view, given reusable is a new object but it is probably (object creation strategies will be told later) a pre-created object with a new object's field values. For the optimum performance, client should notify object pool when reusable is no longer needed. Just in case client doesn't notify, object pool may define a timeout for each created reusable. Object pool must also have a synchronization mechanism for reusable serving, especially on multithreaded or multiuser applications.

When to use/Trade offs:

If objects are not costly, object pool pattern should not be used because this pattern needs clients to inform object pool (brings extra code complexity) and object creation management code (synchronization of pool, object creation limitation strategy etc.). This extra management code also brings a little performance loss. If performance gain of reusable object usage is bigger than extra management code performance loss, and application must frequently create those reusable objects, object pool pattern is recommended to be used.

Implementation Strategies:

    Object pool limit:

• If memory is limited and/or maximum number of clients are needed to be restricted, an object number limit value may be defined for object pool (limited pool).
• If there is no restriction, limit value is not needed (unlimited pool).
• If all object pool list is in use, new objects may be created (expanding pool) or client may be enforced to waiting (fixed pool).

   Eager/lazy creation:

• If application startup is performed infrequently and startup time is not very important, object pool list objects may be created at the startup (eager ceration).
• If no restrictions exist, no objects are needed to be created eagerly (lazy creation).
• Some number of objects may be created eagerly, others may be created lazily according to the application parameters (mixed creation).

    Empty object pool strategy:

• If object pool is expanding, create a new object and return it.
• If object pool is not expanding, return null or enforce client to wait until an object is ready to be given.

    Synchronization strategy:

• Object pool should have a synchronization mechanism for object serving. Otherwise, especially on multiuser systems, pooling system may fail.

    Unused object strategy:

• Usage of the pool objects may be lower than expected in some cases. Object pool may have a pool object removing strategy (i.e. descreasing object limit) for increasing performance.

    Returning object strategy:

• Clients should return pool objects back to the pool after their job is completed. But pool code can't control this and poor client code may return pool objects. For this situation, object pool may have a timer mechanism for given but unused pool objects.

According to the project requirements, some of those strategies or mixed versions should be selected and implemented for object pool. But "reusing available objects" principle is the key and can not be changed for any implementation strategy.

Example Implementations will exist on the next post.