Is there an efficient algorithm for calculating which tiles are within a set walking distance of your character in a 2d grid?

Question

Lets say that on a 2d grid of 20x20, you have your character at position (5,5).

He is able to walk up to 4 tiles in his move. However, there may be obstacles blocking your path such as a wall.

Is there any efficient / easy way for calculating exactly which tiles he would be able to walk to without checking every single possible move ( e.g. move up 0 and right 0 then move up 0 and right 1 e.t.c )?

At the moment I'm calculating the places that you can walk through with this horrific thing:

int playerx = GridPane.getRowIndex(button);
int playery = GridPane.getColumnIndex(button);
int position = playery*8+playerx;

for (int i = 0; i < 5; i++)
{
    for (int j = i-4; j < 5-i; j++)
    {
        try
        {
            int expectedCollumn  = playerx+j;
            int actualCollumn = ((position+i+j*8)-((position+i+j*8)%8))/8;
                if(expectedCollumn==actualCollumn)
                {
                    Button temp = (Button)gridPane.getChildren()
                                  .get(position+i+j*8);
                    if (!temp.getText().equals("W")  && 
                        !temp.getText().equals("P"))
                    {
                        temp.setText("T");
                    }
                }
                actualCollumn = ((position-i+j*8)-((position-i+j*8)%8))/8;
                if(expectedCollumn==actualCollumn)
                {
                    Button temp2 = (Button)
                    gridPane.getChildren().get(position-i+j*8);
                    if (!temp2.getText().equals("W") && 
                        !temp2.getText().equals("P"))
                    {
                        temp2.setText("T");
                    }
                }
        }
    }
}

However, its showing as if you are able to walk to the otherside of the wall and I'm not sure how I would go about fixing this.

Many thanks in advance.

Not sure about how your algorithm is supposed to work, but assuming you've got a efficient way of listing the unobstructed neighbors it should be possible to modify any pathfinding algorithm to simply ignore nodes with distances greater than 4. At 41 nodes to consider there shouldn't be much point in optimizing the algorithm asuming the path-finding algorithm was decent to begin with... — fabian, Jan 12 '19 at 21:25
I dont have a way of listing the unobstructed neighbours which is what Im trying to figure out - sorry if the post is confusing — Aliator, Jan 12 '19 at 21:43
The game cited [here](https://stackoverflow.com/a/20600275/230513) illustrates one approach. — trashgod, Jan 12 '19 at 23:35
Thanks for the comment but I'm not sure I understand how that applies to my problem:| — Aliator, Jan 13 '19 at 02:18

score -1 · Answer 1 · answered Jan 14 '19 at 17:17

-1

For path finding, you should figure out how this works:

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

and then move on to A* or something more efficient.

answered Jan 14 '19 at 17:17

EverNight

964
7
16

score -1 · Accepted Answer · answered Jan 15 '19 at 00:54

Thanks to everyone that answered but the solution was simple

incase somehow someone finds this post and is interested it was a simple recursive call

void getReachableTiles(Tile current, Int stamina, List<Tile> visited, List<Tile> reachable) {
    if (stamina <= 0) return;

    List<Tile> neighbours = new List<>(current + up, current + left, ..)

    for (Tile t in neighbours) {
        if (!visited.contains(t)) {
            visited.append(t);
            if (!t.isWall()) {
                reachable.append(t);
                getReachableTiles(t, stamina - 1, visited, reachable);
            }
        }
    }
}

Is there an efficient algorithm for calculating which tiles are within a set walking distance of your character in a 2d grid?

2 Answers2