1

我正在做一个基于瓷砖的游戏。我尝试创建一个返回数组的方法，我的角色可以根据 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 相比。

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

十分感谢。

4

2 回答 2

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. 在这里“在范围内”是一个健全性检查，确保你没有超出范围（例如，假设你只需要得到一个正值，得到一个 -1 的 x 值。
于 2012-11-08T13:51:29.357 回答
0

尝试从元素（上、左、下、右）计算长度“moveLimit”的所有组合。

例如

UUU
UUL
UUD
UUR

ULL
ULD
ULR

UDD
UDR

URR

LLL
...

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

于 2012-11-08T13:34:35.400 回答