1"""
   2- Authors: Peter Mawhorter
   3- Consulted: Nissi Awosanya, Kitty Boakye
   4- Date: 2023-6-8
   5- Purpose: Types for representing open-world explorations.
   6
   7Key types in this file are:
   8
   9- `MetricSpace` (TODO): Represents a variable-dimensional coordinate system
  10    within which locations can be identified by coordinates.
  11- `FeatureGraph` (TODO): A graph-based representation of one or more
  12    navigable physical, virtual, or even abstract spaces, each composed
  13    of nodes, paths, edges, regions, landmarks, and/or affordances. It
  14    supports a variety of edge types between nodes, such as "contains"
  15    and "touches." Each conceptually separate space is marked as a
  16    domain.
  17- `FeatureDecision` (TODO): Represents a single decision made about what
  18    action to take next. Includes information on position(s) in a
  19    `FeatureGraph` (and possibly also in a `MetricSpace`) and about which
  20    features are relevant to the decision, plus what the chosen course
  21    of action was (as a `FeatureAction`).
  22- `GeographicExploration` (TODO): Represents a single agent's
  23    exploration progress through a geographic space. Includes zero or
  24    more `MetricSpace`s, a single list of `FeatureGraph`s representing
  25    the evolution of a single feature graph through discrete points in
  26    time, and a single list of `FeatureDecision`s representing the
  27    decisions made about what to do next at each of those time points.
  28    Supports cross-reference information between these data structures,
  29    and also links to multimedia resources such as images, videos, or
  30    audio files which can in turn be cross-referenced to metric spaces
  31    (and thence to the other data structures).
  32"""
  33
  34from typing import (
  35    Optional, Union, List, Tuple, Set, Dict
  36)
  37
  38import networkx as nx  # type: ignore[import]
  39
  40from . import base
  41
  42
  43#--------------#
  44# Main Classes #
  45#--------------#
  46
  47class MissingFeatureError(KeyError):
  48    """
  49    An error raised when an invalid feature ID or specifier is
  50    provided.
  51    """
  52    pass
  53
  54
  55class AmbiguousFeatureSpecifierError(KeyError):
  56    """
  57    An error raised when an ambiguous feature specifier is provided.
  58    Note that if a feature specifier simply doesn't match anything, you
  59    will get a `MissingFeatureError` instead.
  60    """
  61    pass
  62
  63
  64class FeatureGraph(nx.MultiDiGraph):
  65    """
  66    TODO
  67    A graph-based representation of a navigable physical, virtual, or
  68    even abstract space, composed of the features such as nodes, paths,
  69    and regions (see `FeatureType` for the full list of feature types).
  70
  71    These elements are arranged in a variety of relationships such as
  72    'contains' or 'touches' (see `FeatureRelationshipType` for the full
  73    list).
  74    """
  75    def __init__(self, mainDomain: base.Domain = "main"):
  76        """
  77        Creates an empty `FeatureGraph`.
  78        """
  79        self.domains: List[base.Domain] = [mainDomain]
  80        self.nextID: base.FeatureID = 0
  81        super().__init__()
  82
  83    def _register(self) -> base.FeatureID:
  84        """
  85        Returns the next ID to use and increments the ID counter.
  86        """
  87        result = self.nextID
  88        self.nextID += 1
  89        return result
  90
  91    def findChainedRelations(
  92        self,
  93        root: base.FeatureID,
  94        relation: base.FeatureRelationshipType,
  95        names: List[base.Feature]
  96    ) -> Optional[List[base.FeatureID]]:
  97        """
  98        Looks for a chain of features whose names match the given list
  99        of feature names, starting from the feature with the specified
 100        ID (whose name must match the first name in the list). Each
 101        feature in the chain must be connected to the next by an edge of
 102        the given relationship type. Returns `None` if it cannot find
 103        such a chain. If there are multiple possible chains, returns the
 104        chain with ties broken towards features with lower IDs, starting
 105        from the front of the chain.
 106
 107        For example:
 108
 109        >>> fg = FeatureGraph.example('chasm')
 110        >>> root = fg.resolveFeature('east')
 111        >>> fg.findChainedRelations(root, 'within', ['east', 'main'])
 112        [1, 0]
 113        >>> root = fg.resolveFeature('downstairs')
 114        >>> fg.findChainedRelations(
 115        ...    root,
 116        ...    'within',
 117        ...    ['downstairs', 'house', 'west', 'main']
 118        ... )
 119        [17, 15, 2, 0]
 120
 121        # TODO: Test with ambiguity!
 122        """
 123        if self.nodes[root]['name'] != names[0]:
 124            return None
 125        elif len(names) == 1:
 126            return [root]
 127        elif len(names) == 0:
 128            raise RuntimeError(
 129                "Ran out of names to match in findChainedRelations."
 130            )
 131
 132        assert len(names) > 1
 133        remaining = names[1:]
 134
 135        neighbors = sorted(self.relations(root, relation))
 136        if len(neighbors) == 0:
 137            return None
 138        else:
 139            for neighbor in neighbors:
 140                candidate = self.findChainedRelations(
 141                    neighbor,
 142                    relation,
 143                    remaining
 144                )
 145                if candidate is not None:
 146                    return [root] + candidate
 147
 148            # Couldn't find a single candidate via any neighbor
 149            return None
 150
 151    def featureName(self, fID: base.FeatureID) -> base.Feature:
 152        """
 153        Returns the name for a feature, given its ID.
 154        """
 155        return self.nodes[fID]['name']
 156
 157    def resolveFeature(
 158        self,
 159        spec: base.AnyFeatureSpecifier
 160    ) -> base.FeatureID:
 161        """
 162        Given a `FeatureSpecifier`, returns the feature ID for the
 163        feature that it specifies, or raises an
 164        `AmbiguousFeatureSpecifierError` if the specifier is ambiguous.
 165
 166        Cannot handle strings with multiple parts; use
 167        `parsing.ParseFormat.parseFeatureSpecifier` first if you need to
 168        do that.
 169
 170        For example:
 171
 172        >>> fg = FeatureGraph.example('chasm')
 173        >>> import exploration.parsing
 174        >>> pf = exploration.parsing.ParseFormat()
 175        >>> fg.resolveFeature('main')
 176        0
 177        >>> fg.resolveFeature('east')
 178        1
 179        >>> fg.resolveFeature('west')
 180        2
 181        >>> fg.resolveFeature(pf.parseFeatureSpecifier('main::west'))
 182        2
 183        >>> fg.resolveFeature(pf.parseFeatureSpecifier('main//main::west'))
 184        2
 185        >>> fg.resolveFeature(
 186        ...     base.FeatureSpecifier('main', ['main'], 'west', None)
 187        ... )
 188        2
 189        >>> fg.resolveFeature(base.FeatureSpecifier(None, [], 2, None))
 190        2
 191        >>> fg.resolveFeature(2)
 192        2
 193        >>> fg.resolveFeature(base.FeatureSpecifier(None, [], 'chasm', None))
 194        3
 195        >>> fg.resolveFeature(pf.parseFeatureSpecifier("main//main::chasm"))
 196        3
 197        >>> fg.resolveFeature(pf.parseFeatureSpecifier("main//east::chasm"))
 198        Traceback (most recent call last):
 199        ...
 200        exploration.geographic.MissingFeatureError...
 201        >>> fg.resolveFeature("chasmm")
 202        Traceback (most recent call last):
 203        ...
 204        exploration.geographic.MissingFeatureError...
 205        >>> fg.resolveFeature("house")
 206        Traceback (most recent call last):
 207        ...
 208        exploration.geographic.AmbiguousFeatureSpecifierError...
 209        >>> fg.resolveFeature(pf.parseFeatureSpecifier("east::house"))
 210        6
 211        >>> fg.resolveFeature(pf.parseFeatureSpecifier("west::house"))
 212        15
 213        >>> fg.resolveFeature(pf.parseFeatureSpecifier("east::bridgePath"))
 214        13
 215        >>> fg.resolveFeature(pf.parseFeatureSpecifier("west::bridgePath"))
 216        14
 217        >>> fg.resolveFeature(pf.parseFeatureSpecifier("crossroads"))
 218        8
 219        >>> fg.resolveFeature(pf.parseFeatureSpecifier("east::crossroads"))
 220        8
 221        >>> fg.resolveFeature(pf.parseFeatureSpecifier("west::crossroads"))
 222        Traceback (most recent call last):
 223        ...
 224        exploration.geographic.MissingFeatureError...
 225        >>> fg.resolveFeature(pf.parseFeatureSpecifier("main::crossroads"))
 226        Traceback (most recent call last):
 227        ...
 228        exploration.geographic.MissingFeatureError...
 229        >>> fg.resolveFeature(
 230        ...     pf.parseFeatureSpecifier("main::east::crossroads")
 231        ... )
 232        8
 233        >>> fg.resolveFeature(pf.parseFeatureSpecifier("house::basement"))
 234        16
 235        >>> fg.resolveFeature(pf.parseFeatureSpecifier("house::openChest"))
 236        7
 237        >>> fg.resolveFeature(pf.parseFeatureSpecifier("house::stairs"))
 238        19
 239        >>> fg2 = FeatureGraph.example('intercom')
 240        >>> fg2.resolveFeature("intercom")
 241        7
 242        >>> # Direct contains
 243        >>> fg2.resolveFeature(pf.parseFeatureSpecifier("kitchen::intercom"))
 244        7
 245        >>> # Also direct
 246        >>> fg2.resolveFeature(pf.parseFeatureSpecifier("inside::intercom"))
 247        7
 248        >>> # Both
 249        >>> fg2.resolveFeature(
 250        ...     pf.parseFeatureSpecifier("inside::kitchen::intercom")
 251        ... )
 252        7
 253        >>> # Indirect
 254        >>> fg2.resolveFeature(pf.parseFeatureSpecifier("house::intercom"))
 255        Traceback (most recent call last):
 256        ...
 257        exploration.geographic.MissingFeatureError...
 258
 259        TODO: Test case with ambiguous parents in a lineage!
 260        """
 261        spec = base.normalizeFeatureSpecifier(spec)
 262        # If the feature specifier specifies an ID, return that:
 263        if isinstance(spec.feature, base.FeatureID):
 264            return spec.feature
 265
 266        # Otherwise find all features with matching names:
 267        matches = [
 268            node
 269            for node in self
 270            if self.nodes[node]['name'] == spec.feature
 271        ]
 272
 273        if len(matches) == 0:
 274            raise MissingFeatureError(
 275                f"There is no feature named '{spec.feature}'."
 276            )
 277
 278        namesToMatch = [spec.feature] + list(reversed(spec.within))
 279        remaining: List[base.FeatureID] = [
 280            match
 281            for match in matches
 282            if (
 283                self.findChainedRelations(match, 'within', namesToMatch)
 284         is not None
 285            )
 286        ]
 287
 288        if len(remaining) == 1:
 289            return remaining[0]
 290        else:
 291            matchDesc = ', '.join(
 292                f"'{name}'" for name in reversed(spec.within)
 293            )
 294            if len(remaining) == 0:
 295                raise MissingFeatureError(
 296                    f"There is/are {len(matches)} feature(s) named"
 297                    f" '{spec.feature}' but none of them are/it isn't"
 298                    f" within the series of features: {matchDesc}"
 299                    f"\nf:{spec.feature}\nntm:{namesToMatch}\n"
 300                    f"mt:{matches}\nrm:{remaining}"
 301                )
 302            else: # Must be more than one
 303                raise AmbiguousFeatureSpecifierError(
 304                    f"There is/are {len(matches)} feature(s) named"
 305                    f" '{spec.feature}', and there are still"
 306                    f" {len(remaining)} of those that are contained in"
 307                    f" {matchDesc}."
 308                )
 309
 310    def featureType(self, fID: base.FeatureID) -> base.FeatureType:
 311        """
 312        Returns the feature type for the feature with the given ID.
 313
 314        For example:
 315
 316        >>> fg = FeatureGraph()
 317        >>> fg.addFeature('A', 'region')
 318        0
 319        >>> fg.addFeature('B', 'path')
 320        1
 321        >>> fg.featureType(0)
 322        'region'
 323        >>> fg.featureType(1)
 324        'path'
 325        >>> fg.featureType(2)
 326        Traceback (most recent call last):
 327        ...
 328        KeyError...
 329        >>> # TODO: Turn into an exploration.geographic.MissingFeatureError...
 330        >>> # Use in combination with resolveFeature if necessary:
 331        >>> fg.featureType(fg.resolveFeature('A'))
 332        'region'
 333        """
 334        return self.nodes[fID]['fType']
 335
 336    @staticmethod
 337    def example(name: Optional[str]):
 338        """
 339        Creates and returns one of several example graphs. The available
 340        graphs are: 'chasm', 'town', 'intercom', and 'scripts'. 'chasm'
 341        is the default when no name is given. Descriptions of each are
 342        included below.
 343
 344        ### Canyon
 345
 346        Includes all available feature types, and all available relation
 347        types. Includes mild feature name ambiguity (disambiguable by
 348        region).
 349
 350        - One main region, called 'main'.
 351        - Two subregions called 'east' and 'west'.
 352        - An edge between them called 'chasm' with a path called
 353          'bridge' that touches it. The chasm is tagged with a 'flight'
 354          power requirement. The bridge is tagged with an
 355          'openBridgeGate' requirement.
 356            * The east side of bridge has an affordance called 'bridgeLever'
 357              which is also in the east region, and the effect is to grant
 358              openBridgeGate. It requires (and consumes) a single
 359              'bridgeToken' token and is not repeatable.
 360        - In the east region, there is a node named 'house' with a
 361          single-use affordance attached called openChest that grants a
 362          single bridgeToken.
 363        - There is a path 'housePath' from the house that leads to a node
 364          called 'crossroads'. Paths from crossroads lead to startingGrove
 365          ('startPath') and to the bridge ('bridgePath'). (These paths touch
 366          the things they lead to.)
 367        - The landmark 'windmill' is at the crossroads.
 368        - In the west region, a path from the bridge (also named
 369          'bridgePath') leads to a node also named 'house.'
 370            * In this house, there are three regions: 'basement',
 371              'downstairs' and 'upstairs.' All three regions are connected
 372              with a path 'stairs.'
 373            * The downstairs is tagged as an entrance of the house (from the
 374              south part of the house to the south part of the downstairs).
 375              There is another entrance at the east part of the house
 376              directly into the basement.
 377        - The east and west regions are partially observable from each
 378          other. The upstairs and downstairs region of the west house can
 379          observe the west region, but the basement can't.
 380        - The west house is positioned 1 kilometer northeast of the
 381          center of the west region.
 382        - The east house is positioned TODO
 383
 384        ### Town
 385
 386        Has multiple-containment to represent paths that traverse
 387        through multiple regions, and also paths that cross at an
 388        intersection.
 389
 390        - Top level regions called 'town' (id 0) and 'outside' (id 10).
 391        - An edge 'wall' (id 9) between them (touching both but within
 392          neither).
 393        - Regions 'market' (id 3), 'eastResidences' (id 4),
 394          'southResidences' (id 5), and 'castleHill' (id 1) within the
 395          town.
 396        - A node 'castle' (id 2) within the 'castleHill'.
 397        - A node 'marketSquare' (id 6) in the market.
 398        - Paths 'ringRoad' (id 7) and 'mainRoad' (id 8) in the town.
 399          Both of them touch the marketSquare.
 400            * 'ringRoad' is additionally within the market,
 401              eastResidences, and southResidences.
 402            * mainRoad is additionally within the market, castleHill,
 403              and outside.
 404            * mainRoad also touches the castle and the wall.
 405
 406        ### Intercom
 407
 408        Has complicated containment relationships, but few other
 409        relationships.
 410
 411        - A top-level region named 'swamp' (id 0)
 412        - Regions 'eastSwamp', 'westSwamp', and 'midSwamp' inside of
 413          that (ids 1, 2, and 3 respectively). Conceptually, there's a
 414          bit of overlap between the mid and the two other regions; it
 415          touches both of them.
 416        - A node 'house' (id 4) that's in both the midSwamp and the
 417          westSwamp.
 418        - A region 'inside' (id 5) that's inside the house.
 419        - A region 'kitchen' (id 6) that's inside the 'inside.'
 420        - An affordance 'intercom' (id 7) that's inside both the kitchen
 421          and the 'inside.'
 422
 423        ### Scripts
 424
 425        This graph has complex affordances and triggers set up to
 426        represent mobile + interactive NPCs, as well as including an
 427        entity to represent the player's avatar. It has:
 428
 429        - A region 'library' (id 0)
 430        - Regions '1stFloor', '2ndFloor', and '3rdFloor' within the
 431            library (ids 1, 2, and 3). These are positioned relative to
 432            each other using above/below.
 433        - A path 'lowerStairs' (id 4) whose bottom part is within the
 434            1st floor and whose top part is within the 2nd floor.
 435        - A path 'upperStairs' (id 5) whose bottom part is within the
 436            2nd floor and whose top part is within the 3rd floor. This
 437            path requires the '3rdFloorKey' to traverse.
 438        - An entity 'librarian' which is in the 1st floor. The librarian
 439            TODO
 440        """
 441        if name is None:
 442            name = 'chasm'
 443
 444        fg = FeatureGraph()
 445        if name == 'chasm':
 446            fg.addFeature('main', 'region') # 0
 447            east = fg.addFeature('east', 'region', 'main') # 1
 448            west = fg.addFeature('west', 'region', 'main') # 2
 449
 450            chasm = fg.addFeature('chasm', 'edge', 'main') # 3
 451            fg.relateFeatures(
 452                base.feature('east', 'west'),
 453                'touches',
 454                base.feature('chasm', 'east')
 455            )
 456            fg.relateFeatures(
 457                base.feature('west', 'east'),
 458                'touches',
 459                base.feature('chasm', 'west')
 460            )
 461            fg.tagFeature(chasm, 'requires', 'flight')
 462
 463            bridge = fg.addFeature('bridge', 'path', 'main') # 4
 464            fg.relateFeatures(
 465                'bridge',
 466                'touches',
 467                base.feature('chasm', 'middle')
 468            )
 469            fg.relateFeatures(
 470                'bridge',
 471                'touches',
 472                base.feature('east', 'west')
 473            )
 474            fg.relateFeatures(
 475                'bridge',
 476                'touches',
 477                base.feature('west', 'east')
 478            )
 479            fg.tagFeature(
 480                bridge,
 481                'requires',
 482                base.ReqCapability('openBridgeGate')
 483            )
 484
 485            bridgeLever = fg.addFeature('bridgeLever', 'affordance') # 5
 486            fg.relateFeatures(
 487                'bridgeLever',
 488                'within',
 489                base.feature('east', 'west')
 490            )
 491            fg.relateFeatures(
 492                'bridgeLever',
 493                'touches',
 494                base.feature('bridge', 'east')
 495            )
 496            fg.tagFeature(
 497                bridgeLever,
 498                'requires',
 499                base.ReqTokens('bridgeToken', 1)
 500            )
 501            # TODO: Bundle these into a single Consequence?
 502            fg.addEffect(
 503                'bridgeLever',
 504                'do',
 505                base.featureEffect(deactivate=True)
 506            )
 507            fg.addEffect(
 508                'bridgeLever',
 509                'do',
 510                base.featureEffect(gain='openBridgeGate')
 511            )
 512            # TODO: Use a mechanism for this instead?
 513            fg.addEffect(
 514                'bridgeLever',
 515                'do',
 516                base.featureEffect(lose='bridgeToken*1')
 517            )
 518
 519            fg.addFeature('house', 'node') # 6
 520            fg.relateFeatures(
 521                'house',
 522                'within',
 523                base.feature('east', 'middle')
 524            )
 525
 526            fg.addFeature('openChest', 'affordance') # 7
 527            fg.relateFeatures('openChest', 'within', 'house')
 528            fg.addEffect(
 529                'openChest',
 530                'do',
 531                base.featureEffect(deactivate=True)
 532            )
 533            fg.addEffect(
 534                'openChest',
 535                'do',
 536                base.featureEffect(gain=('bridgeToken', 1))
 537            )
 538
 539            fg.addFeature('crossroads', 'node', 'east') # 8
 540            fg.addFeature('windmill', 'landmark', 'east') # 9
 541            fg.relateFeatures(
 542                'windmill',
 543                'touches',
 544                base.feature('crossroads', 'northeast')
 545            )
 546
 547            fg.addFeature('housePath', 'path', 'east') # 10
 548            fg.relateFeatures(
 549                base.feature('housePath', 'east'),
 550                'touches',
 551                base.feature('house', 'west')
 552            )
 553            fg.relateFeatures(
 554                base.feature('housePath', 'west'),
 555                'touches',
 556                base.feature('crossroads', 'east')
 557            )
 558
 559            fg.addFeature('startPath', 'path', 'east') # 11
 560            fg.relateFeatures(
 561                base.feature('startPath', 'south'),
 562                'touches',
 563                base.feature('crossroads', 'north')
 564            )
 565
 566            fg.addFeature(
 567                'startingGrove',
 568                'node',
 569                base.feature('east', 'north')
 570            ) # 12
 571            fg.relateFeatures(
 572                base.feature('startingGrove', 'south'),
 573                'touches',
 574                base.feature('startPath', 'north')
 575            )
 576
 577            fg.addFeature(
 578                'bridgePath',
 579                'path',
 580                base.feature('east', 'west')
 581            ) # 13
 582            fg.relateFeatures(
 583                base.feature('bridgePath', 'west'),
 584                'touches',
 585                base.feature('bridge', 'east')
 586            )
 587            fg.relateFeatures(
 588                base.feature('bridgePath', 'east'),
 589                'touches',
 590                base.feature('crossroads', 'west')
 591            )
 592
 593            fg.addFeature('bridgePath', 'path', 'west') # 14
 594            fg.relateFeatures(
 595                base.feature('bridgePath', within=('west',)),
 596                'touches',
 597                base.feature('bridge', 'west')
 598            )
 599
 600            h2ID = fg.addFeature(
 601                'house',
 602                'node',
 603                base.feature('west', 'middle')) # 15
 604            fg.relateFeatures(
 605                base.FeatureSpecifier(None, [], h2ID, 'south'),
 606                'touches',
 607                base.feature('bridgePath', 'east', within=('west',))
 608            )
 609
 610            fg.addFeature(
 611                'basement',
 612                'region',
 613                base.feature('house', 'bottom', within=('west',))
 614            ) # 16
 615            fg.addFeature(
 616                'downstairs',
 617                'region',
 618                base.featurePart(h2ID, 'middle')
 619            ) # 17
 620            fg.addFeature('upstairs', 'region', base.featurePart(h2ID, 'top'))
 621            # 18
 622            fg.addFeature('stairs', 'path', h2ID) # 19
 623
 624            fg.relateFeatures(
 625                base.feature('stairs', 'bottom'),
 626                'touches',
 627                base.feature('basement', 'north')
 628            )
 629            fg.relateFeatures(
 630                base.feature('stairs', 'middle'),
 631                'touches',
 632                base.feature('downstairs', 'north')
 633            )
 634            fg.relateFeatures(
 635                base.feature('stairs', 'top'),
 636                'touches',
 637                base.feature('upstairs', 'north')
 638            )
 639            fg.relateFeatures(
 640                base.feature('downstairs', 'south'),
 641                'entranceFor',
 642                base.feature('house', 'south', within=('west',))
 643            )
 644            fg.relateFeatures(
 645                base.feature('house', 'east', within=('west',)),
 646                'enterTo',
 647                base.feature('basement', 'east')
 648            )
 649
 650            fg.relateFeatures('east', 'observable', 'west')
 651            fg.tagRelation(east, 'observable', west, 'partial')
 652            fg.relateFeatures('west', 'observable', 'east')
 653            fg.tagRelation(west, 'observable', east, 'partial')
 654
 655            fg.relateFeatures('downstairs', 'observable', 'west')
 656            fg.relateFeatures('upstairs', 'observable', 'west')
 657
 658        elif name == 'town':
 659            fg.addFeature('town', 'region') # 0
 660            fg.addFeature('castleHill', 'region', 'town') # 1
 661            fg.addFeature('castle', 'node', 'castleHill') # 2
 662            fg.addFeature('market', 'region', 'town') # 3
 663            fg.addFeature('eastResidences', 'region', 'town') # 4
 664            fg.addFeature('southResidences', 'region', 'town') # 5
 665            fg.addFeature('marketSquare', 'node', 'market') # 6
 666            fg.addFeature('ringRoad', 'path', 'town') # 7
 667            fg.relateFeatures('ringRoad', 'within', 'market')
 668            fg.relateFeatures('ringRoad', 'within', 'eastResidences')
 669            fg.relateFeatures('ringRoad', 'within', 'southResidences')
 670            fg.relateFeatures('ringRoad', 'touches', 'marketSquare')
 671            fg.addFeature('mainRoad', 'path', 'town') # 8
 672            fg.relateFeatures('mainRoad', 'within', 'castleHill')
 673            fg.relateFeatures('mainRoad', 'touches', 'castle')
 674            fg.relateFeatures('mainRoad', 'within', 'market')
 675            fg.relateFeatures('mainRoad', 'touches', 'marketSquare')
 676            fg.addFeature('wall', 'edge') # 9
 677            fg.relateFeatures('wall', 'touches', 'town')
 678            fg.relateFeatures('wall', 'touches', 'mainRoad')
 679            fg.addFeature('outside', 'region') # 10
 680            fg.relateFeatures('outside', 'touches', 'wall')
 681            fg.relateFeatures('outside', 'contains', 'mainRoad')
 682
 683        elif name == 'intercom':
 684            fg.addFeature('swamp', 'region') # 0
 685            fg.addFeature('eastSwamp', 'region', 'swamp') # 1
 686            fg.addFeature('westSwamp', 'region', 'swamp') # 2
 687            fg.addFeature('midSwamp', 'region', 'swamp') # 3
 688            # Overlap:
 689            fg.relateFeatures('midSwamp', 'touches', 'eastSwamp')
 690            fg.relateFeatures('midSwamp', 'touches', 'westSwamp')
 691            fg.addFeature('house', 'node', 'midSwamp') # 4
 692            fg.relateFeatures('house', 'within', 'westSwamp') # Overlap
 693            fg.addFeature('inside', 'region', 'house') # 5
 694            fg.relateFeatures('inside', 'entranceFor', 'house')
 695            fg.addFeature('kitchen', 'region', 'inside') # 6
 696            fg.addFeature('intercom', 'affordance', 'kitchen') # 7
 697            fg.relateFeatures('intercom', 'within', 'inside') # Inside both
 698
 699        return fg
 700
 701    def listFeatures(self) -> List[
 702        Tuple[base.FeatureID, base.Feature, base.FeatureType]
 703    ]:
 704        """
 705        Returns a list of tuples containing the id, name, and type of
 706        each feature in the graph. Note that names are not necessarily
 707        unique.
 708
 709        For example:
 710
 711        >>> fg = FeatureGraph()
 712        >>> fg.addFeature('R', 'region')
 713        0
 714        >>> fg.addFeature('N', 'node', 'R')
 715        1
 716        >>> fg.addFeature('N', 'node', 'R')
 717        2
 718        >>> fg.addFeature('P', 'path', 'R')
 719        3
 720        >>> fg.listFeatures()
 721        [(0, 'R', 'region'), (1, 'N', 'node'), (2, 'N', 'node'),\
 722 (3, 'P', 'path')]
 723        """
 724        result: List[
 725            Tuple[base.FeatureID, base.Feature, base.FeatureType]
 726        ] = []
 727        for fID in self:
 728            result.append(
 729                (fID, self.nodes[fID]['name'], self.nodes[fID]['fType'])
 730            )
 731
 732        return result
 733
 734    def fullSpecifier(
 735        self,
 736        fID: base.FeatureID,
 737        part: Optional[base.Part] = None
 738    ) -> base.FeatureSpecifier:
 739        """
 740        Returns the fully-qualified feature specifier for the feature
 741        with the given ID. When multiple parent features are available
 742        to select from, chooses the shortest possible component list,
 743        breaking ties towards components with lower ID integers (i.e.,
 744        those created earlier). Note that in the case of repeated name
 745        collisions and/or top-level name collisions, the resulting fully
 746        qualified specifier may still be ambiguous! This is mostly
 747        intended for helping provide a human-recognizable shorthand for
 748        a node rather than creating unambiguous representations (use the
 749        ID you already have for that).
 750
 751        A part may be specified for inclusion in the returned specifier;
 752        otherwise the part slot of the specifier will be `None`.
 753
 754        TODO: Support numeric disambiguation and mix that in here?
 755
 756        For example:
 757
 758        >>> fg = FeatureGraph.example('intercom')
 759        >>> # Accessible from both a child and parent regions (unusual)
 760        >>> fg.fullSpecifier(4)
 761        FeatureSpecifier(domain='main', within=['swamp', 'westSwamp'],\
 762 feature='house', part=None)
 763        >>> # Note tie broken towards smaller-ID feature here
 764        >>> fg.fullSpecifier(7)
 765        FeatureSpecifier(domain='main', within=['swamp', 'westSwamp',\
 766 'house', 'inside'], feature='intercom', part=None)
 767        >>> # Note shorter 'within' list was chosen here.
 768        >>> fg.fullSpecifier(0)
 769        FeatureSpecifier(domain='main', within=[], feature='swamp',\
 770 part=None)
 771        >>> fg.fullSpecifier(0, 'top')
 772        FeatureSpecifier(domain='main', within=[], feature='swamp',\
 773 part='top')
 774        >>> # example of ambiguous specifiers:
 775        >>> fg.addFeature('swamp', 'region')
 776        8
 777        >>> fg.fullSpecifier(0)
 778        FeatureSpecifier(domain='main', within=[], feature='swamp',\
 779 part=None)
 780        >>> fg.fullSpecifier(8)
 781        FeatureSpecifier(domain='main', within=[], feature='swamp',\
 782 part=None)
 783        """
 784        parents = self.relations(fID, 'within')
 785        best = base.FeatureSpecifier(
 786            domain=self.nodes[fID]['domain'],
 787            within=[],
 788            feature=self.nodes[fID]['name'],
 789            part=part
 790        )
 791        for par in sorted(parents, reverse=True):
 792            option = self.fullSpecifier(par)
 793            if isinstance(option.feature, base.FeatureID):
 794                amended = list(option.within) + [
 795                    self.featureName(option.feature)
 796                ]
 797            else:
 798                amended = list(option.within) + [option.feature]
 799            if (
 800                best.within == []
 801             or len(amended) <= len(best.within)
 802            ):
 803                best = base.FeatureSpecifier(
 804                    domain=best.domain,
 805                    within=amended,
 806                    feature=best.feature,
 807                    part=part
 808                )
 809
 810        return best
 811
 812    def allRelations(
 813        self,
 814        feature: base.AnyFeatureSpecifier
 815    ) -> Dict[base.FeatureRelationshipType, Set[base.FeatureID]]:
 816        """
 817        Given a feature specifier, returns a dictionary where each key
 818        is a relationship type string, and the value for each key is a
 819        set of `FeatureID`s for the features that the specified feature
 820        has that relationship to. Only outgoing relationships are
 821        listed, and only relationship types for which there is at least
 822        one relation are included in the dictionary.
 823
 824        For example:
 825
 826        >>> fg = FeatureGraph.example("chasm")
 827        >>> fg.allRelations("chasm")
 828        {'within': {0}, 'touches': {1, 2, 4}}
 829        >>> fg.allRelations("bridge")
 830        {'within': {0}, 'touches': {1, 2, 3, 5, 13, 14}}
 831        >>> fg.allRelations("downstairs")
 832        {'within': {15}, 'entranceFor': {15}, 'touches': {19},\
 833 'observable': {2}}
 834        """
 835        fID = self.resolveFeature(feature)
 836        result: Dict[base.FeatureRelationshipType, Set[base.FeatureID]] = {}
 837        for _, dest, info in self.edges(fID, data=True):
 838            rel = info['rType']
 839            if rel not in result:
 840                result[rel] = set()
 841            result[rel].add(dest)
 842        return result
 843
 844    def relations(
 845        self,
 846        fID: base.FeatureID,
 847        relationship: base.FeatureRelationshipType
 848    ) -> Set[base.FeatureID]:
 849        """
 850        Returns the set of feature IDs for each feature with the
 851        specified relationship from the specified feature (specified by
 852        feature ID only). Only direct relations with the specified
 853        relationship are included in the list, indirect relations are
 854        not.
 855
 856        For example:
 857
 858        >>> fg = FeatureGraph.example('town')
 859        >>> t = fg.resolveFeature('town')
 860        >>> ms = fg.resolveFeature('marketSquare')
 861        >>> rr = fg.resolveFeature('ringRoad')
 862        >>> mr = fg.resolveFeature('mainRoad')
 863        >>> fg.relations(ms, 'touches') == {rr, mr}
 864        True
 865        >>> mk = fg.resolveFeature('market')
 866        >>> fg.relations(ms, 'within') == {mk}
 867        True
 868        >>> sr = fg.resolveFeature('southResidences')
 869        >>> er = fg.resolveFeature('eastResidences')
 870        >>> ch = fg.resolveFeature('castleHill')
 871        >>> os = fg.resolveFeature('outside')
 872        >>> fg.relations(rr, 'within') == {t, mk, sr, er}
 873        True
 874        >>> fg.relations(mr, 'within') == {t, ch, mk, os}
 875        True
 876        >>> fg.relations(rr, 'touches') == {ms}
 877        True
 878        >>> c = fg.resolveFeature('castle')
 879        >>> w = fg.resolveFeature('wall')
 880        >>> fg.relations(mr, 'touches') == {ms, c, w}
 881        True
 882        >>> fg.relations(sr, 'touches')
 883        set()
 884        """
 885        results = set()
 886        for _, dest, info in self.edges(fID, data=True):
 887            if info['rType'] == relationship:
 888                results.add(dest)
 889        return results
 890
 891    def domain(self, fID: base.FeatureID) -> base.Domain:
 892        """
 893        Returns the domain that the specified feature is in.
 894
 895        For example:
 896
 897        >>> fg = FeatureGraph()
 898        >>> fg.addFeature('main', 'node', domain='menu')
 899        0
 900        >>> fg.addFeature('world', 'region', domain='main')
 901        1
 902        >>> fg.addFeature('', 'region', domain='NPCs')
 903        2
 904        >>> fg.domain(0)
 905        'menu'
 906        >>> fg.domain(1)
 907        'main'
 908        >>> fg.domain(2)
 909        'NPCs'
 910        """
 911        if fID not in self:
 912            raise MissingFeatureError(f"There is no feature with ID {fID}.")
 913        return self.nodes[fID]['domain']
 914
 915    def addFeature(
 916        self,
 917        name: base.Feature,
 918        featureType: base.FeatureType,
 919        within: Optional[base.AnyFeatureSpecifier] = None,
 920        domain: Optional[base.Domain] = None
 921    ) -> base.FeatureID:
 922        """
 923        Adds a new feature to the graph. You must specify the feature
 924        type, and you may specify another feature which you want to put
 925        the new feature inside of (i.e., a 'within' relationship and
 926        reciprocal 'contains' relationship will be set up). Also, you
 927        may specify a domain for the feature; if you don't specify one,
 928        the domain will default to 'main'. Returns the feature ID
 929        assigned to the new feature.
 930
 931        For example:
 932
 933        >>> fg = FeatureGraph()
 934        >>> fg.addFeature('world', 'region')
 935        0
 936        >>> fg.addFeature('continent', 'region', 'world')
 937        1
 938        >>> fg.addFeature('valley', 'region', 'continent')
 939        2
 940        >>> fg.addFeature('mountains', 'edge', 'continent')
 941        3
 942        >>> fg.addFeature('menu', 'node', domain='menu')
 943        4
 944        >>> fg.relations(0, 'contains')
 945        {1}
 946        >>> fg.relations(1, 'contains')
 947        {2, 3}
 948        >>> fg.relations(2, 'within')
 949        {1}
 950        >>> fg.relations(1, 'within')
 951        {0}
 952        >>> fg.domain(0)
 953        'main'
 954        >>> fg.domain(4)
 955        'menu'
 956        """
 957        fID = self._register()
 958        if domain is None:
 959            domain = 'main'
 960        self.add_node(fID, name=name, fType=featureType, domain=domain)
 961        self.nodes[fID]['domain'] = domain
 962
 963        if within is not None:
 964            containerID = self.resolveFeature(within)
 965            # Might raise AmbiguousFeatureSpecifierError
 966            self.relateFeatures(fID, 'within', containerID)
 967        return fID
 968
 969    def relateFeatures(
 970        self,
 971        source: base.AnyFeatureSpecifier,
 972        relType: base.FeatureRelationshipType,
 973        destination: base.AnyFeatureSpecifier
 974    ) -> None:
 975        """
 976        Adds a new relationship between two features. May also add a
 977        reciprocal relationship for relations that have fixed
 978        reciprocals. The list of reciprocals is:
 979
 980        - 'contains' and 'within' are required reciprocals of each
 981          other.
 982        - 'touches' is its own required reciprocal.
 983        - 'observable' does not have a required reciprocal.
 984        - 'positioned' does not have a required reciprocal.
 985        - 'entranceFor' and 'enterTo' are each others' required
 986          reciprocal.
 987
 988        The type of the relationship is stored in the 'rType' slot of the
 989        edge that represents it. If parts are specified for either the
 990        source or destination features, these are stored in the
 991        sourcePart and destPart tags for both the edge and its
 992        reciprocal. (Note that 'rType' is not a tag, it's a slot directly
 993        on the edge).
 994
 995        For example:
 996
 997        >>> fg = FeatureGraph()
 998        >>> fg.addFeature('south', 'region')
 999        0
1000        >>> fg.addFeature('north', 'region')
1001        1
1002        >>> fg.relateFeatures('south', 'touches', 'north')
1003        >>> fg.allRelations(0)
1004        {'touches': {1}}
1005        >>> fg.allRelations(1)
1006        {'touches': {0}}
1007        >>> # Multiple relations between the same pair of features:
1008        >>> fg.relateFeatures('north', 'observable', 'south')
1009        >>> fg.allRelations(0)
1010        {'touches': {1}}
1011        >>> fg.allRelations(1)
1012        {'touches': {0}, 'observable': {0}}
1013        >>> # Self-relations are allowed even though they usually don't
1014        >>> # make sense
1015        >>> fg.relateFeatures('north', 'observable', 'north')
1016        >>> fg.allRelations(1)
1017        {'touches': {0}, 'observable': {0, 1}}
1018        >>> fg.relateFeatures('north', 'observable', 'north')
1019        >>> fg.addFeature('world', 'region')
1020        2
1021        >>> fg.relateFeatures('world', 'contains', 'south')
1022        >>> fg.relateFeatures('north', 'within', 'world')
1023        >>> fg.allRelations(0)
1024        {'touches': {1}, 'within': {2}}
1025        >>> fg.allRelations(1)
1026        {'touches': {0}, 'observable': {0, 1}, 'within': {2}}
1027        >>> fg.allRelations(2)
1028        {'contains': {0, 1}}
1029        >>> # Part specifiers are tagged on the relationship
1030        >>> fg.relateFeatures(
1031        ...     base.feature('south', 'south'),
1032        ...     'entranceFor',
1033        ...     base.feature('world', 'top')
1034        ... )
1035        >>> fg.allRelations(2)
1036        {'contains': {0, 1}, 'enterTo': {0}}
1037        >>> fg.allRelations(0)
1038        {'touches': {1}, 'within': {2}, 'entranceFor': {2}}
1039        >>> fg.relationTags(0, 'within', 2)
1040        {}
1041        >>> fg.relationTags(0, 'entranceFor', 2)
1042        {'sourcePart': 'south', 'destPart': 'top'}
1043        >>> fg.relationTags(2, 'enterTo', 0)
1044        {'sourcePart': 'top', 'destPart': 'south'}
1045        """
1046        nSource = base.normalizeFeatureSpecifier(source)
1047        nDest = base.normalizeFeatureSpecifier(destination)
1048        sID = self.resolveFeature(nSource)
1049        dID = self.resolveFeature(nDest)
1050        sPart = nSource.part
1051        dPart = nDest.part
1052
1053        self.add_edge(sID, dID, relType, rType=relType)
1054        if sPart is not None:
1055            self.tagRelation(sID, relType, dID, 'sourcePart', sPart)
1056        if dPart is not None:
1057            self.tagRelation(sID, relType, dID, 'destPart', dPart)
1058
1059        recipType = base.FREL_RECIPROCALS.get(relType)
1060        if recipType is not None:
1061            self.add_edge(dID, sID, recipType, rType=recipType)
1062            if dPart is not None:
1063                self.tagRelation(dID, recipType, sID, 'sourcePart', dPart)
1064            if sPart is not None:
1065                self.tagRelation(dID, recipType, sID, 'destPart', sPart)
1066
1067    def addEffect(
1068        self,
1069        feature: base.AnyFeatureSpecifier,
1070        affordance: base.FeatureAffordance,
1071        effect: base.FeatureEffect
1072    ) -> None:
1073        """
1074        Adds an effect that will be triggered when the specified
1075        `Affordance` of the given feature is used.
1076
1077        TODO: Examples
1078        """
1079        # TODO
1080
1081    def tagFeature(
1082        self,
1083        fID: base.FeatureID,
1084        tag: base.Tag,
1085        val: Union[None, base.TagValue, base.TagUpdateFunction] = None
1086    ) -> Union[base.TagValue, type[base.NoTagValue]]:
1087        """
1088        Adds (or updates) the specified tag on the specified feature. A
1089        value of 1 is used if no value is specified.
1090
1091        Returns the old value for the specified tag, or the special
1092        object `base.NoTagValue` if the tag didn't yet have a value.
1093
1094        For example:
1095
1096        >>> fg = FeatureGraph()
1097        >>> fg.addFeature('mountains', 'region')
1098        0
1099        >>> fg.addFeature('town', 'node', 'mountains')
1100        1
1101        >>> fg.tagFeature(1, 'town')
1102        <class 'exploration.base.NoTagValue'>
1103        >>> fg.tagFeature(0, 'geographicFeature')
1104        <class 'exploration.base.NoTagValue'>
1105        >>> fg.tagFeature(0, 'difficulty', 3)
1106        <class 'exploration.base.NoTagValue'>
1107        >>> fg.featureTags(0)
1108        {'geographicFeature': 1, 'difficulty': 3}
1109        >>> fg.featureTags(1)
1110        {'town': 1}
1111        >>> fg.tagFeature(1, 'town', 'yes')
1112        1
1113        >>> fg.featureTags(1)
1114        {'town': 'yes'}
1115        """
1116        if val is None:
1117            val = 1
1118        tdict: Dict[base.Tag, base.TagValue] = self.nodes[
1119            fID
1120        ].setdefault('tags', {})
1121        oldVal = tdict.get(tag, base.NoTagValue)
1122        if callable(val):
1123            tdict[tag] = val(tdict, tag, tdict.get(tag))
1124        else:
1125            tdict[tag] = val
1126        return oldVal
1127
1128    def featureTags(
1129        self,
1130        fID: base.FeatureID
1131    ) -> Dict[base.Tag, base.TagValue]:
1132        """
1133        Returns the dictionary containing all tags applied to the
1134        specified feature. Tags applied without a value will have the
1135        integer 1 as their value.
1136
1137        For example:
1138
1139        >>> fg = FeatureGraph()
1140        >>> fg.addFeature('swamp', 'region')
1141        0
1142        >>> fg.addFeature('plains', 'region')
1143        1
1144        >>> fg.tagFeature(0, 'difficulty', 3)
1145        <class 'exploration.base.NoTagValue'>
1146        >>> fg.tagFeature(0, 'wet')
1147        <class 'exploration.base.NoTagValue'>
1148        >>> fg.tagFeature(1, 'amenities', ['grass', 'wind'])
1149        <class 'exploration.base.NoTagValue'>
1150        >>> fg.featureTags(0)
1151        {'difficulty': 3, 'wet': 1}
1152        >>> fg.featureTags(1)
1153        {'amenities': ['grass', 'wind']}
1154        """
1155        return self.nodes[fID].setdefault('tags', {})
1156
1157    def tagRelation(
1158        self,
1159        sourceID: base.FeatureID,
1160        rType: base.FeatureRelationshipType,
1161        destID: base.FeatureID,
1162        tag: base.Tag,
1163        val: Union[None, base.TagValue, base.TagUpdateFunction] = None
1164    ) -> Union[base.TagValue, type[base.NoTagValue]]:
1165        """
1166        Adds (or updates) the specified tag on the specified
1167        relationship. A value of 1 is used if no value is specified. The
1168        relationship is identified using its source feature ID,
1169        relationship type, and destination feature ID.
1170
1171        Returns the old value of the tag, or if the tag did not yet
1172        exist, the special `base.NoTagValue` class to indicate that.
1173
1174        For example:
1175
1176        >>> fg = FeatureGraph()
1177        >>> fg.addFeature('plains', 'region')
1178        0
1179        >>> fg.addFeature('town', 'node', 'plains') # Creates contains rel
1180        1
1181        >>> fg.tagRelation(0, 'contains', 1, 'destPart', 'south')
1182        <class 'exploration.base.NoTagValue'>
1183        >>> fg.tagRelation(1, 'within', 0, 'newTag')
1184        <class 'exploration.base.NoTagValue'>
1185        >>> fg.relationTags(0, 'contains', 1)
1186        {'destPart': 'south'}
1187        >>> fg.relationTags(1, 'within', 0)
1188        {'newTag': 1}
1189        >>> fg.tagRelation(0, 'contains', 1, 'destPart', 'north')
1190        'south'
1191        >>> fg.relationTags(0, 'contains', 1)
1192        {'destPart': 'north'}
1193        """
1194        if val is None:
1195            val = 1
1196        # TODO: Fix up networkx.MultiDiGraph type hints
1197        tdict: Dict[base.Tag, base.TagValue] = self.edges[
1198            sourceID,  # type:ignore [index]
1199            destID,
1200            rType
1201        ].setdefault('tags', {})
1202        oldVal = tdict.get(tag, base.NoTagValue)
1203        if callable(val):
1204            tdict[tag] = val(tdict, tag, tdict.get(tag))
1205        else:
1206            tdict[tag] = val
1207        return oldVal
1208
1209    def relationTags(
1210        self,
1211        sourceID: base.FeatureID,
1212        relType: base.FeatureRelationshipType,
1213        destID: base.FeatureID
1214    ) -> Dict[base.Tag, base.TagValue]:
1215        """
1216        Returns a dictionary containing all of the tags applied to the
1217        specified relationship.
1218
1219        >>> fg = FeatureGraph()
1220        >>> fg.addFeature('swamp', 'region')
1221        0
1222        >>> fg.addFeature('plains', 'region')
1223        1
1224        >>> fg.addFeature('road', 'path')
1225        2
1226        >>> fg.addFeature('pond', 'region')
1227        3
1228        >>> fg.relateFeatures('road', 'within', base.feature('swamp', 'east'))
1229        >>> fg.relateFeatures('road', 'within', base.feature('plains', 'west'))
1230        >>> fg.relateFeatures('pond', 'within', 'swamp')
1231        >>> fg.tagRelation(0, 'contains', 2, 'testTag', 'Val')
1232        <class 'exploration.base.NoTagValue'>
1233        >>> fg.tagRelation(2, 'within', 0, 'testTag', 'Val2')
1234        <class 'exploration.base.NoTagValue'>
1235        >>> fg.relationTags(0, 'contains', 2)
1236        {'sourcePart': 'east', 'testTag': 'Val'}
1237        >>> fg.relationTags(2, 'within', 0)
1238        {'destPart': 'east', 'testTag': 'Val2'}
1239        """
1240        return self.edges[
1241            sourceID, # type:ignore [index]
1242            destID,
1243            relType
1244        ].setdefault('tags', {})
1245
1246
1247def checkFeatureAction(
1248    graph: FeatureGraph,
1249    action: base.FeatureAction,
1250    featureType: base.FeatureType
1251) -> bool:
1252    """
1253    Checks that the feature type and affordance match, and that the
1254    optional parts present make sense given the feature type.
1255    Returns `True` if things make sense and `False` if not.
1256
1257    Also, a feature graph is needed to be able to figure out the
1258    type of the subject feature.
1259
1260    The rules are:
1261
1262    1. The feature type of the subject feature must be listed in the
1263        `FEATURE_TYPE_AFFORDANCES` dictionary for the affordance
1264        specified.
1265    2. Each optional slot has some affordance types it's incompatible with:
1266        - 'direction' may not be used with 'scrutinize', 'do', or
1267            'interact'.
1268        - 'part' may not be used with 'do'.
1269        - 'destination' may not be used with 'do' or 'interact'.
1270    """
1271    fID = graph.resolveFeature(action['subject'])
1272    fType = graph.featureType(fID)
1273    affordance = action['affordance']
1274    if fType not in base.FEATURE_TYPE_AFFORDANCES[affordance]:
1275        return False
1276    if action.get('direction') is not None:
1277        if affordance in {'scrutinize', 'do', 'interact'}:
1278            return False
1279    if action.get('part') is not None:
1280        if affordance == 'do':
1281            return False
1282    if action.get('destination') is not None:
1283        if affordance in {'do', 'interact'}:
1284            return False
1285    return True
1286
1287
1288def move():
1289    """
1290    The move() function of the feature graph.
1291    """
1292    # TODO
1293    pass
1294
1295
1296class GeographicExploration:
1297    """
1298    Unifies the various partial representations into a combined
1299    representation, with cross-references between them. It can contain:
1300
1301    - Zero or more `MetricSpace`s to represent things like 2D or 3D game
1302        spaces (or in some cases 4D+ including time and/or some other
1303        relevant dimension(s)). A 1D metric space can also be used to
1304        represent time independently, and several might be used for
1305        real-world time, play-time elapsed, and in-game time-of-day, for
1306        example. Correspondences between metric spaces can be added.
1307    - A single list containing one `FeatureGraph` per exploration step.
1308        These feature graphs represent how the explorer's knowledge of
1309        the space evolves over time, and/or how the space itself changes
1310        as the exploration progresses.
1311    - A matching list of `FeatureDecision`s which details key decisions
1312        made by the explorer and activities that were engaged in as a
1313        result.
1314    - A second matching list of exploration status maps, which each
1315        associate one `ExplorationState` with each feature in the
1316        current `FeatureGraph`.
1317    - A third matching list of game state dictionaries holding both
1318        custom and conventional game state information, such as
1319        position/territory information for each domain in the current
1320        `FeatureGraph`.
1321    """
1322    # TODO