Need advice on best way to implement dynamic grid-based terrain

Hi,
I am an experienced java programmer and software developer although I have never created a video game using a gaming framework before.
I had a nice idea I wanted to work on in my spare time but before I get started I wanted to ask for opinions from more experienced users of JMonkeyEngine. So here it goes:

I wanted to create a 3D terrain consisting of many cells on a two-dimensional grid. Each cell has a height and a flat top. If two neighbouring cells have different height there is a completely vertical cliff connecting the two. It would look similar to classical isometric games like Final Fantasy Tactics or Tactics Ogre (see links below) but be in full 3D. The texturing and height of individual cells will change frequently during the game and needs to be updated in real time.

I am not exactly sure what the best way would be to create a world like this. My naive approach would be to create a custom mesh and specify all vertices and texture coordinates myself. I would tile the entire terrain into larger chunks, perhaps each chunk consisting of 128x128 cells. Would this be a good approach?

I was also thinking about having a water implementation where waves would be implemented as an animated mesh which is rising and falling continuously. Are there any implementations for something like already? What would be a good way to implement this myself, a custom mesh again?

Thank you for your help.

Example Final Fantasy Tactics:
Link: https://vignette1.wikia.nocookie.net/finalfantasy/images/a/a1/FFT_Battle.jpg

Example Tactics Ogre:

1 Like

The terrain sounds like any mine craft clone (except for the height of the blocks). So I’d venture to say you could search the forums for minecraft clones, in order to get started on the block framework. How you materialize the blocks is up to the shaders you choose.

But I think a more pertinent question is if you want to do it in 3d or in 2d. Because based on the examples you’ve given - I see no reason to do it in 3d. But then again, who am I to ask - I’m currently doing a top-down 2d game in jMonkeyEngine :stuck_out_tongue: just for the heck of it.

But I’d love to see a game dev blog in here if you do choose to continue with it. I see no reason it cannot be done.[quote=“RoomOfMush, post:1, topic:38390”]
I was also thinking about having a water implementation where waves would be implemented as an animated mesh which is rising and falling continuously. Are there any implementations for something like already? What would be a good way to implement this myself, a custom mesh again?
[/quote]

jME has a water filter, so I’d go with that to get started. Then down the road you can tweak it or roll your own.

1 Like

The terrain is not quite like minecraft because there will never be two cells on top of each other. For each coordinate in X and Y there will always be only one cell. And for most cells only the top face will be visible unless it has neighbours with different heights. So I believe there is definitely some way to improve it a lot more.

The examples I have shown have a fixed camera angle. I need a camera that can freely be rotated so a 3D implementation is a must.

Please correct me if I am wrong but the water filter from jME does not do what I wanted as far as I can tell. The water filter uses shaders to change the “texture” of the water. The waves are not actually 3D meshes but only differently coloured fragments. I want to implement the waves as dynamic meshes. Or is there another water filter I dont know about?

Thanks for the reply.

1 Like

But you could implement the blocks and then batch every tile so its essentially just one ‘tall’ block.

Is https://www.youtube.com/watch?v=JNHo0mEKGJs what you are searching for?

1 Like

I’m not an expert on that type of case, so not sure if there is a better approach or starting point. I think what you described will work fine even with the periodic changes you’d be making. Building your own meshes is challenging but really cool when you get it working. You’ll need to find a balance between mesh size and number of objects you’re rendering. Meshes too large (i.e. buffers too large), and pushing out changes will be a bottleneck. But (you seem to be aware) you can’t make them all tiny, because too many objects is another way to kill performance. 128x128 sounds like a good starting point for testing. I’ve been working on something similar for a case much more demanding and I haven’t had rendering issues (but, for desktops only).

I’m not sure if batching would even be needed, it depends on your object counts and changes being made. Depending on what’s going on, it could actually make things slower–it takes time to batch(). Maybe on this scale that’s not an issue but I know I’ve pushed it past acceptable limits before.

No physics involved, I assume. Only reason I mention it is, that would impact your basic design heavily so you’d need to start with testing that early.

What platforms are you targeting? If you want to do something mobile, performance is your biggest challenge (duh). Desktops should blast right through this kind of thing so you get to focus more on all the other fun problems you’ll inevitably run into.

1 Like

Is https://www.youtube.com/watch?v=JNHo0mEKGJs3 what you are searching for?

Yes, this looks very much like what I wanted. It would be simpler than in the video though. I dont need any reflections and there would not be any objects on top of the water surface. Is this a build-in feature of jMonkeyEngine or a third party creation? Is this freely available?

