Determining all the adjacent spaces on a 2D grid

Question

I can't seems to find a good way to solve this problem I'm working on.

Suppose I have a point on a 2D grid describing the location of a character(board game):

                                 [n,m]

Now, on each turn I can move the character depending on the roll of a dice (1,2,3...), and I want to find all possible ways the character can move.

Moving the character once means changing only n or m in which a diagonal movement counts as 2 movements (i.e. [n+1,m] moved once, [n+1,m+1] moved twice).

For example, if I roll a 2 then all possible movements are:

                                 [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]

I can't seem to get a clear algorithm for this.

What I have so far is another suggestion from 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'

However, it misses the [n][m+2],[n+2,m] (or the way I wrote it misses it).

Any suggestions for concise answers or fixes?

Answer 1

With 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]]

If you wanted to test it with PyGame, you could do it like:

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)

In this example, the character can move 50 steps. If you move around a point keeping the same distance to the center, the result is a circle. If you can go anywhere inside that circle, you get the cartesian coordinates of a disk.

Answer 2

Walk through (inclined) lines of diamond and transform into normal coordinates. Python code

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'

Alternative approach: you can shift along the first coordinate in range of n in both directions. If some moves are left (movesleft), you can shift along the second coordinate in any direction using movesleft steps. The second stage must preserve oddity (parity?), so step 2 is used.

pseudocode

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)     

Delphi code for n=2 and n=3 gives results

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]

1st method (the same result in another order):

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 3

Suppose the dice shows p. Now you want to know how many points are there from your current location having manhattan distance p. Now what you can do it simply do this.

Pseudocode:

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)