JS: is there a point in the 2d array and a distance whose coordinates are moving?

Question

For a two-dimensional array of any size:

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 the given [y] [x] point in this array, such as:

 board[3][4] 

... and a given number of spaces that it can move (up / down / left / right, rather than diagonally), for example:

 var distance = 3; 

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

(Here's a good example of a given coordinate (*) in an array and the surrounding moving 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 

Link: JS: how to algorithmically select a diamond choice of x / y coordinates? (I asked this question before, but I can't figure out how to enter a coordinate and get a list of coordinates)

Answer 1

This is the simplest solution that I could think of, it includes working from top to bottom and from left to right, iterating only along the allowed coordinates, 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 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 put together a demo that allows you to set up all the various variables, for example. board size, distance, etc.

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

Answer 2

Iterate over all coordinates (or a subset of xd,yd ... x+d,y+d if the area is large).

For each field from them, calculate the distance - in your case, as dx - dy - and whenever you find a point with a distance> 0, do whatever you want with it. Otherwise, ignore it. What is it!

Compared to the flood approach, you get simple code and no overhead for additional lookup tables.

Answer 3

Use recursion along with a list / hash of visited links. Take a step, reduce your ability to travel one at a time and go through the list of what you saw. Add your current location to your list of visited places. Go in each direction one step (using recursion), going over the value of "step left", which is one less than you.

Here is an answer that almost works ; the only problem is that it never revises the cell, even if the long path was used to get it. You could overcome this either by searching in width , or by determining whether the visited cell has been reached with more steps than you are going to take to get there.