瓷磚移動範圍生成模式？

我正在做一個基於瓷磚的遊戲。我嘗試做一個方法，返回一個我的角色可以根據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。

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

非常感謝。

來源

2012-11-08 Brian Lin

讓我們先來定義問題，你正在尋找正式：

表示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)

注：

這是因爲你檢查所有可能的步驟，在這兩個軸系W¯¯保證條件限制abs(a-x) + abs(b-x) <= k
在這裏「是在範圍內」是一個健全的檢查，確保你沒有超出限制（例如，得到一個x值爲-1，假設你需要得到一個正值只要。

來源

2012-11-08 13:51:29 amit

非常感謝你^^現在我可以繼續：D –

請注意，這將返回（（3,2），（2,3），（3,4），（4,3）*和（3,3）*）。 – Vortexfive

@Vortexfive：正如它應該的那樣。我讀取「移動限制」作爲可能移動的最大數量，並且0是包含的。通過「跳過」'i = j = 0'，可以輕鬆解決。但是 - 它會輸出'（3,3）'幾次（確切地說，4），如果這是一個問題，應該特別檢查這個特定的情況。 – amit

嘗試從元素（UP，LEFT，DOWN，RIGHT）計算長度「moveLimit」的所有組合。

E.g.

UUU 
UUL 
UUD 
UUR 

ULL 
ULD 
ULR 

UDD 
UDR 

URR 

LLL 
...

這應該已經減少了很多計算次數。你仍然可能會得到不同的移動組合，導致相同的位置。

來源

2012-11-08 13:34:35 Vortexfive

瓷磚移動範圍生成模式？

回答

相關問題