This Week In Veloren 111

This week, we hear about many improvements to systems across the codebase. Network and metric improvements, airships, physics, pathfinding, AI, and much more.

- AngelOnFira, TWiV Editor

Contributor Work

Thanks to this week's contributors, @xMAC94x, @Sam, @zesterer, @aweinstock, @AngelOnfira, @James, @imbris, @Synis, @DaforLynx, @Snowram, @PersianKnight, @Christof, @Slipped, @tukilo, @ccgauche, @BryanQuigley, and @Pfau!

This week, Veloren is preparing for code freeze as 0.9 approaches. @Snowram added the latest batch of NPCs made by Gemu into the game. @DaforLynx updated and moved the "Getting Started" new player's guide to the Veloren Wiki (along with other topics in the Wiki) in preparation for an influx of new (and returning) players when 0.9 releases.

@Frinksy packaged Airshipper for Fedora and set up a Copr repository to help with installing/integrating the game. @Christof get trading merged and created several bug fixes afterwards. @lboklin has been working on density and buoyancy, and there are two videos you can go check out to see the progress (1) (2).

Improvements by @xMAC94x

Network Improvements

Veloren's backend recently had a huge network improvement. It was a complete rewrite which allows it to easily switch the underlying protocol on an abstracted layer. We use a technique called I/O-Free Protocol, in which we implement the protocol-code without the need for an actual TCP or UDP connection, which makes testing much easier.

As a result of this, we were able to implement a MPSC backend in addition to our current TCP backend. Which will be used in singleplayer. The MPSC backend will reduce the load on networking while in singleplayer and thus give you more CPU performance for higher FPS.

Metrics Improvements

We redid the way we are tracking all different systems in Veloren. Veloren has all kinds of systems for internal tasks, such as NPC controlling, physics, and persistence. Before we just measured the runtime each system took, now we additionally also track WHEN a system starts, and on how many cores it runs. This helps us devs to get a better overview of what's going on on the server and where we need to improve things.

For example, you may think that a system that is only single-threaded is bad and slow? But if it's designed in a way to run in parallel with 7 other systems it still behaves quite well in terms of multitasking. If a system is single-threaded AND many other systems are waiting on it to complete, it's a different story though. We need to improve this by either changing the algorithm, introducing multithreading, or change the dependency of those systems. It also gives us a better overview of how expensive our systems are in total.

In the image above you can see a list of all our systems, suffixed with an s for start or e for end. You can either read the exact times when a system is started or a have a look at the graph. For reference, the big red system is our physics.

Pathfinding improvements by @Yakei

With school work done, I was finally able to start working on the pathfinding rework. The current pathfinding algorithm used is the A* (A Star). While it has plenty of benefits in a controlled environment, it is definitely lacking in result in Veloren for multiple reasons. Primarily, AI currently can't climb nor fly outside of RtSim. After talking a lot with @aweinstock and @zesterer, the goal for now is to implement a rapidly exploring random tree. This is an algorithm tailored for exploration of the environment until a working path has been found.

In theory, I finished a very crude and naive working proof-of-concept. In practice, there are plenty of limitations that I need to remove as soon as possible. The biggest one for now is how explored paths are stored. I am using a K-dimension tree as the primary data structure. Nonetheless, the crate I found does not really suit our need in many ways:

• You can query data related to spatial points but you can't query the actual point. In our case, we want the coordinates, while we don't store data.
• You can't build a path in the coordinates graph. This means I need to store each point in the KdTree in order to query the nearest neighbor, but I need to store it in a vector along a parent-id so that I can return a complete route for the agent system to follow.

I ended up forking the crate and rewriting a part of the code in order to remove some of these limitations (and I gained a 40/45% perf increase in some of my benchmarks). However, the graph part is not properly doable without tricks that I wouldn't consider long term. My plan is now to rewrite from scratch the KdTree implementation in order to achieve better performances, more convenience for our needs and a more Rust idiomatic code.

Input improvements by @Sam

I have completely rewritten how inputs are handled by the game. Previously, there was a struct containing a field for each input, and each field contained data on whether the input was pressed and how recently it was pressed. Now, inputs are represented by an enum, and an input being pressed and unpressed are sent as separate control actions. When an action to start input is received, it is added to a BTreeSet, and when an action to cancel an input is received, it is removed from the BTreeSet.

Changing inputs this way has a few advantages:

• If an input happened within the space of a tick, before it could go unnoticed if it was pressed and unpressed within the same tick, now that input should be recognized by the server when doing an action.
• Now that inputs are collected in a BTreeSet, we can also prioritize inputs such that certain inputs are handled before others as the BTreeSet orders the inputs.
• The amount of data synced from the client to the server is now also moderately smaller, as less information needs to be sent

Agent Code Update by @James

My agent code refactor got merged almost two weeks ago, but I haven't yet written anything about it. I refactored the agent system into a behavior tree. Previously it was a finite state machine (FSM) with massive states and confusing transitions hidden all over the place. It looked a little bit like a plate of spaghetti with transitions and states all tangled up.

Luckily for me, I had written a good chunk of that spaghetti and found it relatively palatable. The fact that the file was ~1500 lines of code and in such a messy state didn't exactly make it easy for other developers to work on the agent code.

For those of you who aren't familiar with the Veloren code base, the agent system is what governs NPC AI. Before this refactor, an agent could be in one of a number of states, such as Idling, Fleeing, etc. Transitions between these states were scattered throughout the states and as overrides before and after the bulk of the code in the agent system making the decision-making logic difficult to follow.

