In the Asteroid Panic-game, @pspeed detects collisions by going through all combinations of entities that have a position and collisionshape. Now, my question is, is this an effecient way of doing it ? In every update-cycle there’s a check for collisions. I guess it can work because its a contained environment, where the amount of combinations wont explode.
Im developing a tower defense/rts game, where we aim to have lots of enemies and lots of towers. To see if a tower has any valid targets, would the most efficient way be to use the GhostControl-framework to keep track of current targets?
I guess it wont be efficient to go through all combinations of tower/enemy as we might have 100 towers and 500 enemies, so 50000 combinations in each cycle. This could then divided across several threads. A more efficient tracking of the enemies (seeing as the towers are static in place) could probably be done (can’t think of any way at the top of my head).
I guess im asking if you have anyone has any pointers as to how you would go about checking for targets when you have many entities to do it with.
You won’t get around doing some check. Even bullet cannot perform any magic here… so a ghost control may not be helpful but it would do the work for you.
If you are really worried about the processing time for 50000 checks then you could break your world down into zones and only check things in adjacent zones. You could also not perform the checks every frame since it’s the AI making the decision… 60 decisions per second seems excessive. A zone approach may even be smarter than what bullet can do. You also could take advantage of cohesion based on the following facts:
a) enemies that don’t move don’t need a range update
b) enemies that were in range of one tower will probably be in range the next time you check.
c) enemies that are sufficiently close to a tower cannot move out of range in one frame
d) super-advanced, towers that are not in intersecting range of one another mean that an enemy in range of one tower is automatically not in range of the others.
On the other hand, if you are using a data driven design then 50000 checks may not even be so bad. You should test it but it’s just a handful of subtractions and a couple multiplies per check. JME is doing more than this per frame just to render your 600 objects.
if( mobPosition.distanceSquared(towerPosition) < towerRangeSquared )
3 subtractions, 3 multiplies, 2 adds, and a compare.
If your mob radii can be different then you would probably need to account for this in the “towerRangeSquared” calculation. That would be an extra add and multiply.
The more complicated ways trade simplicity for extra data book-keeping and complexity.
Note: while this probably could be multithreaded… I think you will end up trading one problem for another. Synchronizing across the threads could get tricky if not done right. And in the time it takes you to dispatch X number of entities to a separate thread you probably could have performed a distance check.
The simplest optimisation would be to keep a list of creeps per grid square. Then the towers just need to check those creeps that are in the squares it can reach. Also don’t forget that most towers acquire a target and then stay on that target - so you only need to check for a new target if there isn’t one already.
<cite>@zarch said:</cite>
The simplest optimisation would be to keep a list of creeps per grid square. Then the towers just need to check those creeps that are in the squares it can reach. Also don't forget that most towers acquire a target and then stay on that target - so you only need to check for a new target if there isn't one already.
When you say ‘grid square’ you mean if I used the terrain grid framework ? I’ll get around to that once our map has to grow so i’ll keep your suggestion in mind
<cite>@zarch said:</cite>
The simplest optimisation would be to keep a list of creeps per grid square. Then the towers just need to check those creeps that are in the squares it can reach. Also don't forget that most towers acquire a target and then stay on that target - so you only need to check for a new target if there isn't one already.
Just re-read your reply. The placement of towers in our world wont be using grids to align them.
No, i meant grid square as in most tower defence games are divided into a grid where you place towers/etc. For each grid keep a list of the occupants. For each tower keep a list of grids that are 1: all in range, 2: partially in range.
Then simply walk the list of everything where all in range…and walk the list of partially in range and do the range check.
@asser.fahrenholz said:
Allright. I guess the grid/zone scheme makes alot of sense. Although, I dont know if a specific gridsize is better than any other.
I’ll see if I can come up with ways of how to construct sensible zones in the game world.
Thanks
It would be a tuning thing… though I suspect somewhere around the minimum tower range is a good place to lock it in.
Still, it seems like in the worst case you could still end up doing 50000 checks (which I still think will not kill you if you are doing them right).
@guys If you really want to look in to promising solution (efficient but not simple), try google “spatial indexing” as seen in Map application:
The common techique is RTree (similar to Octree) but something more generic and suitable for “not only” grid base stuffs, and have sotiphicated algorimth adapted to solve “neibor nearest problem” …
For dynamic entities, like moving or add/remove able tree try “Q+RTree”
There also few open source java implementation for such techniques ready to use.
I’m using one to index my spatial in my MMORPG too.
As in my MMO, RTree, ScenGraph compromise with a No-SQL database, to store the relevant related informations, called InfoGraph.
The “big” idea:
SceneGraph is linked to
InfoGraph as its multi-graph, which store in graphDB (or else), can be extracted as
RTree to perform efficient data query and other algorimth.
So the compromise here leverage the efficience of those three a lot.
In fact, Neo4J soon released version is also packed with nice spatial indexing algorimth. I’m a fan of Neo4J so I recommended you who into MMO try that path. But you can also find various papers and open source implementation of spatial indexing “Graph” thingy.
As far as I remmember @pspeed also lead one No-SQL db, which also nice I guessed (not use it yet) . So may be he way better then me to offer solutions in this area.
That’s all kind of overkill when a simple grid will work fine.
Add a grid ID to the position component. Calculate it based on x,y when the position is created. Maybe like:
cellId = (int)(x/32) << 16 | (int)(y/32)
…or whatever. (That’s the approach that Mythruna uses for zones.) (The 32 part doesn’t matter much… probably err on the side of larger, though. I said smallest range before, I think… but largest range is probably better.)
Then just check the objects with positions with cellIds in range of the tower’s grid.
<cite>@pspeed said:</cite>
That's all kind of overkill when a simple grid will work fine.
Add a grid ID to the position component. Calculate it based on x,y when the position is created. Maybe like:
cellId = (int)(x/32) << 16 | (int)(y/32)
…or whatever. (That’s the approach that Mythruna uses for zones.) (The 32 part doesn’t matter much… probably err on the side of larger, though. I said smallest range before, I think… but largest range is probably better.)
Then just check the objects with positions with cellIds in range of the tower’s grid.
Clever solution. Then I just have to figure out which cellIdds are in range.
Thanks for all the replies. My game project is as much about learning as it is about getting a game developed in no time, so its great to hear about the various techniques used.
But if you have to query the entities every cycle, no, the data structures is build up to help you do spatial indexing and querying, especially nearest neighbor finding is very efficient.
Remember that grid (if not octree) is for 2D only. So, as topic’s owner what to ask about the way to detect in-range entites ( and a lot of theme) , I recommend researching a little bit to that direction.
@atomix said:
@pspeed :
Overkill , kind of. For small game.
…which is what this thread has always been about… but I’ll play along.
@atomix said:
But if you have to query the entities every cycle, no, the data structures is build up to help you do spatial indexing and querying, especially nearest neighbor finding is very efficient.
Remember that grid (if not octree) is for 2D only. So, as topic's owner what to ask about the way to detect in-range entites ( and a lot of theme) , I recommend researching a little bit to that direction. :p
Cheers,
Storage aside for a moment, a spatial index can never be faster than a fixed grid look-up. It’s impossible. There are many other good reasons to use spatial indexes but this is not one of them.
Fixed grid lookups are the standard by which all other indexing will be measured because they look up data in constant time. This is why I tend to be really critical of quad-tree approaches where there is a minimum cell size. A fixed grid is always more efficient. O(1) versus log time. (I’ve ranted about quad trees before… the same applies to oct-trees and it’s a separate discussion.)
In a database (which is not at all what we’re talking about here really), the indexing scheme may lend itself to one approach over another. But really, if your database can’t index an integer field as the “most efficient thing it does” then there is a problem.
Moreover, in a purely data-driver architecture (like an ES-based game) you will want to do everything you can to avoid lots of “nearest neighbor” style lookups in favor of some other scheme when possible. A data-driven design prefers approaches that iterate over all entities and perform minimal data operations. Avoid branching. Avoid extra inner loop lookups. Again, where possible. I think you end up embedding something similar to graph relationships in right into the ES. (Calling out to an external graph service also defeats the point.) Or you loop per active zone… (which would be cells in a sparse fixed grid)
So, if we were actually talking about a lot of objects (and we aren’t… 600 objects is a really small number of objects) then the approach might be completely different than anything we’ve talked about so far. I would need to have the problem reframed appropriately because scaling this one up doesn’t make sense… I could see an example with 5000000 units but the tower placement style starts to matter when you have one million of them.
I really haven’t thought about this problem much because usually worlds are sparse… but my guess:
When an entity moves (the move update loop) and that movement causes the cellId to change then the now defunct InRange entities are removed and new InRange entities are added to any tower entities in the same cell. This is like a graph relationship but ES friendly. This is the only thing that does “spatial style” queries… and they will happen relatively rarely. Only for entities that move from one cell to another.
A “targeting” loop is iterating over InRange entities as often as necessary for the AI. For each tower, it adjusts a “best target” component based on the current InRange entity it is evaluating.
The actual AI loop then uses the “best target” to shoot or whatever it wants to do.
This approach would scale to millions and millions of entities. With this data driven approach, loops can be split up, threaded, whatever… given the nature of this game one loop iteration doesn’t even technically have to finish before another one is using the results.
I try to imagine how I’d write algorithms that could operate iterating over a 1 billion record JDBC ResultSet. Technically, a good scalable ES design should support (in theory) splitting it up with different servers running different systems all accessing the same database.
Well, beforehand I hadn’t thought about it - but we would like to have some sort of nearest neighbour-mechanism in place, for example for effects that trigger on the nearest neighbour: Lightning that forks to nearest neighbours, Diseases that spreads, Shielding the nearest neighbours.
This is, at the moment, seperate from the in-range mechanism, which was the topic of this thread.
Would a combination of the two somehow defeat the purpose of having two (spatial indexing to find nearest neighbour, for spell effects, grids/zones to find available targets) ?
Small game, i know, so I also said in my first post, if you guys are into bigger problem and real 3d scheme, eg: a mmo 3d space shooter , yeah can be
<cite>@pspeed said:</cite>
A fixed grid is _always_ more efficient. O(1) versus log time
The data structure called RTree reduce the number of the Zones or the Nodes you have store the informations about partioning, just simple as that. So if your grid is NxN zones or nodes, RTree which is suitable for spare entities placement, should be less than NxN for sure!
What ever your algorimth is after the RTree is built and maintained, required less loop than the Grid.
You can speed up your indexing with some “numberic magic” by using integer with a Grid, I can not deny how efficient that is, but … a Graph is always efficient in term of travelling than flat tables. That’s what they explain in the introduction of Neo4J, Graph vs table.
And Graph dont against pure ES, or at least I don’t see it can not live well together, now I’m still trying to figure out… explain a little bit below.
You can also do any thing you like with your Entities outside of the the usage of System (the Processors), especially Read-only operation, or stricted operation. So, as far as you have operation in which contracted not to violated the next run of the ES processor over those touched components, you good to go.
<cite>@pspeed said:</cite>
.Moreover, in a purely data-driver architecture (like an ES-based game) you will want to do everything you can to avoid lots of "nearest neighbor" style lookups in favor of some other scheme when possible.
A data-driven design prefers approaches that iterate over all entities and perform minimal data operations. Avoid branching. Avoid extra inner loop lookups. Again, where possible. I think you end up embedding something similar to graph relationships in right into the ES.
(Calling out to an external graph service also defeats the point.) Or you loop per active zone… (which would be cells in a sparse fixed grid)
Ehr,… again we end up here! As far as I see, you tend to use the pure ES mechanism for every aspect of the game, which is good but not nessesary. Mark milions of entities with a component of CellId just to pretend their has relationship with each other is not the way to go in my oppinion.
You always can consider that your Entities is pure “data” outside of the the usage of System (the Processors) and just process it what way you like, as a graph with efficient travel, not a loop through flat table!!!
It can also not worth it but should be given a try in the design phase.
The point behind the “real” data driven approaches is to keep things cache-coherent. You load big arrays with structs of exactly what the loop needs. You avoid things that will break cache.
Java doesn’t easily support these pure data-driven approaches but often the algorithms turn out better if you think this way. So I try to think that way. Traversing a graph in the inner loop violates this principle in a big way so I try to figure out another way to see what the data-driven approach would look like.
I’m familiar with all of the tech you mention a few times over… that doesn’t make it data-driven. It may perform better or the same as a purely data-driven approach but it will never scale up as high. It a proper data-driven algorithm exists then it will always scale better… well, at least it will scale linearly, can be easily split, etc… There are lots of positive properties of a data-driven approach: when it can exist.
So, now off topic:
Spatial indexes (like R-Trees) are good at some things but really poor at things like dynamic data (moving ships, etc.) The insertion costs will eat up lots of time and the tree will become really fragmented to the point where every lookup is close to “worst case”. Also, while their best case may be similar to the constant time lookup of a sparse fixed grid the worst case is much much worse. I think the tree maintenance could easily overshadow any gains you get.
If you were making a space shooter, you could use the R-Tree for all of your static stuff but I’d strongly hesitate to use it for the ships and objects flying around. So you will still need something to track the individual objects. A sparse fixed grid can still work best here… especially if you can easily embed the larger grid cells into the same codes just by masking.
. So may be he way better then me to offer solutions in this area.