Keeping track of lots of entities

Questions & Answers
1

Hi people.

I’m currently coding a space management sim (in the like of X3: reunion) and i would like some advises on the way to keep tracks AI Ships.

Right now, the game is a galaxy composed of sectors. Ships can fly in sector and from one sector to another, to reach infrastructure. The aim is to generate some life with useless travels, but also simulate a real economy with AI Ships looking for opportunity.

There is no graphic, so no 2d representation of where a ship is, only logic and references.

When the player has intel on a sector, the game needs to quickly list the ships in the current sector. So here is my “problem” (“” because it’s not a real problem right now, i just want to know which way is better performance wise).

How can i track theses ships on the global galaxy ?

For that i have three ideas.

1- Either i use my variable Location of type Sector that every ship have, so i loop through all ships (contained in a hashset) to find which one are in the sector. It should work at first, but i fear that in the more advanced stage of the game, where more ships will be available, this loop will be costly. I do that once to fill a temporary list available only to the sector the player is looking at. From now on, every time a ship will move, it will send an alarm to check if the ship entered or left the current sector, to update the local List.

2- The other solution is that each sector have a list of ships. So i just have to ask the current sector about his list that will constantly update real time. The thing is, I will end up with a lot of various size List that will change a lot through the game. I’m not sure this is performance friendly to have the list resize again and again to remove object and add object every 5 or 10 seconds. What do you think ? We’re talking about about several dozens sectors, maybe a hundred (so 50 to 100 lists).

3- I could also store a single List of KeyValuePair, containing ships and their location, in the static GameManager. But is that even more efficient than a loop on a List of Ships to check their Location value ?

I got the exact same problematic with stations. They need to know which ships are docked. Sure, their list won’t change as often as sectors, but we are still talking hundreds of small list that will change size and content through the game.

Overall i think solution 1, ships knowing their location, and a method to loop through all of them and generate a filtered list based on the selected sector seems to be the best choice. Did any of you encountered such problem ?

2

I’m not going to be able to give you a definitive answer, but I think these are good questions to be asking.

This is kind of a classic tiling problem. I’d suggest looking up Octrees as an example of spatially sorting your entities and managing sub-list sizes. If all your tracking is sector crossings, you could even sort entities so that those closest to sector boundaries are updated more frequently (as they are more likely to cross).

But first, I’d also take a look at the new Entity Component System and Jobs System. I don’t know much about them, but I think they are specifically designed to facilitate high performance code design patterns. Well within the scope of your problem.

3

You’ve brought a design question where implementation can hit C# in its Achilles heal. If I were doing this in Unity for a product, I’d be motivated to use a native plugin written in C++. For the moment I’ll assume that’s not an option for you. It is possible, but it brings to the table the tedium of managing compilation for every platform and platform variation.
You should consider building an experiment in C# (even outside of Unity) to test solutions. The option 1 may perform well enough for you, because code can rip through entries of a List<> somewhere in the range of 100,000 items per millisecond, more on a PC hardware this side of 3 Ghz.
Creating a result list is going to take a lot more time, though, because the limitations of C# and the default containers require unusual machinations to avoid creating copies of objects, or at least preparing smart pointers for insertion into a result list.
That said, one thing you can do to mitigate stalling the Unity main thread (and thus frame stutters) is to launch a thread to do work like this (System.Threading).
Threads are not as scary is some forum posts might lead one to think, but they do require some thought regarding synchronization. However, it is possible to have a thread collect the data, prepare a result set, then ‘send a message’ (sometimes just setting a bool to true to indicate the results are ready when the next update comes) that the results are ready.
An example of thread interactions to consider in your case (as best I can deduce) is adding or deleting ships from the list. Doing this will change the list, and it can take a while. If you enforce the notion that there is one and only one thread that will do any threaded work, and that list insertion and deletion will only happen in that thread, you have no problem. If, however, it is possible that a thread would read from the list at the same time the Unity main thread adds to or deletes from that list, there can be an issue. To coordinate that, you’d have to consider using a lock (on a System.Object) - and that means using a lock everytime the list is accessed, everywhere.
To avoid that, you could launch a thread that’s always waiting. For this you use an AutoResetEvent. The idea is to create an executive function for the thread, which waits on an AutoResetEvent. The Unity thread then (by means of your own design) sets an instruction for something the thread should do (I like to use delegates for this, likely a collection of delegates in a Queue container), then signal the AutoResetEvent (by calling Set on the event). This releases the thread’s wait, it then executes the instruction(s), and returns to waiting. If everything involving this “inventory” is managed by that thread, nothing is going to be a problem. Using a simple design, then, what you have is a way to send what would be a function call to a thread that waits for things to do. When your ship needs to update it’s location in the list (if that’s a thing), it can call a function on the thread which adds that instruction to the instruction que, signals the event for the thread to wake up and do it, and go on as if that function had been performed normally. Everything involving this inventory, from updating to inserting and deleting, would be handled this way. The entire purpose is to avoid stalling the Unity main thread (so the animation doesn’t suffer) while still being able to perform work that might stall the animation.
You could determine if that is even necessary through a few C# experiments and timings, from which you’d have materials you could then plug into your application that are already tested (by copying the code from the test into Unity’s solution). I use these kinds of threaded queues extensively. I developed the first implementations of this idea for my own toolkit in C++ about 25 or so years ago, and have reused that code in projects to this day, with an adaption built for C#. It is a very useful concept applicable to a wide range of projects.