Minecraft Style Chunk building problem
- by David Torrey
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
