New Version Released + Website

I've pushed out a new version (.0a1.0.1.4151.31367) to the testers.  The game should load faster now and take up less memory.  My Dictionary<Vector3,bool> that stored all visible cubes is now a Hashset<Int16>.  Almost as fast but a lot less memory, so it's worth it.  I also just realized that I forgot to update the version number to .0a2.

Feature-wise, you can now switch the type of block that they're adding by using the number keys.  ~ key is a hard stone, 1 and 2 are stone and dirt, 3 and 4 are water and 0 is whatever the texture algorithm picks.  I've re-enabled fog and added clouds and I've added a primitive day/night cycle.  I've created a 1x500px image file that has all the colors starting with nighttime->sunrise/set->daytime.  I load that in, pull all of those colors into a Color[500] array and dispose of it.  The day is 500 ticks long (each tick lasting a second) and I change the color of the sky by setting it to whatever that position in the gradiant is.  The file is located in the %appdata%/.r01 folder and is called skyColor.png.

Lastly, I've switched r-01.com to a new server and am working on setting it all up.  Until then, the forums are down.  Hopefully I can put something pretty together by the end of the week.

Clouds

Nothing amazing, but it's a start :]

I also have them slowly moving along the X axis.  I'm going to make it so different altitudes have different wind speeds.

All I've been doing is playing.

I know I should be working on stuff, but I've spent most of the day playing.  I did add a "sprint" capability and the ability to pick what type of block you want to add.  For the most part, though, I've just been creating my mountain home and putting beacons everywhere so I don't get lost.

This game is fun.

Screenshots + Video

Nothing besides that really.. just some screenshots and a video :]

 

~

More Optimization and Mod Support

I know I was supposed to move onto the next version, but I just wasn't happy so I went back to the drawing board.

Long story short, cubes used to be ~16-26 bytes each (depending on how many faces are visible.  Then (thanks to the help, again, of the guys at SA and reddit) I realized that I don't even need to store the cube position.  Everytime I reference a cube I'm going through some kind of dictionary that has the position stored as a key.  I pulled that Vector3 out.

Next on my list of attack was the type.  I don't have more than 256 texture types (and if I do eventually, it's easy to change it) so I switched that from an Int16 to a byte.

Next was the visible faces.  That's normally in a List<Int16>.  I was able to fit all the data into a byte.  I did that by splitting up the byte into 3 parts:  the first digit, the second and the third.  If the first digit is 1, the front is visible.  If it's 2, the back is visible.  If it's 0, neither are visible.  If the second digit is 1, the top is visible.  2, bottom.  0, neither.  3, both top and bottom.  The last digit is a special case.  If it's 1, the left side is visible.  2, right side.  0, neither side.  If the third digit is > 5, we subtract 5 from the value to get the official size and set the first digit to 3 (both front and back are visible).  The reason I did it this way is since I wanted to fit it all into a byte, the value couldn't be more than 255.  That means the first digit has to always be 2 or less.  The third digit can be any value since the highest the first and second digits can be is 2 and 3 respectively, so I used that as the key.  Sounds complicated, but here are some examples:

123
1:  front face visible
2:  bottom face visible
3:  both left and right faces are visible

201
2:  back face visible
0:  neither top nor bottom are visible
1:  left face visible

005
Due to the 5 in the third digit, we subract 5 from it and the value changes to what would be 300.
3:  both front and back faces visible.
0:  neither top nor bottom visible
0:  neither right nor left are visible

I hope those examples fully explain it.  Thanks to these changes, each cube now takes 2 bytes total.  Coming from 16-26, that's a huge memory saver.

