Tile movement range generate pattern?

Question

I am doing a tile based game. I try make a method that return an array that my character can move based on x,y coordinate and move limit.

For example, if I input currentPosition:(3,3) moveLimit:1

then it should give me back ((3,2),(3,2),(3,4),(4,3))

and if I input currentPosition:(3,3) moveLimit:2

then it should back ((3,1),(2,2),(3,2),(4,2),(1,3),(2,3),(4,3),(5,3),(2,4),(3,4),(4,4),(3,5))

I planning to use recursive method by making all possible of -1 and +1 on both x and y. but it is quite inefficient, since a lot of repeated case may occur such as +1 then -1 compared to -1 then +1.

Anyone know if there is any good pattern for this?

Thank you a lot.

amit amit · Accepted Answer · 2012-11-08T13:51:29

Let's first define the question and what you are looking for formally:

Denote k as the distance and (x,y) as the origin point (source).

f((x,y),k) = { (a,b) | abs(x-a) + abs(y-b) <= k }

This means, a set with all points (a,b) such that: abs(x-a) + abs(y-b) <= k (which is the distance restriction)

Now, to get all the relevant elements you can do:

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)

Note:

This guarantees the condition because you check all possible steps in both axises with the limitation of abs(a-x) + abs(b-x) <= k
In here "is in range" is a sanity check, make sure you don't get out of bound (for example, get an x value of -1, assuming you need to get a positive value only.

Tile movement range generate pattern?

2 Answers