Many times when I have to deal with grids and adjacency, I always come up with a solution that results in difficult to understand code that makes no sense to anyone who uses it. Here I will try and explain my system to defining adjacency in a square grid and why I use it.

Consider a grid where you stand on AA and you want the coordinates for the things around you.

I will for this thing assume you have a simple expression to convert your xy coordinates to position in an array

Lets not consider the diagonals for now and concentrate on just the sides. I usually set numbers to define directions:

These numbers seem arbitrary but there is a reason to them, in binary these numbers are

When you do this its now possible to get adjacent cells like this:

Let’s unpack that. The numbers we chose for each direction lets us assign a meaning to each of the bits, so we have one bit for direction, and one bit for dimension:

Using this arrangement, first we assume we are on the X axis, and if its a 1 we want to move forward and if its 0 we want to move backwards. This means we have to convert 0 to -1 and 1 to 1. We can do this by subtracting 1 from 2 times the direction bit.

Next, we want to use the dimension bit to choose a dimension. This is straightforward because we simply create an array with two elements, and use the dimension bit to index the array.

Since we are walking a one dimensional array, we can simply substitute each bit of the directions int our array:

Putting it all together, we have

We realize that anything multiplied by two is just a left shift, so we first of all shift the entire number up one bit. (I will show why we do the entire number instead of the direction bit later)

And then dx simply becomes

Lets get rid of dx since its so simple now, and we can use oper as well with a down shift of 2, but it doesn’t really matter. Both are equally fast.

By making this a function, we can use it to produce an amount we can move in the array to where we want to be:

Using this, say we have the position somewhere in the array

## Usage

We can simply add our movement into the position to give us the say, cell below ours:

If we wanted to access all the side cells, we just have to loop through all of the 4 numbers.

## Diagonals

Say we want to also do diagonals, then we modify our map to this

I usually set a bunch of values for this:

This way we can add to our directions enum:

Our function then becomes:

Now, lets analyze this again. First of all, notice that the new directions all have an extra bit set, this bit is what I call the diagonal bit. We first of all need to remove this diagonal bit from our original oper variable, because it will cause a buffer overflow.

By masking out our oper bit, now the function behaves as if it was

However, since these are diagonals, we need to set the other dimension’s diff as well. The missing directions then are:

Since our second directions are -1, 1, 1, -1 respectively, we need to use the XOR operator to produce them. Recall that dir values are

Using an XOR operator on the bottom two bits, we can create

Now we can go

And then applying the (x * 2) - 1 trick, we can essentially make that

By just applying

However, since we know that oper is dir shifted up one, we can instead just let secondbit operate in the 2nd bit field, without having to mask and shift dir down by one, we can just use it where it is, along with oper.

Now that we have our second bit, all we need to do is assign it to the dimension that was not assigned to.

But we aren’t done yet, we only need the second dimension to be filled if the diagonal bit is set, so we need to do this:

And simply multiply the diagonal bit in, to mask it out.

We are also repeating ourselves by going oper >> 2 so we go

Now you can use this to access all 8 squares around by iterating from 0 to 7, or simply iterate from 0 to 4 to get adjacent squares only.

Obviously this is very much a toy example and you will still have to check bounds and manage datatypes yourself, but it gives a very nice set of shortcuts to anyone who wishes to work easily on a grid, and hopefully will go some way to explaining the bit twiddling I do when I work on grids.