This Week In Veloren 25

Thanks to all of the contributors this week, @Songtronix, @Zesterer, @tommywatson, @Pfau, @Vechro, @xMAC94x, and @Jewel_Knight!

Saturday Screenshot Winner

Thanks to @imbris for this week's screenshot. We're excited to see what comes out next week!

Programming

Lights by @Zesterer

@Zesterer has been working on point lights and static entities this week! Static entities are now quite easy to add to the game, and you can give them a Stats component to make them possible to punch around the world. Below you can see how the light count is limited to 32, and the game will automatically show only the closest 32 point lights. There is also now a LightEmitter component that defines the colour and strength of the light that a particular entity should emit.

OctTrees and ECS with @xMAC94x

In the past, we haven't used OctTrees at all. OctTrees are generally a good way to save memory in applications like voxel-based games because you can easily apply a Level Of Detail storage. That is, store more details where the player is, store fewer details far away. Take a look at this video to learn some more about the concept of OctTrees and why they are helpful for voxel-based applications.

The problem with OctTrees is that they are not performant. You have to move through a lot of memory hops, and all of these hops reduce performance because the cache can't work as well with it. An Entity Component System (ECS) can mass-handle thousands of entities, but it's not perfect for handling blocks and terrain data. Because of this, ECS is quite structured and if you know that data is structured you can apply more optimizations.

So neither OctTrees nor ECS is perfect, and that's why we use Chonks for Terrain data. Chonks are more like a HashMap(Chunks, offset) which are super optimized for accessing a block.

I am working on a ECS-like OctTree model which aims to combine the speed of data-driven programming and the efficiency of OctTrees. Yesterday (I think) I managed to get the first functional working version running. Today I managed to generate performance numbers with "cargo bench":

tests::bench_access_0            ... bench:          50 ns/iter (+/- 3)
tests::bench_access_0_4_multiple ... bench:         592 ns/iter (+/- 12)
tests::bench_access_0_random1    ... bench:  49,703,526 ns/iter (+/- 1,152,348)
tests::bench_access_0_random2    ... bench: 554,240,752 ns/iter (+/- 65,435,192)
tests::bench_access_4            ... bench:          36 ns/iter (+/- 1)
tests::bench_clone_region        ... bench:     145,983 ns/iter (+/- 8,634)
tests::bench_make_at_least1      ... bench:  58,263,925 ns/iter (+/- 1,322,574)
tests::bench_make_at_least2      ... bench:     190,072 ns/iter (+/- 7,958)
tests::bench_make_at_least3      ... bench:  26,786,832 ns/iter (+/- 723,765)
tests::bench_region              ... bench:   4,700,958 ns/iter (+/- 352,252)

As we can see in these benchmarks, simple access of a block under this system in release takes about 50 nanoseconds (ns). These numbers scale quite well, even if random positions are accessed, like in the test bench_access_0_random1 where 1 million different positions are accessed by random, which takes about 49,7ns per access.

Even when reading 10 million blocks, the access time seems to be stable. The dataset used for these tests is always 1 billion (10^9) blocks big.

We currently see really slow numbers in "make_at_least" column. This is the metric for adding more detail to the OctTree by increasing the level of detail. Current analysis shows that this is mainly because allocation takes a lot of time.

In the future, I will have a look if we can speed up Vector allocation even further in these cases. Also, we can evaluate if a separation of data and indices can make increased use of CPU caching even more. Also, a cached version of that OctTree, which holds the last access-information might increase access-performance even more.

The system I am currently building has the chance to replace/extend (implementation dependent) the current Chonk system to scale better with larger worlds. It will not replace the ECS system because it just can't compete with its performance and convenience in programming.

The OctTree I'm building stores the data in once continuous vector. That means all data is in one block in memory, which increases performance in ways similar to ECS. In the future, I will try to increase memory efficiency and write about the results :)

Other Work

@Pfau, @imbris, and @Vechro have been working on more crosshair options. You can see this in the settings window.

@Qutrin has been working on camera modes. For now, there will be two modes: first person and third person. First person mode would only be used for build mode for now. There will be lots of experimenting and discussion in the future to find the best way to handle the different views. Thought has to be put into how it will affect PVP and allow players to look around corners.

@Vechro has been working a layout prototype for the social window, which could include a friends and online list.

In other news, @Yeedo is working on debugging glider code, @imbris is at work on tooltips, and @AngelOnFira and @YuriMomo are working on improving the CI system for Veloren. There will be more to come on this topic in the following weeks, but if you want a sneak peek, check this out.