Determining allowable moves on a grid

Answer 1

Suppose piece p is at position x, y and can move n squares away to position x2, y2. This means that the sum of the absolute differences between (x - x2) and (y - y2) can be no greater than n.

If you're going to show which squares can be moved to (rather than taking inputs x2 and y2), I think it'd be best to loop over all positions in a square around the piece. That is...

for (x - n TO x + n):
    for (y - n TO x + n):
        if (abs(x - x2) + abs(y - y2) <= n):
            mark as okay.

This answer assumes pieces can only move to adjacent squares and not diagonally.

Edit: If you want diagonal movement, and moving along a diagonal costs just as much as moving horizontally or vertically, then the problem is actually much easier - the piece p can move between the ranges of (x - n, x + n) and (y - n, y + n).

The answer becomes a lot more complex if moving diagonally doesn't cost as much as a horizontal + vertical movement (e.g., if diagonal costs 1.5, whereas h/v costs 1).

Answer 2

This is purely on a conceptual level, but try this logic:

1. Take all possible locations one step away from your starting point and put them on the stack (Moves Taken =0)

2. Pop one off the stack and repeat, using that new coordinate as your new starting point. (Moves Taken=1). You'll have to ensure that you don't put any duplicate coordinates on the stack

3. Repeat 2 until you've exhausted all your piece's available moves.

I may not be explaining this to well, let me know if you have any questions about what I'm trying to say.

Answer 3

You could use the approach above but use recursion instead.

The recursion "depth" is the movement distance.

Break out when depth > movement.

Each iteration should return a vector of spaces and add its own location.

Remove duplicates

Answer 4

In general such problems involve a reasonably limited grid of places one can possibly reach. Take a data structure of the size of the grid and whose elements can hold the number of remaining movement points with sufficient precision.

Initialize the grid to a not-visited value. This must not be in the range of zero to the maximum possible move speed. A negative value is ideal.

Initialize the starting location to the number of moves remaining.

At this point there are three possible approaches:

1) Rescan the whole grid each step. Simple but slower. Termination is when no points yield a legal move.

2) Store points on a stack. Faster than #1 but still not the best. Termination is when the stack is empty.

3) Store points in a queue. This is the best. Termination is when the queue is empty.

Repeat
   ObtainPoint {From queue, stack or brute force}
   For Each Neighbor do
      Remaining = Current - MovementCost
      If Remaining > CurrentValue[Neighbor] then
         CurrentValue[Neighbor] = Remaining
         Push or Queue Neighbor
Until Done

Note that with the stack-based approach you will always have some cases where you end up throwing out the old calculations and doing them again. A queue-based approach will have this happen only if there are cases where going around bad terrain is cheaper than going through it.

Check the termination condition only at the end of the loop, or else terminate when ObtainPoint attempts to use an empty queue or stack. An empty queue/stack after ObtainPoint does NOT mean you're done!

(Note that is is a considerable expansion on Ian's answer.)