1"""
  2# `exploration` library Overview
  3
  4This page explains an overview of the most important concepts that the
  5`exploration` library deals with.
  6
  7## What is it for?
  8
  9The `exploration` library is designed to support **formal** analysis of
 10exploration processes in videogame spaces which can be approximated as a
 11graph of **discrete** and **repeatable** decisions. It's heavily inspired
 12by [the Boss Keys YouTube
 13series](https://www.youtube.com/playlist?list=PLc38fcMFcV_ul4D6OChdWhsNsYY3NA5B2)
 14
 15It could also be applied in some non-game contexts as well. Adventure
 16games, 2D RPGs, action-adventure games, and most centrally, Metroidvania
 17games (roughly, side-scrolling 2D exploration-adventure games) are all
 18genres where it should be applicable. The kinds of questions it might
 19help answer include questions like:
 20
 21- "Which areas are accessible via which other areas, with which items?"
 22- "How many untaken branches has the player passed at this point?"
 23- "What percentage of players get item X before item Y?"
 24
 25Along with more qualitative analysis, it might also help support research
 26into other questions, like "what level structures make players feel
 27claustrophobic?" The main goal is to have a data format that can be used
 28to write down exploration processes, which is abstract enough to enable
 29comparisons between different games and/or different players playing the
 30same game (though there are lots of issues with the latter application).
 31
 32It does rely on human judgement to figure out what should be classified
 33as a "decision," and it also does not work well for certain types of
 34games, like open-world games, where you never really make the same
 35decision twice (code for dealing with these types of games is in the
 36planning stages).
 37
 38
 39## The DTER Model
 40
 41We model the exploration process in games using a highly abstract model
 42that includes Decisions, Transitions, Effects, and Requirements as part
 43of a **decision graph** (represented by the `core.DecisionGraph` class).
 44Many aspects of the game, such as how difficult the enemies are, what the
 45story, graphics, and audio are like, and how a player specifically
 46navigates the geometry of individual rooms are by default not
 47represented, although some of that information could be added as
 48annotations. The four key components of the model are:
 49
 501. Decisions. These represent a position or small region where the player
 51is forced to make a decision about where to go next. See the section on
 52"Decisions are Fractal" below for more details about what qualifies as a
 53decision, but for one example, we can imagine each room might be a
 54decision, where the options are the doors of the room. Each decision is
 55assigned an ID number, and is also given a name (which does not have to
 56be unique).
 57
 582. Transitions. These are the links between decisions, and represent the
 59available options. For each move the player could make (e.g., for each
 60door going out of a room), we add a transition and connect it to another
 61decision representing where the player would be once they take that
 62transition. Each transition has a name, which must be unique among all
 63transitions outgoing from a particular decision (but which is usually NOT
 64unique across the entire graph). Something like "west" can be used to
 65indicate "the west door of this room." Each transition starts from a
 66specific decision and ends at a specific decision. Transitions are
 67allowed to start and end at the same decision, we call these "actions"
 68and they represent things like pulling a lever where the options you're
 69faced with don't directly change, but some kind of effect might be
 70applied which indirectly changes things.
 71
 723. Effects. Each transition has the immediate effect of changing the
 73player's current decision, and thus the options available to them.
 74Transitions may also apply one or more secondary effects, which interact
 75with the player state composed of **capabilities** and **tokens**, plus
 76the world state composed of **mechanism states**. A secondary effect can
 77be something like gaining a new key, gaining a certain number of coins,
 78or setting a mechanism in the world to a particular state. By creating
 79standardized data structures for player & world states, we enable deeper
 80comparisons between different games, although in some cases we then need
 81to abstract some of the details of those games. See the "Effects and
 82Requirements" section below for more details.
 83
 844. Requirements. Using the same abstract player & world state data that
 85effects manipulate, each transition may have a requirement to represent
 86situations like a locked door requiring a certain key, or a bridge where
 87a toll must be paid at each crossing (a toll would also involve an effect
 88to represent losing the money paid). When figuring out the options
 89available to the player, the system can automatically disregard
 90transitions at the current decision whose requirements are not met. A
 91requirement can be a series of specific capabilities, token counts,
 92and/or mechanism states which are combined using AND (`&`), OR (`|`),
 93and/or NOT (`!`) operators. For example, the requirement
 94`fly | (climb & stamina*3)` represents a situation where the player must
 95either have the "fly" capability, or they must have the "climb"
 96capability, along with *at least* three "stamina" tokens. As with
 97effects, sometimes expressing the exact requirements imposed by a
 98particular game engine is difficult, and some abstraction must be used,
 99but the format of requirements has been designed and tested to cover most
100situations that arise in the videogame genres we've studied. See the
101"Effects and Requirements" section below for more details.
102
103Putting together Decisions, Transitions, Effects, and Requirements, we
104create a "decision graph" (represented by the `core.DecisionGraph`
105class). This details every decision, each transition at that decision,
106and what the effects of those transitions are along with the requirements
107necessary for taking them. These decision graphs are rich enough models
108of game spaces to allow for lots of analysis, and because they're
109abstract, they allow for comparison between different games (although
110they remain fundamentally subjective).
111
112
113## Decisions are Fractal
114
115When creating decision graphs, the player needs to choose what level of
116decision they wish to capture. Since the actions used to carry out most
117decisions can be decomposed into a series of more-local decisions, we can
118view decisions in games as having a fractal structure. For example, the
119actions taken as a result of a decision to "visit the water temple"
120probably involve many specific navigation moves, like "go left at the
121crossroads" or "cut across the field towards the river," and each of
122these is the result of a decision that's made in support of the
123higher-level goal of reaching the water temple. Likewise, "go left at the
124crossroads" requires deciding to move the character to the left by a
125certain amount, and that lower-level decision could even be broken down
126into individual decisions to press certain buttons required to make that
127happen. In theory, a decision map could be constructed at the level of
128button presses, but it would be excruciatingly hard to do so manually,
129and analysis of such a map would probably be very difficult. Instead,
130analyzing at the "go left at the crossroads" level is probably more
131productive, since at that level, we can see that many similar game states
132result in very similar sets of choices (e.g., you always have the option
133to go left or right at the crossroads, and those two choices always lead
134to similar subsequent decisions). One could of course analyze decisions
135at the level of "go to the water temple" instead, and here there might
136still be enough similarity in decisions for this to be useful (e.g., when
137at the water temple, you always have the same few options of what to
138visit next).
139
140The `exploration` library does not require you to use any particular
141level of decision, and through the use of `Zone`s it does allow grouping
142base-level decisions into larger groups to capture multiple levels of
143decision structure. Zones can also be stacked within other zones to
144represent complex multi-layer groupings. Support for deriving a
145higher-level decision graph from zones of a lower-level graph is a
146planned feature.
147
148
149## Effects and Requirements
150
151To model game state in a manner that can be abstracted across multiple
152games, we use the following kinds of state:
153
1541. **Capabilities**: Each capability is identified by a unique string,
155    and represents some specific capability that affects which
156    transitions a player can take. Examples include movement abilities
157    (e.g., "doubleJump") and re-usable key items (e.g., "yellowKeyCard").
158    At each step of an exploration, a player either has or does not have
159    each capability, which is represented by a set of capability strings
160    that they player has. The 'gain' effect adds a capability to this
161    set, while the 'lose' effect removes one (in both cases nothing
162    happens if the capability is already present/absent). A requirement
163    may stipulate that a player must have or must not have a certain
164    capability in order to traverse a transition.
1652. **Tokens**: using capabilities alone, it's difficult to represent
166    situations where items can be accumulated (like holding multiple keys
167    that get used up when unlocking doors). So we also maintain a mapping
168    from token names to integers, and the 'gain' and 'lose' effects can
169    specify a token name plus number to add or remove that many tokens of
170    the specified type. Currently, minimum or maximum token limits are
171    not supported, but we plan to add these in a future release. For
172    tokens, a 'set' effect is also available that sets the token count to
173    a specific amount regardless of the previous amount. A token
174    requirement means "at-least-this-many" and negating it thus means
175    "fewer-than-this-many". Using 'and', 'or', and/or 'not' more specific
176    requirements can be created. By combining a token requirement with a
177    'lose' effect on the same transition, we can create transitions that
178    have costs.
1793. **Mechanisms*: in many games there are things like levers that open
180    nearby doors. These could be represented by creating unique
181    capability names for each lever, but that becomes tedious and
182    error-prone, since if you re-use the same name by accident, the
183    library will assume that the capability for one location applies
184    equally to the other. So we include **mechanisms**, which are tied to
185    a particular decision point, and their name only needs to be unique
186    at-that-decision. When referring to a mechanism by name alone, the
187    system will assume that we mean a mechanism at the current decision
188    point, or if no such mechanism exists, one with that name in the
189    current zone, searching higher-level zones if necessary and finally
190    the entire decision map. Each mechanism can have any number of
191    specific states, each identified by a string. The associated effect
192    is 'set' with a mechanism name + state string, which changes the
193    mechanism's current state to the specified one (each mechanism starts
194    out as not-in-any-state and once given a state, can only be in one
195    state at once). Requirements can be that a mechanism is in a specific
196    state, or that it's not in a specific state. There is also a 'toggle'
197    effect which cycles the mechanism through a specific sequence of
198    states on each activation. When a mechanism requirement exists on a
199    transition, we start looking for the named mechanism at both ends of
200    the transition first. A mechanism may also be identified by a
201    decision ID plus mechanism name to avoid the search process. In the
202    most common case where, for example, multiple levers open different
203    doors, but each lever is adjacent to the door it opens and no two
204    levers are at adjacent decisions, each lever could use the same
205    mechanism name, and each door could simply require that that
206    mechanism be in the 'open' state, and the search process would match
207    up levers with doors correctly. Using names like "leftLever" and
208    "rightLever" might be necessary when multiple levers are in the same
209    or adjacent locations, but that's often natural in any case.
210
211Whereas capabilities and tokens are stored as part of the player state,
212mechanism states are stored as part of a separate global decision-graph
213state This helps in situations where, for example, the map state gets
214reset while the player state stays the same, or vice versa. Although we
215won't get into it here, there's also support for maintaining multiple
216separate player states for games where the player switches between
217different avatars with different capabilities.
218
219Besides the 'gain', 'lose', 'set', and 'toggle' effects mentioned above,
220a transition can also have a 'deactivate' effect which disables that
221transition once taken; this is useful for things like chests that can
222only be opened once.
223
224
225## Advanced Effects can Challenges
226
227The base effects system triggers each effect whenever a transition is
228taken, and this can cover probably 90% of cases. However, in some
229situations, things are more complex than that. The effects of a
230transition are actually represented as a `Conesquence`, which is a list
231that can contain `Effect`s as well as `Condition`s or `Challenge`s, and
232the latter two options can contain their own sub-`Consequence`s. This
233forms a tree structure of consequence and sub-consequence lists, which
234can represent quite complicated situations, including conditional and
235random effects. The three types that can be present in a `Consequence`
236list are:
237
2381. `Effect`s are as described above, and are applied in-order. When a
239    consequence list is applied, each effect in the list is applied to
240    the current state.
2412. `Condition`s specify a `Requirement`, and trigger their
242    sub-`Consequence` list of additional effects if that requirement is
243    met. This is different from `Requirement`s applied to transitions,
244    which prevent the player from taking that transition. Even if a
245    `Condition` requirement is not met, the associated transition can
246    still be taken, but the sub-effects of that specific condition will
247    not be applied. We can use this to represent situations like "if you
248    don't have the master key you will use up a small key" (with "master
249    key or one small key" as a requirement to take the transition).
2503. `Challenge`s are used to represent random outcomes, and they have two
251    sub-`Consequence` lists: one for 'success' and the other for
252    'failure' (although these need not represent exactly those two
253    things). Multi-outcome processes can be represented by nesting
254    challenges inside each other. By default, each option has a 50/50
255    chance of happening, although in practice, the player usually knows
256    which outcome actually did happen during a particular traversal.
257    There is a `Skill`s system to indicate how player skills and/or
258    upgrades might affect probabilities of different outcomes (see the
259    `Challenge` documentation), and in theory challenges allow for a
260    model to be playable, although we have not yet implemented an
261    interface for this. Although challenges only offer a rough
262    approximation of potentially very complex game systems, they do allow
263    for comparison between games when players are able to estimate the
264    likelihood of different outcomes and the effects of skills on those
265    likelihoods. In theory, we hope that this will enable things like
266    checking whether players who lose to a 'difficult' boss are more
267    likely to decide to explore other areas compared to players who lose
268    to a boss they think they can beat in a few more tries.
269
270Because `Challenge`s can be placed inside of `Condition`s and vice-versa,
271relatively complex game logic can be attached to a particular transition.
272There are a few more complex effects that can be used to control
273traversal of decision graphs when used conditionally:
274
275- 'bounce' is an effect which cancels the movement associated with a
276    transition. Each transition has a destination and normally the
277    player's next decision will be made using the options at that
278    destination (we call this decision the 'primary decision').
279    If a 'bounce' effect triggers when taking a transition, the player's
280    primary decision will stay the same, even though other effects of
281    that transition may also apply. This can model situations where the
282    player can attempt to take a transition, but without the proper
283    requirements they will be unable to actually complete the transition.
284    It can also model challenges which must be passed in order to
285    progress, where a 'bounce' effect is included in the challenge
286    failure outcome.
287- 'goto' is an effect which sets the player's primary decision to a
288    particular decision. Normally unnecessary since the transition has a
289    destination, but it could be used to model a movement challenge where
290    the player falls down to another decision point if they fail, for
291    example.
292- 'follow' is an effect which names a transition, and forces the player
293    to immediately take the named transition once they arrive at their
294    initial destination. Again most useful with a `Condition` or
295    `Challenge`, it can be used in situations where without meeting
296    certain requirements, a player is shunted off to a different
297    destination, or it could force the player to trigger an action at the
298    destination of a transition. Effects of the secondary transition are
299    applied as normal after all effects of the initial transition, so a
300    chain of 'follow' effects might occur.
301
302These more complex effects are rarely needed, but help model games more
303faithfully for certain key design patterns, such as the "broken bridge"
304scenario where the player's initial attempt to reach a goal unexpectedly
305redirects them elsewhere.
306
307Additionally, transitions can be tagged as 'trigger' transitions, and
308whenever the player faces a decision, any 'trigger' transitions at that
309decision will apply their effects before the player actually gets to make
310a choice. This can approximate things like environmental hazards that
311apply passive damage over time.
312
313
314## Saving, Loading, and Endings
315
316The effects described above can model or at least approximate most game
317logic (although note that token values being integers restricts things a
318bit). However, dying and restoring from a save point is a common
319occurrence in games that isn't well modeled by anything described above.
320For this specific mechanic, we have a 'save' effect which snapshots the
321current game state, and a 'load' action can be taken by the player to
322restore state to that snapshot. 'save' as an `Effect` can be applied to
323any transition, whereas 'load' is not a transition effect but rather a
324type of action the player can take regardless of which other options are
325available to them based on the current decision.
326
327There are options to control exactly which parts of the game state are
328restored when loading a saved state, since in many games only some state
329reverts upon death. Multiple save slots with different names can be used.
330
331To represent endings, including death but also various ways of beating
332the game, we use a special domain. Domains are parallel decision spaces,
333where when making a decision the player can chose any transition from an
334active decision in any of their current domains. However, the 'endings'
335domain is special: When any ending decision point is active, the only
336legitimate action is to load a previous state. So by activating a 'death'
337decision point in the 'endings' domain, we can represent the fact that
338the player has died, and their only option remaining is to load a saved
339game.
340
341Usually, we can annotate the possibility of death as a 'goto' effect of a
342challenge failure, or when dying accidentally even when a challenge is
343not significant enough to be annotated, a special 'warp' action can be
344used to represent movement without taking a listed transition.
345
346
347## More Details
348
349More details of the API not mentioned here can be found in the
350documentation for various API functions and core classes. The
351`exploration.base` and `exploration.core` modules contain most of the
352relevant definitions, particularly the methods of the
353`exploration.core.DecisionGraph` and
354`exploration.core.DiscreteExploration` classes, plus the `Requirement`,
355`Effect`, `Challenge`, `Condition`, and `Consequence` definitions in the
356`exploration.base` module.
357"""