iCE³ - clone of Minecraft

[Sylmael]

:idea:
Oh thanks, i understand now perfectly. Well I work on a minecraft clone myself too. (first tried coding it in c++ but then moved to java and lwjgl). Maybe i can help you with my pearls of wisdom and knowledge somehow.

[Kalith]

That would be greatly appreciated
Do you have a website or some other place where we can take a look at what you've done ?
And also, what made you switch to Java ?

[Groogy]

Actually Kal I have to say your lighting looks way better. You also seem to be one with some understanding to the whole thing. (Lighting and 3D Graphics) Which is more than you can say for Notch.

I would hope you soon end up with a more complete version with maybe survival? Maybe even do better and realistic water instead of that annoying fake algorithm in Minecraft.

[Kalith]

Actually Kal I have to say your lighting looks way better. You also seem to be one with some understanding to the whole thing. (Lighting and 3D Graphics) Which is more than you can say for Notch.

Thanks ! I still think that his lighting is better than mine though : [sample from Minecraft 1.8.1].
Although, I'd say that Notch has learned many things since he started Minecraft. True, the very first versions of his game were full of possible optimizations, unexpectedly slow etc. But the community, and - I guess - his co-workers, helped him a lot in improving the whole thing.
I don't know his previous works, but to me Minecraft looks like his first project. We all start somewhere : I for example am not proud of the very first lines of code of my life...
And you have to admit that he has a good sense of what a proper gameplay is

I would hope you soon end up with a more complete version with maybe survival? Maybe even do better and realistic water instead of that annoying fake algorithm in Minecraft.

It depends on what you mean by "soon". As I said in a previous post, I worked on this project during my summer holidays, and now I'm back to work, serious work, so I have very little time to spare.
I still feel the current version is buggy : there are some remaining collision bugs, chunk generation is not very pleasant performance wise (although chunk loading from disk is), and I miss several important features (like different light attenuation per block type and, as you said, proper water physics*).
Before thinking about a "survival mode" (for non Minecraft players : it's the game mode that contains monsters etc, to be compared to "creative mode" where you cannot die and have an infinite inventory), I'd first need to settle all this.
Then, and only then, I'd have to implement drops, a real inventory, monsters, weapons, a really interesting terrain generation algorithm, and on top of that : networking...
That's huge.

So I'm sorry but to be realistic, it won't be ready before 2012 (and we'll all be dead then... no ?).

* : Note that, in a blocky world of that kind, you can't do everything you want. Minecraft's water physics is probably the simplest ok-looking implementation, but it works and allows for interesting gameplay. Better water physics (like in Terraria for example) has a cost, but I still haven't thought deeply about it.

[Sylmael]

Saddly i don't have a website or blog for shoving my project. But i can share some screenshots. Sorry for the image quality. It's night here and i start to feel very sleepy.

About the project :
* currently there is a big bug after refactoring chunk class so the framerate is pretty bad
* working sliding collision
* working animated models
* sun & block lighting but only per face
* terrain and cave generator
* block placing, removing
* sky with sun (sunrise/sunset), moon, stars and clouds
* raining and snowing







And sorry if i spam your topic with pictures. I can delete them, or you can,  after watching.

Yes and why i switched to java. Simple reason : portability, faster developing and flexible code. Who knows, maybe i port it back to c++ someday.

[Kalith]

Looking great !

I have a question then : how do you perform frustum culling ? Do you test each chunk against the camera's frustum on each frame ?
For now, I only perform culling when the camera moves. When the camera is still, performances are good of course, but not when moving... (it costs  5ms on my computer).
Do you have a special technique to improve that ?

[Groogy]

I can actually propose something. Use a octree for the chunks. Should be perfect and let you cut down on the amount of checks you have to do. The only problem would be that you have to be able to extend the octree somehow which would either require you to reconstruct it or add a new root level ontop of the previous one which increases the depth. Though I think if you implement a 2D grid ontop of the octree you should be able to have it extendable efficiently as well.

Wha I'm thinking is that you make it so that a octtree have 5-10 chunks in it each. So testing would first be "Find what octree to test against" and since the grid cells are so big it should be very fast( more or less, what is my position and take the cells surrounding it) and then you test against the octree's in selected cells to find what chunks.

Might even be able to get away with using Quadtree since if I remember correctly, chunks don't grow in one direction right? You don't generate more chunks when going up and down.

[Sylmael]

Thanks
This is the part i am trying to optimize now. I recalculate frustrum every frame even if the camera doesn't move (pretty hardcore i know).

Here is how it works :

* i have an array of big chunks 16x128x16 blocks (data) + bbox
* then i make 8 mini chunks (16x16x16 blocks) from each big chunk (8 display lists) and calculate their bbox as well

Render loop :
* looping through array of big chunks and testing against frustum : if in frustum then check which one from 8 mini chunks are in frustum too and add them to render array

It looks like simple octree algorythm.

[Kalith]

Yes, using octrees is a possible solution I've been thinking of.
I've never implemented such a system but that shouldn't be too hard, I'll think about it more, thanks !

Might even be able to get away with using Quadtree since if I remember correctly, chunks don't grow in one direction right? You don't generate more chunks when going up and down.

Actually no. That's the way Minecraft works, but I decided to allow unlimited depth and height (as Minetest does). It complicates things a little, but I think it is worth it.
You loose some performance, as you have much more chunks to deal with (10 times more approximately), but you can also use that at your advantage to perform more culling (Minecraft renders everything that is below your feets, even if you can't see it). For example, in the current version, every chunk (15x15x15) that is surrounded by non empty chunks is not rendered if all its faces are hidden. That helps a little.

Edit : cross posting !
Yes that's more or less the philosophy of the octree... I'll try to see what I can come up with, thanks

[Groogy]

I you need help with the octree just let me know.

I was thinking first that kD-tree's might be something because the cubes are more or less static. But then I remembered that if you remove a block then you have to recalculate the whole kD-tree and you would be VERY limited by what is possible to do.

I think Octree is the way to go. Just doing a single octree over the whole map won't cut it of course but I think you should start out with it and see the improvement. I can give you the code for finding a node fast for an object at aPosition with a size of aRadius:

Code: [Select]

Node *FindNode( const Vector3f aPosition, const float aRadius ) const
{
        Node *currentNode = myRootNode;
        while( currentNode != NULL )
        {
                bool straddle = false;
                int index = 0;
                float deltaX = 0;
                float deltaY = 0;
                float deltaZ = 0;

                deltaX = aPosition.x - currentNode->center.x;
                straddle = !( deltaX - aRadius > -currentNode->halfWidth && deltaX + aRadius < currentNode->halfWidth );
                if( deltaX > 0.0f )
                {
                        index = 1;
                }

                if( straddle == false )
                {
                        deltaY = aPosition.y - currentNode->center.y;
                        straddle = !( deltaY - aRadius > -currentNode->halfWidth && deltaY + aRadius < currentNode->halfWidth );
                        if( deltaY > 0.0f )
                        {
                                index += 2;
                        }

                        if( straddle == false )
                        {
                                deltaZ = aPosition.z - currentNode->center.z;
                                straddle = !( deltaZ - aRadius > -currentNode->halfWidth && deltaZ + aRadius < currentNode->halfWidth );
                                if( deltaZ > 0.0f )
                                {
                                        index += 4;
                                }
                        }
                }

                if( straddle == false )
                {
                        if( currentNode->children[ index ] != NULL )
                        {
                                currentNode = currentNode->children[ index ];
                        }
                        else
                        {
                                float step = currentNode->halfWidth * 0.5f;
                                Vector3f newCenter = Vector3f::Zero;
                                newCenter.x = currentNode->center.x + ( ( index & 1 ) ? step : -step );
                                newCenter.y = currentNode->center.y + ( ( index & 2 ) ? step : -step );
                                newCenter.z = currentNode->center.z + ( ( index & 4 ) ? step : -step );
                                currentNode->children[ index ] = new Node( newCenter, step, currentNode );
                                currentNode = currentNode->children[ index ];
                        }
                }
                else
                {
                        break;
                }
        }
        return currentNode;
}

There might be faster or better ways to do it. My class mates octree's check for straddle is a bit different. But they don't handle dynamically allocating new nodes. Anyway this is the basis for insertion. The rest is just collision checking with sphere against AABB and frustum vs AABB for each node as you traverse the tree. Removing an object from the tree should be the fastest(objects should remember what node they exist in)

[Sylmael]

One more question for you Kalith. Can you please explain me, which faces do you use when you calculate smooth - per vertex lighting?

[Kalith]

I you need help with the octree just let me know.

Thank you ! I'll keep you in touch

Can you please explain me, which faces do you use when you calculate smooth - per vertex lighting?

Sure ! Here is a little drawing, that will most likely be clearer than my words :


The exact same algorithm is used for LEFT, RIGHT, FRONT, BACK and BOTTOM faces (of course, except the fact that the drawing is rotated), and for any of their 4 vertices.

[Sylmael]

Wow, this sure will help me further. Thank you very much.

[easy]

Check this out!

[Kalith]

Nice initiative ! And thank you for picking up a picture of iCE3