Find point clusters during ramp search faster
Use flood fill algorithm to only compare nearby points
from typing import Tuple, Set, FrozenSet, Sequence, Generator
+from collections import deque
from copy import deepcopy
import itertools
@@ -169,33 +170,53 @@ class GameInfo(object):
def _find_groups(self, points: Set[Point2], minimum_points_per_group: int=8, max_distance_between_points: int=2) -> List[Set[Point2]]:
""" From a set/list of points, this function will try to group points together """
- foundGroups = []
- currentGroup = set()
- newlyAdded = set()
- pointsPool = set(points)
-
- while pointsPool or currentGroup:
- if not currentGroup:
- randomPoint = pointsPool.pop()
- currentGroup.add(randomPoint)
- newlyAdded.add(randomPoint)
-
- newlyAddedOld = newlyAdded
- newlyAdded = set()
- for p1 in newlyAddedOld:
- # create copy as we change set size during iteration
- for p2 in pointsPool.copy():
- if abs(p1.x - p2.x) + abs(p1.y - p2.y) <= max_distance_between_points:
- currentGroup.add(p2)
- newlyAdded.add(p2)
- pointsPool.discard(p2)
-
- # Check if all connected points were found
- if not newlyAdded:
- # Add to group if number of points reached threshold - discard group if not enough points
+ """ Paint clusters of points in rectangular map using flood fill algorithm. """
+ NOT_INTERESTED = -2
+ NOT_COLORED_YET = -1
+ currentColor: int = NOT_COLORED_YET
+ picture: List[List[int]] = [[NOT_INTERESTED
+ for j in range (self.pathing_grid.width)]
+ for i in range (self.pathing_grid.height)]
+
+ def paint (pt: Point2) -> None:
+ picture[pt.y][pt.x] = currentColor
+
+ nearby: Set[Point2] = set ()
+ for dx in range (-max_distance_between_points, max_distance_between_points + 1):
+ for dy in range (-max_distance_between_points, max_distance_between_points + 1):
+ if abs (dx) + abs (dy) <= max_distance_between_points:
+ nearby.add (Point2 ((dx, dy)))
+
+ for point in points:
+ paint (point)
+
+ remaining: Set[Point2] = set (points)
+ queue: Deque[Point2] = deque ()
+ foundGroups: List[Set[Point2]] = []
+ while remaining:
+ currentGroup: Set[Point2] = set ()
+ if not queue:
+ currentColor += 1
+ start = remaining.pop ()
+ paint (start)
+ queue.append (start)
+ currentGroup.add (start)
+ while queue:
+ base: Point2 = queue.popleft ()
+ for offset in nearby:
+ px, py = base.x + offset.x, base.y + offset.y
+ if px < 0 or py < 0 or px >= self.pathing_grid.width or py >= self.pathing_grid.height:
+ continue
+ if picture[py][px] != NOT_COLORED_YET:
+ continue
+ point: Point2 = Point2 ((px, py))
+ remaining.remove (point)
+ paint (point)
+ queue.append (point)
+ currentGroup.add (point)
if len (currentGroup) >= minimum_points_per_group:
foundGroups.append (currentGroup)
- currentGroup = set()
+
""" Returns groups of points as list
[{p1, p2, p3}, {p4, p5, p6, p7, p8}]
"""
