• Create Account

### #ActualTrienco

Posted 14 February 2012 - 11:38 PM

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
   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.

### #1Trienco

Posted 14 February 2012 - 11:25 PM

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
   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.

PARTNERS