| | | 1 | | using System; |
| | | 2 | | using System.Collections; |
| | | 3 | | using System.Collections.Generic; |
| | | 4 | | using UnityEngine; |
| | | 5 | | |
| | | 6 | | // The k-means clusterer class performs k-means clustering. |
| | | 7 | | public class KMeansClusterer : IClusterer { |
| | | 8 | | public const float Epsilon = 1e-3f; |
| | | 9 | | |
| | | 10 | | // Number of clusters. |
| | 0 | 11 | | private int _k = 0; |
| | | 12 | | |
| | | 13 | | // Maximum number of iterations. |
| | 0 | 14 | | private int _maxIterations = 20; |
| | | 15 | | |
| | 0 | 16 | | public KMeansClusterer(List<GameObject> objects, int k, int maxIterations = 20) : base(objects) { |
| | 0 | 17 | | _k = k; |
| | 0 | 18 | | _maxIterations = maxIterations; |
| | 0 | 19 | | } |
| | 0 | 20 | | public KMeansClusterer(List<Agent> agents, int k, int maxIterations = 20) : base(agents) { |
| | 0 | 21 | | _k = k; |
| | 0 | 22 | | _maxIterations = maxIterations; |
| | 0 | 23 | | } |
| | | 24 | | |
| | | 25 | | // Cluster the game objects. |
| | 0 | 26 | | public override void Cluster() { |
| | | 27 | | // Initialize the clusters with centroids located at random game objects. |
| | | 28 | | // Perform Fisher-Yates shuffling to find k random game objects. |
| | 0 | 29 | | System.Random random = new System.Random(); |
| | 0 | 30 | | for (int i = _objects.Count - 1; i >= _objects.Count - _k; --i) { |
| | 0 | 31 | | int j = random.Next(i + 1); |
| | 0 | 32 | | (_objects[i], _objects[j]) = (_objects[j], _objects[i]); |
| | 0 | 33 | | } |
| | 0 | 34 | | for (int i = _objects.Count - 1; i >= _objects.Count - _k; --i) { |
| | 0 | 35 | | _clusters.Add(new Cluster(_objects[i])); |
| | 0 | 36 | | } |
| | | 37 | | |
| | 0 | 38 | | bool converged = false; |
| | 0 | 39 | | int iteration = 0; |
| | 0 | 40 | | while (!converged && iteration < _maxIterations) { |
| | 0 | 41 | | AssignObjectsToCluster(); |
| | | 42 | | |
| | | 43 | | // Calculate the new clusters as the mean of all assigned game objects. |
| | 0 | 44 | | converged = true; |
| | 0 | 45 | | for (int clusterIndex = 0; clusterIndex < _clusters.Count; ++clusterIndex) { |
| | | 46 | | Cluster newCluster; |
| | 0 | 47 | | if (_clusters[clusterIndex].IsEmpty()) { |
| | 0 | 48 | | int objectIndex = random.Next(_objects.Count); |
| | 0 | 49 | | newCluster = new Cluster(_objects[objectIndex]); |
| | 0 | 50 | | } else { |
| | 0 | 51 | | newCluster = new Cluster(_clusters[clusterIndex].Centroid()); |
| | 0 | 52 | | } |
| | | 53 | | |
| | | 54 | | // Check whether the algorithm has converged by checking whether the cluster has moved. |
| | 0 | 55 | | if (Vector3.Distance(newCluster.Coordinates, _clusters[clusterIndex].Coordinates) > |
| | 0 | 56 | | Epsilon) { |
| | 0 | 57 | | converged = false; |
| | 0 | 58 | | } |
| | | 59 | | |
| | 0 | 60 | | _clusters[clusterIndex] = newCluster; |
| | 0 | 61 | | } |
| | | 62 | | |
| | 0 | 63 | | ++iteration; |
| | 0 | 64 | | } |
| | | 65 | | |
| | 0 | 66 | | AssignObjectsToCluster(); |
| | 0 | 67 | | } |
| | | 68 | | |
| | 0 | 69 | | private void AssignObjectsToCluster() { |
| | | 70 | | // Determine the closest centroid to each game object. |
| | 0 | 71 | | foreach (var obj in _objects) { |
| | 0 | 72 | | float minDistance = Mathf.Infinity; |
| | 0 | 73 | | int minIndex = -1; |
| | 0 | 74 | | for (int clusterIndex = 0; clusterIndex < _clusters.Count; ++clusterIndex) { |
| | 0 | 75 | | float distance = |
| | | 76 | | Vector3.Distance(_clusters[clusterIndex].Coordinates, obj.transform.position); |
| | 0 | 77 | | if (distance < minDistance) { |
| | 0 | 78 | | minDistance = distance; |
| | 0 | 79 | | minIndex = clusterIndex; |
| | 0 | 80 | | } |
| | 0 | 81 | | } |
| | 0 | 82 | | _clusters[minIndex].AddObject(obj); |
| | 0 | 83 | | } |
| | 0 | 84 | | } |
| | | 85 | | } |
| | | 86 | | |
| | | 87 | | // The constrained k-means clusterer class performs k-means clustering under size and radius |
| | | 88 | | // constraints. |
| | | 89 | | public class ConstrainedKMeansClusterer : ISizeAndRadiusConstrainedClusterer { |
| | | 90 | | public ConstrainedKMeansClusterer(List<GameObject> objects, int maxSize, float maxRadius) |
| | | 91 | | : base(objects, maxSize, maxRadius) {} |
| | | 92 | | |
| | | 93 | | // Cluster the game objects. |
| | | 94 | | public override void Cluster() { |
| | | 95 | | int numClusters = (int)Mathf.Ceil(_objects.Count / _maxSize); |
| | | 96 | | KMeansClusterer clusterer; |
| | | 97 | | while (true) { |
| | | 98 | | clusterer = new KMeansClusterer(_objects, numClusters); |
| | | 99 | | clusterer.Cluster(); |
| | | 100 | | |
| | | 101 | | // Count the number of over-populated and over-sized clusters. |
| | | 102 | | int numOverPopulatedClusters = 0; |
| | | 103 | | int numOverSizedClusters = 0; |
| | | 104 | | foreach (var cluster in clusterer.Clusters) { |
| | | 105 | | if (cluster.Size() > _maxSize) { |
| | | 106 | | ++numOverPopulatedClusters; |
| | | 107 | | } |
| | | 108 | | if (cluster.Radius() > _maxRadius) { |
| | | 109 | | ++numOverSizedClusters; |
| | | 110 | | } |
| | | 111 | | } |
| | | 112 | | |
| | | 113 | | // If all clusters satisfy the size and radius constraints, the algorithm has converged. |
| | | 114 | | if (numOverPopulatedClusters == 0 && numOverSizedClusters == 0) { |
| | | 115 | | break; |
| | | 116 | | } |
| | | 117 | | |
| | | 118 | | numClusters += |
| | | 119 | | (int)Mathf.Ceil(Mathf.Max(numOverPopulatedClusters, numOverSizedClusters) / 2.0f); |
| | | 120 | | } |
| | | 121 | | _clusters = new List<Cluster>(clusterer.Clusters); |
| | | 122 | | } |
| | | 123 | | } |