是否有一种有效的算法来计算哪些图块在二维网格中角色的设定步行距离内？

Question

假设在 20x20 的二维网格上，您的角色位于位置 (5,5)。

他最多可以走 4 个方块。但是，可能有障碍物挡住您的路径，例如墙壁。

是否有任何有效/简单的方法来准确计算他可以走到哪些地块而不检查每一个可能的移动（例如向上移动 0 和向右移动 0 然后向上移动 0 和向右移动 1 e.t.c )?

目前我正在计算你可以带着这个可怕的东西走过的地方：

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

对于路径查找，您应该弄清楚它是如何工作的：

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

然后继续学习 A* 或更高效的东西。

Answer 2

感谢所有回答的人，但解决方案很简单

万一有人发现了这个 post 并且感兴趣它是一个简单的递归调用

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?

grid

2d

javafx

fxml