CODEWITHSUNDEEP
javascriptarraysmultidimensional-array2dtiles
Adam Hunter Peck
Adam Hunter Peck

Reputation: 317

JS: given a point in a 2d array and a distance, which coordinates are travelable?

Given a 2D array of any size like so:

var board = [
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]
];

...and a given [y][x] point in that array, such as:

board[3][4]

...and a given number of spaces it can travel (up/down/left/right, not diagonally), like: 

var distance = 3;

...how would a function loop through the 2D array and create a list of only those coordinates that may be traveled?

(Here's a visual example of the given coordinate (*) in the array, and the surrounding travelable coordinates.)

0 0 0 0 0 0 0 0
0 0 0 3 0 0 0 0
0 0 3 2 3 0 0 0
0 3 2 1 2 3 0 0
3 2 1 * 1 2 3 0
0 3 2 1 2 3 0 0
0 0 3 2 3 0 0 0
0 0 0 3 0 0 0 0

Reference: JS: how to algorithmically highlight a diamond-shaped selection of x/y coordinates? (I asked this question before, but I can't understand how to input a coordinate and receive a list of coordinates)

Upvotes: 4

Views: 2047

Answers (3)

Andy E
Andy E

Reputation: 344665

This is the simplest solution I could think of, it involves working from top to bottom and left to right, iterating over only the co-ordinates that are permissible moves so it should be pretty fast:

function getPossibleMoves(x, y) {
    var r, c, cMax, 
        distance = 3,
        rows = board.length,
        cols = board[0].length, 
        rMax = Math.min(y + distance + 1, rows),
        ret  = [],
        yOff;

    // Start at the first row with a permissible move
    for (r = Math.max(y - distance, 0); r < rMax; r++) {
        yOff = Math.abs(r - y);

        // Work out where we should stop looping for this row
        cMax = Math.min(x + distance - yOff + 1, cols);

        // Start at the first column with a permissible move
        for (c = Math.max(x - distance + yOff, 0); c < cMax; c++) {
            // If it's not the current position, add it to the result
            if (x != c || y != r)
                ret.push([c, r]);
        }
    }
    return ret;
}

To give you a better idea, I threw together a demo that allows you to adjust all the different variables, e.g. board size, distance, etc.

Working demo: http://jsfiddle.net/AndyE/fWDHy/2/

Upvotes: 1

Kos
Kos

Reputation: 72281

Iterate over all coordinates (or a subset x-d,y-d ... x+d,y+d if the area is big).

For each field of those, calculate the distance - in your case as dx - dy - and whenever you find a point with the distance > 0, do anything you want with it. Otherwise, ignore it. That's it!

Compared to a flood-fill approach, you get simple code and no overhead of additinal lookup tables.

Upvotes: 3

Phrogz
Phrogz

Reputation: 303361

Use recursion along with a list/hash of visited links. Take a step, reduce your ability to travel by one and pass along the list of what you've seen. Add your current location to the list of visited spots. Go in each direction one step (using recursion), passing along a 'steps left' value that is one less than you were given.

Here's an answer that almost works; the only problem is that it never re-visits a cell even if the long way was used to get there. You could overcome this either via a breadth-first search or by detecting if the visited cell was reached via more steps than you are about to take to get there.

Upvotes: 0

Related Questions