I'm going to keep working on some performance mods but while I'm doing that, I'm also thinking of .02a.  After I am happy with this optimization stuff, I'm going to start adding plants and creatures.  I was thinking about how I want to do creatures when I realized something.  I'm going to be spending lots of time creating different plant types and creatures to put into the game.  If there's one thing I've learned from Minecraft, it's that the community can come up with things a lot faster than a single dev team can.  Based off that, I've decided that instead of writing plants/animals into the game, I'm going to write an API to add plants and animals.  Once I have that API, I'll create a base set of creatures that I'll bundle with the game (all plugged in through the API).  That way the second people get the game, they will have a way to add their own creatures.  If the game takes off, maybe someone can create some kind of creature 'library' so people can download different plants/animals into their game.

That way forward makes a lot more sense than relying on solely me to create things.

So next thing on my list is investigating Triangle Strips.  I currently use a Triangle List to create everything on the screen.  After investigating my memory, I realized that my vertex buffers take ~half of the RAM that my game uses.  Triangle Strips have less objects stored in memory due to the way they are built, so theoretically they should lower my RAM usage.

Theoretically.  I don't know if that's how it really is but I'm about to find out!

So.. a build and push to the testers tonight and Triangle Strips for the rest of the week.

Time to move onto the next version.

With this latest optimization, I think I can safely say that it's time to move onto Version .02a.

Thanks to the help from reddit and the SomethingAwful forums I was able to greatly reduce my memory footprint.  I am now implementing a Dictionary<Int16,bool> which should technically be the smallest possible Dictionary combination for me.  I did this by changing it so instead of storing the cubes global position to the world, I'm storing it's relative position to the chunk.  When I need its global position I just take its local position and add it to the chunk position.

The formula I'm using to convert from Vector3 to Int16 is:

location.X + (location.Y * 256) + (location.Z * 16)

To convert back, I do the following:

            int y = index / 256;
            index -= (short)(y * 256);
            int z = index / 16;
            index -= (short)(z * 16);
            int x = index;

            return new Vector3(x, y, z);

This won't give me any collisions as long as I stay within 16x128x16. With the memory I save, this is the best possible combination that I can think of between the memory saved from not storing any visible cubes and always doing an algorithm check to the speed from storing all visible cubes and only doing the algorithm check once.

With this, I'm going to force myself to go onto .02a and do more fun programming stuff.  I'll push it out to the testers and have them test it to make sure I didn't make any obvious mistakes.

Here are some more cool screenshots with a drawOut of 30 (61x61 chunk world).

Love this mountain range.

Working on some more performance optimizations.

I've been spending the last couple weeks working on performance optimizations.

The area I've been looking at, mainly, is where I store what cubes are visible in a chunk.  I'm currently using a Dictionary<Vector3,bool> with the Vector3 being a position of the cube and the bool as just a throw-away variable.  It's the smallest possible type as it only takes up 1 byte.  The reason I'm using a Dictionary is I want to be able to do a lookup without having to search through the whole array.  Dictionaries are indexed and have an O(1) key search, but they also use a good amount of overhead.  I decided to test different types of dictionaries and see how much space they take.  I created a trio of nested for loops to insert 32,768 objects in the Dictionary (the size of a full chunk).  By changing the types, I was able to see the amount of bytes each Dictionary took.  Here are my results:


18,568 dictionary<string,bool>
15,444 dictionary<vector3,bool>
15,424 dictionary<vector3,int/int16>
13,620 dictionary<int,bool>
13,612 dictionary<int16,bool>
13,608 dictionary<int,int>
13,588 dictionary<int16,int16>

I knew the <string,bool> would be high, but I tested it anyway for good measure.  My current solution is 2nd highest (<vector3,bool>) and the lowest solution simply isn't feasible (<int16,int16>).  What is feasible, though, is the <int,int> or <int,bool> solutions.  The only problem is that it'd have to be a 1-way conversion.

When I instantiate a chunk, I go through every possible cube position x,y,z and check if a cube is supposed to be there.  If it is, I put it into an Dictionary<Vector3,bool> called allCubesVisible.  After that's all done, I go to the next step which is detect which cube faces should be displayed.  I use a foreach(Vector3 location in allCubesVisible.Keys) to go through the dictionary and build the faces.  If a cube is visible, I add it to a master Dictionary<Vector3,bool> called allCubes.  allCubes only has cubes with visible faces.  From here on out, allCubesVisible becomes a lookup table and nothing else (it's cheaper to check if a key exists in a dictionary than it is to run the Perlin Noise algorithm each time).

