<commit_before>#!/usr/bin/env python
# DungeonMap - the Model for our dungeon generator
#
# Represented as a collection of Regions and Connections.
# Each Region owns a single polygon that does not overlap any other Regions.
# Each Connection straddles the border between two Regions.
# The DungeonMap handles collision detection between Regions and so forth.
# A Region may have one or more Decorations which are items placed on the map
# that do not have any direct implications for the map geometry.
#
# In order to ensure reproducibility (i.e., using the same random seed will
# always generate the same dungeon map), the DungeonMap can use sets internally
# but all access through get_foo() functions must return consistently sorted
# lists.

import logging
import math
import re
from itertools import count

import aagen.geometry
from aagen.geometry import to_string
from aagen.direction import Direction

log = logging.getLogger(__name__)

class SortedSet:
    """A container class for a set of objects that is always ordered by
    object's self-declared ID. Needed for consistent random dungeon generation.
    """

    def __init__(self, contents=None):
        self.set = set()
        if contents is not None:
            for item in contents:
                self.add(item)


    def __len__(self):
        return len(self.set)


    def __contains__(self, item):
        return item in self.set


    def __iter__(self):
        return iter(sorted(self.set, key=lambda item: item.id))


    def __repr__(self):
        return "<SortedSet: {0}>".format([item for item in self])


    def add(self, item):
        assert hasattr(item, 'id')
        self.set.add(item)


    def remove(self, item):
        self.set.remove(item)


