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 · Accepted Answer · 2012-11-08 13:51:29Z

1

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.

answered Nov 8, 2012 at 13:51

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

kheyse Over a year ago

Note that this will return ((3,2),(2,3),(3,4),(4,3) and (3,3)).

amit Over a year ago

@Vortexfive: As it supposed to. I read "move limit" as maximum number of possible moves, and 0 is inclusive. It can be easily solved if it is not the case by "skipping" i=j=0. However - It will output (3,3) several times (4, to be exact), if it is an issue this specific case should be specifically checked.

kheyse Over a year ago

@amit: I understand your interpretation, and it is probably what the asker wanted. I just wanted to point out that it does not return the same result as the askers example, where an exact amount of moveLimit moves is used.

kheyse · Accepted Answer · 2012-11-08 13:34:35Z

0

Try calculating all combinations of length "moveLimit" from the elements (UP,LEFT,DOWN,RIGHT).

E.g.

UUU
UUL
UUD
UUR

ULL
ULD
ULR

UDD
UDR

URR

LLL
...

This should already reduce the number of calculations a lot. You still might end up with different combinations of moves that result in the same position.

answered Nov 8, 2012 at 13:34

kheyse

1,91913 silver badges20 bronze badges

Collectives™ on Stack Overflow

Tile movement range generate pattern?

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related