Hey guys, I've been working on my tower defense game for a bit, and as I have been adding features to my game, the struct size for my monstars has been increasing a bunch recently (currently at 400 bytes). Now this size is still small, I can have over 1000 of these and be under a megabyte of memory usage but I do a lot of querying in my game and I noticed that its starting to take up more time than I'd like. Since my game is on mobile, I know this is a problem I'm eventually going to have to tackle and for querying, I only need to store position information for my entities, as well as some kind of id that lets me reference the entity that this position is coming from. So watching data oriented design vids, I should be trying to store the positions of my monstars in some kind of SOA format outside the monstar that can be quickly run through with SIMD. I came up with some ways of achieving this:
1) Every frame I can run through all the monstars in my world, assemble their positions into a SOA array, and use this array for all queries during that frame. Then after the logic is done for this frame, write all the positions back into the monstar structs. This has the benefit that I don't need to do much book keeping since the array is created once every frame brand new. It does use up more memory tho (since technically, the same data gets stored twice), and I run through the cache misses of building and writing back this array twice per frame.
2) I can have a linked list where every element of the linked list can be 64 positions in a SOA format. This list would store the positions (the positions would not be stored in the monstars anymore), and although its not completely linear, the amount of cache misses on every jump in the linked list is small because we pack 64 positions into every element of the linked list. It has the benefit that adding new monstars becomes easy, if we run out of space, we just add an element to our linked list. It does suck for deleting monstars since once monstars die, they can die in a sparse way so we can end up with lots of elements in the linked list being arrays of 64 positions, but only 12 of those positions correspond to alive monstars, the rest are unused. So unless all 64 monstars that belong to a element of this list die, the element cannot be deleted. Of course, we can make the size smaller, like 16 but the smaller we make it, the less linear our array becomes so the simd optimizations become less effective. We also have to keep track of which parts of our 64 position array correspond to unused memory so that we can place data there if a new monstar gets created.
3) I can have a hashtable to store the position data in a SOA way. So if my position is 2d (x,y), then the id that my hash function spits our for a monstar would be the index in a x array for the x position data and a index in the y array for the y array position data. So using the hash table, I still get SOA benefits but the main problem instead comes from the fixed size nature of hash tables. Hashtables can't be resized so I'd have to make the hash table larger than the max number of monstars I expect to have in a level. This uses up extra memory but the worst part is that if the max amount of monstars in a level is 1000 but currently there are 60 monstars, then I lose all benefits of SOA and simd since there are so many unused positons stored sparsly in the hash table, that I'm just wasting most of the cache with unused memory.
The properties that 1) has are really useful since we have very little constant book keeping that we need to do to store our positions linearly, but I feel like 2), 3) or some other algorithm should be able to get more of the benefits of 1) with a little less book keeping. I know the kind of data I'm working with doesn't need some kind of crazy efficient system to solve my above problem, like 1) will probably provide enough of a speed up in my situation that it doesn't matter. I can also just make a grid data structure to not be looping through every monstar in my game for every query, but I'm interested to know how games go about solving this problem. I feel like there is a better way to do this, and even if its over engineering for my circumstance, I wanna know how other people solve this kind of problem. Thanks in advance.