瓷砖运动范围生成模式

Question

我正在做一个基于瓷砖的游戏。我尝试制作一种返回数组的方法，我的角色可以根据x，y坐标和移动限制移动。

例如，如果我输入电流置置：（3,3）movelimit：1

那么它应该给我退还（（3,2），（3,2），（3,4），（4,3））

，如果我输入CurrentPosition：（3,3）Movelimit：2

然后应该返回（（3,1），（2,2），（3,2），（4,2），（1,3），（2,3），（4,3），（4,3），（4,3），（5,3），（2,4），（3,4），（4,4），（3,5））

我计划通过在x和y上使所有可能的-1和 1都可以使用递归方法。但这是非常低效的，因为可能发生许多重复情况，例如 1 -1与-1相比 1。

有人知道是否有任何好的模式？

非常感谢。

Answer 1

让我们首先定义问题以及您正式寻找的内容：

将 k表示为距离，而 (x,y)作为原点点（源）。

f((x,y),k) = { (a,b) | abs(x-a) + abs(y-b) <= k } 

这意味着，一个具有所有点（a，b）的集合，因此： abs(x-a) + abs(y-b) <= k（这是距离限制）

现在，要获取所有可以执行的相关元素：

moves((x,y),k):
  for i=0 to k+1: //number of steps in the x axis, some number between 0 to k inclusive
     //number of steps in the y axis, some number between 0 to k-i inclusive:
     for j=0 to k-i+1: 
        if (x-i,y-j) is in range: output (x-i,y-j)
        if (x+i,y-j) is in range: output (x+i,y-j)
        if (x-i,y+j) is in range: output (x-i,y+j)
        if (x+i,y+j) is in range: output (x+i,y+j)

注意：

1. 这可以保证条件，因为您在两个轴上检查所有可能的步骤，并限制abs(a-x) + abs(b-x) <= k
2. 在此处" IS in in range"是一项理智检查，请确保您不会摆脱束缚（例如，获得-1的X值，假设您只需要获得正值。

Answer 2

尝试从元素（向上，左，向下，右）计算所有长度" movelimit"的组合。

，例如

UUU
UUL
UUD
UUR
ULL
ULD
ULR
UDD
UDR
URR
LLL
...

这应该已经大量减少了计算数量。您仍然可能会以不同的动作组合最终导致相同位置。