It occurs to me that there are a few definitions of “data driven programming” running around. I’m trying to find the source papers for the definition that I’m using.
Ahah… my bad. “Data Oriented Design”
Google brings up a ton of articles and I cannot properly choose one. I’ll pick one at random that looks half-way decent: http://gamesfromwithin.com/data-oriented-design
…worth googling on your own, I suppose. I was first exposed to the idea in the Game Programming Gems 2 book. (chapter 15) When I was reading it, it occurred to me that it is like the parent of Entity Component Systems. So it stuck with me even if the proper term didn’t.
And apparently I am not the first one to confuse the terms as it happens quite often it seems: http://stackoverflow.com/questions/1641580/what-is-data-oriented-design
@pspeed :
I also learnt things from component base solutions that I still can not adapt yet. Sorry!
In despite of its clean design, it’s not an universe key for every problem, Nearest neighbor search problem is one and will always be problematic in this kind of pure data driven that you mentioned.
About R-Tree, yeah, it’s also not a superb magical alien tech or something… It’s just usable in a few use case. I don’t really into complain about how scale it is, but a few Map application use it, and the apps also widely use, such as Google map, or OpenGIS.
Dynamic spatial indexing can not be achieve with R-Tree without modifying. http://pdf.aminer.org/000/279/092/efficient_indexing_of_moving_objects_using_time_based_partitioning_with.pdf <=Take a look.
And the cost of building the initial tree of milions object is un-affordable to use in run time! It’s just like that well crafted techs we use to boost the dynamic lighting in a 3d scene, scene partioning and culling… etc. That’s it, precomputed and stored the heavy computing on design phase.
So, I can not agree more that ES and Hash, cached cellId component or what ever used to mark the connection between entities is… “suitable” and “just work” in 90% of usecases and games that we needs. But still it had its missing piece, Graph in other hand is more familiar with OOP and I can not pretend that it’s bad in this case 
I’m not prepared to do more research about thing im not going to use very soon, so may be next time when I got more idea and knowledge in my head. Thank you for the explaination and the papers.
Well, the interesting thing about this exercise is it showed that in the large scale data-oriented approach, the “nearest neighbor” is not really a check by the tower ever frame. We end up dynamically creating a “range graph” that is tower centric and maintaining it whenever the unit moves.
However, because we did in the ES instead of a graph, we can easily iterate over all of those relationships… not just the ones for a particular node. For example, neo4j will return the relationships for a node in roughly constant time… but last I checked there is no way to return all relationships of a given type. In fact, for many graph databases this would a difficult query. (Difficult to answer efficiently if it answers it at all.)
It’s kind of its own game-specific (read: game optimized) form of spatial index geared directly to the problem. It just doesn’t look that way. It looks just like useful game data.
By attempting to keep the data as compact and addressable as possible, we see that the real spatial queries are relatively rarely necessary anyway. And they happen only under certain unit movement conditions. Furthermore, we open the possibility up of picking a tower target not just based on nearest but based on whatever other unit criteria we choose. For example, maybe a flame thrower tower will pick ice units first or whatever. We get that essentially for free.
Other side benefits, these range entities could be used for other things by different systems.
The only unnecessary cost of this approach is that it checks units that may not actually be in range of the tower. These would be the units that are within “cell range” but not actually in “tower range”. A small price to pay, I think.
These are the kinds of reasons I like to look at problems this way.
Very well explained. Though, im still wondering if ES solves the nearest neighbour problem for moving entities ?
I understand that we can pick a target based on a set of priorities, which coincides well with the topology of my game: We want to allow the player to micromanage each tower (newest target / strongest targets / weakest etc. etc.)
But how does ES solve the nearest neighbour problem - for effects that specifically trigger on the nearest neighbour (diseases / electricity that forks etc): Would it still be a loop over all entities checking the distance to each ? For towers that need this effect, the cost is no more than you described, but for creeps that move about - would scaling be a problem ?
@asser.fahrenholz said: Very well explained. Though, im still wondering if ES solves the nearest neighbour problem for moving entities ?I understand that we can pick a target based on a set of priorities, which coincides well with the topology of my game: We want to allow the player to micromanage each tower (newest target / strongest targets / weakest etc. etc.)
But how does ES solve the nearest neighbour problem - for effects that specifically trigger on the nearest neighbour (diseases / electricity that forks etc): Would it still be a loop over all entities checking the distance to each ? For towers that need this effect, the cost is no more than you described, but for creeps that move about - would scaling be a problem ?
An ES will not solve the problem of spatial queries. But you can use your game data to limit the scope of your spatial queries as I’ve described with the grids/zones.
By checking only the entities in a particular zone or surrounding zones then you’ve already cut the size down considerably. The nature of what can fit in a zone will limit the amount of entities you have to search. These are broad-phase style bounding sphere distance checks… they are very fast. As I said before, even 600 entities is not really a lot in this case.
The grid helps limit the checks to just those nearby. It’s hard to get faster than this because other methods will just move the expense elsewhere and/or don’t work well with dynamic data. Maintaining these data structures (or pre-sorting the data) easily dwarfs the cost of hundreds of bounding sphere distance checks… where as the grid approach is basically free. It’s also simpler… which means less error-prone to implement.
Given that none of these queries are performed particularly often, I think it’s the best approach. And if you are performing these queries once per frame then there is something else wrong with the design… or at least something that can be optimized. Short of collision detection (which really must be run often) it seems like most use-cases would be infrequent in comparison.
Thanks. This thread has helped me tons. I’ll probably be back with questions in other areas 