You’ll need to find a balance between mesh size and number of objects you’re rendering. Meshes too large (i.e. buffers too large), and pushing out changes will be a bottleneck. But (you seem to be aware) you can’t make them all tiny, because too many objects is another way to kill performance. 128x128 sounds like a good starting point for testing.

I was thinking about having up to a few million cells in a scene. Although each cell, individually would be a simple quad made of two triangles, rendering them all in each frame would be a bad idea. Does JME do the culling automatically when I create these 128x128 cell chunks as custom meshes? By the way, I would probably use a texture atlas (or array texture if that is supported) and all cells would use the same texture, material and shader.

No physics involved, I assume. Only reason I mention it is, that would impact your basic design heavily so you’d need to start with testing that early.

No real-world physics, no. I wanted to add some heavily simplified physics based on the cell grid though. I would like water from higher cells to flow down to lower cells, possibly with a particle effect but not necessarily. The water-flow logic would be similar to conways game of life.

What platforms are you targeting? If you want to do something mobile, performance is your biggest challenge (duh). Desktops should blast right through this kind of thing so you get to focus more on all the other fun problems you’ll inevitably run into.

I am not too sure yet. Since this is simply a hobby project I wanted to work on in my spare time I just wanted to get started and see what happens. I dont think I will ever get it finished so I am not spending much time thinking about mobile platforms.

I think I will get started working on those custom meshes then. Thank you both very much.

1 Like

The simplest way I can think of to get started is to just use a standard heightmap-based terrain, fixing the camera to your desired perspective (or not - i mean if it’s all 3D - when in rome…).

There is an implementation that should work out of the box here:

https://github.com/jayfella/TerrainWorld

Combine that with texture splatting for paths, etc… It comes with LOD and chunk removal.

But… the screenshot you posted is written nothing like the link I posted. It’s tile-based.

1 Like

When you say “cell” do you mean one grid square that a single character would stand on, or a 128x128 group of grid squares (16384 spaces to stand on)?

Each grid square would be two triangles, but you also have the sides/walls, and since you want to rotate, you’d have up to 8 additional tris (4 sides) worst case, so up to 10 total per grid square. With 4 vertices each side, that’s up to 20 vertices per grid square since I’m pretty sure you don’t want faces to share vertices.

I don’t think you’ll be able to do millions of dynamic spaces like that without some tricks. JME should cull stuff that’s totally outside of the view frustum (for rendering anyway) but I’m thinking you’ll face some memory and other issues if you just try to brute force things, even with that. I do believe you’ll be able to spit out small groups of grid spaces (ex. 128x128) pretty fast though, so you could start with that and see how well it scales.

Custom building geometry isn’t the fast path, if you’re not the patient type perhaps you can adapt something like the TerrainWorld posted above to do what you need. Getting the look you want is a challenge but it could be the way to go. I don’t have any experience with the challenges you’ll face in the genre you’ve picked, but I know some others here do…

For individual cell physics, heavily simplified or just a water/particle effect, I doubt you’d need (or want) Bullet and the complexities it’d bring. So nevermind. :slight_smile:

1 Like

