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:

enter image description here

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?

  • $\begingroup$ 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 $\endgroup$ – Ross Millikan Oct 18 '17 at 20:35

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


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.