KMeansClustering.calcPathBased() causes precompute to time out and throws ArithmeticException

[ToB213]

Summary

calcPathBased() has two bugs that together make precompute unusable:

1. O(R·N·K·N) complexity — comparePathDistance() runs an uncached BFS for every entity × center × iteration, causing precompute to exceed the time limit on standard maps.
2. ArithmeticException: / by zero — when a cluster receives no entities during iteration, clusterEntitiesList.get(index).size() returns 0 and the subsequent division crashes the thread.

Both bugs were confirmed on the RSL 2025 kobe1 map with the default configuration.

Bug 1: Excessive BFS calls in the assignment step

Inside the K-means iteration loop, each entity is assigned to its nearest center via:

// calcPathBased(), line ~336
StandardEntity tmp = this.getNearEntity(this.worldInfo, this.centerList, entity);

This calls comparePathDistance() for each candidate center, which in turn calls shortestPath() (BFS, O(N)) twice per comparison with no caching:

private StandardEntity comparePathDistance(...) {
    double firstDistance  = getPathDistance(worldInfo, shortestPath(target.getID(), first.getID()));
    double secondDistance = getPathDistance(worldInfo, shortestPath(target.getID(), second.getID()));
    return (firstDistance < secondDistance ? first : second);
}

Total complexity: O(R·N·K·N)

Symbol	Value (RSL 2025 kobe1, default config)
N	2,359 (road + building entities)
K	30 (agents per type)
R	7 (repeatPrecompute default)

With these values: approximately 2.3 × 10⁹ BFS node accesses per precompute call.

Measured impact: precompute did not complete within 6 minutes and had to be killed.

Bug 2: Division by zero when a cluster becomes empty

In the center update step, if a cluster receives no entities, the code divides by zero:

// calcPathBased(), line ~347
int centerX = sumX / clusterEntitiesList.get(index).size(); // size() == 0 → crash
int centerY = sumY / clusterEntitiesList.get(index).size();

This throws ArithmeticException and kills the agent thread before precompute data is written.

Observed stack trace:

Exception in thread "Thread-29" java.lang.ArithmeticException: / by zero
    at adf.impl.module.algorithm.KMeansClustering.calcPathBased(KMeansClustering.java:347)
    at adf.impl.module.algorithm.KMeansClustering.precompute(KMeansClustering.java:107)
    ...

Note: the same isEmpty() guard is also missing in calcStandard() at the corresponding location.

Proposed Fix

For Bug 1: Replace the per-entity BFS with multi-source Dijkstra, which expands from all K centers simultaneously and assigns each entity to the nearest center in a single O(N log N) pass. This also eliminates the empty cluster problem (Bug 2) for connected graphs, since every reachable entity is guaranteed to be assigned.

This requires two changes:

1. Replace initShortestPath (unweighted adjacency graph) with initWeightedGraph (edge-weighted adjacency graph). Edge weight between adjacent areas A and B is defined to match getPathDistance():

   cost(A→B) = dist(A.center, midpoint of A-B edge)
             + dist(B.center, midpoint of B-A edge)
   

2. Replace the per-entity getNearEntity() call with assignByMultiSourceDijkstra():

   private Map<EntityID, Integer> assignByMultiSourceDijkstra(List<StandardEntity> centers) {
       PriorityQueue<double[]> pq = new PriorityQueue<>(Comparator.comparingDouble(a -> a[0]));
       // seed all K centers at distance 0
       for (int i = 0; i < centers.size(); i++) { ... }
       // Dijkstra expansion
       while (!pq.isEmpty()) { ... }
       return assignment; // EntityID → clusterIndex
   }

For Bug 2 (defensive fix): Add an isEmpty() guard before the division in both calcPathBased() and calcStandard() to handle any remaining edge cases:

List<StandardEntity> clusterEntities = this.clusterEntitiesList.get(index);
if (clusterEntities.isEmpty()) continue;
int centerX = sumX / clusterEntities.size();
int centerY = sumY / clusterEntities.size();

Measured Results (RSL 2025 kobe1 map, K=30)

• Before: some agents threw ArithmeticException immediately; the remaining agents did not complete precompute and were manually killed after 6 minutes.
• After: precompute completed successfully — BUILD SUCCESSFUL in 49 seconds.

Complexity reduces from O(R·N·K·N) to O(R·N·log N).

Additional Notes

• The two getNearEntity() overloads used exclusively in calcPathBased() (getNearEntity(list, entity) using comparePathDistance, and getNearEntity(list, x, y) using compareLineDistance) become dead code after the fix and can be removed.
• initShortestPath() and shortestPathGraph are no longer needed. shortestPath() (used by getNearAgent()) can be updated to use weightedGraph.keySet() as the adjacency list.
• LazyMap, HashSet, and Set imports can be removed.

Environment

• Repository: adf-core-java
• File: src/main/java/adf/impl/module/algorithm/KMeansClustering.java
• Map: RSL 2025 kobe1 (https://cdn.robocup.org/rsim/public/competitions/2025-RSL/info/agent/results/kobe1/index.html)