the infinite world can of worms

[SwadicalRag]

seasonal greetings from glua.team!

With the hiatus gone, and development well underway on voxelate, I feel that it is important that we talk about how to tackle an arbitrary, infinite world with gm_voxelate.

In the past, we've been avoiding this due to the sheer complexity of introducing an infinite or arbitrary world system into a game like Garry's Mod that uses a static, limited world size (which, frankly, is quite tiny!).

However, now that an infinite world is definitely on our to do list, it is time to open that can of worms. So, how do we do it?

In the past we’ve seen some pure Lua implementations (and I’ve made one before too, before shortly giving up on my efforts) that divide the world into chunks and repeat a central chunk serverside and create an illusion of an infinite world clientside. This was one of our considerations for gm_voxelate, but from personal experience I heavily disagree.

The world repeater

Pros

• Re-use gmod’s data structures

  Cons

• SUPER HACKY
• Extremely difficult to maintain compatibility with gmod
• Re-using gmod’s datastructures will also mean that we have to deal with some of gmod’s limitations, like the global entity limit
• Floating point math being wildly wrong on a large scale infinite map

---

My proposal: our own world system

Now, now it seems like packaging our own physics engine and writing the logic to a world management system may be too hard, but I feel that this is the right way to go.

Firstly and importantly, we won’t have to go through the worry of figuring out how to interface with some of gmod’s shittiest libraries. Given that we’re already including a binary module both clientside AND serverside, I think that it’s only appropriate that we use the binary module’s capabilities to its fullest and include whatever libraries we need, rather than depending on or hacking a shitty one within gmod.

So, summarised:

Pros

• Our own system, and the freedom that comes with designing our own system
• We can use our own data types for the system
• Less hacky since we won’t have to repeat a map
• Possible performance improvements due to using our own custom designed world system

  Cons

• The engineering and planning effort behind getting such a system working

• Perceived lack of functionality when comparing a custom designed system to the plethora of functions Garry’s Mod already provides us with (since we’ll have to redesign an entity system, and won’t be able to use gmod’s entity system)

  So, what now? I believe that we shouldn’t rush into the implementation phase of this world management system just yet. Careful planning is key to pulling off such an engineering effort.

In the next few posts I’ll outline some concepts and ideas that we’ll have to take into account when designing this system.

-- SWAD OUT

[ghost]

I agree

-- FOOTSIES OUT

[meepen]

Have u tried not

On May 6, 2017 6:28 AM, "WansonSwanson" notifications@github.com wrote:

I agree

-- FOOTSIES OUT

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/glua/gm_voxelate/issues/3#issuecomment-299630595, or mute the thread https://github.com/notifications/unsubscribe-auth/AF5lSU_9jMREUId8f-a35jhldSLLvc-tks5r3EtpgaJpZM4NStN5 .

[SwadicalRag]

good night meep

[SwadicalRag]

we need to roll our own physics engine and after careful consideration, ReactPhysics3D seemed like the best minimal library that we could use for a voxel based world.

it uses double precision floats internally, so we shouldn't have an issue with lack of precision (according to wikipedia, we lose all decimal precision at 2^52=4,503,599,627,370,496). We can set a safe world limit of perhaps 32 million (or even 2^31 for convenience!) blocks in each direction?

Thus, we should be able to use a 3 dimensional int32 hashmap to store voxel data.

To reduce memory usage, we'll only load all the entities' current chunks and surrounding chunks (in a 1 chunk radius around the entity) into the physics engine in the form of a single mesh in a static rigid body.

As entities move around and exit chunks, unused chunk rigid bodies will be destroyed in the physics engine

[SwadicalRag]

see #4 for the ReactPhysics3D integration

[SwadicalRag]

Arbitrary units and axes

FIRST THINGS FIRST, I'M A REALIST X/Y = horizontal Z = vertical idk why minecraft chooses Y to be vertical

ReactPhysics3D doesn't really enforce any units onto us, so we can say that 1 unit in the physics engine instance will be equivalent to 1 metre. I suppose we can then designate each block to be 1m x 1m x 1m = 1m^3

Players are 0.5m x 0.5m x 1.8 m?

[SwadicalRag]

Should we use meshes or spam a shit tonne of boxes?

// Half extents of the box in the x, y and z directions 
const rp3d::Vector3 halfExtents(2.0, 3.0, 5.0); 

// Create the box shape 
const rp3d::BoxShape boxShape(halfExtents);

[mcd1992]

Whatever has better perf.

[SwadicalRag]

i think generating a mesh for a million cubes would have a worse performance impact than just generating a million cubes

[bmwalters]

Wait, if we lose compatibility with everything that already exists in the GMod ecosystem, what's the point of building this for GMod? I think we should try to maintain as much compat as possible. I want to be able to spawn a vortigaunt in the voxel world and kill it with voxel world physics.

[SwadicalRag]

too hard and impractical: gmod is filled with shitty APIs, and the engine is ancient so we'll have to deal with float precision errors if we use the existing APIs

I think this project is a good opportunity to truly see what we can do with binary modules.

We're obviously still using the source engine renderer but we're overhauling physics, world Management and entities

Why remain chained to old legacy APIs? WE ARE BETTER THAN THAT! Go further! Explore the true possibilities of programming!

