Re: Game world and implementation

Procedural controls, instead of being told ‘press space to jump’ it just says ‘JUMP’ and maps whatever you push. :grin:

3 Likes

You would be surprised how the intitial set controls can be defined, if you dont choose the default. XD

I do plan for the Tutorial to only show off the Controls that you should know about, and then let you set whichever Button you want to be what, and how you want to press it, so you dont have to go into the Options Menu.

2 Likes

Okay, so for example if you have fifteen identical trees, then fifteen leaf nodes in the octree correspond to the bottom of a tree. In turn, each of those nodes points to a single block object which says “I’m the bottom of a tree”.

And so the maximum number of block objects which may have to exist is equal to the maximum number of permutations of valid block data, correct?

3 Likes

Not even, each block just needs to point in one of 6 directions, the rest can be done by chaining. Though pointing to a specific Center of Tree Coordinate would work too, and might be faster depending on Situation, especially for large Trees.

Some things really need testing to be figured out in the best way possible. :wink:

2 Likes

If you can get that to work, that’s great. But another option if the transition proves too difficult is to use the outer boundary of the atmosphere as a wall of fog when you break through. That way the observer in space sees the baked model planet while the observer on the planet sees a baked skydome. See for example the beginning of this clip: https://youtu.be/71XGAbjfn4Q?t=116

3 Likes

You may have seen my other post which showed you how expensive this kind of octree would be - 36 bytes per node just to store four bytes of actual data! I recommend dropping the tree structure.

If you still want all the benefits of an octree - namely level-of-detail for rendering - just cache the non-leaf-nodes in separate linear arrays and use math on the pointers.

Example:

pub struct BlockData<'a> { pub name: &'a str }
impl<'a> BlockData<'a>
{
	pub fn new(name: &str) -> BlockData
	{
		BlockData { name }
	}
}


#[derive(Clone)]
pub struct Color { pub red: u8, pub green: u8, pub blue: u8, pub alpha: u8 }
impl Color
{
	pub fn new(red: u8, green: u8, blue: u8, alpha: u8) -> Color
	{
		Color { red, green, blue, alpha }
	}
}

#[derive(Clone)]
pub enum Node<'a>
{
	Internal { color: Color },
	Leaf { block_data: &'a BlockData<'a> }
}

pub struct Octree<'a>
{
	depth: usize,
	forest: Vec<Vec<Node<'a>>>
}

