How to optimize a Minecraft-like Voxel system?


(BluePrintRandom) #41

I seem to do ok

I think the issue is #of blocks added per frame (in this case moved)

so more detail = slower moving agent required.

I am using a large KDTree (15x15x15) ‘Chunks’ of 10x10x10 Kdtrees

one could do this again and do

a 15 x15 x15 table of chunks
and make a truely massive world.

with this code, I can quickly get all blocks in a radius.
for everything from pathfinding to explosions.


(statikregimen) #42

Fairly impressive, but what happens when you set your view distance to Minecraft scales?

~

Right now, I can easily get enough geometry on screen fast enough to kill frame rates. I need to solve that problem before it’s worth generating chunks any faster, or on-the-fly. I swear I’ve said framerates are the current issue before…

Here’s the latest project (though I don’t think much has changed since last time):
bge_voxel_test.blend (542.0 KB)


(jesusmora) #43

my code uses the current position of the for loop as the coordinates. i don’t need to save the coordinates to a variable and is much faster than calling a function each iteration. that is your problem, that is why you get low framerates.

ob1.worldPosition = [abc, adc, aec]

either calculate the position using a point of reference or use world space.

memory is cheaper than processing power. you are doing it wrong. please calculate how much memory you need:

https://minecraft.gamepedia.com/Chunk
16x16x256 = 65536
65536 ints is (calculating one byte per int) 64 KILOBYTES. do you understand how LITTLE that is?
you can fit 16 chunks in one megabyte. you can fit 16384 chunks in one gigabyte.
it’s not even much MEMORY usage, much less DISK usage.
your method on the other hand increases memory usage by three (x y z of every block), and uses ridiculous amounts of processing power.
minecraft only generates the world once, and i’m sure it stores the entirety of the voxel in a file. the only objects using additional memory are entities.


(statikregimen) #44

Your code would work for 1 single chunk - a matrix of blocks. This world needs to be a matrix of CHUNKS. Add more chunks with your code, and they will all spam on top of the first one without calculating an offset. self.x, self.y, self.z are offets used for this purpose and are provided by w/e code adds the chunks. I dont think you’re understanding me or going off something old. My code is providing the exact expected/desired result so it’s most certainly not wrong…

All the chunk data IS cached in memory but it has to be pulled out of the noise before it gets there…So I guess I’m not really sure what more you want from me lol…You’re telling me I’m doing things wrong when my code is most clearly working perfectly and is very fast - fast enough for sure.

Please ensure you’re looking at the latest project file (attached in my last reply to BluePrintRandom).

Until framerates are improved, there is no point in improving the chunk generator any further. It is NOT the culprit. It is the reason it takes several seconds to load the scene. It is NOT why the framerates are low.

p.s. I do appreciate your help - everyone’s for that matter - I just don’t think we’re communicating on a couple of points very well. It happens =/


(BluePrintRandom) #45

my issue when the draw distance is larger becomes

A. physics - at the moment each cube has physics
B. the cost of “freeing” old cubes and adding new cubes becomes expensive

(we don’t ever add or destroy cubes we simply mark them free, and set them invisible / parent to a object that is no collision)

my cubes are all marked as occluders which makes the physics higher, however it does not draw the occluded cubes.

what I need is to accelerate this in C.

def get_list(near, filled):
    return [entry for entry in near if entry[1] not in filled]

this is how I can tell what blocks are not filled in a chunk.

I think what we need is to find a way to skin these chunks with blocks instead of filling all of them and this will be plenty fast enough.


(statikregimen) #46

I am essentially “skinning” them now using planes. Idk if you can borrow my approach for this in any way (it does have an issue where it’s not adding some faces when adding more than 1 chunk to the scene…I have yet to figure out why but probably a derp in my logic). It’s a LOT of gameobjects, though, when doing it that way which may be contributing to my bad framerates. I had to turn off physics - it was just too much.

I’m still very interested in the “pixel meshing” concept by VegetableJuiceF but the code is pretty complex and I haven’t had a chance to really pull it apart. Unfortunately, the demo doesn’t seem to work for me, but it sounds like it may solve the too-many-gameobjects issue, but I’m not sure.


(BluePrintRandom) #47

