Minecraft Style Chunk building problem

Posted by David Torrey on Game Development See other posts from Game Development or by David Torrey
Published on 2012-12-02T11:18:13Z Indexed on 2012/12/02 11:22 UTC
Read the original article Hit count: 250

Filed under:
|
|
|

I'm having some problems with speed in my chunk engine. I timed it out, and in its current state it takes a total ~5 seconds per chunk to fill each face's list.

I have a check to see if each face of a block is visible and if it is not visible, it skips it and moves on.

I'm using a dictionary (unordered map) because it makes sense memorywise to just not have an entry if there is no block.

I've tracked my problem down to testing if there is an entry, and accessing an entry if it does exist. If I remove the tests to see if there is an entry in the dictionary for an adjacent block, or if the block type itself is seethrough, it runs within about 2-4 milliseconds.

so here's my question: Is there a faster way to check for an entry in a dictionary than .ContainsKey()? As an aside, I tried TryGetValue() and it doesn't really help with the speed that much.

If I remove the ContainsKey() and keep the test where it does the IsSeeThrough for each block, it halves the time, but it's still about 2-3 seconds. It only drops to 2-4ms if I remove BOTH checks.

Here is my code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

using System.Runtime.InteropServices;
using OpenTK;
using OpenTK.Graphics.OpenGL;
using System.Drawing;



namespace Anabelle_Lee
{
    public enum BlockEnum
    {
        air = 0,
        dirt = 1,
    }
    [StructLayout(LayoutKind.Sequential,Pack=1)]
    public struct Coordinates<T1>
    {
        public T1 x;
        public T1 y;
        public T1 z;

        public override string ToString()
        {
            return "(" + x + "," + y + "," + z + ") : " + typeof(T1);
        }
    } 
    public struct Sides<T1>
    {
        public T1 left;
        public T1 right;
        public T1 top;
        public T1 bottom;
        public T1 front;
        public T1 back;
    }
    public class Block
    {
        public int blockType;

        public bool SeeThrough()
        {
            switch (blockType)
            {
                case 0:
                    return true;   
            }
            return false ;
        }
        public override string ToString()
        {
            return ((BlockEnum)(blockType)).ToString();
        }
    }

    class Chunk
    {
        private Dictionary<Coordinates<byte>, Block> mChunkData;  //stores the block data
        private Sides<List<Coordinates<byte>>> mVBOVertexBuffer;
        private Sides<int> mVBOHandle;
        //private bool mIsChanged;
        private const byte mCHUNKSIZE = 16;

        public Chunk()
        {
        }

        public void InitializeChunk()
        {   //create VBO references
#if DEBUG
            Console.WriteLine ("Initializing Chunk");
#endif

            mChunkData = new Dictionary<Coordinates<byte> , Block>();

            //mIsChanged = true;

            GL.GenBuffers(1, out mVBOHandle.left);
            GL.GenBuffers(1, out mVBOHandle.right);
            GL.GenBuffers(1, out mVBOHandle.top);
            GL.GenBuffers(1, out mVBOHandle.bottom);
            GL.GenBuffers(1, out mVBOHandle.front);
            GL.GenBuffers(1, out mVBOHandle.back);

            //make new list of vertexes for each face
            mVBOVertexBuffer.top    = new List<Coordinates<byte>>();
            mVBOVertexBuffer.bottom = new List<Coordinates<byte>>();
            mVBOVertexBuffer.left   = new List<Coordinates<byte>>();
            mVBOVertexBuffer.right  = new List<Coordinates<byte>>();
            mVBOVertexBuffer.front  = new List<Coordinates<byte>>();
            mVBOVertexBuffer.back   = new List<Coordinates<byte>>();

#if DEBUG
            Console.WriteLine("Chunk Initialized");
#endif
        }
        public void GenerateChunk()
        {
#if DEBUG
            Console.WriteLine("Generating Chunk");
#endif
            for (byte i = 0; i < mCHUNKSIZE; i++)
            {
                for (byte j = 0; j < mCHUNKSIZE; j++)
                {
                    for (byte k = 0; k < mCHUNKSIZE; k++)
                    {
                        Random blockLoc = new Random();
                        Coordinates<byte> randChunk = new Coordinates<byte> { x = i, y = j, z = k };

                        mChunkData.Add(randChunk, new Block());
                        mChunkData[randChunk].blockType = blockLoc.Next(0, 1);
                    }
                }
            }
#if DEBUG
            Console.WriteLine("Chunk Generated");
#endif
        }
        public void DeleteChunk()
        {   //delete VBO references
#if DEBUG
            Console.WriteLine("Deleting Chunk");
#endif

            GL.DeleteBuffers(1, ref mVBOHandle.left);
            GL.DeleteBuffers(1, ref mVBOHandle.right);
            GL.DeleteBuffers(1, ref mVBOHandle.top);
            GL.DeleteBuffers(1, ref mVBOHandle.bottom);
            GL.DeleteBuffers(1, ref mVBOHandle.front);
            GL.DeleteBuffers(1, ref mVBOHandle.back);

            //clear all vertex buffers
            ClearPolyLists();

#if DEBUG
            Console.WriteLine("Chunk Deleted");
#endif
        }