Yes, what I called a “cell” would be a single grid square, a tile, a “point” in the game world. This afternoon I sat down and produced something simple which already generates the flat tops without any cliffs yet. Creating the custom mesh was not very difficult at all although I am not sure I am doing it the best way. I noticed the sample code on the wiki page (Link: https://jmonkeyengine.github.io/wiki/jme3/advanced/custom_meshes.html) is creating a lot of java objects and doing a lot of copying as well. Especially copying all vertex components one float at a time seemed incredibly slow for huge numbers of vertices.

Instead I am populating large float arrays and then wrap them in a FloatBuffer in bulk. Are those buffers memory mapped by the way? Or do I need to send changes down the pipe every time I am updating? I am currently using Mesh.setBuffer which does not accept an offset and size parameter so I dont know how to update only a small portion of the entire position buffer.

This is the code I am using for building the terrain chunks right now:


public class ChunkBuilder {
    
    public static final int CELLS_PER_CHUNK = CHUNK_W * CHUNK_H;
    
    // These are used for all created chunks
    private final float[] vertices = new float[CELLS_PER_CHUNK * 4 * 3];
    private final float[] texCoords = new float[CELLS_PER_CHUNK * 4 * 2]; // unused at the moment
    private final float[] colors = new float[CELLS_PER_CHUNK * 4 * 4];
    private final float[] normals = new float[CELLS_PER_CHUNK * 4 * 3];
    private final short[] indices = new short[CELLS_PER_CHUNK * 6];
    
    public ChunkBuilder() {
        // all cell tops are looking "up" the z-axis
        for (int i = 0; i < normals.length; i += 3) {
            normals[i+0] = 0; //x
            normals[i+1] = 0; //y
            normals[i+2] = 1; //z
        }
        // the indices for each cell follow the same pattern for a simple quad
        for (int i = 0; i < indices.length; i += 6) {
            int offset = (i / 6) * 4;
            // first triangle
            indices[i+0] = (short) (offset + 2);
            indices[i+1] = (short) (offset + 0);
            indices[i+2] = (short) (offset + 1);
            // second triangle
            indices[i+3] = (short) (offset + 1);
            indices[i+4] = (short) (offset + 3);
            indices[i+5] = (short) (offset + 2);
        }
        // colors used for testing at this point
        for (int i = 0; i < colors.length; i += 4) {
            colors[i+0] = 1f / (1+i%5); //r
            colors[i+1] = 0.75f / (1+i%7); //g
            colors[i+2] = 1f / (1+i%3); //b
            colors[i+3] = 1; //a
        }
    }
    
    /*
     * Creates a new TerrainChunk for the given world using (startX, startY) as 
     * its upper left corner.
     */
    public TerrainChunk build(World world, int startX, int startY) {
        TerrainChunk chunk = new TerrainChunk(world, startX, startY);
        
        // Fill the positions for each cell
        for (int i = 0; i < CELLS_PER_CHUNK; i++) {
            Cell cell = chunk.cells[i];
            int x = cell.getX();
            int y = cell.getY();
            int z = cell.getZ();
            
            // the starting index for the quad for the cell
            // each quad has 4 vertices with 3 components (x, y, z)
            int quadIdx = i * 4 * 3;
            vertices[quadIdx+ 0] = x; //x
            vertices[quadIdx+ 1] = y; //y
            vertices[quadIdx+ 2] = z; //z
            
            vertices[quadIdx+ 3] = x + 1; //x
            vertices[quadIdx+ 4] = y; //y
            vertices[quadIdx+ 5] = z; //z
            
            vertices[quadIdx+ 6] = x; //x
            vertices[quadIdx+ 7] = y + 1; //y
            vertices[quadIdx+ 8] = z; //z
            
            vertices[quadIdx+ 9] = x + 1; //x
            vertices[quadIdx+10] = y + 1; //y
            vertices[quadIdx+11] = z; //z
        }
        
        chunk.setDynamic();
        // BufferUtils does a bulk copy from the shared float arrays to newly generated buffer objects
        chunk.setBuffer(VertexBuffer.Type.Position, 3, BufferUtils.createFloatBuffer(vertices));
        chunk.setBuffer(VertexBuffer.Type.Normal, 3, BufferUtils.createFloatBuffer(normals));
        chunk.setBuffer(VertexBuffer.Type.TexCoord, 2, BufferUtils.createFloatBuffer(texCoords));
        chunk.setBuffer(VertexBuffer.Type.Color, 4, BufferUtils.createFloatBuffer(colors));
        chunk.setBuffer(VertexBuffer.Type.Index, 1, BufferUtils.createShortBuffer(indices));
        chunk.updateBound();
        
        return chunk;
    }
}

What would you recommend I do with the cliffs? (each cell has a top side (face) which is always visible and up to 4 cliff sides with neighbouring cells of different height)
A) I include each cliff side in the mesh even though it might have a size of zero (vertices have the same position => no size)
B) I calculate which cliff sides exist and update the mesh data accordingly

If I go with A) the dynamic updates would be easier. I could calculate the offset for a given face and upload its data without touching all the other parts of the buffer. If I go with B) I may safe a lot of memory and perhaps improve rendering performance but every time a new cliff is created or removed (because of a height change) I need to update the entire buffer.

Thanks for the help so far.

2 Likes

I’m no expert on this, but I do not believe that there is a way to update only selected parts of a buffer. I think that probably A is your best bet if that’s easier to implement. Odds are that the extra memory cost of always including all vertices won’t be too high, unless you’re creating very large terrains.

1 Like

Glancing at the code, it looks like it’s going to call glBufferData() when we use Mesh.setBuffer(), which calls glBufferData().

