Go game surrounding detection

Go game surrounding detection
0.0 0

#1

Hi, i’m making a game based on a board game called go, but i just can’t figure out how could i detect that a tile or area is surrounded with enemy tiles.

in the image the red ones are enemies and red ones are not, so how could i detect that the blue ones are surrounded with red ones like in the picture. i was thinking of some kind of system that gives an id to every move and every tile has a status of tiles surrounding it.


#2

Off the top of my head, I would use a graph. If you are unfamiliar with what a graph is in programming, here’s some info: https://en.wikibooks.org/wiki/A-level_Computing/AQA/Paper_1/Fundamentals_of_data_structures/Graphs Basically it’s a collection of objects that are connected together, typically used for searching said collection.

Basically, give each space a checked boolean value (set to false by default), and search for an unoccupied space by choosing a starting space, and then returning “found” if the space is unoccupied, returning “not found” if the space has checked set to true or the space belongs to the other player, or setting checked for the space to true and repeat this for each space connected to this space, returning “found” if any of those spaces returned “found” or returning “not found” if none of those spaces returned “found”. Once you have finished searching, reset all checked values back to false.

To set this up, you just have to give each space a checked boolean, a value indicating if the space is unoccupied or which player occupies it, and which spaces it is connected to.


#3

Thak you very much, this solved my problem.:grinning:


#4

I really don’t understand the concept of graph well enough, do you know any good examples of graphs, i didn’t find any


#5

I recommend learning about Graphs at some point, because they are useful and interesting, but I guess you can use an easier method for now.

Try this:

  1. Make each space on your board an object, called something like Space. (If you are using Sprite objects to represent your spaces, then consider creating a subclass of Sprite and adding these variables to it.) Each Space object should have a bool called something like checked (set to false by default) and an integer to indicate which player controls the space, called something like player (set to -1 by default.) You will need to either store your Space objects in a way where you know the spaces around it, or you need to store references to the spaces around it in the Space object itself.
  2. Create a function called something like searchForUnoccupied. This function will take a Space object that belongs to the group you want to check if surrounded, and an integer to indicate which player controls the piece you are checking. The function returns false if the spaces are not surrounded and true if they are.
  3. Make searchForUnoccupied do this, in this order:
  • If the checked value of the Space is true, return true.
  • Set checked for the Space to true.
  • If player for the Space set to -1, return false.
  • If player for the Space is different from the player parameter, return true.
  • Call searchForUnoccupied for each Space connected to the current Space and using the player parameter you already have for the call. If any of these calls return false, then return false. Otherwise, return true.
  1. Whenever whoever controls a Space changes, remember to change its player variable to its new controller.

When you want to check if a group is surrounded:

  1. Choose a Space in the group and call searchForUnoccupied with that Space and the integer of the player who controls it. If the function returns true, the group is surrounded. Otherwise, if the the function returns false, the group is not.
  2. After the search is complete, reset the checked value of each Space to false.

I’m doing this off the top of my head, so hopefully it should work. Feel free to ask questions if this doesn’t make sense.


#6

Try flood fill algorithm


#7

Thank you very much this helped me so much, thank you.:grinning: