Finding the surrounding cells in a Matrix (2D Array) #DailyAlgorithm

Amazon AD Banner

The objective here is to build a function that can return an object containing the surrounding or adjacent values of a given cell (that we can obtain with two values, the row index and the column item; x or y; n or m; i or j; depends on how you need to view it as). The minesweeper game is a good example because when we click on a little square, behind the scenes, the software first checks to see if the value of that cell is a mine and if it is, you lose, but if it's not, you get the amount of mines that are at that cell's sides and corners.

The credit of the header image goes to Jiguy. Couldn't find a better image, it represents Conway's "Game of Life" which is something this tutorial can be applied to. I was planning on placing an image of Minesweeper but I found this one more suitable.

Two useful ways you can start viewing matrices for the sake of understanding this tutorial 100% are:

  1. As if they were a plain, many small 2D game engines use bidimensional arrays to represent the state of a board or platform game.
  2. The first item could be the starting point of a cartesian system where [0, 0] is the first cell of the matrix.

A very simple introduction to matrices

In linear algebra, a matrix is a block of rows (normally represented by the letter "i") and columns (letter "j"), we can also define it as a bidimensional array of numbers because we have a height and a width, a matrix can be of n (rows) x m (items), for example, if I were to have a 3x4 matrix, it would be like this:

    [0,  4, -1,  5]
A = [1,  3,  1,  2]  
    [2, -4,  0, -3]

The letter A is the name of the matrix (name them to perform operations) and the we can extract some data from that simple matrix, we can say that the rows are the following vectors: [0, 4, -1, 5], [1, 3, 1, 2] and [2, -4, 0, -3] and the columns would in turn be: [0, 1, 2], [4, 3, -4], [-1, 1, 0] and [5, 2, -2]. As expected, we have 3 rows and 4 columns!

In programming, this is a bidimensional array, to access a single value (or cell) we have to provide two indices, the first for the row index (0 to n-1) and the second one for the column index (0 to m-1). Imagine the matrix that I put above (the "A" matrix) was an array in JavaScript, to port it to a 2D array all we have to do is nest three arrays of 4 items each inside an array (yeah, arrays inside arrays, arrayception), I'll put the code later on but to access the item with the subindices 2 and 3 (2nd row and 3rd column, the following piece of code is necessary: aMatrix[2-1][3-1] because indices start from 0; or we can do it like this: aMatrix[row-1][col-1], aMatrix[i-1][j-1], aMatrix[x-1][y-1] assuming you have the column and row number in variables and they're not considered to start from 0. If you subtract the 1 in the variable declarations or if you're using a nested for loop with index values that start incrementing from 0, you can ditch the -1 part because we're actually counting from 0 in the nested for loop or did that during the variable declaration.

Let's create the function

We're gonna start with the function to return the surrounding cells of a given cell, we're going to accept three parameters first: the array that we're going to check and the rest parameters are gonna be the row and column numbers; notice that we're not gonna pass those numbers as we would regularly do, we will start thinking in programming indices, which start from 0. This will allow us to work with nested for loops, we're also building a function to iterate over EVERY cell in a matrix using a nested for loop (a loop inside a loop, because we're dealing with a bidimensional array). In summary, this means that if we want to access the surrounding cells of the item that is located in the 2nd row and 3rd column, we will pass 1 and 2 as coordinates instead of 2 and 3 (because again, indices start from 0).

But we need a matrix first, right? Let's recreate the matrix that I put in the introductory explanation in JavaScript:

var myMatrix = [  
  [0,  4, -1,  5],
  [1,  3,  1,  2],
  [2, -4,  0, -3]
];

And then we create the function, I'm not gonna do a matrix class or something like that because that's something you need to decide, do you need a class to abstract all the matrix functionality? Are you a functional programmer that doesn't like OOP that much? Are you only gonna use this code once? Implement this however you want, the algorithm remains the same, the ideas on how to implement it are completely up to you.

// ... Matrix declaration goes here

function getCell(matrix, y, x) {  
  var NO_VALUE = null;
  var value, hasValue;

  try {
    hasValue = matrix[y][x] !== undefined;
    value    = hasValue?  matrix[y][x] : NO_VALUE;
  } catch(e) {
    value    = NO_VALUE;
  }

  return value;
}

function surroundings(matrix, y, x) {  
  return {
    up:        getCell(matrix, y-1, x),
    upRight:   getCell(matrix, y-1, x+1),
    right:     getCell(matrix, y,   x+1),
    downRight: getCell(matrix, y+1, x+1),
    down:      getCell(matrix, y+1, x),
    downLeft:  getCell(matrix, y+1, x-1),
    left:      getCell(matrix, y,   x-1),
    upLeft:    getCell(matrix, y-1, x-1)
  } // Directions are clockwise
} // End of working with the Matrix

NOTE: Remember that the y and x parameters that the function is taking are indices, they can start from 0, so, if you want for example the adjacent values of the cell located at [2, 3], you'll have to pass 1 (row index) as y and 2 (column index) as x.

First, we abstracted the "get a cell value" part into a function where we can use a try and catch statement to prevent for "index out of bound" errors when dealing with 2D Arrays. The NO_VALUE constant can be replaced with a fallback value of your choice, but if you wonder why I strictly compared the value of the cell to undefined, it was because some people tend to put zeroes as values for the matrix cells to represent that the cell is "turned off", if I were to do if (!matrix[y][x]), it would return true for zeroes, empty strings and false.

Next, we access the cell that is adjacent to the current one for each property in the object literal, check the following list to make things clearer:

Sides
  1. Up: The cell located at the same column and the previous row (up).
  2. Right: The cell located in the next column (right) and the same row.
  3. Down: The cell located at the same column and the next row (down).
  4. Left: The cell located in the previous column (left) and the same row.
Corners
  1. Upper Right Corner: The cell located in the next column (right) and the previous row (up).
  2. Lower Right Corner: The cell located in the next column (right) and the next row (down).
  3. Lower Left Corner: The cell located in the previous column (left) and the next row (down).
  4. Upper Left Corner: The cell located in the previous column (left) and the previous row (up).

Taking a line of code for the sake of the example:

upRight: getCell(matrix, y-1, x+1)  

There are 4 sides and 4 corners, that makes 8 property names that I named as directions but you can go with cardinal or whatever you can think of; we execute the first function we created, send the matrix that was passed to the function, the row index (or y) and the column index (or x). The function is then going to return the value for that adjacent cell (hence the -1 or +1 in some argument values as explained above).

The Boundary Approach

You could check to see if you are in the first or last row, the first or last column and construct a logic around that but it would take extra steps and mental exercise, this way you can avoid the try and catch statements and add an extra utility to your matrix logic but in this particular case, I don't see the case; maybe in collision detection.

Print all cells' surroundings!

Why don't we create an algorithm to iterate over every cell in the matrix from top to bottom and left to right? The right way to do this is with a nested for loop, the outer loop to access the rows and the inner loop to access each cell of the current row.

function eachCell(matrix, action, thisArg) {  
  var rows = matrix.length;

  thisArg = (typeof thisArg === 'object')?
    thisArg : null;

  // Access each row in the matrix
  for(var y = 0; y < rows; y++) {
    var row   = matrix[y];
    var cells = row.length;

    // Access each cell in the row
    for(var x = 0; x < cells; x++) {
      var cell = row[x];

      action.call(thisArg, cell, y, x, matrix);
    } // End of cell iteration
  } // End of row iteration
}

This function takes three arguments, the matrix that it needs to iterate over, an action that uses the cell values and since every good library has a thisArg (optional) parameter to set the custom context of the this keyword, I thought it was nice to add. If you don't feel comfortable with Function.prototype.call or the topic of context in JavaScript, ignore it for now.

To the action (callback function, I'm sending the cell value and the y and x (row index and column index) coordinates, if you use the indices or not is up to your action's needs. Here's a cleaner ES6 alternative which may be a little slower than native for loops:

const eachCell = (matrix, action, thisArg = null) => {  
  matrix.forEach((row, y) => {
    row.forEach((cell, x) => {
      action.call(thisArg, cell, y, x, matrix);
    });
  });
};

And for the printing, we pass a callback function to the eachCell function, in this case, we're gonna print the values object and the coordinates. Invoke the function we just created and the callback is going to be a console.log statement with the info we need.

eachCell(myMatrix, function(cell, y, x, matrix) {  
  console.log(
    'Adjacent cells to [' + y + ', ' + x + ']: ',
    surroundings(matrix, y, x),
    'Current Value: ' + cell + '.'
  );
});

The output is a list of the cell values, the adjacent values, and the coordinates in terms of indices, the number of times you'll see a printed statement is the same amount of cells your matrix has, since we're using a 3x4 matrix, we'll get 12 console.log statements but let's extract just 1 and verify it:

Adjacent cells to [1, 0]:  Object {  
  down: 2, downLeft: null, downRight: -4, left: null, right: 3, up: 0, upLeft: null, upRight: 4, __proto__: Object }
Current Value: 1.  

If we compare that to the original matrix, you'll see that there's no mistake about it, the adjacent values are correct! We're finished with the algorithm, there's a ton of things you can do with this, I already gave you two ideas for possible challenges: re-create the Minesweeper game and Conway's Game of Life.

Lastly, I'm sure there will be at least one person who comments: "Oh, but there's really no bidimensional Arrays in JavaScript, just arrays inside arrays", while they're correct, with bi-dimentionality I'm trying to convey the message of a "plain" in space which is what some JS game and canvas libraries do. If at least one row isn't the length of the rest, it may cause trouble in general, that's why you need to make sure you have a better way to create a matrix of n x m without any holes in it, I'm thinking maybe you could do a constructor that has integrated validations to make sure every row has the right amount of values. Also, if you don't feel comfortable with passing the array "matrix" around (which for me, is totally ok since it's not creating copies of it) you can create a Matrix class and work with an Object Oriented approach.

These comments are powered by Disqus