Get all possible destinations of an object in a game

[Mason Wyatt]

I have a matrix that represents a grid and would like to find out all possible places an object can move to.

An object can only move horizontally or vertically.

Let's assume that the example below is the grid I'm looking at, which is represented as a 2d matrix. The object is the *, the 0s are empty spaces that an object can move to, and the 1s are walls which the object cannot jump over or go on to.

What is the best way to find all possible movements of this object provided that it can only move horizontally or vertically?

I'd like to print a message saying: "There are 9 places the object can go to." The 9 is for the example below, but I would like it to work for any configuration of the below grid. So all I have to do is give the current coordinates of the * and it will give me the number of possible positions it can move to.

A thing to note is that the *'s original position is not considered in the calculations, which is why for the example below the message would print 9 and not 10.

I have a isaWall method that tells me if the cell is a wall or not. The isaWall method is in a Cell class. Each cell is represented by its coordinates. I looked into using Algorithms like BFS or DFS, but I didn't quite understand how to implement them in this case, as I am not too familiar with the algorithms. I thought of using the Cells as nodes of the graph, but wasn't too sure how to traverse the graph because from the examples I saw online of BFS and DFS, you would usually have a destination node and source node (the source being the position of the *), but I don't really have a destination node in this case. I would really appreciate some help.

00111110
01000010
100*1100
10001000
11111000

[Carey Brown]

This is a good problem to solve using recursion. I would add another field, hasVisited, to your Cell class, so that as you attempt to find adjacent cells that you can move to, you eliminate both Wall cells and Visited cells.

[Winston Gutkowski]

Samantha Rupasingha wrote:An object can only move horizontally or vertically.

OK, then I'm confused, because in the example you gave, even if '*' can move any distance (and assuming a '1' means a wall), the number of places it can move to is 4 unless you ALSO include any combination of valid vertical and horizontal moves from each endpoint.

Either way, I'd say that Carey's solution is a darn good place to start.

Winston