How to optimize a Minecraft-like Voxel system?


(statikregimen) #62

I wasn’t sure how to translate my knowledge of using noise on continuous meshes (where you can augoment vertex coordinates directly with noise values). Here, you need everything “quantized” to the block size.

However, I figured it out, and I’d say.NOW I’m cookin’ with gas:

Fast chunk generation time (will get slower when I add caves), “real” terrain w/ Fractal Brownian Motion, and good view distance (will only get better from here - actually, not even close to pushing the limits in this test) :smiley:

Edit:
For reference, here is the literal code, but it’s NOT what I’ll be using - I just cooked this up for more prototyping to get the result above. It still has to deal with caves (which I have a few approaches I’m experimenting with):

from bge import logic, types, events
from opensimplex import OpenSimplex
from time import time
#from mathutils import Vector

seed = 123
chunkSize = 16 # Chunks will be NxNxN blocks
noiseScale = 0.005 # Sample noise at smaller/larger scale
threshold = -0.2 # If noise sample > this, add a block


blockSpacing = 1 # Generally, don't change this....


noise = OpenSimplex(seed)
n2 = noise.noise2d
n3 = noise.noise3d


s = logic.getCurrentScene()

b = types.KX_BatchGroup([s.addObject("Cube.002")])


def remapVal(x, in_min = -1, in_max = 1, out_min = -20, out_max = 20):
    return (
        (x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min
    )


def fbm(x,y,z=0,octaves=8,lacunarity=2,gain=0.5):
    #noise = PerlinNoise3(nsx, nsy, nsz, table_size, seed)
    amp = 1
    freq = 1
    total = 0
    for i in range(octaves):
        total += amp * n3(x * freq, y * freq, z * freq)
        amp *= gain
        freq *= lacunarity
    return total

t = time()

# Surface only noise crawl
for x in range(chunkSize*8):
    for y in range(chunkSize*8):
            h = int( 
                remapVal( fbm(x*noiseScale,y*noiseScale, 0*noiseScale) )
            )

            o = s.addObject("Cube")
            o.worldPosition = x,y,h

I will ofc, be switching to mathutils’ noise offerings, et al. Again: this was just hacked together from what I already had.

Decided to take another screenshot with some color, b/c I’m so damn pleased with these results:

Looking back from the opposite corner:

Low framerates are just simply due to the fact I haven’t applied previously implemented optimizations to this approach and these were taken on my AMD APU. Mainly, I’m just super happy with the terrain results at this stage. By tweaking some of the variables/function params, I can get plenty of variation for biomes. The only thing this can’t do yet is overhangs, but I think i can solve this with my cave generator.

Nevertheless, this last screenshot shows just how far Fractal Brownian Motion can go without much effort…Planes to foothills. I have yet to see what lies beyond, as I’m working on other problems now.


(statikregimen) #63

This seems like it should be easy, but I’m struggling to find an answer on google:

it seems like one or more engines I’ve worked with had a simple setting to put a mist/fog effect around the far clip plane so distant objects “fade out of view” rather than seeing a hard cutoff. Does anything like that exist for BGE/UPBGE that I’m overlooking?

edit: and yes I know this wont help performance…just make it look nicer lol


(- Click for resources) #64

it exists and you are looking over it indeed :), in the world tab you find the mist settings.
You can even handle the mist trough python.


(statikregimen) #65

Good grief…Found it!! Thank you!


(statikregimen) #66

BluePrintRandom -