So my thinking is that once I'm done figuring out the initial set of visible cubes, I can convert my allCubesVisible dictionary from <vector3,bool> to <int,int>.  Since I won't need to go through the allCubesVisible through a foreach anymore, I can convert it without looking back.  I found a formula online that I can use:   

index = x + (y * chunkSize) + (z * chunkSize * chunkSize);

[edit:  that formula doesn't work.  It generates duplicates.  Time to figure out a new one.]

I don't think there's a way to go back to a Vector3 position from that, but it'd still give me a unique index for each position that I can use as a lookup.

So anyway, I'm toying around with a lot of ideas.  One of the concepts I toyed with is destroying the allCubesVisible Dictionary and just running the Perlin Noise function check each time.  This resulted in a drastically lower memory profile, but chunks went from taking 100-200ms to be built to 4-500ms.  It let me build a lot more cubes though and I got several nice screenshots from it.

Neat chain of islands off the coast.

Mountain range out in the distance.

Wish I had a skybox so the in-game screenshot didn't look so bad..  maybe I'll take a break from optimization and dip my feet into .02a to add a skybox.

Pics from the latest build.

My computer used to have a max drawOut of 8.  That's 17x17 chunks.  That was a pretty decent distance so I was ok with it (temporarily).  With the new optimizations, my computer can do up to 41x41 chunks (drawOut of 20).

Here's what that view looks like:

Awesome.

Code optimization build has been released to testers.

Details of the major changes here:  http://r-01.com/f/viewtopic.php?f=3&t=5

With all the changes I've made, I've gone from being able to support ~3 million cubes in the previous build to over 10 million in this one.  Highest # I've had reported back from a tester is 10,597,391.

Awesome.

Next step is to start removing from the pool.  I have an idea on how to make it elastic so it can grow/shrink as needed without having a set number, but I'll see if I can implement it.  Going to keep going forward with memory optimizations before I move onto the next version.

Latest Code Optimizations

I've been chugging away at the code lately fixing memory leaks as I go along.  I posted this thread on reddit yesterday and got some great advice.

First off, XNAs garbage collection is pretty bad.  Even when I thought I was deleting objects from memory, I more than likely wasn't.

The first type of solution for this is reuse.  I was already instantiating as little new objects as possible but it was due to performance issues.  Instantiating an object takes CPU and it's a waste when you can use an old one.  I wanted to make sure I did it as little as possible, so I went through the code with a fine toothed comb and took out even more new objects.

The second thing I did was create object pools.  Whenever a new chunk needs to be created, I instantiate it and then build() it.  Inside of build(), I instantiate up to 32,768 (a completely full chunk) new cubes.  When I'm done with a chunk, I remove those cubes and then remove the chunk from memory.  Or at least I thought I was doing that (damn you XNA).

With an object pool, I am still requesting a new cube.  This time I'm requesting it from the pool though.  For the first several chunks, I am instantiating a new object each time.  The difference is when I delete a chunk.  Instead of removing it from memory, I mark it as 'free'.  The pool notices this and the next time I request a chunk, it resets the values in this free one and gives me that instead.  The same thing happens with the cubes.  This means that instead of creating several million new cube() instances throughout the game life, I'm only create a couple hundred thousand that are reused over and over again.

After setting that up, I'm still having some issues that I've narrowed down to be threading problems.  I decided to change how I use threads.  Beforehand, I had 3 threads.  1 for the main game, 1 for the delete chunks functionality and 1 for the add chunks functionality.  I decided to combine the delete chunks and add chunks functionality into 1 thread so I was always referencing the pool from the same thread (removing any threading issues). 

While I haven't perfected it yet, my memory footprint is drastically lower.  I'm going to spend this week hopefully focusing on that and perfecting it.  No new gameplay additions will happen until I figure this out.

Just plugging some memory leaks..

After I considered .01a complete, I played through a couple seeds for the week just to get a feel for things before I went forward.  One thing I noticed is that as time goes on, the game uses more and more memory.  Memory leaks - the bane of my existance.

I've been going through the code as meticulously as I can trying to find where this leak is coming from but I haven't had much luck.  The good thing about this, though, is that as I'm going through code I have been optimizing things as much as possible.  I've come up with some ideas about how I can lower the memory footprint even more and I might try and implement them.  I rewrote the chunk unloading code to be more efficient too.  All this effort is not to waste :]

