# A little math problem

This topic is 1252 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm trying to work out an indexing scheme for a scene graph and I made the silly mistake of not going with a simple zero-based solution. This has since become a bit of a pet peeve for me, meaning that I really want to figure it out - you know, for kicks. So far I haven't been able to.

I've attached an image that explains the basic problem. Below is a solution that seems to work, but doesn't.

[attachment=28663:grid.jpg]

I have a grid that runs from -n to n centered on node 0. Currently I need to get this working in 2D, although I want to extend it to 3D later on. Basically, in 2D indexing starts from [-n; -n] in the top left corner and increases to [n; n] in a row major order towards the bottom right. I need to write two translator functions: GetNodeCoordinatesFromID() and GetNodeIDFromCoordinates().

One way of getting the ID is simple, pretty much what a forward conversion would be for a zero-based grid: i = y * dimx + x, where dimx is the horizontal dimension of the grid. For dimx = dimy = 5, x and y run from -2 to 2.

My math skills suck, but as far as I know, deducing x and y algebraically from this formula alone is impossible. Hence I tried going with a bit of logic and came up with y = (i -|+ (dx / 2)) / dx and x = i - (y * dimx) (all divisions rounded down), depending on whether i is negative or positive. Initially these seemed to work for small grids, but made no sense when I substituted them into the forward conversion. This solution also fails miserably in a little test loop I wrote.

So yeah, in short - any ideas?

3y + x

##### Share on other sites

Shift everything so that the range becomes 0 to 2n + 1, then it's basically the same as indexing a normal array:

i = (y + n) * dimx + x + n
x = i % (2n + 1) - n
y = i / (2n + 1) - n

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 9
• ### Forum Statistics

• Total Topics
634082
• Total Posts
3015401
×