my original test was using a ‘gfx mesh’ and placing cubes made of geometry over invisible physics cubes, this worked ok, however since I am using the occlusion now it basically removed any savings that would have had, by removing many many faces that would have been drawn/ overdrawn.

if you could find a way to only place blocks on areas the player can see, this would likely make the system perform about 8 - 16x faster.

upbge_mind_craft_2.blend (508.9 KB)
(edit: made in upbge 0.2.4 + )

edit:
we may need something like his -


(BluePrintRandom) #48

from what I am reading they raycast inside the chunk out to the corner, and push a culling block out at each corner based on how far out the chunk is occupied - this is fine for GFX culling but does not help the fast physics culling issue (if you use occlusion + physics culling it breaks)


(statikregimen) #49

Yea, I loosely understand it. I’ll have to read it a couple more times though, probably lol… But I was afraid it would be more complicated than it seemed when I started this quest.

For physics, I think that would be easy enough to do by hand with a script and ray tracing.

Edit:
Looks like some good notes in here: https://sites.google.com/site/letsmakeavoxelengine/

Also, I don’t know if I mentioned this already, but I wonder if an “imposters” system would work for this, e.g. https://www.youtube.com/watch?v=Zhbu1lOto0M


(VegetableJuiceF) #50

The easiest method to add physics is spawn invisible actual physics enabled cubes in the voxels that are around each player / actor, while having your chunks without physics.

Not everything you see needs to be physical, only things that are touched :D.

Having to do just a 3x3x3 voxel lookup each frame is no biggie.

I have here a visual example of this with bit larger check range
(the red outlines are the physics debug things from bge, showed on physics enabled objects)

Hope this helps


(statikregimen) #51

Yes it helps a lot - very good insight. I hadn’t thought too far into it and don’t know if this would have occurred to me.

I’m still trying to wrap my head around your pixel meshing idea. but given some of the recent echanges here, I’m not sure it alone would help much with my current issue of maintaining framerates with high view distances, but voxels are proving to be a bit more of a challenge than i thought so every little optimization seems like it will be valuable.

Thanks!


(statikregimen) #52

So I’ve realized from day 0 (b/c I’ve made terrain generators before - just not with voxels), that my terrain generation approach here is useless and temporary. Just a quick way to get something on screen.

After some time thinking about it, I realized it’s adding to the framerate/view distance issue, probably a lot. It causes way too many hollow areas to be realistic, and thus way more faces that my current approach will add to the scene. So it’s not remotely useful, even for testing.

What needs to happen instead, is a subtractive approach. Generate the terrain in layers, then subtract hollow areas, and holes for water. This will obviously slow chunk generation down, but was inevitable anyway as those features would be needed to control biomes. Once I realized this, I searched more specifically about how Minecraft does terrain, and found this: https://studentgamedev.blogspot.com/2013/09/unity-voxel-tutorial-part-3-perlin.html - and one other approach that I can’t find now that seems to use my thoughts already so I’m at least semi-on-track.

Another question I’ve had for a while - is there a way to sample light level of a given face (or at least vertex)? if so, one could just not render faces below a certain light level. I haven’t even tried to Google it yet as I keep forgetting about it. Will answer unless someone beats me to it. Edit: initial searches yield nothing :frowning:


(mataii) #53

I did my own minecraft styled game prototype like a year ago, still working on it from time to time.

Since im not very familiar with python I used only logic bricks to achieve this, but it works just fine with object culling and logic culling, so at certain distance “logic” and “physics” get deactivated and the game performance is quite constant.

I have different kind of objects to put on scene, like walls, pillars, doors, cubes and stairs.


(jesusmora) #54

there is the minecraft aproach to lighting. first you raytrace from the top of the voxel (find the upmost block in a given column), and put a “1” in a parallel matrix. that will give you solar light.
then, all adjacent blocks to the column will be given “0.5” (use a str for better memory performance, something like “5” would be “0.5”, 6 would be “0.4”, etc) as long as they are not 1 already.
then you can do a second pass to cast 0.25, or even more. or use your own aproach.
then, when adding or updating blocks, you use a method to put the level of bright of each block. you can scroll a texture, use obj color, or have precreated blocks with different textures representing light levels, and add them according to the current block. this for each individual block.
torches would need to be a different pass, just put 1 on blocks with a torch/lava.
you don’t need to do this every frame, just when altering the voxel/creating a new voxel.