class DungeonMap:
    """Master model class. Stores a collection of Regions and Connections"""

    _ids = count(0)

    def __init__(self):
        """Initialize a new empty DungeonMap"""
        self.regions = SortedSet()
        self.connections = SortedSet()
        self.decorations = SortedSet()
        self.conglomerate_polygon = None
        self.id = self._ids.next()
        log.debug("Initialized {0}".format(self))


    def __repr__(self):
        return ("<DungeonMap {4}: {0} regions, "
                "{1} connections ({2} incomplete), "
                "{5} decorations, "
                "total {3} square feet>"
                .format(len(self.regions), len(self.connections),
                        len(self.get_incomplete_connections()),
                        (self.conglomerate_polygon.area if
                         self.conglomerate_polygon is not None else 0),
                        self.id,
                        len(self.decorations)))


    def __getattr__(self, name):
        if name == "bounds":
            return self.get_bounds()
        raise AttributeError("'{0}' object has no attribute '{1}'"
                             .format(self.__class__, name))


    def object_at(self, (x, y)):
        """Get the Connection or Region at the clicked location"""
        point = aagen.geometry.point(x, y)
        for dec in self.decorations:
            if dec.polygon.contains(point):
                return dec
        for conn in self.connections:
            if conn.polygon.contains(point):
                return conn
        for reg in self.regions:
            if reg.polygon.contains(point):
                return reg
        return self


    def get_bounds(self):
        """Returns (x0, y0, x1, y1) describing the extent of the map"""
        if self.conglomerate_polygon is None:
            log.warning("{0}: no conglomerate polygon?".format(self))
            return (0, 0, 0, 0)
        return self.conglomerate_polygon.bounds


    def flush(self):
        """Mark all recently added elements as permanent parts of the map"""
        for region in self.regions:
            region.tentative = False
        for conn in self.connections:
            conn.tentative = False
        for decoration in self.decorations:
            decoration.tentative = False


    def add_map_elements(self, elements):
        for elem in elements:
            if isinstance(elem, Region):
                self.add_region(elem)
            elif isinstance(elem, Connection):
                self.add_connection(elem)
            elif isinstance(elem, Decoration):
                self.add_decoration(elem)
            else:
                raise RuntimeError("Not sure how to add {0} to the map!"
                                   .format(elem))


    def add_region(self, region):
        assert isinstance(region, Region)
        if not region in self.regions:
            log.info("Adding Region ({0}) to {1}".format(region, self))
            self.regions.add(region)
            self.refresh_conglomerate()
            for decoration in region.decorations:
                self.add_decoration(decoration)
            for connection in region.connections:
                self.add_connection(connection)
            # Look for any existing connections to fix up
            for connection in self.get_incomplete_connections():
                log.debug("Checking {0} for intersection with {1}"
                         .format(connection, region))
                if (connection.polygon.intersects(region.polygon) and
                    not connection.polygon.touches(region.polygon)):
                    # TODO fix up any funky edges
                    connection.add_region(region)
                    self.add_connection(connection)

    def refresh_conglomerate(self):
        """Regenerate the conglomerate polygon.
        """
        polygons = set([r.polygon for r in self.regions])
        self.conglomerate_polygon = aagen.geometry.union(polygons)


    def add_decoration(self, dec):
        assert isinstance(dec, Decoration)
        if not dec in self.decorations:
            log.info("Adding {0} to {1}".format(dec, self))
            self.decorations.add(dec)


    def add_connection(self, connection):
        assert isinstance(connection, Connection)
        if not connection in self.connections:
            log.info("Adding {0} to {1}".format(connection, self))
            self.connections.add(connection)
            for region in connection.regions:
                self.add_region(region)
            # Look for any existing regions to fix up
            for region in self.regions:
                log.debug("Checking {0} for intersection with {1}"
                          .format(connection, region))
                if (region.polygon.intersection(connection.line)
                    .equals(connection.line) or
                    (connection.polygon.intersects(region.polygon) and
                     not connection.polygon.touches(region.polygon))):
                    # TODO fix up any funky edges
                    region.add_connection(connection)


    def remove_connection(self, connection):
        assert isinstance(connection, Connection)
        if connection in self.connections:
            log.info("Removing {0} from {1}".format(connection, self))
            self.connections.remove(connection)
            for region in connection.regions:
                region.remove_connection(connection)


    def get_incomplete_connections(self):
        return [item for item in self.connections if item.is_incomplete()]


    def find_adjacency_options(self, old_shape, new_shape, direction):
        """Given the two shapes and a direction, figure out how to position
        new shape so that it is adjacent to old shape in the given direction.

        Returns ((x0, y0), (pos_x, pos_y), (shift_x, shift_y)) where:
        (x0, y0) is the initial offset to apply to new_shape
        (pos_x, pos_y) is successive offsets to apply to new_shape to determine
            candidate positions for intersection (if desired)
        (shift_x, shift_y) is offsets to apply to each position to adjust the
            intersection

        An example:

        Given:
           OO           NNNN
           OO     ,     NNNN    ,     direction (1, 0)
           OO
        will return (x0, y0) to apply to the new shape so that:
         NNNN
         NNNN      is the starting position, and:
           OO      (pos_x, pos_y) will be ---->
           OO      (shift_x, shift_y) will be |
           OO                                 V

        If new were narrower than old, the starting position would instead be:
           NN
           NN
           OOOO
           OOOO

        Clear as mud?
        """

        assert isinstance(direction, Direction)

        (old_x0, old_y0, old_x1, old_y1) = old_shape.bounds
        (new_x0, new_y0, new_x1, new_y1) = new_shape.bounds
        (dir_x, dir_y) = direction

        if dir_y < 0 and dir_x == 0: # North
            # Position new so its south edge touches the north edge of old
            # and its east edge overlaps the west edge of old
            (x0, y0) = (min(old_x0 - new_x0, old_x1 - new_x1),
                        old_y0 - new_y1)
            # Snap to grid
            (x0, y0) = (10 * math.ceil(x0 / 10),
                        10 * math.ceil(y0 / 10))
            # Try possible positions every 10' to the east
            (pos_x, pos_y) = (10, 0)
            # For each position, if it doesn't intersect, shift it 10' south
            # until it does
            (shift_x, shift_y) = (0, 10)
        elif dir_x < 0 and dir_y == 0: # west
            # Position new so its east edge touches the west edge of old
            # and its south edge overlaps the north edge of old
            (x0, y0) = (old_x0 - new_x1,
                        min(old_y0 - new_y0, old_y1 - new_y1))
            # Snap to grid
            (x0, y0) = (10 * math.ceil(x0 / 10),
                        10 * math.ceil(y0 / 10))
            # Try possible positions every 10' to the south
            (pos_x, pos_y) = (0, 10)
            # For each position, if it doesn't intersect, shift it 10' east
            # until it does
            (shift_x, shift_y) = (10, 0)
        elif dir_y > 0 and dir_x == 0: # south
            # Position new so its north edge touches the south edge of old
            # and its east edge overlaps the west edge of old
            (x0, y0) = (min(old_x0 - new_x0, old_x1 - new_x1),
                        old_y1 - new_y0)
            # Snap to grid
            (x0, y0) = (10 * math.ceil(x0 / 10),
                        10 * math.floor(y0 / 10))
            # Try possible positions every 10' to the east
            (pos_x, pos_y) = (10, 0)
            # For each position, if it doesn't intersect, shift it 10' north
            # until it does
            (shift_x, shift_y) = (0, -10)
        elif dir_x > 0 and dir_y == 0: # east
            # Position new so its west edge touches the east edge of old
            # and its south edge overlaps the north edge of old
            (x0, y0) = (old_x1 - new_x0,
                        min(old_y0 - new_y0, old_y1 - new_y1))
            # Snap to grid
            (x0, y0) = (10 * math.floor(x0 / 10),
                        10 * math.ceil(y0 / 10))
            # Try possible positions every 10' to the south
            (pos_x, pos_y) = (0, 10)
            # For each position, if it doesn't intersect, shift it 10' west
            # until it does
            (shift_x, shift_y) = (-10, 0)
        else:
            raise ValueError("Only cardinal directions are supported - not {0}"
                             .format(direction))

        # Snap initial delta to grid
        log.info("Rounding off ({x}, {y})".format(x=x0, y=y0))
        (x0, y0) = (round(x0, -1), round(y0, -1))

        log.info("Base offset is ({x}, {y})".format(x=x0, y=y0))
        return ((x0, y0), (pos_x, pos_y), (shift_x, shift_y))


    def find_options_for_connection(self, width, region, direction,
                                    new_only=True):
        """Find valid positional options (if any) for placing a Connection
        of the given size along the given edge of the given region).
        If new_only is set then only positions leading to new (unmapped) space
        will be considered as valid.
        Returns a list of CandidateConnections."""

        log.info("Finding options for a connection (width {0}) adjacent to "
                 "{1} in {2}".format(width, region, direction))

        assert isinstance(region, Region) and isinstance(direction, Direction)

        segments = aagen.geometry.find_edge_segments(region.polygon, width,
                                                     direction)
        candidates = []
        for segment in segments:
            log.debug("Evaluating candidate segment: {0}"
                          .format(to_string(segment)))
            valid = True
            if aagen.geometry.grid_aligned(segment, direction):
                conn_poly = aagen.geometry.polygon()
            else:
                (segment, conn_poly) = aagen.geometry.loft_to_grid(
                    segment, direction, width)
                log.debug("segment: {0}, conn_poly: {1}"
                          .format(to_string(segment), to_string(conn_poly)))

            # Make sure it doesn't intersect any existing conns
            for conn in region.connections:
                if aagen.geometry.intersect(conn.line, segment).length > 0:
                    log.debug("Conflicts with existing conn {0}"
                              .format(conn))
                    valid = False
                    break
            if valid and new_only:
                # Make sure it doesn't intersect any other regions
                for test_region in self.regions:
                    if test_region == region:
                        continue
                    if aagen.geometry.intersect(test_region.polygon,
                                                segment).length > 0:
                        log.debug("Conflicts with existing region {0}"
                                  .format(test_region))
                        valid = False
                        break
            if valid:
                candidates.append(CandidateConnection(segment, conn_poly,
                                                      direction, region))

        log.info("{0} candidate positions were identified after inspecting "
                 "{1} possibilities"
                 .format(len(candidates), len(segments)))
        return candidates


    def find_options_for_region(self, shape_list, connection):
        """Find valid positional options (if any) for placing one of the
        given shapes adjacent to the given Connection.
        Returns a list of Candidate_Region objects"""<commit_msg>Check conn_poly for intersection against existing conglomerate_polygon. Fixes #40<commit_after>#!/usr/bin/env python
