確定2D網格上的所有相鄰空間

Question

我似乎無法找到解決我正在處理的這個問題的好方法。

假設我有上描述的字符（棋盤遊戲）的位置的2D網格上的點：現在

        [n,m] 

，每個轉我可以根據一個擲骰子移動字符（1 ，2,3 ...），我想找出角色可以移動的所有可能的方式。

移動字符一旦裝置僅改變n或m其中對角線移動記爲2個運動（即[N + 1，M]移動一次，[N + 1，M + 1]移動兩次）。

例如，如果我搖一2，那麼所有可能的走勢是：

        [n,m+2] 
         [n-1,m+1][n,m+1][n+1,m+1] 
        [n-2,m][n-1,m][n,m][n+1,m][n+2,m] 
         [n-1,m-1][n,m-1][n+1,m-1] 
           [n,m-2] 

我似乎無法得到這個明確的算法。

我至今爲Daniel Lew

position = [3,2] #position 
n = 2 #number of moves allowed 
for i in range(position[0]-n,position[0]+n): 
    for j in range(position[1]-n,position[1]+n): 
     if abs(position[0]-i) + abs(position[1]-j) <= n: 
       print i,j,'works\n' 

另一項建議然而，它錯過了[n][m+2],[n+2,m]（或辦法，我寫的懷念它）。

任何建議爲簡明的答案或修復？

Answer 1

穿過（傾斜）菱形線並轉換成法線座標。 Python代碼

n = 2 #number of moves allowed 
for i in range(0, n+1): 
    for j in range(0,n+1): 
     print i + j - n, i - j,'\n' 

替代做法：你可以沿着兩個方向n範圍的第一個座標偏移。如果剩下一些動作（movesleft），則可以使用movesleft步驟沿任意方向沿第二個座標移動。第二階段必須保持奇數（奇偶校驗？），所以使用第二步。

僞

n_moves = 2 
for dy = -n_moves to n_moves do 
    movesleft = n_moves - Abs(dy) 
    for dx = - movesleft to movesleft] step 2 do 
     make_turn(pos_x + dx, pos_y + dy)  

對於n

Delphi代碼= 2和n = 3給出的結果

var 
    n, ml, dx, dy: Integer; 
begin 
    n := 3; 
    for dy := - n to n do begin 
    ml := n - Abs(dy); 
    dx := - ml; 
    repeat 
     Memo1.Lines.Add(Format('[%d, %d]', [dy, dx])); 
     dx := dx + 2; 
    until dx > ml; 

    end; 
[-2, 0] 
[-1, -1] 
[-1, 1] 
[0, -2] 
[0, 0] 
[0, 2] 
[1, -1] 
[1, 1] 
[2, 0] 

[-3, 0] 
[-2, -1] 
[-2, 1] 
[-1, -2] 
[-1, 0] 
[-1, 2] 
[0, -3] 
[0, -1] 
[0, 1] 
[0, 3] 
[1, -2] 
[1, 0] 
[1, 2] 
[2, -1] 
[2, 1] 
[3, 0] 

第一方法（相同的結果以另一順序）：

for i := 0 to n do 
    for j := 0 to n do begin 
     dx := i + j - n; 
     dy := i - j; 
     Memo1.Lines.Add(Format('[%d, %d]', [dy, dx])); 
    end; 

[0, -2] 
[-1, -1] 
[-2, 0] 
[1, -1] 
[0, 0] 
[-1, 1] 
[2, 0] 
[1, 1] 
[0, 2] 

Answer 2

假設骰子顯示p。 現在你想知道從你當前的位置有多少點有曼哈頓距離p。 現在你可以做到這一點，只需做到這一點。

僞代碼：

for i=0..p 
    if(x+i or x-i is valid and y+p-i or y-p+i is valid) 
     then move in (x+i,y+p-i) or/and (x-i,y-p+i) or/and (x-i,y+p-i) or/and (x-i,y+-i) 

Answer 3

使用Python 2。7：

import math 

# Get coordinates of possible dislocations 

def get_possible_dislocations(initial_x, initial_y, max_steps): 
    possible_dislocations = [] 

    for x in range(-max_steps,max_steps+1): 
     for y in range(-max_steps,max_steps+1): 
      if math.pow(x, 2) + math.pow(y, 2) <= math.pow(max_steps, 2): 
       possible_dislocations += [[initial_x + x, initial_y + y]] 
    return possible_dislocations 

print get_possible_dislocations(0,0,2) 

# Returns [[-2, 0], [-1, -1], [-1, 0], [-1, 1], [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], [1, -1], [1, 0], [1, 1], [2, 0]] 

如果你想與pygame的測試它，你可以做到這一點，如：

import math 
import pygame, sys 
from pygame.locals import * 

# Get coordinates of possible dislocations 

def get_possible_dislocations(initial_x, initial_y, max_steps): 
    possible_dislocations = [] 

    for x in range(-max_steps,max_steps+1): 
     for y in range(-max_steps,max_steps+1): 
      if math.pow(x, 2) + math.pow(y, 2) <= math.pow(max_steps, 2): 
       possible_dislocations += [[initial_x + x, initial_y + y]] 
    return possible_dislocations 

# Initialize Pygame 

pygame.init() 

crashed = False 
display_width = 500 
display_height = 500 
clock = pygame.time.Clock() 
display=pygame.display.set_mode((display_width,display_height),0,32) 
white=(255,255,255) 
blue=(0,0,255) 

display.fill(white) 

center_w = display_width/2 
center_h = display_height/2 

# Calculate possible dislocations 
possible_dislocations = get_possible_dislocations(center_w, center_h, 50) 

# Draw pixels on every possible dislocation, starting from the center of the display 

for loc in possible_dislocations: 
    pygame.draw.rect(display,blue,(loc[0],loc[1],2,2)) 

# Run the display 
while not crashed: 
    for event in pygame.event.get(): 
     if event.type==QUIT: 
      pygame.quit() 
      sys.exit() 
    pygame.display.update() 

    clock.tick(60) 

在這個例子中，角色可以移動50步。如果圍繞與中心保持相同距離的點移動，則結果爲圓形。如果你可以去那個圈內的任何地方，你可以得到磁盤的笛卡爾座標。