在游戏板上找到我可以移动到的位置的算法

Question

我遇到的问题如下(简化):

• 我有一 block 板，表示为 n x m 方 block 的矩阵(n 可能等于 m)
  
• 里面有p个棋子
  
• 每个游戏 block 都有一个预定义的速度，即轮到它可以走多少步
  
• 片段不能重叠
  
• 共有三种类型的格子:不需要额外移动即可通过的单元格(通过时您会失去 0 额外速度)，需要 1 次额外移动才能通过的单元格以及您根本无法通过的单元格穿过(像一堵墙)
  

因此，在我的游戏板中的某个 [i,j] 位置给定一个游戏 block ，我想找出:
a) 它可以移动到的所有地方，以它的速度
b) 棋盘中某个[k,l]位置的路径

a) 解决了，b) 几乎是微不足道的。目前我正在使用的算法如下，假设一种语言，其中大小为 n 的数组从 0 到 n-1:

• 创建一个 speed*2+1 大小的正方形矩阵，表示移动的成本，就好像所有单元格都没有额外的成本要穿过(棋子在位置 [speed, speed] 上)
  <
• 创建另一个大小为 speed*2+1 的方阵，其中包含每个单元格的额外成本(那些不能穿过的方阵，因为它要么是墙，要么其中有另一 block 的值是无限的)(棋子在 [speed, speed] 位置)
  
• 创建另一个speed*2+1大小的方阵，它是前两者的和(棋子在位置[speed, speed])
  
• 修正后一个矩阵，确保每个单元格的值是:所有相邻单元格的最小成本 + 1 + 该单元格的额外成本。如果不是，我会更正它并从头开始使用矩阵。

一个例子:
P 是棋子，W 是墙，E 是不需要额外移动的空单元格，X 是不需要额外移动的单元格需要 1 个额外的 Action 才能越过。

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) 点。

请注意，我想要最优解，所以我使用了动态规划算法。随机行走者会更好吗？据我所知，这个解决方案(目前)还没有失败，但我没有证明它的正确性，我想确保它有效。

Answer 1

A-star 是一种标准算法，用于确定二维板上障碍物的最短路径和每平方移动成本。您还可以使用它来测试特定移动是否有效，但要实际生成所有有效移动，我只需从起始位置开始，在每个方向上移动一个方 block 标记，哪些方 block 是有效的，然后从您的每个新方 block 重复确保不再访问同一个广场的地方。这将是一个递归算法，每次调用最多调用自己 4 次，并将有效地生成有效的移动。如果有限制，比如您可以一次移动多少个方格，成本不同，只需传递您为每个方格走了多远的总和。