Advertisement Jump to content
Sign in to follow this  

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.

If you intended to correct an error in the post then please contact us.

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.
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?

Share this post

Link to post
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

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!