Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Minesweeper algorithm

 
Duran Harris
Ranch Hand
Posts: 608
Eclipse IDE Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi...

This may not be a puzzle in you eyes,but I'm no math guru.So the situation is that I designed a minesweeper game(in Javascript)..Now as you know when a tile is clicked that has no mines surrounding it,the program will continue to evaluate and reveal surrounding tiles in all directions resulting in a polygon with a perimeter defined by tiles that are touching mines(possibly with isolated mines forming islands).
I had a version working which had logic along the following lines:

If a tile is clicked,it's coordinates are passed to the recursive(reveal) function.The function checks all 8 surrounding tiles and passes each tile that has no surrounding mines back to the recursive(well not really recursive,but it does call itself :p)And so in turn each surrounding tile will be checked in this manner.
Problem is though,when I made the game I didn't realise that Javascript was object-oriented!So when I discovered this,I decided to re-write the minesweeper game...but now it's days later and I can't seem to get my reveal function to work....I always get a too much recursion error.

So I have 2 options(one of which might not be valid):

1-Make the recursive method reveal an inner function(because apparently in javascript,a recursive inner function is not repeatedly(compiled?) with each invocation...hence,possibly allowing my method to run to completion.
OR
2-Could someone please give me a functional algorithm to do so?I've googled it,but I only came across a Java game that had very heavy syntax(ternary operators everywhere!)and minesweeper solving algorithms.

Arg,maybe I should make chess instead
 
Ulf Dittmer
Rancher
Posts: 42967
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I always get a too much recursion error.

That sounds like the condition for ending the recursion isn't being triggered (or the condition isn't correct). For each tile you should only recurse for adjacent tiles that have not been checked yet after the last click. So you need to keep track of which tiles have been checked already, regardless of whether the result was to reveal them or not.
 
Duran Harris
Ranch Hand
Posts: 608
Eclipse IDE Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes,there is no base case to stop the recursion..I can't think of the criteria that need to be meet for recursion to stop.I tried to do what you say but then the result that I get is that only the 8 surrounding tiles get revealed....ie.they have all been marked as checked resulting in them not being checked again.
The revealed tiles sort of form a barrier:
TTTT
000T
0x0T
000T
TTTT

In this case no further tiles can/will be checked .... Another solution that I investigated was performing a check on 8 compass directions...resulting in a star shape,but the further away that the revealing stops the bigger the gaps of unchecked tiles that occur ie:
 
Ulf Dittmer
Rancher
Posts: 42967
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Each recursive call should in turn check its 8 surrounding tiles. Of those, either 3 (for a NW/NE/SW/SE tile) or just 1 (for a W/N/S/E tile) should trigger further recursions - assuming those tiles are still covered, and that they haven't been marked checked by previous calls.
 
vaibhav mishra
Ranch Hand
Posts: 168
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I had developed same program using recursive algorithm
the sources can be found at project page
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic