我正在做一个基于图 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 相比。
有人知道这是否有好的模式吗?
非常感谢。
最佳答案
让我们首先正式定义问题和您要寻找的内容:
表示 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)
注意:
- 这保证了条件,因为您在
abs(a-x) + abs(b-x) <= k
的限制下检查了两个轴上的所有可能步骤。 - 这里的“在范围内”是一种合理性检查,确保您没有超出范围(例如,假设您只需要获得正值,则获得 -1 的 x 值。
关于algorithm - 瓷砖移动范围生成图案?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13289526/