Finite state machines and behavior trees are the two most popular game AI code structures. At its simplest, a behavior tree is a decision tree that determines behavior based on a series of conditions. The end (or action) nodes represent an agent behavior. For Veloren's implementation, all the random information about a specific agent pulled from the ECS is put in a tidy struct. Methods on this struct act as the action nodes.

Now if someone wants to adjust an agent behavior they only need to find the proper function. The decision-making process is modeled directly as a series of if and match statements making it easy for other developers to design new behaviors. Since the action nodes all belong in separate functions, multiple devs can work on different behaviors at the same time without worrying much about conflicting work. My hope for this system is that other devs will be able to jump in and design some neat behavior for Veloren's NPCs.

This week I made some quality of life changes for NPC interaction. Most NPCs in the game world are created and destroyed as terrain is loaded and unloaded by the server. The exception to this rule are the RtSim entities (short for real-time simulation). These entities persist when unloaded and currently are visible as the travelers that roam between towns and castles (there are also RtSim birds that fly between dungeons).

RtSim entities have a "Brain" that can store information that changes their behavior. This is where they store their destination and they now also store memories of interactions. If you talk with a traveler (press E to interact) the first time, it will give a generic response about its destination. The second time, it may greet you by name if it remembers your character. If you attack a traveler it will remember your name and attack you on sight if it runs into you again while that memory hasn't faded.

I also fixed some issues with merchants. Merchants should no longer wander away while engaged in a trade with a player. When you interact with a merchant, it will offer to trade with you (press R to send a trade invite). Additionally, the price demands that the merchant says now appear in the chat box for players in the near vicinity. This is helpful as the merchant chat bubble is often obscured by the trading window. Villagers may also find your presence less tasteful if you walk around wearing cultist armor.

Airships and Physics by @aweinstock

@zesterer and I implemented airships this week. Currently, they can be spawned by an admin or in singleplayer with /airship, and we plan to have RtSim airships flying routes between towns as soon as some agent flight code is fixed (which also affects birds). Airships can be flown by mounting them, and act like terrain for other entities. You can climb on them, jump and glide from them, climb stairs on them, and so on.

When I first added the airship model (which Pfau made, and Sarra added stairs and a second floor to) as a normal entity to the game, it had a Box collider, which meant you could push it around on the ground much like an item, but you couldn't stand on it (if you tried, you'd fall through, and push it aside). In order to find out how to make physics work for them, I refactored the physics system into functions (previously it had been a single ~1K line of code run function).

In the process, I discovered that the terrain code could be made more generic: the specific type it was using was a TerrainGrid, which is a statically sized grid of voxels used for chunks. By changing the function to accept anything that satisfies the trait bound T: BaseVol<Vox=Block>+ReadVol, it became capable of also accepting Dyna models, which are the voxel models used by the figure pipeline for entities.

By translating and rotating an entity's collider into the reference frame of the airship model, it became possible to support airships collisions with floating-point positions and rotations while still using the same dense array of integer-aligned voxels. By combining the abstract physics states it became possible to climb both airships and terrain without interleaving the processing of their blocks.

Once the collision was implemented, there were some more quirks with movement which were addressed by @zesterer. He changed friction and air resistance to make movement smoother, and to move the player along the airship with friction. This is more accurate than what many other engines do (coordinate locking), and makes it so that your velocity is still aligned with the airship when you're jumping on it or gliding from it. He also made various tweaks to the block hopping and block snapping parts of terrain collision, which facilitate walking uphill and downhill as if it were a curved surface despite being made of voxels.

@zesterer also tasked me with implementing client-side interpolation for positions, velocities, and orientations, which make airships smoother to ride in the presence of network latency. Without interpolation, the clients assume that if they haven't received input from the airship in a while, it will have started falling due to gravity. When the server corrects the client, the airship jumps back up, which may cause the player to fall through the floor of the airship to their death.

With position interpolation, the client predicts that the airship will keep going at its current velocity, causing it to move smoothly even if there's a delay in receiving the airships inputs (and likewise with velocity interpolation and acceleration, and orientation interpolation and rotation speed). Interpolation is currently linear, as we tried a cubic model called Hermite Spline Interpolation and found that it was less smooth with the settings we tried at the latencies we tested under (although it's intended to preserve derivatives better than linear interpolation once well-tuned).

The physics improvements caused a few regressions in Agent and RtSimController movement, which @Sam and @James have been helping to diagnose and fix, due to those systems having been tuned against the old, physically unrealistic friction and air resistance values. @imbris has also been working on physics engine improvements such as reducing the number of allocation in the physics code, and adding chunk based broadphase pruning for making entity-entity collision detection faster.

It's worth noting that the voxel colliders added for airships can support other features too. Possibilities include elevators (which could be generated as an alternative to spiral stairs), water orb attacks that cause swimming and slow movement for entities they pass through, temporary defensive fortifications with HP or timers, moving/floating platforms in dungeons, and possibly even doors.

Since @Christof merged NPC merchants this week, I also made some improvements to the trading UI; in voxygen, each player's offer always appears on the right side of their screen (near their inventory), and I fixed a bug that @Mog pointed out where the crafting recipe cache wasn't getting updated on completion of a trade.

In the process of developing a load-testing bot client for @xMAC94x, I found and fixed a bug where character creation allowed the creation of arbitrary tools due to a lack of server-side validation of client input.