impl<'a> Octree<'a>
{
	pub fn new(depth: usize, color: Color, block_data: &'a BlockData) -> Octree<'a>
	{
		let mut forest: Vec<Vec<Node>> = Vec::with_capacity(depth);
		let base_interior = Node::Internal { color };
		let base_leaf = Node::Leaf { block_data };
		
		use std::convert::TryInto;
		let levels: u32 = depth.try_into().unwrap();
		for i in 0..levels
		{
			let node;
			if i == levels - 1
			{
				node = base_leaf.clone();
			}
			else
			{
				node = base_interior.clone();
			};
			let siblings = std::iter::repeat(node)
				.take(8_usize.pow(i))
				.collect();
			forest.push(siblings);
		}
		Octree { depth, forest }
	}
	
	pub fn root(&self) -> &Node
	{
		&self.forest[0][0]
	}
	
	pub fn depth(&self) -> usize
	{
		self.depth.clone()
	}
	
	pub fn get(&self, depth: usize, index: usize) -> &Node
	{
		&self.forest[depth][index]
	}
}

fn main()
{
	let block_air = BlockData::new("air");
	let color_clear = Color::new(0, 0, 0, 0);
	
	let tree = Octree::new(3, color_clear, &block_air);
}
3 Likes

Do you mean, if there are only two possible block states (Air and Stone), there will only be two leaf nodes in memory - even if the octree is very deep?

ETA: Question: If so, how will you update the colors of the parent node? That seems very complex now.

3 Likes

I did have someone contact me, showing their own Screenshot of how Rendering with an Octree and Marching Cubes would look like, and giving me some rough performance Data. An equivalent of the furthest possible Minecraft Render Distance uses less than 2GB of RAM, and can run on a Raspberry Pi 3.

For that one I more meant like “This Node has 8 Leaves that are all Air, instead of storing 8 more Leaves we will store one Leaf referencing Air”, meaning “All Sub-Leaves are Air, so why waste Memory storing them and just say ALL of this giant Cube is Air”

That will be left to the setBlock() and loadNodeFromFile() Functions, lol.

2 Likes

Okay. That makes sense now.

3 Likes

I think there’s enough information actually written in this topic to write the octree code and replace that linear array in your repository. That’s good progress, on the conceptual side!

3 Likes

Oh that 4x4x4 Egg thing, that was to test marching cubes rendering, and is full of misconceptions, so it will definitely need replacing, lol.

2 Likes

What do you think about this blueprint? Just for colors, not blocks yet.

## Node struct (private)
fields:
* color
* children[8]
methods:
* get_child that takes a number between 0 and 7 and returns the corresponding child
  node from children[] if it exists, or children[0] if there is only one child node,
  or an error if there are no children in the list.
* set_child which takes a Node and a number between 0 and 7. If there is a correspo-
  -nding child node in children[] then compare it with the new node and replace it
  if there is a difference.
* set_color which sets the color field but fails if there are children
* update_color which calculates a new average color from the child nodes and compar
  -es it to the existing color, if different then set the color field and return
  true, otherwise return false

## Octree struct
fields:
* something that will allocate nodes on the heap
methods:
* pub new takes depth and fill color as input and outputs a new Octree
* pub set_color that takes x y z coordinates, sets the node at those coords, and
  calls update_color on parent nodes going up the tree until it returns false
* pub get_color that takes x y z coordinates and returns a color
3 Likes

As i mentioned, color may be sent to the GPU and not cached in the Octree itself.

Also there might need to be a Field for which kind of Shape that Node has, specifically for Slopes and such (and those optimized areas might also get such a Shape assigned, if there is Blocks and Air only, or Blocks and Water, so everything looks smoother in the distance). It is a complicated thing for sure, and will need lots of experimenting to find the optimal Solution. ^^

And the Octree Nodes dont have to be 1 Class, they can be 2 Classes, one for “Has Leaves” and one for “Is big Giant Block”. And maybe also one for “Has Leaves but is submerged in a Liquid/Gas/Air”, but that might be too special of a case.

2 Likes

I picked color because I thought it would be easier to write first. I have no idea how to work the GPU so I can’t help with that particular optimization.

I thought all that other information - shape, properties - would be stored behind a single pointer for all block data, not in the octree itself.

[last paragraph moved to next post]

3 Likes

Finally if you don’t use a single “class” for a field in the octree itself, I think that adds runtime overhead. You would need a Box<dyn Trait> for the octree to put different types of structs in the same field. As I understand it that would add an extra byte to each node’s memory footprint (so Rust could enforce type rules during runtime).

If you put the BlockState directly behind a pointer then you don’t have to worry about all that, it’s more efficient since all blocks with the same state share the same instance of BlockState.

Octree Blueprints v3, now supporting block state (I edited away a v2)

## pub BlockState struct
fields:
* color
* shape
* weight
* hardness
* etc
methods:
* pub new returns a new &BlockState, probably from a static hashmapped pool to
  prevent exact duplicates
* pub get_color which borrows self and returns a color
* pub get_shape which borrows self and returns a shape
* pub get_weight which borrows self and returns weight
* pub get_hardness which borrows self and returns hardness
* getters for anything else you think all blocks should have

## Node enum (private)
variants:
### Interior
    fields:
    * color
    * Node children[8]
### Leaf
    fields:
    * &BlockState block_state
methods:
* get_child that takes a number between 0 and 7 and returns the corresponding
  child node from children[] if it exists, or children[0] if there is only one
  child node, or an error if there are no children in the list. Fails if called
  on a leaf.
* pub get_color which returns a color from either self or by calling the getter
  on block_state
* get_block_state which returns block_state. Fails if called
  on an interior node
* set_child which takes a Node and a number between 0 and 7. If there is a
  corresponding child node in children[] then compare it with the new node and
  replace it if there is a difference. Fails if called on a leaf.
* set_color which sets the color field but fails if called on a leaf.
* update which calculates a new average color from the child nodes and
  compares it to the existing color, if different then set the color field and
  return true, otherwise return false. Fails if called on a leaf.

## pub Octree struct
fields:
* max_depth
* something that will allocate immutable nodes on the heap
methods:
* pub new takes max_depth and fill block as input and outputs a new Octree
* pub get_block_state which takes x y z coordinates and returns the block_state at
  that leaf node (return type &BlockState)
* pub get_color which takes x y z coordinates and a depth level and
  returns get_color from the node covering those coordinates at that depth level
  (used for rendering)
* pub set_block_state that borrows mutable self and takes x y z coordinates and
  a &BlockState, replaces the leaf node at those coords, and calls update on
  parent nodes going up the tree until it returns false
2 Likes

(This whole post is a suggestion.)

Now that I’m somewhat versed in Amethyst and ECS, I think it’s clear that the octree would be part of an “OctreeModel” component, or some other component.

But I’m also wondering whether each large octree should have its own specs::world::World.

In all the examples and documentations there is only one World object for the whole game, which is created in main(). The World object is the foundation of the entity-component system. You register entities and components with the World object, and it keeps track of both internally. (Types of components are not restricted to a single world object, but component storage is instantiated by world objects) Systems borrow the world object to do anything useful.

If you look at a game like Minecraft, there is a distinction between top-level entities and entities that are specific to the voxel or block grid (the “overworld” or the “planet”, etc). You have things like mobs which have orientation expressed as a floating point, then you have things like trees or machines which aren’t true entities, which have orientation expressed as a side of the unit cube. (The latter would be “block entities” in Minecraft.)

So when you remove all the abstraction from ECS, and look at the way things are being represented in memory, with only one world object you have only one storage per component. That means there’s one table dedicated to FloatingPointOrientation and another table dedicated to SideOrientation. You’ll have FloatingPointPosition for “true” entities, and IntegerPosition for “block” entities. With one world object all of the component storage tables share the same indexing scheme, which is inefficient because there are really two classes of entities with little to no component overlap. If you’re using a VecStorage, for example, you’re going to waste all that memory because a significant number of entities won’t be associated with the component. With a DenseVecStorage you’re wasting a usize (eight bytes on a 64-bit machine) per entity without the component, which may be more or less than the inefficiency from VecStorage.

And it’s the same with systems. It is only natural for a planet to have its own systems, like weather, pollution, local gravity, etcetera. All you’re going to do is tell each celestial body entity to handle their own internal systems by calling some method on each of them. And to do that you need to know which bodies have weather components, which have pollution, which have internal local gravity, and so on. Each time you’re iterating over a table and skipping the null entries for entities like mobs. Then you finally reach a planet, and the next step is to iterate over a big table again this time only grabbing the mobs so you can make them wet from rain, cough from pollution, fall from gravity, etc. Inefficient!

I think it makes more sense to have two tiers of worlds. So, worlds within worlds.