I finally had a look at your latest .blend. You’re most likely running it on a “good” CPU, so thought you might like to know, it still holds 60fps on my AMD A12 (but takes a hot minute to start), which has been an achilles’ heal to my own code (it runs Minecraft well at a render distance of 16 chunks so I"m using it as my “minimum hardware requirements”.

I would like to better understand your approach to live-updating the world. I’m having a hard time following your code, especially sans-comments. I’m fluent in Python, but this kind of thing gets stupidly confusing with all the for-loops and if-statements. So hoping you’d indulge me with either comments or a plain English description :smiley: If not, thanks anyway - your input has been invaluable to my progress so far!

Currently, I’m happy enough with my own results to start actually working on a “main” function. I’ve had a few false-starts, before eventually realizing there were other problems that had to be solved before the work was worth it (namely, view distance, which I’ve licked well enough for my requirements now). I have a few ideas in mind, but my new approach to separating ground-level surface generation from cave generation is also adding to the problem. I can no longer think in a 3D grid of chunks - only a 2d surface layer, assuming solid below/air above, unless otherwise specified. However, the advantage is an unlimited height and depth. Minecraft “mountains” are weaksacue. I can already generate everything from terrestrial-sized mountain ranges with peaks thousands of feet high, to foothills, planes, canyons, and thousands of ft deep oceans with ease - just by tweaking some parameters.

Just to add some substance to that claim, here is a shot using some parameters that would roughly make the side of a mountain (note at the current view distance, you’re not seeing the top - just a random facet):

If I can keep framerates up with this, I’ll blow the doors off of this style of terrain generation (well, atleast I haven’t seen it pushed to this extreme before), and it will be powerful if I can actually pull it off in UPBGE with its simplicity and approachability :smiley:


(BluePrintRandom) #67

MIND_CRAFT_2.blend (523.8 KB)

import bge
import mathutils 
import math
import random

own = bge.logic.getCurrentController().owner
player = own.scene.objects['Player']
from mathutils import Vector
Scale = 10
WorldSize = 10

Radius1 = 20     
Radius2 = 15

def get_list(near, filled):
    return [entry for entry in near if entry[1] not in filled]
      
def main():
    
    #generate all chunks that will be used
    #we can always add more later this is just the first set
    #the 'masterlist' is a list of the origin of all chunks
    
    
    
    
    
    
    if 'Chunks' not in own:
        KDChunks = {}
        Chunks = []
        index = 0
        
        Size = Scale*Scale*Scale
        
        for X in range(WorldSize):
            for Y in range(WorldSize):
                for Z in range(WorldSize):
                    Chunk = Vector([ (X*Scale) - ((Scale*Scale)/2), (Y*Scale) -  ((Scale*Scale)/2), (Z * Scale) -  ((Scale*Scale)/2)  ])
                    added = own.scene.addObject('block',own,10)
                    added.worldPosition = Chunk
                    ChunkParts = [ ]
                    KDChunks[index] = mathutils.kdtree.KDTree(Scale*Scale*Scale)
                    index+=1
                    index2 = 0
                    for X1 in range(Scale):
                        for Y1 in range(Scale):
                            for Z1 in range(Scale):
                                micro =  Vector([ (Chunk[0] - Scale/2 ) + X1 , (Chunk[1] -Scale/2) + Y1, (Chunk[2] - (Scale/2)) + Z1 ])
                                ChunkParts.append(micro)
                                KDChunks[index-1].insert(micro,index2)
                                index2+=1
                    KDChunks[index-1].balance()
                    filledLocations = {}
                    Chunks.append( (Chunk, ChunkParts, filledLocations) )
        # each chunk is a kdtree
        # a kdtree of all chunks is used to decide what blocks need to be evaluvated for loading, it is called KDMaster
        # we could break this up later into many smaller trees
        # and have a much larger world.
        

        kdMaster = mathutils.kdtree.KDTree(len(Chunks))
        index = 0
        for entry in Chunks:
            kdMaster.insert(entry[0], index)
            index+=1
        
        kdMaster.balance()
        print('Tree is '+str(len(Chunks))+' entries in size')
        
        #data we generated is now stored
        own['KDMaster']= kdMaster
        own['KDChunks']= KDChunks
        own['Chunks']=Chunks
        
        #this is used to store / free / and manage physics of cubes
        own['FreeCubes']=[]
        own['FilledCubes']=[]
        own['P_index']=0
        
        
    else:
        fill = 8
        nearChunks = own['KDMaster'].find_range( player.worldPosition, Radius1)
        #print(len(nearChunks))

        for Chunk_index in nearChunks:
            
            Chunk = own['Chunks'][Chunk_index[1]]
            KDSmall = own['KDChunks'][Chunk_index[1]] 
            Micro = KDSmall.find_range(player.worldPosition, Radius2)
            Empty = get_list(Micro, Chunk[2])
            for entry in Empty:
                
                noise = mathutils.noise.hetero_terrain(entry[0], .125, .125, 8, .1, mathutils.noise.types.STDPERLIN)
                Chunk[2][entry[1]] = noise
                #print(noise)
                if noise>.25:
                    if len(own['FreeCubes'])>=1:
                        added = own['FreeCubes'][0]
                        own['FreeCubes'].pop(0)
                        added.visible =True
                        added.removeParent()
                    else:
                            
                    
                        added = own.scene.addObject('block', own, 0)
                    added.worldPosition = entry[0]
                    added.color = [math.cos(noise*34), math.cos(noise*34),math.cos(noise*34),1]
                    #added.occlusion = True
                    added['Owner']=( Chunk_index[1], entry[1])
                    own['FilledCubes'].append(added)
                    fill-=1
                    if fill<=0:
                        break
                        #we can also sample perlin noise here to fill/not fill / decide what type of block we have here
    if len(own['FilledCubes'])>=96:
        go=96
    else:
        go = len(own['FilledCubes'])               
        
    for i in range(go):
        cube = random.choice(own['FilledCubes'])
        if cube.getDistanceTo(player)>Radius2*1.1:
            index_cube = own['FilledCubes'].index(cube)
            own['FilledCubes'].pop(index_cube)
            data = cube['Owner']
            chunk = own['Chunks'][data[0]]
            
            
            del chunk[2][data[1]]
            
            own['FreeCubes'].append(cube)
            cube.visible = False
            cube.setParent(own,0,1)
if 'FilledCubes' in own:            
    for x in range(int(len(own['FilledCubes'])/16)):
        own['P_index']+=1
        if own['P_index']>len(own['FilledCubes'])-1:
            own['P_index']=0
        cube =    own['FilledCubes'][own['P_index']]
        D =cube.getDistanceTo(player)
        if D>Radius2*.5 and cube['Physics']==True:
            
            
            cube.setParent(own,0,0)
            cube['Physics']=False
        elif D<Radius2*.5  and cube['Physics']==False:
            cube['Physics']=True
            cube.removeParent()
             
        
    
        
main()            

(statikregimen) #68

Thanks! Makes a little more sense now… I’m not familiar with kdtrees so I"m edumuhcating myself on that now.


(BluePrintRandom) #69

I added the physics culling system at the bottom and forgot to comment on it / and freeing system


(wkk.py) #70

kdtrees are useful on sparse points, you can balance the tree in order to lookup items quickly inside it based on a 3d vector.

In the case of a regular grid like you have, where each block is next to each other, this is not useful at all.

The lookup is trivial enough to be done by hand, rather than relying on a kdtree to manage the lookups.
The balancing will take useless time to compute.


(BluePrintRandom) #71

I balance the tree precisely one time bro :smiley:
at frame zero

I never re-balance it.

it’s used to not have to try and look up the adjacent points with iteration
in py
it also sorts the blocks in order of distance when returned (important when moving especially)

we can also use it for chunking out all blocks around tnt or whatever.

edit: this is made in upbge 0.2.5 / master so it may not work correctly in vanilla bge*


(statikregimen) #72

I read up a bit…Thought for a second kd trees might be useful, but I’m not sure given my new approach. Either way, still not sure how I want to write my “main” function. Thought I could pull some inspiration from your code, but I think I’ve diverged too far now.

I sort of detailed it above, but in short, I no longer need to generate/cache every single block of every single chunk, as there is no need - I assume the chunk is solid below the surface, unless otherwise specified by the cave generator. When the player removes blocks, I’ll just pick what’s under/behind it directly from the noise (well, obv. check the cache first to make sure we’re not about to fall into a cave). Explosions might be a bit laggy this way, but it makes everything else so fast, I kind of don’t care.

The other nice thing about this, is you don’t even have to render any cave blocks - just cache them, unless it interestcts with the main surface to create a cave mouth/entrance.

Anyway, I’ll keep posting my progress and greatly appreciate all the help!!! I was honestly not expecting much feedback as most people would be like “not this again” or “dear god the world has enough minecraft wannabes” lol

EDIT:
Don’t need a bump right now, as this is just sort of a thought dump.

My new approach is evolving, but there seems to be a hard limit to it on its own. I am getting usable view distances, but nowhere close to goals yet.

My aforementioned “plane skinning” approach no longer helps (I didn’t have high hopes for it anyway). It did previously make a big difference with solid chunks, but with the same amount of blocks spread out on a “surface”, too many faces become visible (adding way more gameobjects), negating the benefit. I should have thought of this but didn’t.

I did some experiments with LOD scaling to my latest algorithm, where past a certain distance, it renders half the detail. This seems farily promising in limited tests.

I have,(at least temporarily) decided to eliminate any concept of “chunks” in my approach. I am going to try “leap froging” the edge(s) of the view distance. Basically, as the player moves, swap the edge blocks in that(those) direction(s) with the opposite, updating heights from noise. A floating origin will also be used b/c reasons, and ease of implementing w/ my leap-frog idea.

The “pixel meshing” idea by VegetableJuiceF still seems super promising to push my view distance way out. I’m slowly understanding it, but as I said above (before the edits), the code is quite complex and not working on my system. Thus, I don’t know how to use it as-is with my approach, let alone how to fix it on my system (Gentoo/UPBGE latest).

—Simple floating origin system, for reference:
A floating origin is essentially a 3D treadmill, to keep the camera close to 0,0,0 for the sake of maintaining decimal precision, while still allowing the player to travel vast distances. Without this system, the further from 0,0,0 you travel through the game world, the less precicely the hardware can calculate vertex positions, eventually leading to jerky movement and wildly placed objects.

I use an Empty object as a parent to all world objects so we can shift them in unison. This does not seem to work with batch groups out of the box. I’m thinking it probably can be done but haven’t looked into how yet.

The code is very simple:

def main():
    # How far to shift the world to keep it in the same pos relative to cam
    camShift = cam.worldPosition - Vector((0,0,0))

    if camShift.length > 10:
        s.objects["WorldParent"].worldPosition -= camShift
        cam.worldPosition = 0,0,0

(statikregimen) #73

Well, I regret to say, I’m probably going to give up on this for now.

I can get my absolute minimum view distance on my minimum cpu requirement, but as soon as I started adding the logic to update the world, it all went to hell, again, and I fear it’s just going to be like that at every step. Between Python not being the fastest, and BGE not giving lower level access to create meshes on the fly, it’s starting to feel like an excercise in madness.

I may re-visit in the future, but even the best demos I’ve seen here fall way short of my goals, and despite how far I was able to push the envelope compared to where I started, it’s getting to the point where I could have done as much as I’ve accomplished here, twice in Panda3D by now. Not to knock BGE/UPBGE in any way - I will be using them for some other projects b/c I think they’re awesome! They’re just not geared for real-time procedural generation at this densisty of geometry - it’s more meant for traditional approaches with pre-made game worlds and art.

So with that, I thank you all for your insights. It was very educational and some techniques will go on to help me in other projects for sure! Anyway, for now, I’ll leave you with my final progress:

bge_voxel_test.blend (607.3 KB)

I do think there is still value to my approach of separating the surface from the caves.as it allows for more realistic terrain with unlimited height of mountains and depth of canyons due to lack of “chunks”. It should also provide a huge benefit in performance for engines that provide lower level access (and ones that use compiled languages).

Edit: I might still try a couple more things before shelving this. I had an idea last night of maybe creating plane meshes w/ lots of vertecies in a grid that I can deform to the shape of the skin of cubes (sort of like my previous plane-skinning, but with fewer planes, and assuming it’s possible to change vertex locations on the fly, which I think it is). Also, I did have some success with LOD scaling - using double block size at half the frequency for LOD lvl 2, etc.

[a few hours later] Just found this, so I recokon vertex manipulation is possible: https://blender.stackexchange.com/questions/11005/bge-chaging-the-position-of-a-vertex-in-real-time

LOD scaling I think shows the most promise, especially because it’s easier to implement. Skinning with bigger planes will require more thought…


(BluePrintRandom) #74

MIND_CRAFT_3.blend (599.1 KB)


(statikregimen) #75

What are your goals/plans for this? I assume this is something you made before this post…It looks nice, anyway so I hope you do something with it!


(wkk.py) #76

@BluePrintRandom, hijacking threads since 2008! :wink:


(BluePrintRandom) #77

nope - re-wrote for you

trying to expand the radius without killing the frame rate or move speed


(statikregimen) #78

He’s been genuinely helpful…

BluePrintRandom -

Thanks! I’ll take a closer look tomorrow (a few beers deep now lol). I’m really bad at reading other people’s code so bear that in mind…I’m self-taught, but managed to build a career on it. I just only take jobs I can work alone on lol


In other news, I’m pushing forward a little more. I almost gave up last night, but per my edits above, I have a couple more promising-enough avenues to try. I did a test w/ LOD scaling that went very well a few days ago, and then today learned I can indeed maniuplate mesh verts on the fly (have not tested, but again: seems promising).

Cheers


(Lostscience) #79

when i tried your blendfile the player character just fell through floor.


(BluePrintRandom) #80

it was made in upbge 0.2.4 @Lostscience


(Lostscience) #81

i am using upbge 0.2.4 on a hewlett packard computer .windows 10 os.