Tuesday, May 03, 2011

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:

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

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

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.


Ephphatha said...

You can indicate which face is visible in a much clearer and easier method using bit masking.

You will need a set of constants to use as the masks, you may end up with the following values;

const char TOP = 1 << 0;
const char BOTTOM = 1 << 1;
const char FRONT = 1 << 2;
const char BACK = 1 << 3;
const char LEFT = 1 << 4;
const char RIGHT = 1 << 5;

A byte is 8 bits, and you only need 6 bits to store all the information needed about the visible faces of a cube.

Your cube data structure may look like;
public class Cube {
char faces;

You can now do a bitwise AND to determine if a face is visible.

if (cube.face & TOP) {
//The top face is visible

When the chunk is modified you can then set a face as visible by doing;
this.face = this.face | TOP; //The top face is now visible

or you can mark a face as no longer visible by doing;
this.face = this.face & ~TOP; //The top face is no longer visible.

You may want to look up bitwise operations on wikipedia if you've never used them before, but the basics are:
An AND operation (&) compares the two numbers bit by and returns a number with a 1 in each position that is also 1 in both of the other numbers.
An OR operation (|) compares two numbers and returns a number with a 1 in each position that is set to 1 in either of the two numbers.
The negation operation (~) returns a number which has a 1 where the input had 0, and 0 where the input had 1. If the input was 111, the output will be 000.

Roy said...

You need to use a uint for that. That takes up 4 bytes of space. My solution fits in 1 byte. Not as elegant, but it works and takes up 1/4 of the ram.

Joseph said...

You can implement Ephphatha's suggestion using a byte, but I suppose if you have something working then there would be no reason to change it unless it became an issue.