我正在尝试解决从开始到结束在网格上移动对象的问题。我很清楚A *寻路算法,但是对于如何修改它却一无所知,因此它可以解决我的问题:
我有一个WxH网格。我需要将星形框移动到空框位置(它们始终处于相同位置:0,0和W-1,H-1)。我的出发点是空的(W-1,H-1),我迈出的每一步都是非对角的。如果我向上移动,则需要将阻碍自己前进的盒子向下移动到空白处,依此类推,直到到达恒星(0,0),然后我需要以相同的方式向起点移动。为了使事情变得更容易,恒星的运动总是朝着起点的方向进行,并且永远不会偏离起点。我需要找到最短的路线,也就是将恒星移到起始位置所需的最短步骤。
这显然是最短路径的问题(也许是A *),但是我无法弄清楚这里需要的修改。我不是在寻找解决方案或答案,而只是在寻找方向,因为我对应该从哪里开始感到迷茫。
P.S。网格中可能也有固定的盒子,但是一旦我理解了问题本身的算法,我就可以解决这个问题