This Week In Veloren 136

- AngelOnFira, TWiV Editor

Contributor Work

Thanks to this week's contributors, @zesterer, @Naryadchikov, @XVar, @xeriab, @Sam, @Slipped, @khalludi, @xMAC94x, @slashplusplus, @Sharp, @juliancoffee, @ubruntu, @Snowram, @knightresspaladin, @imbris, and @Capucho!

@nomango hosted a gliding race from the town of Sist, in the highest mountain peak of the map, to the town of Irronk at the foot of the mountain. Organizing it was a fun experience, and in the end 5 people participated and a bunch more watched. The winner was @Boudin, congratulations!

Improvements by @juliancoffee

I've recently been working on new server setting and command!

• battle_mode setting Global(PvP/PvE) or PerPlayer(default: PvP/PvE)
• /battlemode command which allows you to switch between your battle mode (pvp and pve). Can be used once in 5 minutes, only in towns and only if server enabled PerPlayer() battle_mode setting. Enabled on official server which means no more ganking of new players!

Balance changes

Chests no longer spawn on the starting floor of dungeons (and more of them spawn in final floors). Chests now have equal chance of spawning between different dungeon levels.

Developer experience changes

• VELOREN_ASSETS_OVERRIDE environmental variable should help to run servers with modified assets (should be declared as on server machine and on client machines) and allows you to add folders with assets you want to have at a higher priority (while keeping every other assets the same).
• Refactor of server and voxygen code that interacted with skills to make it easier to add new skills and modify existing ones. Main changes are the SKILL_MODIFIERS constant which stores every constant used for skills in a more declarative way to specify skill icons in voxygen code.

Cultist Raiders by @Sam

Cultist raiders have been added. Now, cultist raiding parties will periodically set out from cultist dungeons to raid nearby settlements for sacrifices. In adding them, the real-time simulation system needed to be slightly expanded to allow for rtsim entities being attached to a particular site as well as have the species, loadout, and alignment of the rtsim entity being specified instead of just entirely random.

Naga by @Capucho

Last week we merged the MR replacing shaderc with naga, but despite the MR only having one commit and a three week merge window, the work to make naga capable of parsing all of Veloren's GLSL shaders and emitting spir-v took more than a year!

The initial reasoning behind this switch was to make the lives of developers easier. shaderc adds more requirements to the tools needed to compile Veloren and was a bit of nightmare when trying to cross-compile to macOS in CI. But after working with naga and integrating into Veloren, there are some other benefits:

Validation

naga, being part of the WebGPU pipeline means that it's exposed to potentially bad shaders that can cause issues with GPU drivers and potentially bring them down. A validation layer is added that rejects shaders that can cause this bad behavior. In Veloren, this is very helpful since bad shaders can go unnoticed on developers' machine and produce bad results for end users or affect performance. In particular, uniformity analysis has caught a handful of errors with texture sampling that can cause undefined behavior.

Error messages

The error infrastructure of naga allows easy coupling with error reporting crates like codespan. This allows for Rust-like error reporting, but this is an area that needs more work for example hints.

So far everything has behaved extremely well, though there are some people reporting black worlds when using high lightning settings. The cause hasn't yet been identified and for most users has been working correctly. If you do see a black world go to the graphics settings and change lightning to type L - Cheap.

The glsl frontend despite being in a pretty good state is still far from being completed. I intend to support some of the more popular extensions to the language, for example include directives that are for now being handled by glsl_include. There's also the question of optimizations that are for now delegated to the driver, but in the future may also happen in naga.

I really enjoyed working in naga and with the people building it (special thanks to @kvark for reviewing and helping out in my contributions). I've worked on some other things besides glsl, most recently the spir-v frontend so that in the future we can migrate to wgpu 0.10

Assignment problem by @Christof

This week, I've been working on solving the Assignment Problem for Veloren.

Simulating economies is not that hard to understand; you start with a bunch of resources, define a goal (e.g. population growth) and then steer the population to create secondary/tertiary/... goods to fulfill this goal. The above-mentioned "assignment" is the answer to the question "how many farmers/hunters/guards/... do I need to achieve that goal?" (or more generic: "How to assign NPCs to professions?")

The previous solution in Veloren was to assign according to the relative surplus per produced good (called value). This worked just fine for non-merchants, as merchants trade but don’t produce goods, thus there is an upper limit in available goods. At some point employing more and more merchants won’t give you more of that rare good you desperately look for.

Also this was just a relative assignment, you could not plan how long each person would need to work to produce the needed amount of goods. On top of this, I recently added more complications to the system: People use some tools for their work, thus these tools are needed but not consumed. Also I wanted coal and animal dung to potentially replace wood as fuel, introducing another tricky logic puzzle.

So I came up with the plan to define an error function and simply minimize the quadratic sum. This sent me on a path where I learned a lot of numerical algorithms I never took a closer look at before. A mathematician friend was my guide on this journey.

Once the pieces come together the solution is easy and robust; just use a matrix to calculate the necessary change in assignment from the difference to your target in produced goods. If you also want to take stock fill into account, just apply a nonlinear mapping of the difference to the target before applying this matrix. This is similar to the Gauss Newton algorithm and its generalization for not directly invertible matrices, the Levenberg-Marquardt algorithm.

These use a matrix derivative of the error function and invert it to compute the next step. Luckily you can phrase the equation differently; you need the difference in input which causes a change in output. Basically, the derivative of the input to the output (the inverse of the normal derivative). And this matrix is easy to write down by hand; how many people do you need to add of each profession (recursively) for an increase of one - per good. This easy to understand concept is the true meaning of the three multiplied matrices (JT*J)^-1*JT in the Gauss Newton algorithm.

On this journey I also tried pseudo-inversion of matrices - a mathematical concept which defines sort of invertability for non-quadratic matrices. This pseudo inverse is typically computed by using an SVD algorithm and gives the result of the three matrix multiplication with less numerical error.

Unfortunately this matrix also resulted in negative numbers - stealing raw materials from other professions instead of pushing them through the whole supply chain. And in simulation this quickly caused a general shortage of people producing important stuff.

To get the new system ready I still have to complete the planning of merchants and the correct mapping of in game items to economic goods. Also I would like to modify the type of buildings, the loadout and the behaviour of the town dwellers according to the economic situation of the town.