(statikregimen) #55

mataii - That looks really cool. I didn’t think logic bricks could get that far, but I know Python so I haven’t really learned them in-depth. Well, also, I’m not sure they could get all the way to procedural terrain, but I could be wrong…

jesusmora -
Thanks…I think I knew that Minecraft did lighting “manually” but didn’t know any more than that. Doesn’t it actually use it’s own engine made in Java using an OpenGL library/module? So they’d have more low-level access to speed things up, I would think. It sounds like it could be a lot of work at the higher level we seem to be stranded in with this engine. Honestly, I should be doing this in Panda3D if I want to use Python, but I also don’t feel like cooking EVERYTHING from scratch. The big advantage to UPBGE is it’s fast and easy to get great results - good for a 1-man hobbiest team lol

Anyway, it does make me think: The way I am hoping to structure my final terrain algorithm, it will already know where the top layer of blocks are (maybe with the exception of cave mouths, as cave systems will be subtracted from otherwise solid terrain), so I could speed things along that way, Add trees first so it can darken blocks under them in a single pass.

I will give this a lot of thought.


(BluePrintRandom) #56

you can have all types of blocks on 1 atlas texture and just set the UV of the face for lighting basically*

we can even animate this way**

one way to do this would be vertex.uv for each face as it’s placed.


(statikregimen) #57

Thanks. Good insight. I’ve seen this technique before but it didn’t cross my mind.

Also, I was editing my last reply then noticed you replied so decided i"d add it to my new one for visibility:

The main hold-up for my terrain generator is applying noise to a grid of voxels. When I’ve used noise on meshes in the past, it’s simple - you just augment the vertecies position with the noise value. Add some Fractal Brownian Motion, and various erosion algorithms to get pretty beautiful results. I thought maybe remapping the noise (which appears to be -1 to 1 in OpenSimplex) using a function like this:

def remapRange(x, in_min, in_max, out_min, out_max):
    return ((x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min)

Which essentially takes a value in one range and scales it up, as if it were in a larger range (then you round it to nearest int), but haven’t been able to get good results. It seems like it should work (albeit certainly not correct/best), but I’m not sure how to tweak out_min/max and my noiseScale variable (a multiplier to sample noise at smaller or larger scales).

I’m entirely self taught, so I know this is a VERY well known algorithm (e.g. how to approximate a line in pixels - we’ve been doing it since computers had displays and probably knew how to do it long before that), but most of my work is in web apps and data entry.


(BluePrintRandom) #58

checkout mathutils.noise :smiley:

import mathutils = ninja magic

https://docs.blender.org/api/2.79/mathutils.noise.html

also to get a uv for a voxel use the center of the voxel as the calc point, and use the orientation of the normals to set if it’s a side / top / bottom


(statikregimen) #59

Holy crap how did I overlook this? Thanks!! I’m not sure it solves my math problem, but loads of goodies I was expecting to do by hand (and would be slow in Python) if I needed them (and likely will).

Edits:
Some Googling lead me here: https://en.wikipedia.org/wiki/Bresenham's_line_algorithm

I see there is a module: https://pypi.org/project/bresenham/

And here is some C++ code from https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html (I’m translating it to Python now for the excercise):

void linev6(Screen &s,
              unsigned x1, unsigned y1,
              unsigned x2, unsigned y2,
              unsigned char colour )
    {
      int dx  = x2 - x1,
          dy  = y2 - y1,
          y   = y1,
          eps = 0;
    
      for ( int x = x1; x <= x2; x++ )  {
        s.Plot(x,y,colour);
        eps += dy;
        if ( (eps << 1) >= dx )  {
          y++;  eps -= dx;
        }
      }
    }

Translation:


def line(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    y = y1
    eps = 0

    for x in range(x2):
        yield x,y

        eps += dy
        if eps << 1 >= dx:
            y += 1
            eps -= dx

And the motherload: http://members.chello.at/~easyfilter/bresenham.html but I’ve figured out a better way, I think…


(BluePrintRandom) #60

bge.render.drawLine( p1, p2, (r,g,b)) ??