# DungeonMap - the Model for our dungeon generator
#
# Represented as a collection of Regions and Connections.
# Each Region owns a single polygon that does not overlap any other Regions.
# Each Connection straddles the border between two Regions.
# The DungeonMap handles collision detection between Regions and so forth.
# A Region may have one or more Decorations which are items placed on the map
# that do not have any direct implications for the map geometry.
#
# In order to ensure reproducibility (i.e., using the same random seed will
# always generate the same dungeon map), the DungeonMap can use sets internally
# but all access through get_foo() functions must return consistently sorted
# lists.

import logging
import math
import re
from itertools import count

import aagen.geometry
from aagen.geometry import to_string
from aagen.direction import Direction

log = logging.getLogger(__name__)

class SortedSet:
    """A container class for a set of objects that is always ordered by
    object's self-declared ID. Needed for consistent random dungeon generation.
    """

    def __init__(self, contents=None):
        self.set = set()
        if contents is not None:
            for item in contents:
                self.add(item)


    def __len__(self):
        return len(self.set)


    def __contains__(self, item):
        return item in self.set


    def __iter__(self):
        return iter(sorted(self.set, key=lambda item: item.id))


    def __repr__(self):
        return "<SortedSet: {0}>".format([item for item in self])


    def add(self, item):
        assert hasattr(item, 'id')
        self.set.add(item)


    def remove(self, item):
        self.set.remove(item)


