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

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

感谢所有回答的人，但解决办法很简单

万一有人发现了这篇文章，并对它感兴趣，那只是一个简单的递归调用

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/Dijkstras_算法

然后转向A*或更有效的东西。