Clustering Working?

Latest implementation appears to be clustering correctly under given parameters:

– the number of ‘neighbours’ parameter appears to be one higher than expected, the images here are set at 4…

– the minimum distance between neighbours is 1.5f – this is expected as the search nodes are arranged in a 1.0f grid (save a few incorrectly placed tiles

– there does appear to be an issue with noise allocation in this implementation, a final check after the main DBSCAN loop is required to collect some missed nodes


This shot uses the same parameters but over a more complex area, again it appears to identify the search area correctly – including 3 separate clusters (each having their center shown by the blue sphere), and 10 ‘noise’ nodes.


If this currently implementation proves robust enough it will form the basis of the A.I.’s searching function:

– the DBSCAN will return two lists (clusters and noise)

– each will be given a weighted priority based on its size (always one for noise) and the distance of the A.I.’s path to its center

A new list is formed of destinations and weights – allowing the A.I. to search this area.

Larger (clusters) which are closer will have the strongest weighting.

The final thought is not simply for the A.I. to work through this list in order, but for it to choose randomly between them biased by their weighting – the largest nearest cluster would be the logical and most likely outcome, but there would be a small chance of another being chosen.

DBSCAN – Density-Based Spatial Clustering of Applications with Noise

I have been working implementing a suitable search method for nearly two weeks at this point. After rewriting and improving some of the overall area detection code, the DBSCAN implementation almost looks complete.


Initially noise (yellow) nodes were being identified correctly, but clustering was definitely wrong. I have used colours here to attempt to debug the numerous clusters being generated (the actual number was often twice what the colours show).


After a fair amount of heading banging and rewriting this latest implementation appears to be giving pretty decent results, with one dodgy looking noise node to the top of the single cluster, and a rather distant looking cluster member to the bottom.


Here the algorithm has (mostly) correctly identified two main clusters, with another dodgy looking noise. Those two rogue nodes up top are still an issue.


Initial Search Functionality


The tileset shown previously proved to have a few flaws and has been reworked slightly, but now initial functionality has been added towards implementing the required search algorithm.

Red gizmos represent those within a radius that have been highlighted to be searched, green gizmos represent those that can currently be ‘seen’ by the object. Currently this only represents the primary vision arc, and does not factor in obstacles (but that functionality has been implemented elsewhere).

Using the arc meshes for such detection proved troublesome/impossible as the project is actually in 3D rather than 2D. The work-around was:

// Get the normalised forward vector of the ‘entity’ object

Vector3 sight = forward.normalized;

// Get the normalised direction vector from the entity to this search node

Vector3 distanceVector = mSearchNodes[ i ].transform.position – center;
Vector3 direction = distanceVector.normalized;

// Dot product returns 1 (same direction), to 0 (90 degrees)
float cosine = Vector3.Dot( sight, direction );

// Use arc cos and convert from radians to degrees
float degrees = Mathf.Acos( cosine ) * Mathf.Rad2Deg;

The intended angles were about 40 degrees (primary) to 140 degrees (peripheral)  achieved if the returned value was less than half of either value.

An early version of the area system has also been implemented – checking if a search area is within the radius before doing the calculation above for each search node within. Currently this relies on collider checks (returning obstacles and walls as well), but does cut down on unnecessary checks.