algorithm - 瓷砖移动范围生成图案？

Question

我正在做一个基于图 block 的游戏。我尝试创建一个方法，该方法返回一个数组，我的角色可以根据 x、y 坐标和移动限制移动该数组。

例如，如果我输入 currentPosition:(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), (5,3),(2,4),(3,4),(4,4),(3,5))

我计划通过在 x 和 y 上使所有可能的 -1 和 +1 来使用递归方法。但效率很低，因为可能会出现很多重复的情况，例如 +1 然后 -1 与 -1 然后 +1 相比。

有人知道这是否有好的模式吗？

非常感谢。

Answer 1

让我们首先正式定义问题和您要寻找的内容:

表示 k作为距离和(x,y)作为原点(source)。

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. 这里的“在范围内”是一种合理性检查，确保您没有超出范围(例如，假设您只需要获得正值，则获得 -1 的 x 值。