# Finding neighbours of a certain cell using modular arithmetic

Consider a 2-dimensional grid (consisting of cells) of a certain height $h$ and a certain width $w$. The corners of the grid are given by the coordinates $(0,0), (0,h-1), (w-1,0)$ and $(w-1,h-1).$

Take an arbitrary cell $(x,y)$ within the grid. I want to find all 8 neighbours (including "diagonal" neighbours) of the cell.

We consider the grid to be a kind of 2D-representation of a cylinder, so all cells in the leftmost columns have 3 neighbours in the rightmost columns, and vice versa. Similarly, all cells in the top row have 3 neighbours in the bottom row and vice versa.

To illustrate this example, the neighbours of a cell $(0,0)$ would be:

What I want is to determine if a given cell $(x_1, y_1)$ is a neighbour of another cell $(x_2,y_2)$ in the simplest way possible. Since we're dealing with a grid whose borders we cannot cross, I am assuming that it would involve modular arithmetic.

I've tried searching for a pattern but a correct solution eludes me. My first hunch was to look at $h \mod y$ and $w \mod x$. What we want is at least one of the two coordinates of $(x_1, y_1)$ to differ from a coordinate in $(x_2,y_2)$ by one. The edge cases kind of make it difficult though. Anyone know how to tackle this?

• If you connect top and bottom, then right and left, you have a torus, not a cylinder. It is not important for what you are doing here – Ross Millikan Oct 18 '17 at 20:35

## 1 Answer

Don't know if you're doing it as a computer program or something else but
Here is what I come up with,
(x1,y1) is neighbor of (x2, y2) if
rem(rem( abs(x2-x1) ,w), w-1) < 2 and
rem(rem( abs(y2-y1) ,h), h-1) < 2
where w,h is width and height of grid and abs is absolute value.

Also make sure that abs(x2-x1) + abs(y2-y1) > 0