Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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. –  vermiculus 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? –  vermiculus 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
show 1 more comment

1 Answer

up vote 1 down vote accepted

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. :-)

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.