JS: étant donné un point dans un tableau 2d et une distance, quelles coordonnées peuvent être parcourues?

Question

Étant donné un tableau 2D de toutes les tailles comme ceci:

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] 
]; 

... et une donnée [y] [x] point de cette matrice, tels que:

board[3][4] 

... et un certain nombre d'espaces, il peut se déplacer (haut/bas/gauche/droite, pas en diagonale), comme:

var distance = 3; 

... comment une boucle de fonction à travers le réseau 2D et creat e une liste de seulement les coordonnées qui peuvent être voyagées?

(Voici un exemple visuel des coordonnées données (*) dans le tableau, et les coordonnées pouvant être parcourue autour.)

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 

Référence: JS: how to algorithmically highlight a diamond-shaped selection of x/y coordinates? (j'ai posé cette question, mais je ne peux pas comprendre comment entrer une coordonnée et recevoir une liste de coordonnées)

Answer 1

C'est la solution la plus simple que je pouvais penser, il implique de travailler de haut en bas et de gauche à droite, itérer plus que les coordonnées qui sont admissibles se déplace il devrait être assez rapide:

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; 
} 

Pour vous donner une meilleure idée, j'ai jeté ensemble une démo qui vous permet d'ajuster toutes les différentes variables, par exemple taille de la carte, la distance, etc.

démonstration de travail: http://jsfiddle.net/AndyE/fWDHy/2/

Answer 2

Utilisez la récursion avec une liste/hachage de liens visités. Faites un pas, réduisez votre capacité à voyager par un et passez le long de la liste de ce que vous avez vu. Ajoutez votre position actuelle à la liste des sites visités. Aller dans chaque direction d'un pas (en utilisant la récursivité), en passant par une valeur de «pas à gauche» qui est inférieure de un à ce qui vous a été donné.

Voici une réponse que almost works; le seul problème est qu'il ne re-visite jamais une cellule même si le chemin long a été utilisé pour y arriver. Vous pouvez surmonter cela soit par l'intermédiaire d'un breadth-first search, soit en détectant si la cellule visitée a été atteinte par plus d'étapes que ce que vous êtes sur le point de prendre pour y arriver.

Answer 3

Itérer sur toutes les coordonnées (ou un sous-ensemble x-d,y-d ... x+d,y+d si la zone est grande).

Pour chaque champ de ceux-ci, calculez la distance - dans votre cas dx - dy - et chaque fois que vous trouvez un point avec la distance> 0, faites tout ce que vous voulez avec. Sinon, ignorez-le. C'est tout!

Comparé à une approche de remplissage d'inondation, vous obtenez un code simple et pas de surcharge des tables de consultation additinal.