So after I finish this, I'm going to add a skybox with a night/day cycle.  Once that's done I'll add some plants/animals.

I did set up a preliminary website at http://www.r-01.com.  I have some forums up too and I think once I get .02a done, I'll release the alpha on there so I can get more testers.

Version .01a is Complete!

I'm really, really excited to announce that Version .01Alpha of R-01 is finally complete. Tonight I added support for adding and deleting cubes.  I also finished up chunk loading and with those two done, this build is officially complete.  I'm going to publish a new version for my testers to muck around in later this week.


I've learned a ton and there's still a lot more to go.  Version .02a is going to focus primarily on gameplay issues.  The world algorithm will be my primary task for the next few weeks and that'll require me to really learn how to optimize my code so I can get that chunk loading down to <100ms for the higher chunks.

Thanks for coming along this far.  Time for .02a.

~
Roy

Character Controller, new World Algorithm and... another video!

I've been working a lot on a better world algorithm.  The last algorithm was pretty but it really only generated rolling hills at various heights (and it didn't even do that very well).  The new one will generate a preferred height for the chunk itself and then build on that height.  It'll try and make it so the cubes will generate primarily around that area, but it won't necessarily completely limit it (as you'll see in the youtube video).  I'm somewhat happy with what I have so far but it does generate some definable squares.  I have an idea on how to fix them so hopefully that'll be in the new release.

The other thing I worked on is gravity and a character controller.  The player can now walk and jump around.  I need to refine the keyboard controls so they're not as jumpy but the game works great with a 360 controller :]  I also did a lot of performance changes.  Beforehand, I was building a chunk (deciding which cubes are present and which ones aren't (Step 1)), then iterating through all those cubes to figure out which faces are visible (Step 2), and lastly building the TriangleList to send to the GPU (Step 3).  Now I've combined the Steps 1 and 2 into one loop and worked on optimizing Step 3.  This has gotten most of my chunks to generate under 100ms (my target is 150ms per chunk with all wildlife added, so I need the wiggle room).  Some of the higher mountain ranges that have a lot of cubes visible will take up to 200-300ms to generate and that is unacceptable to me, so I will continue to work on making performance optimizations.

The only thing left to do before I can declare version .01a complete is adding/removing cubes.  I toyed around with it for a little but haven't found a final answer.  I also got distracted with the world algorithm and switched to that, so that didn't help.  I will go back to working on that this week so I can officially say that this version is done.  The next version (.02a) will be mainly world items (fun stuff).  This includes more work on the world algorithm, multiple biomes, skybox, day/night cycle, fauna, basic creatures and an actual HUD.  I'll update my roadmap on the right when I get there.

So without further adieu, I give you the latest youtube video (click on it to go to the actual youtube page):

Threading and a new video.

I've fixed the threading issue I had.  The solution came in the form of compartmentalization.

Before my change, I had a giant allCubes Dictionary that stored every single cube in the game.  There was another Dictionary called _terrain that stored each chunk by it's Vector3 location.  The chunk class had a list of cubes that cross-referenced the allCubes Dictionary.  Sounds more complicated than it is.

Anyway, whenever I added/removed a cube or chunk I had to update that huge dictionary.  When you have 2 million cubes in the dictionary, you're going to be referencing it constantly.  This is why adding/deleting from it was causing so many issues.

