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.