Calin said:
JoeJ was saying in a previous thread that when you have a RTS with more than 100 units you need to start thinking about optimizations when it comes collision detection. I’m making a calculus 100 x 100 units is 10.000 collision detection checks. You can cut that in half with well thought looping ( if you avoid to collide same units twice). Colliding two units means 12 comparisons between 2 ints. 5000 collisions means 60000 comparisons. So that is still acceptable. If you use a collision optimization tree each unit collides with up to 8 more units so that’s 800 collision detection checks.
You count collision checks, but then you multiply this by a constant of n comparisons. Notice those comparisons are irrelevant, because they are just a constant factor applied to both options equally, the brute force approach, and the alternative of using some acceleration structure.
More importantly, to see what actually matters, we need to observe how costs of our algorithms change, as N changes.
In your example you pick some number which you assume to be practical, but you should think of a table like this:
N brute force acceleration structure
10 100 10*8
100 10000 100*8
1000 1000000 1000*8
This is the number of collision checks, roughly as you have listed them, but for 3 examples of N (number of units).
Likely you knew it already, but it shows how quickly the brute force cost grows, actually O(N^2).
Contrary, the cost with the AS increases linearly, just like N itself, so O(N).
Notice we ignore some things here: We can half the number for BF; building and looking up / traversing has some cost too; nobody knows where you have pulled out that number of 8 out from.
But nothing of this matters, because it's ‘constant costs’. Similar to your redundant information of integer comparisons, which also is a constant cost.
To get the time complexity of an algorithm, we go a step further: I will now remove the 8 from the table, because it's a constant factor to the cost of the entire column / algorithm. And i have already skipped the division by 2 on the brute force column anyway.
Now you may ask: Is this fair and correct? How can we compare two algorithms costs if we remove factors affecting those costs?
The answer is: We do not compare the algorithms to see which is faster for a given number of N. It looks like that, but that's not what we do. If we want that, we would do something different, more on this soon.
No, we only want to see how the costs of any algorithm change as the size of the problem changes. Because this is all we can generally say about the costs of some algorithm, besides memory requirements.
To find the real costs you actually ask for, you simply try it out.
Run those examples, using your code and your hardware, and measure the time this and that takes.
You need a simple way to measure time accurately. I use this outdated and ugly code. (Modern C++ has std::chrono now, so this should be easier now, but actually isn't. At least it's cross platform.)
#include <mutex>
#include <algorithm>
#include <stdio.h>
#include <windows.h>
#include <direct.h>
#include <Mmsystem.h>
#include "SystemTools.h"
uint64_t SystemTools::GetTimeNS ()
{
static LARGE_INTEGER ticksPerSec;
static bool initialized = false;
if (!initialized)
{
QueryPerformanceFrequency(&ticksPerSec);
initialized = true;
}
LARGE_INTEGER now;
QueryPerformanceCounter(&now);
return (uint64_t) ((1e9 * now.QuadPart) / ticksPerSec.QuadPart);
}
std::string SystemTools::GetDurationStringAndRestart(uint64_t& time)
{
uint64_t time2 = GetTimeNS ();
uint64_t diff = time2 - time;
time = time2;
int ns = int(diff / 1000);
int ms = int(diff / 1000000);
int seconds = int(diff / 1000000000);
int minutes = seconds / 60;
std::string str = "";
if (minutes >= 1) str += std::to_string(minutes) + " min. ";
seconds %= 60;
if (seconds >= 1) str += std::to_string(seconds % 60) + " sec. ";
if (seconds < 10) str += std::to_string(ms % 1000) + " ms. ";
if (seconds < 1) str += std::to_string(ns % 1000) + " ns. ";
return str;
}
Then i do something like this to measure runtime:
uint64_t time = SystemTools::GetTimeNS();
DoCollisionTestWithLotsOfUnits();
ImGui::Text("Collision test done after %s\n", SystemTools::GetDurationStringAndRestart(time).c_str());
That's what you need to do. Measure the time to see if using a simple grid for acceleration structure is faster than brute force.
It's the only way to figure out that magic number of ‘100 units’ this JoeJ guy has claimed, although it can be actually anything.
(The number of 100 was a rough guess taken from the 2D collisions demo i did here somewhere, but i could not really measure it. Runtime is too short and measurement is too noisy. For realtime workloads you need to make an average of many measurements, which i did not do.)
Calin said:
I’m wondering if using Dijkstra is not too much for a 40 x 40 nodes map. Sorting 1600 nodes to pick a node to visit means 160000 comparisons for a web of 100 nodes visited.( that’s almost three times more than colliding 100 units) Am I way off with my numbers? I’m just trying to understand what is reasonable.
I'm confused. But i would say Dijkstra visits each node only once at most, so the cost for a 40x40 map is (≥ 1600) times something you have to measure as well.
Regarding A-star, yes it's faster for ‘one source, one target’ scenarios. Much faster if obstacles are sparse, not faster if we are in some labyrinth.
For ‘one source, many targets’ Dijsktra is still efficient. But idk if that's relevant for games.
