Есть ли эффективный алгоритм для расчета, какие плитки находятся в пределах установленного расстояния ходьбы вашего персонажа в 2-мерной сетке?

Question

Допустим, на двумерной сетке 20x20 ваш персонаж находится в позиции (5,5).

Он может пройти до 4 плиток за ход. Однако, могут быть препятствия, блокирующие ваш путь, такие как стена.

Есть ли эффективный / простой способ точно рассчитать, по каким плиткам он сможет ходить, не проверяя каждое возможное движение (например, подняться на 0 и вправо на 0, затем на 0 и вправо на 1 и т. Д.)?

В данный момент я вычисляю места, через которые вы можете пройти с этой ужасной вещью:

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

Тем не менее, это показывает, что вы можете идти к другой стороне стены, и я не уверен, как бы я это исправил.

Большое спасибо заранее.

Answer 1

Спасибо всем, кто ответил, но решение было простым

если кто-то найдет этот пост и заинтересован, это был простой рекурсивный вызов

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

Answer 2

Для поиска пути вы должны выяснить, как это работает:

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

и затем перейдите к A * или к чему-то более эффективному.