        public void UpdateChunk()
        {
#if DEBUG
            Console.WriteLine("Updating Chunk");
#endif

            ClearPolyLists(); //prepare buffers

            //for every entry in mChunkData map
            foreach(KeyValuePair<Coordinates<byte>,Block> feBlockData in mChunkData)
            {
                Coordinates<byte> checkBlock = new Coordinates<byte> { x = feBlockData.Key.x, y = feBlockData.Key.y, z = feBlockData.Key.z };

                //check for polygonson the left side of the cube
                    if (checkBlock.x > 0)
                    {
                        //check to see if there is a key for current x - 1.  if not, add the vector
                        if (!IsVisible(checkBlock.x - 1, checkBlock.y, checkBlock.z))
                        {
                            //add polygon
                            AddPoly(checkBlock.x, checkBlock.y, checkBlock.z, mVBOHandle.left);
                        }
                    }
                    else
                    {
                        //polygon is far left and should be added
                        AddPoly(checkBlock.x, checkBlock.y, checkBlock.z, mVBOHandle.left);
                    }

                    //check for polygons on the right side of the cube
                    if (checkBlock.x < mCHUNKSIZE - 1)
                    {
                        if (!IsVisible(checkBlock.x + 1, checkBlock.y, checkBlock.z))
                        {
                            //add poly
                            AddPoly(checkBlock.x, checkBlock.y, checkBlock.z, mVBOHandle.right);
                        }
                    }
                    else
                    {
                        //poly for right add
                        AddPoly(checkBlock.x, checkBlock.y, checkBlock.z, mVBOHandle.right);
                    }

                    if (checkBlock.y > 0)
                    {
                        //check to see if there is a key for current x - 1.  if not, add the vector
                        if (!IsVisible(checkBlock.x, checkBlock.y - 1, checkBlock.z))
                        {
                            //add polygon
                            AddPoly(checkBlock.x, checkBlock.y, checkBlock.z, mVBOHandle.bottom);
                        }
                    }
                    else
                    {
                        //polygon is far left and should be added
                        AddPoly(checkBlock.x, checkBlock.y, checkBlock.z, mVBOHandle.bottom);
                    }

                    //check for polygons on the right side of the cube
                    if (checkBlock.y < mCHUNKSIZE - 1)
                    {
                        if (!IsVisible(checkBlock.x, checkBlock.y + 1, checkBlock.z))
                        {
                            //add poly
                            AddPoly(checkBlock.x, checkBlock.y, checkBlock.z, mVBOHandle.top);
                        }
                    }
                    else
                    {
                        //poly for right add
                        AddPoly(checkBlock.x, checkBlock.y, checkBlock.z, mVBOHandle.top);
                    }

                    if (checkBlock.z > 0)
                    {
                        //check to see if there is a key for current x - 1.  if not, add the vector
                        if (!IsVisible(checkBlock.x, checkBlock.y, checkBlock.z - 1))
                        {
                            //add polygon
                            AddPoly(checkBlock.x, checkBlock.y, checkBlock.z, mVBOHandle.back);
                        }
                    }
                    else
                    {
                        //polygon is far left and should be added
                        AddPoly(checkBlock.x, checkBlock.y, checkBlock.z, mVBOHandle.back);
                    }

                    //check for polygons on the right side of the cube
                    if (checkBlock.z < mCHUNKSIZE - 1)
                    {
                        if (!IsVisible(checkBlock.x, checkBlock.y, checkBlock.z + 1))
                        {
                            //add poly
                            AddPoly(checkBlock.x, checkBlock.y, checkBlock.z, mVBOHandle.front);
                        }
                    }
                    else
                    {
                        //poly for right add
                        AddPoly(checkBlock.x, checkBlock.y, checkBlock.z, mVBOHandle.front);
                    }


            }

            BuildBuffers();

#if DEBUG
            Console.WriteLine("Chunk Updated");
#endif
        }
        public void RenderChunk()
        {
        }

        public void LoadChunk()
        {
#if DEBUG
            Console.WriteLine("Loading Chunk");
#endif

#if DEBUG
            Console.WriteLine("Chunk Deleted");
#endif
        }
        public void SaveChunk()
        {
#if DEBUG
            Console.WriteLine("Saving Chunk");
#endif

#if DEBUG
            Console.WriteLine("Chunk Saved");
#endif
        }