Description
glBufferData and glNamedBufferData create a new data store for a buffer object. In case of glBufferData, the buffer object currently bound to target is used. For glNamedBufferData, a buffer object associated with ID specified by the caller in buffer will be used instead.

While creating the new storage, any pre-existing data store is deleted.

So I’d say that’ll push everything out and toss the old data - not what we want.

You could keep a reference to the FloatBuffer/IntBuffer set on a Mesh and use put(), but since those buffers keep an internal position marker, that definitely can’t be done in different threads.

I have no idea yet if this is safe, but since I might be interested in doing something similar I tried overwriting the first component of the first vertex to see what’d happen…

buffers.vertBuff.position(0);
buffers.vertBuff.put(10000);

Those long messed up blue lines appeared! :slight_smile: So it did push out the changes… does that mean this is safe to do? I have no idea! I’m also not sure how it did this (yet). Definitely something to look into some day.

I think JME’s terrain code, IIRC, might be doing something similar with index buffers–I believe it was for LOD.

This kind of thing (changing data in linear buffers like these) can be a real pain to work with sometimes–it’ll take some patience to get it all right. (Not suggesting you shouldn’t try.)

I’ll try to get back to you on your cliffs questions later on if someone else doesn’t first (not that my opinions are worth anything :laughing:).

1 Like

In my own tests it appears the buffers are not memory mapped. I have now implemented a system to click individual cells and change their height and color. Right now I am re-uploading the entire position buffer for every little change which is definitely not very efficient but I havent found a better way of doing things yet.

I am also having some troubles with the collision detection. After I manipulate the mesh the collision detection is unaffected by the change. I thought calling the “updateBound();” method would solve this but it did not. What am I missing?
This is how I am doing it right now:

private void setHeight(int x, int y, float z) {
    // check if the cell is within this TerrainChunk
    int localX = x - getX();
    int localY = y - getY();
    if (!contains(x, y)) {
        throw new IllegalArgumentException("x="+x+"; y="+y);
    }
    // Calculate index of cell within position buffer.
    int cellID = cellID(localX, localY);
    // The buffer has 4 vertices with 3 elements each per cell.
    int quadIdx = cellID * 4 * 3;
    // We need to update the Z-coordinate for all vertices of the quad
    vertBuffer.put(quadIdx+2, z);
    vertBuffer.put(quadIdx+5, z);
    vertBuffer.put(quadIdx+8, z);
    vertBuffer.put(quadIdx+11, z);
    // re-upload the position buffer and calculate mesh bounds
    setBuffer(VertexBuffer.Type.Position, 3, vertBuffer);
    updateBound();
}

The height change works. The raycast doesnt after the update. Help is very much appreciated.

edit: I found this method: “createCollisionData()” the code works when I use this. Is it a good idea to call this method often? Looking at the code it does look kind of expensive to call.

edit2: Okay the above edit was not a good idea. This is much better:
Updating the collision buffer works by calling “getBuffer(VertexBuffer.Type.Position).setUpdateNeeded()” after changing the float data inside. I then call “clearCollisionData()”. Calling createCollisionData() is not necessary as it is called automatically as needed. You just have to invalidate the cache with “clearCollisionData()”.
I also need to call “updateModelBound()” on the geometry using the mesh. Now the collision detection seems to work and updating only parts of the buffer also seems to work.

What I still need help with:

  • Choosing between version A) and B) of how to deal with cliff sides.
  • How to implement the water animation as shown in the link by asser_fahrenholz

Thank you everbody so far. This thread was already a great help.

1 Like

A - All those extra degenerate triangles… I would think should be ignored by the GPU. So I wouldn’t expect a strictly rendering impact, some memory and bandwidth yes.

“upload its data without touching all the other parts of the buffer” - You mentioned this as part of plan “A” but if I understand correctly, your tests didn’t indicate this would work, right? Either way, as long as you divide things into small enough chunks it shouldn’t be a problem to recreate entire buffers often.

B- Sounds like this would make things more CPU limited. I think you’ll need to do some tests to figure out which of these performs better, it’s all going to be highly dependent on the scale of your world. Those nested loops get CPU intensive pretty quick. But you may not need to render all those small cliffs at all when things are very far away (maybe one big billboard mesh underneath everything just to make sure every pixel gets filled). Seems more complicated so I’d probably start with A and see how it goes.

Not certain what I was seeing in my own buffer update test. Maybe it was modified before it was sent to GL, although I didn’t think so. I really didn’t expect it to do anything and was surprised it did. My test case wasn’t exactly ideal/minimal…

1 Like