- Home /
Keeping track of lots of entities
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 ?
From my personal program$$anonymous$$g design, I don't care how much ship you need. It just a matter data control, who contain what and who control who.
I would make each sector/Station have only: - List of Ship currently Docked
List of ship just go out and maybe co$$anonymous$$g to this station
What happen to other ship. Don't care. Station do not contain or control them.
I don't need to update anything. If any ship co$$anonymous$$g, they will tell me. If ship leaving, it will tell me
Ship. Only 3 things:
$$anonymous$$y Begin Station (I inform I just leave)
Update Position function (Only 1 $$anonymous$$anager. 1 $$anonymous$$onobehaviour Update all the ship)
$$anonymous$$y destination Station (I tell them i am co$$anonymous$$g)
For searching ship or station, best practice is several pre-made dictionary.
Dictionary of all Ship: $$anonymous$$ey will be name of ship or ID.
List for update() through 1 monobehavior.
Dictionary of all station:
Each station have List Docked Ship, List of Co$$anonymous$$g Ship, List of leaving ships
To me this is quite simple solution. I am not sure how you got trouble for approaching this problem.
Answer by mikewarren · Jul 24, 2018 at 05:09 PM
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.
Hi, and thanks for the answer ! Yes i was surprised that i wasn't able to find any relevant information on the net on something that seems like an early problem to me. Well maybe i didn't use the right keyword. Someone mentionned something like you, with colliders and such on sector's border, but as i said, there is no graphic involved. Ships indeed have a position, but this is only to simulate distance to the player ship for the information screen. $$anonymous$$y game will be mostly text and description driven. As such, there is no ships crossing borders. It really limit to this :
Ship A is in sector Alpha. Ship A want to go to neighbor sector Beta. Calculation of time estimate to jump to sector Beta : 30s.
Ship A arrive in sector Beta. Ship A want to board station One. Calculation of time estimate to board station One : 3$$anonymous$$20s.
Ship A board station One.
As you see, ships doesn't get close to the sectors border, they don't even really move, it is abstract (for now, later version will indeed include at least radar map with 2d coordinates changes. Right now it's only simulated).
What you said though interest me for the later version, what do mean by updating more frequently ? Here is what my idea was to this point :
Player select sector Alpha to see sector status
Game loop through all ships and generate sector Alpha ship list based on ships location (ships are in an hashset, in the galaxy object)
Whenever a ship in the galaxy switch sector, game check if sector Alpha is either origin or destination of jump. If sector Alpha is concerned, the list is updated and gameObject is either deleted or added to the list view (scrollview)
What do you think about it ? Either that or all sector have their own list updated real time.
Edith : I really hate the answers.unity text editor. Can't even add line space in my answers.
Yeah, the editor blows.
On update loop, I presumed more than you wrote. $$anonymous$$y point was that if you're tracking state changes of a ship (changing sectors) and you know it's going to take, for instance, three $$anonymous$$utes for the ship to reach a sector boundary, there's no sense in checking it's state until three $$anonymous$$utes have elapsed.
It sounds like you have more of an event driven systems. I might be tempted to encode state changes (move to new sector, dock at station, ship status change, etc.) as time sorted list. Then you only have to process the events that fall within the resolution of your delta time update.
Oh, I see what you mean, i'll keep that in $$anonymous$$d when i'll get at the event processing optimization :) right now i'm using tick based system, so each tick, all events are processed, with their resolution based on either the timer or the coordinates. I could, as you said, optimize that by treating event with a real timer ins$$anonymous$$d of ticks, and check for coordinates arrival only after a timer has elapsed, since if my ships have 10 ticks to arrival, it would not be usefull to check the event status before at least 8 tick realtimes have passed.
I'll have to check for limitation when the player go into the menu or artificially block the timer (and how the timer will be handled by save/loading).
For the list updates, i'll got with the event c# system, with list updates beings linked to delegates methods that are setup on scene creation to a static manager. So when my game manager, in the back, process an event, it will call that method delegate which will in turn update the visual. I'm already doing that for the player status string (in flight, docked, etc...) so i don't have to check and update the gameobject.text every frame, when it doesn't change that often.
All that code is still in comment though, i want to see if performances really come an issue before implementing that, i don't know if text update every frame is that costly.
Anyway, thanks for the tips or time elapsed event check, i could divide by 4 the CPU use by checking events that should not be ending soon with that !
Answer by JVene · Jul 24, 2018 at 11:39 PM
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.
Thanks for the full and detailed answer ! I had no idea this could be this complex, even though i guessed that full released games must had some optimized algorithms for managing such cases.
I think i understood your point, and I will keep that in $$anonymous$$d if performance becomes a problem.
From what i understood, you agree with solution one, which would be full loop on all the ships in the galaxy (contained in an Hash-Set, for better performances on access, am I right ?) then generate a local List of Ships for the sector. Then unity scene will need that list to instantiate ShipTemplates in a list view, so all ships are shown in that list for the player to target.
You're totally right though, that list (and the graphical list view) will need to update from time to time to add or remove a gameobject if a ship enter or left the sector. Whenever that happen, the game will generate an event message checking if the current shown sector is either the origin or destination, to correctly alterate the local list without looping again through every ships.
I don't know if the list itself will be used by the game other than generating the list-view though. Once the list-view is filled with ships templates (panel contained name, controller script for updates, and that's pretty much it), i'm not 100% sure the List itself will have some use yet. It will probably be though, when i implement battle maybe, so that the game loop through the local list to assess every ship behavior regarding the threat. So yes, list will be probably accessed while being potentially modified, so threads calculation may become mandatory in my game, unless i find a workaround.
I don't think it would alter the game animation though, if i understood correctly what you explained. Normally, the listview will only instantiate or delete ships template only on sector modification, but without asking for the sector list. I guess, when a ship enter the sector, i would write an event method OnSectorUpdate(Ship ship) to either add one new template, or remove one from the listview, and then altering the list in the back. But the UI should only use the sector list on generation. If i would recreate the listview by looping the list on every sector update, that would generate some stuttering I$$anonymous$$O.
It seems you well understood what I was trying to say.
Hash and Dictionary are so similar, I seem to prefer Dictionary in C#, but...
The primary reason to use it is quick lookup when a ship does it's update. It doesn't help the sweep (can actually slow it down). This means if you have any machination where the ship can update the entry in the list, or if the list is holding a reference to the ship so when the ship updates the list already knows without an update, you could skip the dictionary and therefore improve memory consumption and speed up the sweep.
I think all will come to experimentation on the "field" then :).
Right now, i'll go with a tick based system (one tick every second, maybe less if that's make my game too flickery, which seems to already be the case).
So each tick will check current ship action and process it. If the action end, it will trigger an event (c# event system) by calling a delegate of the update method, that will notice all receiver of the event. That way i can update when i feel like it's actually needed. $$anonymous$$aybe like, ship transition through sector will check if current shown sector is affected, and if it is, then call the delegate to update the scene list object, and then update the scene list-view. Ships will be stored in an hash-set that will be checked only on scene loading. Since my game, for now, is updated every second, that should left enough space for unity to actually use my list in a interval where the list isn't modified.
I'll check if that leads to perf issues, and if that's the case, i'll try mikewarren option, which is to check less event based on their probable timer (like, no need to check a ship every second if he is arrived if he is supposed to travel for 10 seconds), then i'll go on our conversation for all the threads implementation.
Thanks for the tips and insights :)
Your answer
Follow this Question
Related Questions
Fast Game Simulation for Reinforcement Learning 2 Answers
Turn character by force 1 Answer
AI question, characters escaping from light 0 Answers
Problem with AI tracking object 0 Answers
Ai can fire Infinite bullets? 2 Answers