DBSCAN Drawbacks

After testing, it appears that the DBSCAN algorithm has a number of disadvantages that must be overcome in order for it to be used as a group detector for a BWAPI bot. These are what I consider to be the four major drawbacks in no particular order:


1. Instability

The assigned group IDs will often jump around, when groups merge and split, following no particular pattern. Grouping results depend entirely on unit traversal order, so when a small group splits off from a larger one,  sometimes the algorithm counter-intuitively assigns the original ID to the smaller group, rather than keeping it with the larger one. 

This instability means that we cannot simply store a groupID somewhere and come back later to check on our group. The ID could refer to the same group, but it might also point somewhere else, or become unused.

2. Performance
As I mentioned earlier, DBSCAN is too slow to run in debug mode, forcing testing to take place in release mode. The only solution appears to be running it in its own thread, which complicates matters with synchronization. It won't be easy to divide the workload among several frames, as the algorithm wants to be run all in one shot. Speed also degrades rapidly with the number of units in the game, even if most of them are not moving.

3. Inaccuracy
Uses a single radius value for all units; but not all units are equal. Longer-range units should have a larger associative area around them representing the ability to project power, while melee units would have a reduced radius. Unfortunately, the algorithm uses a single radius for all units, and this must be modified to fix the issue.

4. Association
Assume I grab the nearest unit and find out it belongs to group 5. How then can I access all units of group 5? I must iterate through entire set of units. This is probably the most minor of flaws, but creating additional associative sets for faster access is difficult due to ID instability.

Another Approach: Associative Network Clustering
If each unit were to have its own radius of influence, and keep track of the other units within, this would form a graph. We then have the option of using existing graph algorithms on the data. Also, the graph can be updated locally, no need to recompute the whole thing if a single vertex changes; just update its links. This approach allows easy association, higher accuracy, and greater performance, but I have yet to figure out how to get stable IDs.