12

I'm programming my first game and I have one last problem to solve. I need an algorithm to check if I can move a chosen ball to a chosen place.

Look at this picture:

The rule is, if I picked up the blue ball on the white background (in the very middle) I can move it to all the green spaces and I can't move it to the purple ones, cause they are sort of fenced by other balls. I naturally can't move it to the places taken by other balls. The ball can only move up, down, left and right.

Now I am aware that there is two already existing algorithms: A* and Dijkstra's algorithm that might be helpful, but they seem too complex for what I need (both using vectors or stuff that I weren't taught yet, I'm quite new to programming and this is my semester project). I don't need to find the shortest way, I just need to know whether the chosen destination place is fenced by other balls or not.

My board in the game is 9x9 array simply filled with '/' if it's an empty place or one of the 7 letters if it's taken.

Is there a way I can code the algorithm in a simple way?

[I went for the flood fill and it works just fine, thank you for all your help and if someone has a similar problem - I recommend using flood fill, it's really simple and quick]

gsamaras
  • 71,951
  • 46
  • 188
  • 305
Ania
  • 450
  • 4
  • 14
  • 9
    depth first search or breadth first search will both work fine. – NoSenseEtAl Aug 31 '17 at 08:59
  • 11
    You are basically looking for the _flood fill algorithm_, google that. Even the most naive implementation of the algorithm will be good enough for a 9x9 grid. – Jabberwocky Aug 31 '17 at 08:59
  • Since you said that you weren't told what a vector is, this is most basic stuff. If you are really, REALLY in a hurry, skip it, but otherwise what you really should do is to read some basic tutorials. How is your field stored without vectors (or other STL containers)? In a raw array? Those will easily cause trouble for you in the future. – Aziuth Aug 31 '17 at 09:12
  • @Aziuth A square game board is one of the *very few* places where `std::vector` is distracting over `std::array`. I would recommend using `std::array, 9>` for *this* example. `char[9][9]` is too easy to confuse for a string. – Caleth Aug 31 '17 at 09:39
  • @dtech: A question with relevant picture, prior research done into algorithms that are indeed technically correct but overkill for the limited input size? There are plenty of non-beginners still asking worse questions. – MSalters Aug 31 '17 at 14:27
  • @Caleth That's why I wrote "(or other STL containers)". But yeah, `std::array` is the better fit. That said, in your example, I'd replace `char` by some enum class, since `char` has the intrinsic meaning of being a letter. Like `enum class Field : unsigned char {Empty, Green, Red, Blue};` – Aziuth Sep 01 '17 at 09:37

2 Answers2

11

I suggest using Flood fill algorithm:

Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to fill connected, similarly-colored areas with a different color, and in games such as Go and Minesweeper for determining which pieces are cleared. When applied on an image to fill a particular bounded area with color, it is also known as boundary fill.

In terms of complexity time, this algorithm will be equals the recursive one: O(N×M), where N and M are the dimensions of the input matrix. The key idea is that in both algorithms each node is processed at most once.

In this link you can find a guide to the implementation of the algorithm.

More specifically, as Martin Bonner suggested, there are some key concepts for the implementation:

  1. Mark all empty cells as unknown (all full cells are unreachable)
  2. Add the source cell to a set of routable cells
  3. While the set is not empty:
    • pop an element from the set;
    • mark all adjacent unknown cells as "reachable" and add them to the set
  4. All remaining unknown cells are unreachable.

PS: You may want to read Flood fill vs DFS.

Martin Bonner supports Monica
  • 28,528
  • 3
  • 51
  • 88
gsamaras
  • 71,951
  • 46
  • 188
  • 305
4

You can do this very simply using the BFS(Breadth First Search) algorithm.

For this you need to study the Graph data structure. Its pretty simple to implement, once you understand it.

Key Idea

Your cells will act as vertices, whereas the edges will tell whether or not you will be able to move from one cell to another.

Once you have implemented you graph using an adjacency list or adjacency matrix representation, you are good to go and use the BFS algorithm to do what you are trying to do.

wchargin
  • 15,589
  • 12
  • 71
  • 110
Sumeet
  • 8,086
  • 3
  • 25
  • 45
  • I find it consfusing that you use `code formatting` for non code – 463035818_is_not_an_ai Aug 31 '17 at 09:13
  • @gsamaras I hope I am not complaining too much, just trying to give suggestions. Anyhow, `O(NxN)` obvisouly isnt code, but `vertices` and `edges` looks like it is refering to some specific type or variable name, when I understand it as refering to the abstract concept of vertices and edges that dont need special formatting – 463035818_is_not_an_ai Aug 31 '17 at 09:44
  • 1
    @gsamaras yeah i like both answers, and I do like the question. I find it quite interesting, because I never had the chance to try BFS or Flood Fill. I am curious to try it and both your answers will be a nice starting point. Unfortunately its not something I can do during working hours ;) – 463035818_is_not_an_ai Aug 31 '17 at 09:50
  • Hi Sumeet—in English the convention is to use either **bold** or *italics* when you're emphasizing something or defining a new term. (For instance: "A *dog* is a wolf-like animal with four legs.") It is never correct to use code formatting for something that's not code. I've fixed your post for you. – wchargin Aug 31 '17 at 12:48
  • @wchargin Ok, will be careful in the future. – Sumeet Aug 31 '17 at 12:48
  • 1
    Downvoter, care to explain as to why you did not like the answer. – Sumeet Aug 31 '17 at 13:58