javascript grid help

I am wo开发者_如何学Pythonrking on looping through a few grid items and was hoping someone could help me find a way to figure out how to get to the items that I need and possibly I will better understand how to access the items in the grid. So here is the grid.

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

This is basically a 5x5 grid, however it could be any size but I just used this for the example. There are two ways I would like to loop through this. The first one being in this order:

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

Basically all that is doing is going around the outside starting from the top left. The next way I would want to loop through that is through the same exact values except in reverse order (basically inside out instead of outside in) and actually thinking about this now I could just loop through the first method backwards. If anyone can help me with this it would be great. I really want to learn more on how to loop through items in crazy arrangements like this.

This function

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

accepts as input

• i: Index of the item you're looking for
• w: Width of the grid
• h: Height of the grid

and returns the corresponding element of the grid assuming that clock-wise spiral traversal.

The implementation simply checks if we're on the top side (i<w), on the downward right side (i<w+h-1) and so on and for these cases it computes the cell element explicitly. If we complete one single trip around the spiral then it calls recursively itself to find the element in the inner (w-2)*(h-2) grid and then extracts and adjusts the two coordinates considering the original grid size.

This is much faster for big grids than just iterating and emulating the spiral walk, for example computing n(123121, 1234, 3012) is immediate while the complete grid has 3712808 elements and a walk of 123121 steps would require quite a long time.

You just need a way to represent the traversal pattern.

Given an NxM matrix (e.g. 5x5), the pattern is

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

This says move 5 to the right, 4 down, 4 left, 3 up, 3 right, 2 down, 2 left, 1 up, 1 right. The step size shifts after each two iterations.

So, you can track the current "step-size" and the current direction while decrementing N, M until you reach the end.

IMPORTANT: make sure to write down the pattern for a non-square matrix to see if the same pattern applies.

Here's the "walking" method. Less efficient, but it works.

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

This will move through the grid in a direction until it hits the bounds or an item already in the results array, then turn clockwise. It's pretty rudimentary, but I think it would do the job. You could reverse it pretty simply.

Here's a working example: http://www.imakewidgets.com/test/walkmatrix.html