class DungeonMap:
    """Master model class. Stores a collection of Regions and Connections"""

    _ids = count(0)

    def __init__(self):
        """Initialize a new empty DungeonMap"""
        self.regions = SortedSet()
        self.connections = SortedSet()
        self.decorations = SortedSet()
        self.conglomerate_polygon = None
        self.id = self._ids.next()
        log.debug("Initialized {0}".format(self))


    def __repr__(self):
        return ("<DungeonMap {4}: {0} regions, "
                "{1} connections ({2} incomplete), "
                "{5} decorations, "
                "total {3} square feet>"
                .format(len(self.regions), len(self.connections),
                        len(self.get_incomplete_connections()),
                        (self.conglomerate_polygon.area if
                         self.conglomerate_polygon is not None else 0),
                        self.id,
                        len(self.decorations)))


    def __getattr__(self, name):
        if name == "bounds":
            return self.get_bounds()
        raise AttributeError("'{0}' object has no attribute '{1}'"
                             .format(self.__class__, name))


    def object_at(self, (x, y)):
        """Get the Connection or Region at the clicked location"""
        point = aagen.geometry.point(x, y)
        for dec in self.decorations:
            if dec.polygon.contains(point):
                return dec
        for conn in self.connections:
            if conn.polygon.contains(point):
                return conn
        for reg in self.regions:
            if reg.polygon.contains(point):
                return reg
        return self


    def get_bounds(self):
        """Returns (x0, y0, x1, y1) describing the extent of the map"""
        if self.conglomerate_polygon is None:
            log.warning("{0}: no conglomerate polygon?".format(self))
            return (0, 0, 0, 0)
        return self.conglomerate_polygon.bounds


    def flush(self):
        """Mark all recently added elements as permanent parts of the map"""
        for region in self.regions:
            region.tentative = False
        for conn in self.connections:
            conn.tentative = False
        for decoration in self.decorations:
            decoration.tentative = False


    def add_map_elements(self, elements):
        for elem in elements:
            if isinstance(elem, Region):
                self.add_region(elem)
            elif isinstance(elem, Connection):
                self.add_connection(elem)
            elif isinstance(elem, Decoration):
                self.add_decoration(elem)
            else:
                raise RuntimeError("Not sure how to add {0} to the map!"
                                   .format(elem))


    def add_region(self, region):
        assert isinstance(region, Region)
        if not region in self.regions:
            log.info("Adding Region ({0}) to {1}".format(region, self))
            self.regions.add(region)
            self.refresh_conglomerate()
            for decoration in region.decorations:
                self.add_decoration(decoration)
            for connection in region.connections:
                self.add_connection(connection)
            # Look for any existing connections to fix up
            for connection in self.get_incomplete_connections():
                log.debug("Checking {0} for intersection with {1}"
                         .format(connection, region))
                if (connection.polygon.intersects(region.polygon) and
                    not connection.polygon.touches(region.polygon)):
                    # TODO fix up any funky edges
                    connection.add_region(region)
                    self.add_connection(connection)

    def refresh_conglomerate(self):
        """Regenerate the conglomerate polygon.
        """
        polygons = set([r.polygon for r in self.regions])
        self.conglomerate_polygon = aagen.geometry.union(polygons)


    def add_decoration(self, dec):
        assert isinstance(dec, Decoration)
        if not dec in self.decorations:
            log.info("Adding {0} to {1}".format(dec, self))
            self.decorations.add(dec)


    def add_connection(self, connection):
        assert isinstance(connection, Connection)
        if not connection in self.connections:
            log.info("Adding {0} to {1}".format(connection, self))
            self.connections.add(connection)
            for region in connection.regions:
                self.add_region(region)
            # Look for any existing regions to fix up
            for region in self.regions:
                log.debug("Checking {0} for intersection with {1}"
                          .format(connection, region))
                if (region.polygon.intersection(connection.line)
                    .equals(connection.line) or
                    (connection.polygon.intersects(region.polygon) and
                     not connection.polygon.touches(region.polygon))):
                    # TODO fix up any funky edges
                    region.add_connection(connection)


    def remove_connection(self, connection):
        assert isinstance(connection, Connection)
        if connection in self.connections:
            log.info("Removing {0} from {1}".format(connection, self))
            self.connections.remove(connection)
            for region in connection.regions:
                region.remove_connection(connection)


    def get_incomplete_connections(self):
        return [item for item in self.connections if item.is_incomplete()]


    def find_adjacency_options(self, old_shape, new_shape, direction):
        """Given the two shapes and a direction, figure out how to position
        new shape so that it is adjacent to old shape in the given direction.

        Returns ((x0, y0), (pos_x, pos_y), (shift_x, shift_y)) where:
        (x0, y0) is the initial offset to apply to new_shape
        (pos_x, pos_y) is successive offsets to apply to new_shape to determine
            candidate positions for intersection (if desired)
        (shift_x, shift_y) is offsets to apply to each position to adjust the
            intersection

        An example:

        Given:
           OO           NNNN
           OO     ,     NNNN    ,     direction (1, 0)
           OO
        will return (x0, y0) to apply to the new shape so that:
         NNNN
         NNNN      is the starting position, and:
           OO      (pos_x, pos_y) will be ---->
           OO      (shift_x, shift_y) will be |
           OO                                 V

        If new were narrower than old, the starting position would instead be:
           NN
           NN
           OOOO
           OOOO

        Clear as mud?
        """

        assert isinstance(direction, Direction)

        (old_x0, old_y0, old_x1, old_y1) = old_shape.bounds
        (new_x0, new_y0, new_x1, new_y1) = new_shape.bounds
        (dir_x, dir_y) = direction

        if dir_y < 0 and dir_x == 0: # North
            # Position new so its south edge touches the north edge of old
            # and its east edge overlaps the west edge of old
            (x0, y0) = (min(old_x0 - new_x0, old_x1 - new_x1),
                        old_y0 - new_y1)
            # Snap to grid
            (x0, y0) = (10 * math.ceil(x0 / 10),
                        10 * math.ceil(y0 / 10))
            # Try possible positions every 10' to the east
            (pos_x, pos_y) = (10, 0)
            # For each position, if it doesn't intersect, shift it 10' south
            # until it does
            (shift_x, shift_y) = (0, 10)
        elif dir_x < 0 and dir_y == 0: # west
            # Position new so its east edge touches the west edge of old
            # and its south edge overlaps the north edge of old
            (x0, y0) = (old_x0 - new_x1,
                        min(old_y0 - new_y0, old_y1 - new_y1))
            # Snap to grid
            (x0, y0) = (10 * math.ceil(x0 / 10),
                        10 * math.ceil(y0 / 10))
            # Try possible positions every 10' to the south
            (pos_x, pos_y) = (0, 10)
            # For each position, if it doesn't intersect, shift it 10' east
            # until it does
            (shift_x, shift_y) = (10, 0)
        elif dir_y > 0 and dir_x == 0: # south
            # Position new so its north edge touches the south edge of old
            # and its east edge overlaps the west edge of old
            (x0, y0) = (min(old_x0 - new_x0, old_x1 - new_x1),
                        old_y1 - new_y0)
            # Snap to grid
            (x0, y0) = (10 * math.ceil(x0 / 10),
                        10 * math.floor(y0 / 10))
            # Try possible positions every 10' to the east
            (pos_x, pos_y) = (10, 0)
            # For each position, if it doesn't intersect, shift it 10' north
            # until it does
            (shift_x, shift_y) = (0, -10)
        elif dir_x > 0 and dir_y == 0: # east
            # Position new so its west edge touches the east edge of old
            # and its south edge overlaps the north edge of old
            (x0, y0) = (old_x1 - new_x0,
                        min(old_y0 - new_y0, old_y1 - new_y1))
            # Snap to grid
            (x0, y0) = (10 * math.floor(x0 / 10),
                        10 * math.ceil(y0 / 10))
            # Try possible positions every 10' to the south
            (pos_x, pos_y) = (0, 10)
            # For each position, if it doesn't intersect, shift it 10' west
            # until it does
            (shift_x, shift_y) = (-10, 0)
        else:
            raise ValueError("Only cardinal directions are supported - not {0}"
                             .format(direction))

        # Snap initial delta to grid
        log.info("Rounding off ({x}, {y})".format(x=x0, y=y0))
        (x0, y0) = (round(x0, -1), round(y0, -1))

        log.info("Base offset is ({x}, {y})".format(x=x0, y=y0))
        return ((x0, y0), (pos_x, pos_y), (shift_x, shift_y))


    def find_options_for_connection(self, width, region, direction,
                                    new_only=True):
        """Find valid positional options (if any) for placing a Connection
        of the given size along the given edge of the given region).
        If new_only is set then only positions leading to new (unmapped) space
        will be considered as valid.
        Returns a list of CandidateConnections."""

        log.info("Finding options for a connection (width {0}) adjacent to "
                 "{1} in {2}".format(width, region, direction))

        assert isinstance(region, Region) and isinstance(direction, Direction)

        segments = aagen.geometry.find_edge_segments(region.polygon, width,
                                                     direction)
        candidates = []
        for segment in segments:
            log.debug("Evaluating candidate segment: {0}"
                          .format(to_string(segment)))
            valid = True
            if aagen.geometry.grid_aligned(segment, direction):
                conn_poly = aagen.geometry.polygon()
            else:
                (segment, conn_poly) = aagen.geometry.loft_to_grid(
                    segment, direction, width)
                log.debug("segment: {0}, conn_poly: {1}"
                          .format(to_string(segment), to_string(conn_poly)))

            # Make sure the extension doesn't overflow into existing space,
            # as can happen when there is a diagonal passage nearby:
            if aagen.geometry.intersect(conn_poly,
                                        self.conglomerate_polygon).area > 0:
                valid = False

            if valid:
                # Make sure it doesn't intersect any existing conns
                for conn in region.connections:
                    if aagen.geometry.intersect(conn.line, segment).length > 0:
                        log.debug("Conflicts with existing conn {0}"
                                  .format(conn))
                        valid = False
                        break
            if valid and new_only:
                # Make sure it doesn't intersect any other regions
                for test_region in self.regions:
                    if test_region == region:
                        continue
                    if aagen.geometry.intersect(test_region.polygon,
                                                segment).length > 0:
                        log.debug("Conflicts with existing region {0}"
                                  .format(test_region))
                        valid = False
                        break
            if valid:
                candidates.append(CandidateConnection(segment, conn_poly,
                                                      direction, region))

        log.info("{0} candidate positions were identified after inspecting "
                 "{1} possibilities"
                 .format(len(candidates), len(segments)))
        return candidates


    def find_options_for_region(self, shape_list, connection):
        """Find valid positional options (if any) for placing one of the
        given shapes adjacent to the given Connection.
        Returns a list of Candidate_Region objects"""
{'fraction_non_alphanumeric': 0.08495812395309883, 'fraction_numerical': 0.013701842546063651, 'mean_word_length': 1.7276133040935673, 'pattern_counts': {'":': 2, '<': 11, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 24, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2699055', 'n_tokens_mistral': 8328, 'n_tokens_neox': 7762, 'n_words': 2668}