javascript网格帮助

Question

我正在循环浏览一些网格项目，希望有人能帮我找到一种方法来找到我需要的项目，可能我会更好地了解如何访问网格中的项目。这就是网格。

[0]  [1]  [2]  [3]  [4]
[5]  [6]  [7]  [8]  [9]
[10] [11] [12] [13] [14]
[15] [16] [17] [18] [19]
[20] [21] [22] [23] [24]

这基本上是一个5x5的网格，但是它可以是任何大小，但我只是将其用于示例。我想通过两种方式来遍历它。第一个按如下顺序排列：

0,1,2,3,4,9,14,19,24,23,22,21,20,15,10,5,6,7,8,13,18,17,16,11,12

基本上，所做的一切都是从左上角开始绕过外部。下一种我想要循环遍历的方法是遍历相同的值，除了以相反的顺序(基本上是从里到外)，实际上现在我可以向后循环第一个方法。如果有人能帮我解决这个问题，那就太好了。我真的想学习更多关于如何在这样疯狂的排列中循环项目的知识。

Answer 1

此函数

function n(i, w, h)
{
    if (i < w)
        return i;
    if (i < w + h-1)
        return w-1 + (i-w+1)*w;
    if (i < w + h-1 + w-1)
        return w-1 + (h-1)*w - (i - (w + h-1 - 1));
    if (i < w + h-1 + w-1 + h-2)
        return (h - (i - (w + w-1 + h-1 - 2)))*w;
    var r = n(i - (w-1)*2 - (h-1)*2, w-2, h-2);
    var x = r % (w-2);
    var y = Math.floor(r / (w-2));
    return (y+1)*w + (x+1);
}

接受作为输入

要查看的项的索引

• i：grid
• h：的宽度网格的高度

并返回网格的相应元素，假设按时钟螺旋遍历。

该实现只是检查我们是否在顶部的单元格上，在向下的右侧(i<w+h-1)上等等，对于这些情况，它会显式地计算(i<w)元素。如果我们围绕螺旋完成了一次循环，那么它就会递归地调用自己来找到内部(w-2)*(h-2)网格中的元素，然后根据原始网格的大小提取并调整两个坐标。

对于大网格，这比仅仅迭代和模拟螺旋漫步要快得多，例如，计算n(123121, 1234, 3012)是立即的，而完整的网格有3712808个元素，123121步的遍历将需要相当长的时间。

Answer 2

这是“行走”的方法。效率较低，但它很有效。

var arr = new Array();
for(var n=0; n<25; n++) arr.push(n);

var coords = new Array(); 

var x = 0;
var y = 0;
for(var i=0; i<arr.length; i++) {
     if( x > 4 ) {
          x = 0;
          y++;
     }

     coords[i] = {'x': x, 'y': y};

     x++;
}

// okay, coords contain the coordinates of each item in arr

// need to move along the perimeter until a collision, then turn.

// start at 0,0 and move east.

var dir = 0; // 0=east, 1=south, 2=west, 3=north.
var curPos = {'x': 0, 'y': 0};
var resultList = new Array();

for(var x=0; x<arr.length; x++) {
     // record the current position in results
     var resultIndex = indexOfCoords(curPos, coords);

     if(resultIndex > -1) {
         resultList[x] = arr[resultIndex];
     }
     else {
         resultList[x] = null;
     }

     // move the cursor to a valid position
     var tempCurPos = movePos(curPos, dir);

     var outOfBounds = isOutOfBounds(tempCurPos, coords);
     var itemAtTempPos = arr[indexOfCoords(tempCurPos, coords)];
     var posInList = resultList.indexOf( itemAtTempPos );

     if(outOfBounds || posInList > -1) {
          dir++;
          if(dir > 3) dir=0;
          curPos = movePos(curPos, dir);
     }
     else {
          curPos = tempCurPos;
     }
}


/* int indexOfCoords
 *
 * Searches coordList for a match to myCoords.  If none is found, returns -1;
 */
function indexOfCoords(myCoords, coordsList) {
    for(var i=0; i<coordsList.length; i++) {
        if(myCoords.x == coordsList[i].x && myCoords.y == coordsList[i].y) return i;
    }
    return -1;
}

/* obj movePos
 *
 * Alters currentPosition by incrementing it 1 in the direction provided.
 * Valid directions are 0=east, 1=south, 2=west, 3=north
 * Returns the resulting coords as an object with x, y.
 */
function movePos(currentPosition, direction) {
    var newPosition = {'x':currentPosition.x, 'y':currentPosition.y};
    if(direction == 0) {
        newPosition.x++;
    }
    else if(direction == 1) {
        newPosition.y++;
    }
    else if(direction == 2) {
        newPosition.x--;
    }
    else if(direction == 3) {
        newPosition.y--;
    }

    return newPosition;
}

/* bool isOutOfBounds
 *
 * Compares the x and y coords of a given position to the min/max coords in coordList.
 * Returns true if the provided position is outside the boundaries of coordsList.
 *
 * NOTE: This is just one, lazy way of doing this.  There are others.
 */
function isOutOfBounds(position, coordsList) {
    // get min/max
    var minx=0, miny=0, maxx=0, maxy=0;
    for(var i=0; i<coordsList.length; i++) {
        if(coordsList[i].x > maxx) maxx = coordsList[i].x;
        else if(coordsList[i].x < minx) minx = coordsList[i].x;

        if(coordsList[i].y > maxy) maxy = coordsList[i].y;
        else if(coordsList[i].y < miny) miny = coordsList[i].y;
    }

    if(position.x < minx || position.x > maxx || position.y < miny || position.y > maxy) return true;
    else return false;
}

这将在网格中以一定的方向移动，直到它到达边界或结果数组中已有的项，然后顺时针旋转。这是相当初级的，但我认为它可以做这项工作。你可以非常简单地反转它。

下面是一个有效的示例：http://www.imakewidgets.com/test/walkmatrix.html

Answer 3

您只需要一种表示遍历模式的方法。

给定一个NxM矩阵(例如5x5)，该模式为

GENERAL       5x5
-------     -------
N right        5
M-1 down       4
N-1 left       4
M-2 up         3
N-2 right      3
M-3 down       2
N-3 left       2
M-4 up         1
N-4 right      1

这是向右移动5，向下4，向左4，向上3，向右3，向下2，向左2，向上1，向右1。步长在每两次迭代后移动。

因此，你可以跟踪当前的“步长”和当前的方向，同时减少N，M，直到你到达终点。

重要提示:确保写下非方阵的模式，以查看是否适用相同的模式。