seize the means of production!

[bmwalters]

maybe we could develop a compatibility layer when this gets off the ground or a recompiler or something

[SwadicalRag]

but it's virtually impossible, gmod uses floats for position, but we're using doubles

[MDFL64]

I'm okay with going off the deep end for huge worlds, but I would like to maintain some kind of compatibility for small worlds.

[SwadicalRag]

Of course, we'll only just turning the Voxels entity into a World entity which has its own sub entity system

[SwadicalRag]

we're*

[MDFL64]

Honestly I see huge issues with both methods, so I'll go ahead and post my analysis. Overall the world repeater thing should be easier to do with voxels than in vanilla gmod, IMO.

• Global Entity Limit: I'll give you this one, but implementing our own entity system is going to be a huge pain. Source gives us a lot of nice shit including interp and prediction. How high is the entity limit, anyway? I was originally thinking we could implement our own system just for tile entities (essentially blocks that need to store more metadata/perform more logic than our voxel format allows). I guess we're going to want to play with PVS somehow. I'm sure we could hack together an implementation with source entities, but voxel-based PVS could be easier to implement with our own ents.
• Float precision issues: I figure that using doubles in your implementation will probably work. My way of dealing with this would just be to assign each layer(?) its own tag, and tag each entity with the layer it belongs to. Then our actual entity positions will just be offsets within their layers. Hacky? Yes. Hard to code around? Probably. Still not sure it would be less of a shitshow than totally redesigning everything.
• Rendering: Shouldn't be an issue with either scheme. Just build meshes at absolute positions with your method. With the repeater, render all nearby chunks within our layer, then push a matrices to render chunks in nearby layers.
• Collisions: Shouldn't be too bad with the repeater. There's no reason the existing trace code can't just continue tracing into chunks in another layer. On the other hand, your scheme would probably allow us to do more realistic physics that aren't limited to boxes (Marching cubes, anyone?), and what's gmod without them physics.

Whatever implementation we end up going with, huge worlds will break compatibility with other mods. If we eventually want to regain some amount of compatibility, your method is probably the way to go. I just want to reinforce that it's gonna be hard. Which I don't have a problem with. I attempt the impossible on a fairly regular basis, and I usually fail, but I have absolutely no problem with giving it another go.

[Kefta]

Source entity limit is 8192 for networked entities. Implementing your own system in this case would be a lot smarter, or making a block manager entity for groups of blocks since Source doesn't handle large amounts of entities in small clusters very well

[SwadicalRag]

yup, I've had personal experience with how shitty source engine handles large amounts of entities (see @xaviergmail ) and it's not pleasant

I'm still against map repeating. It's still hacky: gmod vectors use floats iirc :/

I'm more than happy designing our own entity system. This project is also a test as to how far we can take the source engine and fuck some shit up

[Kefta]

Source vectors do use Valve's 16-bit floats 🤢

[SwadicalRag]

holy shit ha ha hahaha that makes so much sense as to why my traces kept fucking up in my old infinite world implementation

Ok there is no way I'm agreeing to this

[SwadicalRag]

sorry :b:arakeet

[Kefta]

Also, vector:IsValid() in the C++ will fail if the vector goes out of world bounds (default -16000 something, +16000)

[SwadicalRag]

rip

[MDFL64]

Source vectors do use Valve's 16-bit floats 🤢

wait what the shit

[SwadicalRag]

@Kefta are you sure? wikipedia says 16 bit floats lose decimal precision at 2048

Precision limitations on other decimal values

    Decimals between 2 and 4: fixed interval 2−9
    Decimals between 4 and 8: fixed interval 2−8
    Decimals between 8 and 16: fixed interval 2−7
    Decimals between 16 and 32: fixed interval 2−6
    Decimals between 32 and 64: fixed interval 2−5
    Decimals between 64 and 128: fixed interval 2−4
    Decimals between 128 and 256: fixed interval 2−3
    Decimals between 256 and 512: fixed interval 2−2
    Decimals between 512 and 1024: fixed interval 2−1
    Decimals between 1024 and 2048: fixed interval 20

Precision limitations on integer values

    Integers between 0 and 2048 can be exactly represented
    Integers between 2049 and 4096 round to a multiple of 2 (even number)
    Integers between 4097 and 8192 round to a multiple of 4
    Integers between 8193 and 16384 round to a multiple of 8
    Integers between 16385 and 32768 round to a multiple of 16
    Integers between 32769 and 65503 round to a multiple of 32
    Integers equal to or above 65504 are rounded to "infinity".[8]

[Kefta]

Meepen was the one who mentioned 16 bit floats a few months back somewhere -- I can't find Valve's limits.h. I just know vectors use floats.

[SwadicalRag]

well that's a piss poor decision by valve then :/

[SpencerSharkey]

scale everything else down

[SwadicalRag]

precision, mein friend

[SwadicalRag]

16 bit floats have 3-4 decimals of precision which is pathetic

[SpencerSharkey]

jokes. full cl-localized world is only viable option for inf worlds

how hard is it to make entity management for minecraft seriously and networking

[SwadicalRag]

@SpencerSharkey shouldn't be too hard now that we have a FUNCTIONAL NETWORKING SYSTEM ™️