I could have written a thread-safe dictionary or I could have used ConcurrentDictionary, but I felt that having the giant allCubes dictionary was a bad approach to begin with.  By moving those cubes into the chunk class and referencing them from there, I've compartmentalized the areas that I'm constantly accessing.  I can add/remove cubes from each individual chunk without bothering another one.  That, my friends, is good business.

I didn't do this from the beginning mainly because I was short sighted.  Simple as that.

I also fixed my texture issue.  Switching my sampler from a linear wrap to a point clamp stopped the shader from reading too far out.

Now that chunk loading/unloading has been completed, I'm going to work on adding/removing cubes.  I've been thinking about it a lot and I think I'm going to add a Dictionary called changes inside of each chunk class.  I'll use the Vector3 position of the change for the key and create a change class that will store the type of change.  That way I only have to save that changes dictionary and reference it when I rebuild the chunk each time.  There's no need to store the entire chunk when I know it's going to be consistent.

I'm also going to keep working on the character controller.  I don't know why but I hate programming a character controller.  Everytime I go to start it I find something else I can do.  Eventually I'm going to want to go past Version .01a though and I can't do that without a character controller.

So here's the latest terrain video.  No audio but at least it's pretty.

Threading issues..

I'm having an issue with unloading chunks and it's related to threading.

When I unload a chunk, I need to remove all the cubes from the global cube pool.  I'm currently storing those cubes inside a public static Dictionary<Vector3, cube> named, appropriately, allCubes.  allCubes is inside of a static class named gameData so I can access it from wherever I need.  The Vector3 key in allCubes is the location of the cube itself.  So to make a long story short, the cube at 0,0,0 has the key of Vector3(0,0,0) and I reference it using allCubes[Vector3(0,0,0)].whateverINeed.

Most of the time, all I'm doing is reading this Dictionary and adding to it when I create a new chunk.  Now that I'm working on unloading chunks, I need to remove the cubes from that Dictionary.  If there was no threading, it would be a simple matter of removing it and not thinking twice.  Unfortunately with threading, life is not that easy.  If I pull a cube from the dictionary while I'm iterating through it, I'm going to have an exception thrown.  I've been trying to use the lock() method but that doesn't seem to help. 

Anyway, I thought I knew enough about threading to get by, but clearly that's not the case.  I'll be focusing on that for the week and probably won't go forward until I figure this out.

So until then..

Quick update with textures..

Thought I'd post a quick update.  My textures aren't the greatest but it's better than all 1 grass texture.

 

New Vertex Buffer Controller..

Quick update for tonight.  I've written a controller that can handle multiple vertex buffers.  I wanted to stress test it, so I ran it until I ran out of memory.  I have a pretty shitty video card, but I topped out at ~3 million cubes, a little over 3 million vertices and 531 chunks (each chunk is 16x16x128).  The first screenshot is from the first stress test while the 2nd one is the test where I ran out of memory.

 

 The other awesome part is I was still averaging 63fps :]

Roadmaps and roadtrips...

I wanted to add a crosshair to the screen, so I thought it'd be as simple as using a sprite and just drawing it to the screen.  After doing that, all of my primitives were transparent and messed up.  I researched and couldn't find much, so I resorted to the forums and they led me to a blog post that explained it all.  I should've realized it because it makes sense, but basically when you draw 2d to the screen after you draw 3d, GraphicsDevice resets a bunch of parameters.  Primarily these:

1:        GraphicsDevice.BlendState = BlendState.Opaque;  
2:        GraphicsDevice.DepthStencilState = DepthStencilState.Default;  
3:        GraphicsDevice.SamplerStates[0] = SamplerState.LinearWrap;   

After resetting them back to their previous state, I have the following:

 

Nothing fancy but at least now it's easy to see the FPS and player position.  I've also created a tumblr account to upload some more screenshots to.  http://r01.tumblr.com is the address.

Lastly, if you look to the right, you'll notice a new box showing the current version and its planned roadmap.  I might add/remove stuff as I go along but that's the current plan.

