2
\$\begingroup\$

I am making a simple function that retrieves a 3x3 cells out of NxM grid and determines the direction of cells base on their previous and next neighbor. It will return either any of the following

  1. HORIZONTAL
  2. VERTICAL
  3. TOP_LEFT
  4. TOP_RIGHT
  5. BOTTOM_LEFT
  6. BOTTOM_RIGHT
  7. or INDETERMINATE

Suppose I have this data:

0 1 0
0 1 0
0 1 0
// Direction: VERTICAL

0 0 0
1 1 1
0 0 0
// Direction: HORIZONTAL

0 1 0        0 1 0        0 0 0        0 0 0
1 1 0        0 1 1        1 1 0        0 1 1
0 0 0        0 0 0        0 1 0        0 1 0
//TOP_LEFT   TOP_RIGHT    BOTTOM_LEFT  BOTTOM_RIGHT

0 0 0
1 0 0
1 0 0
// Direction: INDETERMINATE

This function would run many times and would vary(increase) depending on some other factors.

My functioning code so far is this:

var SNAKE_BODY = 1;
var SNAKE_HEAD = 2;

function isSnake(cell) {
    return cell == SNAKE_BODY || cell == SNAKE_HEAD;
}

function getMatrixNeighbors(x, y, board) {
    var neighbors = [];

    for(var row = y - 1; row <= y + 1; ++row) {
        for(var col = x - 1; col <= x + 1; ++col) {
            if ( col >= 0 && col < board.width
              && row >= 0 && row < board.height) {
                var cell = board.at(row, col);
                neighbors.push(cell);
            } else {
                neighbors.push(EMPTY);
            }
        }
    }
    return neighbors;
}

function getBodyDir(x, y, board) {

    var cells = getMatrixNeighbors(x, y, board);

    var top     = cells[1];
    var bottom  = cells[7];
    var left    = cells[3];
    var right   = cells[5];

    if ( isSnake(top) && isSnake(bottom) ) {
        if ( isSnake(cells[0])
          || isSnake(cells[2])
          || isSnake(cells[6])
          || isSnake(cells[8]) ) {
            return BODY_DIR_NEGLECT;
        }
        return BODY_DIR_VERTICAL;
    }

    if ( isSnake(left) && isSnake(right) ) {
        if ( isSnake(cells[0])
          || isSnake(cells[2])
          || isSnake(cells[6])
          || isSnake(cells[8]) ) {
            return BODY_DIR_NEGLECT;
        }
        return BODY_DIR_HORIZONTAL;
    }

    if ( isSnake(top) && isSnake(left) ) {
        return BODY_DIR_TOP_LEFT;
    }

    if ( isSnake(top) && isSnake(right) ) {
        return BODY_DIR_TOP_RIGHT;
    }

    if ( isSnake(bottom) && isSnake(left) ) {
        return BODY_DIR_BOTTOM_LEFT;
    }

    if ( isSnake(bottom) && isSnake(right) ) {
        return BODY_DIR_BOTTOM_RIGHT;
    }

     // return BODY_DIR_VERTICAL;
     return BODY_DIR_UNKNOWN;
}

I think this is the bottleneck in my app so I would like to know if there's anything you could suggest to improve the processing speed of this. Dirty hack is welcomed also as this is scripting and soon to be release.

\$\endgroup\$
1
\$\begingroup\$

Because neither row nor board.height depend on col, you could save two comparisons and an and in your getMatrixNeighbors function:

for(var row = y - 1; row <= y + 1; ++row) {
    var isInBounds = (row >= 0 && row < board.height);
    for(var col = x - 1; col <= x + 1; ++col) {    
        if ( col >= 0 && col < board.width
                      && isInBounds) {
            neighbors.push(board.at(row, col));
        }
        [...]
    }
}

Note also that I removed the unneeded cell variable. It will probably not increase performance, but the code is nicer, I think.

I don't know what values x and y could possibly have, but I would assume that you can somehow save checking col >= 0 (and possibly some of the other bounds checks) each time.

You could also try to save x + 1 and board.width in a local variable to save the computation/accessing, but I would assume that either the compiler optimizes this for you, or that the introduction of an additional variable offsets the performance gain.

I don't think that getBodyDir is the bottleneck (although it would be good if you would profile this), but here you could also save the result of isSnake(top) etc in a local variable, instead of saving top as you are currently doing (top is never used anywhere except as argument for isSnake, so this would actually make sense and should result in nicer code).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.