Search code examples
javafxgrid2dfxml

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


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.


Solution

  • 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);
                }
            }
        }
    }