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.

A Look at DBSCAN Clustering

Finished implementing unit clustering based on the DBSCAN algorithm with parameters set:
threshold=3, and radius=6. Units with more than 3 neighbors in a radius of 6 tiles will be considered a cluster. The following screenshots will illustrate the mechanics of this algorithm.

Probe scout left, encounters clustered SCVS among mineral field.

An example of an early game scouting action. The scout is assigned to group 0, no cluster, since it is alone. The SCVs are in sufficient density to be assigned group 2.

Two SCVs and a Marine guard this ramp.

I have the parameters set so that it takes three units in close proximity to form a cluster. These units at the ramp are assigned group 15; separate from the mining cluster back at the Command Center.

A Protoss army on the move.

All the units in the army manage to get clustered into the same group, along with the Probe that is just passing through. The algorithm reacts instantaneously to unit movement since I have it run every frame. This unfortunately slows debug mode down to a crawl on a quad core AMD Phenom II 955 @ 3.4GHz, but performance is fine compiled in release mode. I have an idea to speed performance, but if continuous processing is required, this algorithm should be run in a separate thread.

A group of stragglers behind the army.

Catching up to the rest of the army.

This sequence shows the proximity needed to be considered part of the same cluster, 6 tiles as configured.

A construction SCV forms bridge between tanks left and workers right.

One shortcoming of the DBSCAN algorithm is that it sometimes allows a single unit to form a bridge, linking two clusters together. In the above shot, the tanks on the left should have their own group, but thanks to the SCV bridge in the center, are considered part of the same cluster as the mining SCVs on the right.