我遇到的问题如下(简化):
- 我有一个棋盘，表示为 n x m 方格的矩阵(n 可能等于 m)
- 里面有p个游戏 block
- 每个游戏 block 都有一个预定义的速度，即它每轮可以走多少步
- 各个部分不能重叠
- 共有三种类型的单元格:不需要额外移动的单元格(通过时您失去 0 额外的速度)、需要 1 额外移动才能穿过的单元格以及您根本无法获得的单元格穿过(如墙)
因此，给定游戏板中某个 [i,j] 位置的游戏 block ，我想找出:
a)以其速度可以移动到的所有地方
b) 到达棋盘中特定[k,l]位置的路径
解决了 a) 后，b) 几乎是微不足道的。
目前我正在使用的算法如下，假设一种语言，其中大小为 n 的数组从 0 到 n-1:
- 创建一个速度*2+1大小的方阵，表示移动的成本，就好像所有单元格都没有额外的穿越成本(棋子位于位置[速度，速度])
< - 创建另一个速度*2+1大小的方阵，其中包含每个单元的额外成本(那些无法跨越的成本，因为它是一堵墙，或者其中有另一 block ，其值为无穷大)(棋子位于[速度，速度]位置)
- 再创建一个速度*2+1大小的方阵，其大小为前两者之和(该棋子位于[速度，速度]位置)
- 修正后一个矩阵，确保每个单元格的值是:所有相邻单元格的最小成本 + 1 + 该单元格的额外成本。如果不是，我会更正它并重新从矩阵开始。
示例:
P 是碎片，W 是墙壁，E 是不需要额外移动的空单元，X 是需要额外移动的单元。需要 1 额外移动才能跨越。
X,E,X,X,X
X,X,X,X,X
W,E,E,E,W
W,E,X,E,W
E,P,P,P,P
第一个矩阵:
2,2,2,2,2
2,1,1,1,2
2,1,0,1,2
2,1,1,1,2
2,2,2,2,2
第二个矩阵:
1,0,1,inf,1
1,1,1,1,1
inf,0,0,0,inf
inf,0,1,0,inf
0,inf,inf,inf,inf
总和:
3,2,3,3,3
3,2,2,2,3
inf,1,0,1,inf
inf,1,2,1,inf
inf,inf,inf,inf,inf
由于 [0,0] 不是 2+1+1，我更正它:
总和:
4,2,3,3,3
3,2,2,2,3
inf,1,0,1,inf
inf,1,2,1,inf
inf,inf,inf,inf,inf
由于 [0,1] 不是 2+1+0，我更正它:
总和:
4,3,3,3,3
3,2,2,2,3
inf,1,0,1,inf
inf,1,2,1,inf
inf,inf,inf,inf,inf
由于 [0,2] 不是 2+1+1，我更正它:
总和:
4,2,4,3,3
3,2,2,2,3
inf,1,0,1,inf
inf,1,2,1,inf
inf,inf,inf,inf,inf
哪一个是正确答案？
我想知道的是这个问题是否有一个我可以搜索的名称(找不到任何东西)，或者是否有人可以告诉我如何解决a)点。
请注意，我想要最佳解决方案，因此我采用了动态规划算法。随机游走者可能会更好吗？ AFAIK，这个解决方案还没有失败，但我没有证明它的正确性，我想确保它有效。
最佳答案
A-star 是一种标准算法，用于确定二维板上的障碍物和每平方移动成本的最短路径。您还可以使用它来测试特定的移动是否有效，但要实际生成所有有效的移动，我只需从起始位置开始，在每个方向上移动一个有效的方格，然后从每个新的方格开始重复确保不要再次访问同一个广场。它将是一个递归算法，每次调用最多调用自身 4 次，并将有效地生成有效的移动。如果存在诸如一次可以以不同成本移动多少个方格之类的限制，只需传递每个方格已移动距离的运行总和即可。
关于在游戏板中查找我可以移动到的位置的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37909575/