5
\$\begingroup\$

In my voxel game, I'm trying to spawn chunks in all directions. But since my world starts at 0,0,0, some chunks can spawn at negative positions like -1,0,-1.

My chunks are 16x16x16 size.

When generating(or not) a block, somewhere in the process, I need to find what block is at position A(xyz 0-15) in chunk B(xyz -max +max), based on block's world position.

So for example, block at world position(can be xyz-max +max) 1, 0, 1 should give me chunk 0, 0, 0 and block's relative position inside chunk is 1, 0, 1.

block at world position -1, 0, -1 should give me chunk -1, 0, -1 and index of block relative to this chunk 15, 0, 15.

But as you see, there is an inconsistency and loss of symmetry(-1 relative to 0 gives -1 and 1 relative to 0 gives 0) relative to 0, 0, 0, that I can't figure out how to fix.

Currently I find relative index in chunk from world position using this:

    int size = 16;

    int x = -1;
    int y = 0;
    int z = -1;

    int chunkRelativeX = x % size; 
    int chunkRelativeY = y % size; //0
    int chunkRelativeZ = z % size; 

    if (x < 0)
    {
        chunkRelativeX += size; //15
    }
    if (z < 0)
    {
        chunkRelativeZ += size; //15
    }

And I find chunk position itself using:

    int chunkPosX = Mathf.FloorToInt((float)x / size); //-1
    int chunkPosY = Mathf.FloorToInt((float)y / size); //0
    int chunkPosZ = Mathf.FloorToInt((float)z / size); //-1

Problem is, with positives, its correct, since before 1st chunk comes 0st, but before -1st chunk, doesn't come 0st.

I'm really confused and not sure what to do :D

Thanks in advance.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Did you try using a bitwise AND operator & 15 instead of modulo % 16? \$\endgroup\$
    – DMGregory
    Commented Jun 16, 2021 at 11:54
  • \$\begingroup\$ @DMGregory This solved the issue! But I don't understand why! \$\endgroup\$
    – Nick
    Commented Jun 16, 2021 at 14:13
  • 2
    \$\begingroup\$ @Nick the way two's complements work you can mask off powers-of-two numbers minus one and they wrap-around eg: (X & 3) in binary is (X & 0011b) : 0000b, 0001b, 0010b, 0011b, 0000b, ... So you get a count that wraps. Only works for power-of-two modulos (2-1, 4-1, 8-1, 16-1, 32-1, ...) and for negative numbers only in two's complements form (this trick doesn't work with one's complements systems, modern systems don't use one's complements for integers so no worries, we're fine there). This is getting past the scope of this question but look up one's complement vs two's complement for more detail \$\endgroup\$ Commented Jun 16, 2021 at 17:56
  • 1
    \$\begingroup\$ Huh, another great reason to keep chunk sizes at power of two sizes... \$\endgroup\$ Commented Jun 23, 2021 at 9:12

2 Answers 2

3
\$\begingroup\$

I think your problem might be partially due to the way the % operator works with negative numbers. I have a vague memory of tripping up in the same way - I present you my method of dealing with this. I have created a special struct that holds 5 numbers - the local XYZ and the chunk position - I use this in a lot of terrain related stuff. I don't use voxels but terrain is still stored in chunks (128x128 but it really doesn't matter here I believe).

What you're probably specifically interested in is creating such coordinates from an arbitrary XYZ - one of the methods in my struct takes a Vector3 and then applies this Normalize method to figure out all the numbers.

   //chunk size
   public const int Stride=128;
   //local coordinates
   public float X;
   public float Y;
   public float Z;
   //chunk coordinates
   public int BX;
   public int BY;
   //make sure local coords are within range of 0...127
   public void Normalize()
   {

        this.BX += ((int)Math.Floor(X / (float)Stride));
        this.X = ((this.X % (float)Stride+(float)Stride)% (float)Stride);
        this.BY += ((int)Math.Floor(Z / (float)Stride));
        this.Z = ((this.Z % (float)Stride+ (float)Stride)% (float)Stride);

       
    }
    //Convert a standard XYZ to local XYZ + chunk coords
    public static implicit operator WorldPosition(Vector3 a)
    {
        WorldPosition result = new WorldPosition();
        //set to XYZ
        result.X = a.X;
        result.Y = a.Y;
        result.Z = a.Z;
        //figure out chunk/local coords
        result.Normalize();
        return result;
    }

What it more or less does is that after the first % that may turn up negative it adds the chunk size again - which for "proper" modulo does not change the result but fixes it for negatives.

\$\endgroup\$
2
\$\begingroup\$

Problem was, as @htmlcoderexe mentioned, the way % works in c#. But I'll accept solution from @DMGregory, which is the simpler one.

@stephane-hockenhull also explained this thing in more technical detail of bitwise & (Under my question), but I'll still write my own answer as a bit simpler interpretation for people like me who get confused easily :)

Modulo in c# is "symmetrical": 15%16 = 15 and -15%16 = -15, 16 % 16 = 0, -16 % 16 = 0.

But in my case(Where chunk 0 is actually a starting point and it goes 0 -> 15), this "symmetry" is actually what broke my count. Since first negative chunk starts at -1 and last block of that chunk will be -16th. So its -1 -> -16 rather than 0 -> 15 as at positives.

To find block position relative to chunk(in negatives), I added 16, so -1 + 16 = 15, which is seemingly correct so far(-1st block is indeed 16th block(or index of 15, we start at 0) in chunk).

Say, we want to find -15th block, -15 % 16 = -15, + 16 = 1, indeed, -15th block is 2nd block in the chunk.

But what block comes next before 2nd? Lets check: -16 % 16 = 0, + 16 = 16, and its wrong. -16th block is not 16th block in chunk, but actually its the 1st one. Hence, we need to make an exception here.

So "correct" version of my initial implementation would be:

if (x < 0)
{
    chunkRelativeX += size; //15
    if(x & size == 0){
      chunkRelativeX = 0;
    }
}
if (z < 0)
{
    chunkRelativeZ += size; //15
    if(x & size == 0){
      chunkRelativeX = 0;
    }
}

But instead of doing this as a multi step Ifs, it could be written using bitwise &(Which in itself contains that "exception" for n%16 = 0 cases at negatives, but for numbers that are power of 2 - 1) simply as:

if (x < 0)
{
    chunkRelativeX = x & (size - 1);
}
if (z < 0)
{
    chunkRelativeZ = z & (size - 1);
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ This definitely looks a lot simpler, I will be definitely going over this once I am back to my projects! \$\endgroup\$ Commented Jun 23, 2021 at 9:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .