Simple game algorithm checking if the move is valid

Question

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]

Answer 1

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.

Answer 2

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.