# Formula for working out an ID number by given set of coordinates

I'm designing an online game and having a bit of a mental block coding the navigation system. It's designed on a 2 dimensional grid, each cell has an ID 0...n, n being the total number of cells in the grid.

What I need to be able to do is figure out the ID number based on the given X & Y coordinates. So in the example below, I'd expect to get the value 25 when entering the co-ordinates 4x2 (0 based index on the co-ordinates)

Bear in mind that the grid could be any given height and width, in this case 5 and 10 respectively.

$$\begin{array}{r} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 \\ 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 \\ 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \end{array}$$

I'm sure this is going to be an embarrassingly simple problem, thanks in advance for any help!

-
What you're talking about is modular arithmetic, I think. Could you give another example where the width $\neq 10$? I'm also assuming you'd like to calculate this value, as opposed to retrieving it. – Sean Allred Apr 28 '13 at 18:26
Hi vermiculus, thanks for that I'll update the tags. So the grid could be 10x10, 15x10, 5x5 etc. there's no real restriction on the dimensions. Yep that's right - I'd like to calculate the ID without having to make a database or cache hit to retrieve the number. – managedheap84 Apr 28 '13 at 18:31
No, I meant how would the numbers roll out? I'm assuming $$\begin{array}&1&2&3&4&5&6\\7&8&9&10&11&12\end{array}$$ would be another example? – Sean Allred Apr 28 '13 at 18:35
Yep that's right, ill have a look at your function below thanks – managedheap84 Apr 28 '13 at 18:47
Do you want to start counting with $0$ or with $1$? (This refers both to the block id and to the x/y coordinates an dI just wonder because your post is contradictory about that) – Hagen von Eitzen Apr 28 '13 at 19:20

Try

$$f(x,y,w)=(x \mod w) + yw$$

(where $x \mod w$ is often x % w)

Why does this work? Consider this arrangement of the natural numbers $\mathbb{N} = \{0,1,2,3,\dots\}$:

$$(y\cdot w)_{y \in \mathbb{N}}\Bigg\{ \overbrace{ \begin{array}{r} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\\ 16 & 17 & \dots & \dots & \dots & \dots & \dots & \dots \end{array}}^{w=8}$$

$w$ here is your modulus. What is a modulus, you say? A modulus is a number by which you divide to obtain a remainder.

Note that for any number $x \in \mathbb{N}$, you can find the remainder of $\frac{x}{w}$ by locating it in the array and looking at the very top column. This is the idea of the modulus, and the operation done by x % w in C-like languages.

Thus, the operation $(x\mod w)$ finds the column in which $x$ is in this modulus, and $y \cdot w$ skips to the row. Thus, $(x\mod w) + yw$ skips to the row and column to find your index. :-)

-
Hey thanks for this it seems to work, would you mind explaining how? :-) – managedheap84 Apr 30 '13 at 17:31
I can certainly try. – Sean Allred Apr 30 '13 at 18:01
@managedheap84 See the edit. – Sean Allred Apr 30 '13 at 18:45