No major updates besides that.  Lots of reading about HLSL and as you can see, a decent shader is going to be required before I can move onto the next version.

Magically, a YouTube video. Also I really need to learn HLSL.

Made some great progress these last few days.  First off, the obligatory pictures:

 

As you can see, I've been toying around with my world gen algorithm.  It finally looks somewhat presentable.  It's very heavy on the top side and I'm not generating any caves yet, but it's still really fun to toy around in.

On the technical side, I'm finally generating the mesh more efficiently.  I'm using indexes so I only have to use 4 vertex points instead of 6 to create 2 triangles.  I also had an issue before with generating faces at the edges of chunks.  I was only checking for cubes inside the current chunk, so when I got to the edge the algorithm thought that there were no cubes on the other side and built a face there.  This wasted a lot of memory if there was a cube in another chunk there, so I'm now checking outside of the chunk when I hit the edge.  Before I threw that in there, for 9 chunks with seed 1143 (my test seed) I was drawing 348,552 triangles with 116,184 indexes.  After I fixed that glitch, my triangles went down to 190,812 and indexes down to 63,604.  This lets me add a lot more chunks before running out of memory.

I also fixed a glitch I had with my textures.  Nothing fancy but at least it doesn't look as crappy.  As my title says, though, I really need to learn HLSL.

Until next time..

HLSL, Threading and more..

Before I give a wall of words, I'll start with 2 screenshots.

I wanted to stress test my renderer, so I generated a 128x128x128 chunk.  It took ~15 seconds to go from launch -> drawing on the screen.

The last few days, I've spent a lot of time getting multi-threading working, reading about HLSL and optimizing my code.

My first issue was getting multi-threading working.  Whenever a new chunk would be generated, the game would pause for a second while I build it and then draw it to the screen.  I could optimize and optimize and work on my code to make it as fast as possible, but at the end of the day the possibility of the pause is still there.  By building my chunk on a different thread I am removing the possibility of that pause.  Now while the concept sounds easy, it's a bit harder to implement.  Issues arise when you have one thread trying to modify a variable at the same time as another thread.  Luckily there are ways to combat this and it's just a matter of organizing your code to make sure that never happens.  This means locking a variable before you change it, not letting another thread touch the variable until it's unlocked and unlocking it when you're done.

After I got that working, I started having issues with my Draw() function.  I was generating more vertices than DrawUserPrimitives() can handle.  Originally, I was building all my mesh and adding it to a giant VertexPositionNormalTexture[] array.  I was then pushing that array to the GPU everytime I called Draw() (which was every single frame).  If you remember from my older posts, pushing data to the GPU is one of the most expensive things you can do.  After reading about my issue some more, I also learned that DrawUserPrimitives() is only meant for objects that will be changing between frames.  Vertex Buffers are meant for meshes that are constant, such as my terrain.  With a Vertex Buffer, you generate the mesh, push it to the GPU once and the GPU stores it on there.  When it comes time to drawing, the GPU pulls your mesh from its own RAM and draws it from there (saving you lots of time).  You still want to change the mesh as little as possible to save on sending a new mesh to the GPU, but at least you only have to send the mesh once per change instead of once per Draw() call.

Between the Vertex Buffer and the threading, generating a 16x128x16 chunk and displaying it to the screen is instantaneous.  I'm really, really happy with the speed so far.

Next on my list was shaders and HLSL is the shading language used in XNA.  The book I have briefly covers HLSL.  I also found this website which has several shader tutorials.  The C# code on that site is for XNA3 but the HLSL code had no issues.  I can't say that I fully understand HLSL yet.  It's going to take me a while before I get it down, but using that site I was able to create a shader that'll do for now.

So that's where I currently am.  The rest of the week will be spent reading about HLSL and trying to understand it more.  I've also started working on a world generation algorithm.  I've been reading a lot about different ways to go about it so I'm really just experimenting now.

So until next time..