        private bool IsVisible(int pX,int pY,int pZ)
        {
       Block testBlock;
       Coordinates<byte> checkBlock = new Coordinates<byte> { x = Convert.ToByte(pX), y = Convert.ToByte(pY), z = Convert.ToByte(pZ) };
            if (mChunkData.TryGetValue(checkBlock,out testBlock ))  //if data exists
            {
                if (testBlock.SeeThrough() == true) //if existing data is not seethrough
                {
                    return true;
                }
            }
            return true;
        }
        private void AddPoly(byte pX, byte pY, byte pZ, int BufferSide)
        {
            //create temp array
            GL.BindBuffer(BufferTarget.ArrayBuffer, BufferSide);

            if (BufferSide == mVBOHandle.front)
            {
                //front face
                mVBOVertexBuffer.front.Add(new Coordinates<byte> { x = (byte)(pX)    , y = (byte)(pY + 1), z = (byte)(pZ + 1) });
                mVBOVertexBuffer.front.Add(new Coordinates<byte> { x = (byte)(pX)    , y = (byte)(pY)    , z = (byte)(pZ + 1) });
                mVBOVertexBuffer.front.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY)    , z = (byte)(pZ + 1) });
                mVBOVertexBuffer.front.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY)    , z = (byte)(pZ + 1) });
                mVBOVertexBuffer.front.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY + 1), z = (byte)(pZ + 1) });
                mVBOVertexBuffer.front.Add(new Coordinates<byte> { x = (byte)(pX)    , y = (byte)(pY + 1), z = (byte)(pZ + 1) });
            }
            else if (BufferSide == mVBOHandle.right)
            {
                //back face
                mVBOVertexBuffer.back.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY + 1), z = (byte)(pZ) });
                mVBOVertexBuffer.back.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY)    , z = (byte)(pZ) });
                mVBOVertexBuffer.back.Add(new Coordinates<byte> { x = (byte)(pX)    , y = (byte)(pY)    , z = (byte)(pZ) });
                mVBOVertexBuffer.back.Add(new Coordinates<byte> { x = (byte)(pX)    , y = (byte)(pY)    , z = (byte)(pZ) });
                mVBOVertexBuffer.back.Add(new Coordinates<byte> { x = (byte)(pX)    , y = (byte)(pY + 1), z = (byte)(pZ) });
                mVBOVertexBuffer.back.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY + 1), z = (byte)(pZ) });

            }
            else if (BufferSide == mVBOHandle.top)
            {
                //left face
                mVBOVertexBuffer.left.Add(new Coordinates<byte> { x = (byte)(pX), y = (byte)(pY + 1), z = (byte)(pZ)     });
                mVBOVertexBuffer.left.Add(new Coordinates<byte> { x = (byte)(pX), y = (byte)(pY)    , z = (byte)(pZ)     });
                mVBOVertexBuffer.left.Add(new Coordinates<byte> { x = (byte)(pX), y = (byte)(pY)    , z = (byte)(pZ + 1) });
                mVBOVertexBuffer.left.Add(new Coordinates<byte> { x = (byte)(pX), y = (byte)(pY)    , z = (byte)(pZ + 1) });
                mVBOVertexBuffer.left.Add(new Coordinates<byte> { x = (byte)(pX), y = (byte)(pY + 1), z = (byte)(pZ + 1) });
                mVBOVertexBuffer.left.Add(new Coordinates<byte> { x = (byte)(pX), y = (byte)(pY + 1), z = (byte)(pZ)     });
            }
            else if (BufferSide == mVBOHandle.bottom)
            {
                //right face
                mVBOVertexBuffer.right.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY + 1), z = (byte)(pZ + 1) });
                mVBOVertexBuffer.right.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY)    , z = (byte)(pZ + 1) });
                mVBOVertexBuffer.right.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY)    , z = (byte)(pZ)     });
                mVBOVertexBuffer.right.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY)    , z = (byte)(pZ)     });
                mVBOVertexBuffer.right.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY + 1), z = (byte)(pZ)     });
                mVBOVertexBuffer.right.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY + 1), z = (byte)(pZ + 1) });
            }
            else if (BufferSide == mVBOHandle.front)
            {
                //top face
                mVBOVertexBuffer.top.Add(new Coordinates<byte> { x = (byte)(pX)    , y = (byte)(pY + 1), z = (byte)(pZ)     });
                mVBOVertexBuffer.top.Add(new Coordinates<byte> { x = (byte)(pX)    , y = (byte)(pY + 1), z = (byte)(pZ + 1) });
                mVBOVertexBuffer.top.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY + 1), z = (byte)(pZ + 1) });
                mVBOVertexBuffer.top.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY + 1), z = (byte)(pZ + 1) });
                mVBOVertexBuffer.top.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY + 1), z = (byte)(pZ)     });
                mVBOVertexBuffer.top.Add(new Coordinates<byte> { x = (byte)(pX)    , y = (byte)(pY + 1), z = (byte)(pZ)     });
            }
            else if (BufferSide == mVBOHandle.back)
            {
                //bottom face
                mVBOVertexBuffer.bottom.Add(new Coordinates<byte> { x = (byte)(pX)    , y = (byte)(pY), z = (byte)(pZ + 1) });
                mVBOVertexBuffer.bottom.Add(new Coordinates<byte> { x = (byte)(pX)    , y = (byte)(pY), z = (byte)(pZ)     });
                mVBOVertexBuffer.bottom.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY), z = (byte)(pZ)     });
                mVBOVertexBuffer.bottom.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY), z = (byte)(pZ)     });
                mVBOVertexBuffer.bottom.Add(new Coordinates<byte> { x = (byte)(pX + 1), y = (byte)(pY), z = (byte)(pZ + 1) });
                mVBOVertexBuffer.bottom.Add(new Coordinates<byte> { x = (byte)(pX)    , y = (byte)(pY), z = (byte)(pZ + 1) });
            }
        }
        private void BuildBuffers()
        {
#if DEBUG
            Console.WriteLine("Building Chunk Buffers");
#endif

            GL.BindBuffer(BufferTarget.ArrayBuffer, mVBOHandle.front);
            GL.BufferData(BufferTarget.ArrayBuffer, (IntPtr)(Marshal.SizeOf(new Coordinates<byte>()) * mVBOVertexBuffer.front.Count),
                          mVBOVertexBuffer.front.ToArray(), BufferUsageHint.StaticDraw);

            GL.BindBuffer(BufferTarget.ArrayBuffer, mVBOHandle.back);
            GL.BufferData(BufferTarget.ArrayBuffer, (IntPtr)(Marshal.SizeOf(new Coordinates<byte>()) * mVBOVertexBuffer.back.Count),
                          mVBOVertexBuffer.back.ToArray(), BufferUsageHint.StaticDraw);

            GL.BindBuffer(BufferTarget.ArrayBuffer, mVBOHandle.left);
            GL.BufferData(BufferTarget.ArrayBuffer, (IntPtr)(Marshal.SizeOf(new Coordinates<byte>()) * mVBOVertexBuffer.left.Count),
                          mVBOVertexBuffer.left.ToArray(), BufferUsageHint.StaticDraw);

            GL.BindBuffer(BufferTarget.ArrayBuffer, mVBOHandle.right);
            GL.BufferData(BufferTarget.ArrayBuffer, (IntPtr)(Marshal.SizeOf(new Coordinates<byte>()) * mVBOVertexBuffer.right.Count),
                          mVBOVertexBuffer.right.ToArray(), BufferUsageHint.StaticDraw);

            GL.BindBuffer(BufferTarget.ArrayBuffer, mVBOHandle.top);
            GL.BufferData(BufferTarget.ArrayBuffer, (IntPtr)(Marshal.SizeOf(new Coordinates<byte>()) * mVBOVertexBuffer.top.Count),
                          mVBOVertexBuffer.top.ToArray(), BufferUsageHint.StaticDraw);

            GL.BindBuffer(BufferTarget.ArrayBuffer, mVBOHandle.bottom);
            GL.BufferData(BufferTarget.ArrayBuffer, (IntPtr)(Marshal.SizeOf(new Coordinates<byte>()) * mVBOVertexBuffer.bottom.Count),
                          mVBOVertexBuffer.bottom.ToArray(), BufferUsageHint.StaticDraw);

            GL.BindBuffer(BufferTarget.ArrayBuffer,0);

#if DEBUG
            Console.WriteLine("Chunk Buffers Built");
#endif
        }
        private void ClearPolyLists()
        {
#if DEBUG
            Console.WriteLine("Clearing Polygon Lists");
#endif

            mVBOVertexBuffer.top.Clear();
            mVBOVertexBuffer.bottom.Clear();
            mVBOVertexBuffer.left.Clear();
            mVBOVertexBuffer.right.Clear();
            mVBOVertexBuffer.front.Clear();
            mVBOVertexBuffer.back.Clear();

#if DEBUG
            Console.WriteLine("Polygon Lists Cleared");
#endif
        }

    }//END CLASS

}//END NAMESPACE

© Game Development or respective owner

Related posts about c#

Related posts about opengl