Updates to our future Patreon Content and Blog (Patreon)

Hi, my name is Timevir, and for those who don’t already know, I’m the new community manager. It has taken some time to get everything in order, and now I’m ready to talk to you about the progress and how we plan to change how we engage with you from today.

As our most loyal supporters, we have a duty to make sure you have as much insight to our process as possible, even for things that might be too sensitive to release to the wider public. We trust you to give us great feedback and use the information we provide to help our project succeed. We will not prohibit you from talking about anything, but we do ask you not copy things from here verbatim as they may be subject to change and may set expectations for the wider public that we do not intend.

Our community engagement will be ramping up real soon, with a blog that will be posted starting next week. We will be posting development logs regularly on Tuesdays and Fridays. Tuesday will just be an introductory post, but Friday’s will be the first real post and will be shown to you here today. As Patreon members, we will be giving you access to posts in advance of the public releases. This is so you can give us early feedback, discuss and ask questions that may be used to add additional detail to the developer logs.

In the next post, I will discuss with you detailed insights into our survey analyses, but first, here’s a sample of what a developer log will look like. Friday’s post will feature this entry written by BADUMP, our primary performance developer. Please note that this is highly technical, it’s ok if you don’t understand it all!

---

Badump File #1

Hi guys, my name is Badump, and this is my first developer log. I am the guy who writes the pathfinding, netcode, unit movement, and right now also targeting code; in general with high performance code. Expect dev logs on those in the near future.

Recently I have been working on the targeting system that we are going to use in Sanctuary.

It is also supposed to handle things like spatial category queries. (Meaning get all units of type x in range n around some location or similar).

First things first, what are the likely use cases, and performance concerns?

Well let's start with a very heavy use case, imagine 10,000 Tier 2 artillery units, 5,000 for both sides. All units are in range of one another.

If we do brute force comparison, then that is 5000^2 or 25 million evaluations. Ouch. (That is not even a peak work case, that would be 30,000 vs 30,000, or 900 million.)

One solution is to spread out calculations over time, but as you know that is going to create some gameplay problems at higher unit counts, which is something we don't want to cause.

Also imagine your radar flickers from a power shortage, now all units need to reacquire targets, causing pretty big gameplay issues, as you lose tons of dps.

So what we need is something that does it instantly and does not wait for so long.

Also we need some other features. Examples are not targeting units that are going to be soon dead (overkill) and trying to target units that have the lowest angular distance, meaning you don't want your battleship guns to rotate 180 degrees if there are enemies in front of the guns.

The solution that I created is to take note of the fact that most of those unit ranges overlap, meaning we can combine them together into a big group, and then calculate for that group instead of calculating for single units. That in the best case scenario reduces our factor by 5000, from 25 million to 5000, or (900m -> 30k). Still that is not always possible so our factor is going to be higher than 1 but much much less than 5000. So it is between 100x-1000x faster, and the gap grows when more units are added. For those familiar with Big O Notation: O(n^2) vs O(n log n).

The next piece of the puzzle is targeting stuff that is close by angle. So we want to prefer enemies that are not going to cost much time to rotate towards. Solving that problem precisely is going to be costly, so we are going to have to create a small workaround.

We split all the units into a ring around the average center of the group itself, in some angle increment, for now 10* meaning 36 ring pieces.

Also units have an overkill factor, we generally try to avoid scheduling units that have more incoming damage than their current hp.

Alright, what must be done now is stated, now how?

Here is an example of how the targeting works, showing one of our code-based test cases;

This code is what our modders would be using to target stuff, or some similar API in lua(which is not in scope for now, stay tuned).

So first the target is instantiated with some fixed size, and player count must be known before the game. Unfortunately for now it generates around 50MB per player, which is the fastest solution, but might be bad in the case where there are 32 players. I am still working on a more efficient solution which I will present at a later date.

The targeting priorities are set, which summarized is what the unit wants to target. Right now it is just a test, but imagine 0 means land and 1 means air. Our unit doesn't target air.

For now it is simply matching if the target contains all the categories in any of the targeting unit list. (Now this code is burstable, don't be misled by the usage of the list, that is just a convenience API).

The other units are of type 0 ie. land. All is good.

Different players also have different groups due to the possibility of multiple teams.

In case there are only 2 teams, and locked teams, it is possible to send team id, instead of player id. So for now 2 teams with 32 players = all good, 32 players FFA = not so good.

Then we finish adding all the targeting units, and perform some magic to make them into groups.

Afterwards we add units that are targets. For now some features are missing, like adding the unit HP (it is always the same). That will be developed later on.

The targets are added into the groups, and distributed to the correct ring segment (for reducing turret movement)

Then comes the last part, where we distribute the targets themselves onto the units, each group is processed in parallel (as they are pretty much independent, they have their own targets).

That is done simply by having each unit iterate radially outwards from the closest ring segment. So if it starts on segment 0(meaning it has rotation of around 0 degrees), it searches for targets by looping like this: 0,1,-1,2 ,-2,3,-3 …

Currently the code as is, for a test case of 20x20 = 400 square of units, targeting 9100 units, finishes in around 800µs (1000µs = 1ms). This is my favorite scenario, of Tier 2 artillery targeting a swarm of Tier 1 units, and the whole reason I went to write all of this code. So that is around 4 million comparisons.

There are currently some big flaws with our performance doctrine that we are still working on. The ring doesn't keep track of segments that are pretty much all dead(overkill) so later units have to loop through earlier overkill units to find a target. Keeping track of it would reduce the time a lot.

And right now this code runs only on a single thread for now, because some parts are not completely thread safe.

Fixing those two issues would allow it to execute much faster.(But it is already 600µs)

Although it’s important to remember that normally you don't have so many units trying to find a target in the same frame, so this is a worst case scenario even with our simulated numbers.

Currently the largest problem is creating a memory efficient list that is also thread safe and well actually fast. Unfortunately, Unity nativeList is not thread-safe for expanding.

PS: When I initially wrote this post, I forgot to turn off debug mode! I got it to 40µs :).

PPS: As the tests were actually too fast for profiling, I increased the size of the scale until they were at the very least hitting 10ms for execution. But I will explain this in the next post.

Anyway stay tuned for next time!

---

Amazing right? BADUMP is honestly excellent. Let us know what you thought on reading this. Was this too difficult to interpret? Was this the level of information you are looking for as Patreons? Do you think the level of transparency is appreciated? Let us know!

Finally, I am often on the Discord community’s voice channels if you’d like to talk to me in person. I’ve already talked with a few of you, and really appreciate the wonderful support and feedback you’ve given me. Alternatively, send messages to me directly or the #patreons-corner and I will discuss with you ad prioritatem.