  • The top-tier world is set on the universe-level. The entire universe, or at least what is currently loaded, is contained in one global specs::world::World variable. Entities and systems on this tier include celestial bodies and their interactions, as well as smaller free-floating objects in space. For example, OrbitComponent might be a component consisting of some representation of an orbital path and an immutable reference to an anchor entity. An orbit system might run every so many ticks to move entities along their orbital paths. Celestial bodies might have a CelestialBody component, with a model field (either polygon or voxel). You’ll have components like shape, position, velocity, mass, temperature, luminosity, etc.

  • Worlds in the lower-tier can coexist, and there are two types.

    • The first type of lower-tier world is for “true” entities that “belong” to a top-tier entity. “True entity” means something you would call an entity even if we weren’t talking about an entity-component-system, for example a mob object or a projectile object. So a mob walking on the surface of planet X would be “true” entity for planet X. There’s no reason to iterate over a thousand mobs on planet X when we’re looking at orbital paths in deep space. Likewise there’s no reason to iterate over planets Y or Z when we’re trying to determine whether mobs on planet X are tired or not. Entities on a planet use a different coordinate system than entities in space, so there would be little to no component overlap between the top layer and the second layer. That’s why each planet - each celestial body - gets its own Option<specs::world::World> field.

    • The second type of lower-tier world is for “block” entities and their components. Planets and the like will have a very large model component such as a voxel octree that represents the entire planet. Some entities would operate entirely within the voxel octree - if we were remaking Minecraft, that means chests, furnaces, signs, banners, furnaces, beacons, and so on. If we were making a normal polygon game, this would be all of the objects that are considered “part of the map itself”, like buildings and trees. These would be registered with a specs::world::World unique to that model and are, for all intents and purposes, considered part of the model.

How about an example? Let’s say you have a large spaceship. This ship has two specs::world::World fields in its various components, one in the (voxel) model component, and one to hold entities that are “on” the ship, like your player character or the crew. Right now, the spaceship is in space so it is technically a top-tier entity with the FreeFloater component.

What happens when you land your ship on a planet? The planet is another top-tier entity, and at some point your ship entity needs to move from the top-tier to the second-tier. The top-tier FreeFloater component will have a method to move all the relevant data over, which means a new entity is created in the planet’s World and all the necessary data (and pointers to data) is moved over. All of the big datasets are behind pointers so it shouldn’t be that computationally expensive.

The end result is that you end up with nested Worlds, there’s the global world for the universe (tier-1), then two Worlds for the planet (tier-2), then two Worlds for your ship which is on the planet (tier-3). In case your ship is a carrier, there may be vehicles on it which have their own World(s) (tier-4). I don’t think there will be more than four tiers, however.

As another example, the debug formatter might produce something like this:

Debug formatting for the top-level World
universe: World
{
	resources:
	[
		entities: EntitiesRes
		&[
			star_1: Entity,
			planet_1A: Entity,
			planet_1B: Entity,
			freefloater_1: Entity,
		],
		component_storage: MaskedStorage
		&[
			position: VecStorage<Position { f32, f32, f32 }>,
			orientation: VecStorage<Orientation { f32 }>,
			shape: VecStorage<ShapeComponent { Box<dyn Shape> }>,
			mass: VecStorage<Mass { f32 }>,
			velocity: VecStorage<Velocity { f32 }>,
			orbit: VecDenseStorage<OrbitComponent { Box<dyn Orbit> }>,
			temperature: VecStorage<Temperature { f32 }>,
			luminosity: VecStorage<Luminosity { f32 }>,
			celestial_body: BTreeStorage<CelestialBody { Option<World>, Box<dyn Model> }>,
			...
		]
	]
}

If we were to then fetch the CelestialBody component of planet_1A, the debug formatter might produce something like this:

Debug formatting for planet_1A's CelestialBody component
{
	world: Option::<World>::Some
	{
		resources:
		[
			entities: EntitiesRes
			&[
				mob_1: Entity,
				mob_2: Entity,
				vehicle_1: Entity,
				projectile_1: Entity
			],
			component_storage: MaskedStorage
			&[
				position: VecStorage<Position { f32, f32, f32 }>,
				orientation: VecStorage<Orientation { f32 }>,
				shape: VecStorage<ShapeComponent { Box<dyn Shape> }>,
				mass: VecStorage<Mass { f32 }>,
				velocity: VecStorage<Velocity { f32 }>,
				health: VecStorage<Health { f32, f32 }>,
				exhaustion: VecStorage<Exhaustion { f32 }>,
				...
			]
		]
	},
	model: VoxelOctreeModel
	{
		world: Option::<World>::Some
		{
			resources:
			[
				entities: EntitiesRes
				&[
					blockstate_1,
					blockstate_2,
					blockstate_3,
					...
				],
				component_storage: MaskedStorage
				&[
					shape: VecStorage<BlockShape>, // enum BlockShape
					color: VecStorage<Color { u32 }>,
					hardness: VecStorage<Hardness { f32 }>,
					orientation: HashMapStorage<Side>, // enum Side
					...
				]
			]
		},
		tree: Octree
		{
			max_depth: u8,
			data: Box<Vec<Node>> // enum Node
		}
	}
}
2 Likes

So one thing I have to say right away, each major “Region” of a Planet (like a Big Island or so) will have its own World, simply for management Reasons, and so that Servers can do things like Clustering properly (I plan to test that with Raspberry Pi’s by the way).

This means a lot of Stuff regarding Region Boundaries, since when you cross them you need to be moved smoothly from one World to another, you need a good transition especially with the Physics (that’s why Islands is gonna be the first non-debug Worldgeneration Type, because you can mostly ignore that Issue for swimming people).

And I did talk a lot about this problem with @OvermindDL1 , and he said it is “easy to share a database between servers”, whatever that will mean for the transition between Regions.

1 Like

Do you mean you want to shard each region onto a different server?

2 Likes

Yep, like having 4 Raspberry Pis run one World as 4 Clustered Servers. That kinda thing.

1 Like

Okay. I don’t think sharding is easy but I also know very little about it. Amethyst’s entity index and component storage tables are not exposed and it’s not implemented as a proper SQL-style database (the the tables are private Vecs allocated on the heap), so you will have to write database management and sharding yourself.

Setting up Shards

I’m assuming you would have all the servers hooked up over LAN. The number of servers and their machine identifiers (MAC addresses, local IP addresses, what have you) can be read from config files.

The thing is, regions (and Worlds in general) are going to be created on the fly. Somehow the software has to decide, on the fly, which server will create each new World. I don’t know how to make that decision, maybe you can base it on some sort of runtime profiling or maybe there’s a way to let the server operator configure it. I don’t know.

I can think of a way to implement the sharding once it is decided where it will go. Wherever above I wrote Option<World>, replace that with Option<Shard>. Shard would be a struct that contains an identifier for, and owned TCP Stream/Listener to communicate with, the server that will contain the new World.

Each method for spec’s World will be wrapped by Shard to send an appropriate EXEC message down the channel (see the next section). I think Rust allows you to go from strings to function calls but if not an enum or static array of closures can match procedure strings from EXEC messages to functions.

For their part, all secondary servers will run the server executable with either a command-line argument or a config file option that puts them in shard mode. In this mode they do not run a full server, but instead listen for messages on a network channel.

Server-Server Interface (within a cluster or between threads on the same server)

AFAIK you have two options,

  • write your own shared memory model
  • write your own messaging model

Even the Rust book says shared memory sucks, so that leaves messaging. The good news is that the Rust standard library has TCP tools, and Specs has built-in serialization (for the purpose of saving/loading games).

There’s only a few messages you really have to implement. Those are, in SQL terms,

  • DELETE: When a system wants to remove data from another World
  • EXEC: When a system wants to call a procedure on another World
  • INSERT: When a system wants to add data to another World
  • SELECT: When a system requires data from another World
  • UPDATE: When a system wants to update data on another World

Client-Server Interface

As far as the client->server interface goes, you have to decide on frontend or backend access.

  • frontend access: client->frontend->shard
  • backend access: client->shard

I think for simplicity’s sake you should use a single point of access (frontend) so the client only uses one interface regardless of server clustering. You could implement both and let the server operator decide, but that seems like a waste of dev time.

2 Likes