I'm working on a 2D game on the same vein as Tower Defense games but with a large world, seemless world.
The player(s) will have to react to attacks from different areas of the world and sometimes defend multiple fronts at once.
The problem I have is the idea of hundreds (potentially thousands) of "towers" trying to acquire targets. Also to avoid unnecessary checks when there are no targets within the maximum range. Line-of-Sight is NOT an issue, only whether the target fits within it's range. (some shoot directly forward, some can aim in a cone, etc)
I have been told that Quadtrees might allow me to optimize this system of target acquisition.
Is this true? Are there any articles I should read? Any pitfalls or alternatives?
Additionally, to prevent unnecessary checks, I had the idea that when a hostile unit enters the world, it "activates" all the defenses within a certain radius. And when there are no enemy units around, the defenses shut-down and go into a kind of "sleep" mode. Any thoughts on this?
Quadtrees for Tower Defense - Target Acquisition
Have you done any research yourself on Quadtrees to see if it would help you?
One idea, besides using quadtrees, is to allow the towers themselves create the "grids" for the enemies to register themselves within.
What I mean is, each tower gives a world location and radius to some list (RangeList). Each enemy, as they move, check if they are within any of the ranges in the list. If so, they notify the tower associated with that range it's within it (realize each enemy could be within multiple tower's range). Once in a range, the enemy would then check if it has exited the range, and remove itself if so.
I would guess, some kind of optimized spatial hashing would be better as far as performance, but it was just a thought.
One idea, besides using quadtrees, is to allow the towers themselves create the "grids" for the enemies to register themselves within.
What I mean is, each tower gives a world location and radius to some list (RangeList). Each enemy, as they move, check if they are within any of the ranges in the list. If so, they notify the tower associated with that range it's within it (realize each enemy could be within multiple tower's range). Once in a range, the enemy would then check if it has exited the range, and remove itself if so.
I would guess, some kind of optimized spatial hashing would be better as far as performance, but it was just a thought.
I'm working on a 2D game on the same vein as Tower Defense games but with a large world, seemless world.
The player(s) will have to react to attacks from different areas of the world and sometimes defend multiple fronts at once.
The problem I have is the idea of hundreds (potentially thousands) of "towers" trying to acquire targets. Also to avoid unnecessary checks when there are no targets within the maximum range. Line-of-Sight is NOT an issue, only whether the target fits within it's range. (some shoot directly forward, some can aim in a cone, etc)
I have been told that Quadtrees might allow me to optimize this system of target acquisition.
Is this true? Are there any articles I should read? Any pitfalls or alternatives?
Additionally, to prevent unnecessary checks, I had the idea that when a hostile unit enters the world, it "activates" all the defenses within a certain radius. And when there are no enemy units around, the defenses shut-down and go into a kind of "sleep" mode. Any thoughts on this?
You can combine both of your above ideas. In a quad tree, you'd often implement a function that takes a volume (usually a rectangle, but you could concievably have a circle or some swept shape), and returns all of the objects that are around that volume by returning the contents of all the nodes with which the circle intersects. So, an enemy can have its own volume (probably a circle with some detection radius), and it might query the tree with that circle to get the list of nearby towers. Then, you can tell those towers to do their thing (is the enemy within range? can we shoot it?...). This would probably give you the efficiency you need.
If you have a dynamic, node-based implementation of the tree, the recursive query function is very simple.
Check this out: http://www.kyleschou...ource-included/
Author
Wow, thanks guys!
This is some really useful stuff.
Beer, you've got me thinking and I'll certainly share anything I come up with.
Shooter, I'm reading through that article and I'm hoping to find time in the next couple of days (full-time job after all!) to write a quick proof-of-concept. I'll then post that on here and hopefully you guys can let me know if I'm doing it right. I'll throw it together using GLUT, love that library.
This is some really useful stuff.
Beer, you've got me thinking and I'll certainly share anything I come up with.
Shooter, I'm reading through that article and I'm hoping to find time in the next couple of days (full-time job after all!) to write a quick proof-of-concept. I'll then post that on here and hopefully you guys can let me know if I'm doing it right. I'll throw it together using GLUT, love that library.
Did you already implement the straight forward "every tower checks squared distance to each enemy, applies sqrt and checks if in range" method? It's brute force, but so trivial and fast that it can compensate for a lot of overhead you get with "clever" methods. I'd suggest doing both and comparing the results, even if it's just to find out at which point the more complicated method starts paying off (ex. frustum culling terrain chunks with a naive quadtree -using pointers- was slower than brute force testing for up to 4000-5000 chunks).
Also, updating the tree might be much faster if you don't use it for the moving enemies, but the static towers. A primitive method without a tree can be sorting your enemies by their x coordinate, so towers will only have to check a much smaller subset.
Bottom line: smart and clever algorithms are great to drastically reduce workload by avoiding lots of expensive operations. However, your operation (basically
is the opposite of expensive, making it important to consider the overhead of other methods, find the break-even point and most of all, decide if the performance increase is worth the headache and potential bugs of a more complicated algorithm.
Another thing to keep in mind in the days of up to 8 cores: how well can you execute it in parallel? Though I'd expect that with your setup, any algorithm can be run independently for each tower, so you can process your tower in (not quite) an nth of the time (with n being the number of cores). As long as you stay away from globals or static variables in your functions. Just grab Intels tbb library and enjoy how easy to use that parallel_for can be.
Also, updating the tree might be much faster if you don't use it for the moving enemies, but the static towers. A primitive method without a tree can be sorting your enemies by their x coordinate, so towers will only have to check a much smaller subset.
Bottom line: smart and clever algorithms are great to drastically reduce workload by avoiding lots of expensive operations. However, your operation (basically
const float enemyDistance = dot(tower.pos, enemy.pos);
if (enemyDistance < previousMinDistance)
previousMinDistance = enemyDistance;
is the opposite of expensive, making it important to consider the overhead of other methods, find the break-even point and most of all, decide if the performance increase is worth the headache and potential bugs of a more complicated algorithm.
Another thing to keep in mind in the days of up to 8 cores: how well can you execute it in parallel? Though I'd expect that with your setup, any algorithm can be run independently for each tower, so you can process your tower in (not quite) an nth of the time (with n being the number of cores). As long as you stay away from globals or static variables in your functions. Just grab Intels tbb library and enjoy how easy to use that parallel_for can be.
Author
Indeed, it did occur to me that using quadtrees for static entities is more optimum than using it for moving entities. As such, perhaps a combined method will be what I end up with. It would be easy for me to subdivide/update the quadtree whenever a tower is placed or destroyed and would be very inexpensive.
On the same train of thought, it occured to me that using a Quadtree for high-speed projectile collision wouldn't make much sense (correct me if I'm wrong?) as I'd spend more time updating the tree than I would spend checking for collisions.
As for mobile enemies, it is entirely possible for them to check against the tower quadtree and inform all towers within n range that they are targettable. Then once a list of towers was formed, they could proceed to acquire targets.
As far as parallel programming is concerned, I'm afraid I'm a newbie in that field but I understand the sentiment. Simple systems can be implemented better and safer.
Thanks for your insight.
On the same train of thought, it occured to me that using a Quadtree for high-speed projectile collision wouldn't make much sense (correct me if I'm wrong?) as I'd spend more time updating the tree than I would spend checking for collisions.
As for mobile enemies, it is entirely possible for them to check against the tower quadtree and inform all towers within n range that they are targettable. Then once a list of towers was formed, they could proceed to acquire targets.
As far as parallel programming is concerned, I'm afraid I'm a newbie in that field but I understand the sentiment. Simple systems can be implemented better and safer.
Thanks for your insight.
There exists a certain data structure called sphere tree. For 2D, it uses embedded circles. For this particular case it would be considered optimal.
Unfortunately, balancing is slightly trickier and I never found an out-of-box implementation, mostly because it's often thrown together with R-trees and those get more attention.
Sphere tree implementation is available in one of earlier game programming gems books.
Unfortunately, balancing is slightly trickier and I never found an out-of-box implementation, mostly because it's often thrown together with R-trees and those get more attention.
Sphere tree implementation is available in one of earlier game programming gems books.
Another thing to keep in mind in the days of up to 8 cores: how well can you execute it in parallel?[/quote]
Unless it will be released as AAA title on Steam, the number of cores will be 2. If it doesn't run acceptably there, it won't matter. 8 cores is very rare, very few people have dual CPU machines. On i7, there are 4 cores with 4 hyperthreads which is far from 8. Construction of QT is serial anyway, even when evaluated on GPU, they are often constructed on CPU.
Unless it will be released as AAA title on Steam, the number of cores will be 2. If it doesn't run acceptably there, it won't matter. 8 cores is very rare, very few people have dual CPU machines. On i7, there are 4 cores with 4 hyperthreads which is far from 8. Construction of QT is serial anyway, even when evaluated on GPU, they are often constructed on CPU.
I wasn't suggesting aiming at 8 cores, but to consider that hardware has for now hit the limit on how fast a single core can get and will mostly just add more and more cores. Even with 2 cores it means you can process some of the hard work in parallel and in (not quite) half the time. Replacing a
for (all towers) select target or for (all bullets) update
with
parallel_for(all towers) select target
is almost no work at all compared to adding complex structures.
As a firm believer in "don't make it more complex than it has to be", I wouldn't throw trees at my problem until a) it really is too slow and b) there is no simple optimization (like sorting enemies by their x coordinate). And even then I'd make sure to keep the old version for comparison and find the break-even point. Finding that a tree starts pulling its own weight at >1000 enemies and then never having more than 200 around...
After all, keep in mind that a player must be able to keep track of all the towers and enemies AND a level designer must still be able to create interesting maps. Going all megalomaniac might be tempting to the programmer, but not necessarily to anyone else.
I also don't see any point in doing collision detection for projectils, until you seriously want towers to be able to miss. All these games I've seen so far never miss, so nothing but the distance of the bullet and its target matters (or even just the precalculated "time til impact").
Author
I also don't see any point in doing collision detection for projectils, until you seriously want towers to be able to miss. All these games I've seen so far never miss, so nothing but the distance of the bullet and its target matters (or even just the precalculated "time til impact").
Yea, mine aren't going to miss but the towers in 'Dungeon Defenders' can.
Just a quick reply as I'm at work. I understand the don't fix it if it isn't broke argument, but I really want to establish my limits now so that I can incorporate that into the design. Sure, it'd never be a problem if this was a single-player game but I don't intend it to be. I wanna see what kind of limits I can push in terms of scale, i.e. How many max players a server will be able to handle with it computing all the logic server-side.
Obviously, that's a long-term goal but I like to be well-researched in the meantime. I'm going to write multiple algorithms anyway and compare them. I plan to post my code and results on here once I've done a prototype.
How many max players a server will be able to handle with it computing all the logic server-side.[/quote]
Same amount as the slowest machine of all players can handle.
Limitation comes from networking. Updating full state of hundreds or thousands of entities in something so dynamic isn't possible. Instead, simulation will need to run by passing input events and advancing simulation deterministically on each machine independently.
See Age of Empires networking, which had thousands of units active at any time, 15 years ago over a dial-up.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
