Tools for video game logic representation and analysis, particularly routing and beatability checks for speedruns and randomizers.
Most video game speedruns are optimization problems of the form, "what's the fastest route to accomplish this list of tasks under these constraints?", otherwise known as the Traveling Salesman Adventurer Problem. While TSP is generally considered intractable in the general case, any given video game is a specific case with a finite number of traversable nodes, and any% speedruns search for ways to skip past as many nodes as possible.
Randomizers produce repeatable challenges from a given video game where the items/tasks needed are found at random throughout the game world, and the difficulty of the challenge can usually be adjusted by adding or removing randomization from various elements. Routing is also a TSP problem, but one that has to be adjusted by speedrunners "on the fly" as items are discovered from the randomized locations and enable new access to other locations.
Randomizers generally enforce that every randomly generated arrangement ("seed") is completable with a certain set of accepted skills. To accomplish this, authors describe the game "Logic" as an access graph, a directed graph used to determine what targets a player has repeatable access to, given an item collection and a root node. A graph search algorithm can be applied to prove that the seed is completable. This kind of graph might look more like a tree: the route a player might have to take between one item and the next isn't important to know; we only need a path from Root to the new location to guarantee that it can be done. Additionally, certain changeable details like cash on hand or time of day aren't taken into account unless the simulated player is guaranteed to be able to set those conditions from any point.
To find an actual game route, however, we need some more details in the graph. Chiefly, we have to track the player's state as they traverse through the graph, including changeable details like position. To additionally predict a fastest route, we will also need time measurements for moving between nodes (whether manually defined in the graph or generated by combining a movement speed and a distance), obtaining items, etc, and potentially we'll have to define multiple edges between nodes when players have a choice. We'll call this kind of graph a traversal graph.
This repository defines a simple format for defining traversal graphs, which must be used to use the analysis tools (even the access-specific tools).
This project aims to eventually accomplish the following:
- Solve speedruns: Produce a static route from a traversable graph with known item assignments. ✔️
- Solve fully-known randomizer seeds: Import or accept a modified item assignment, then solve it.
- Easily record timings: Add a convenient method of adding/editing edge traversal timings.
- Route randomizer runs: Choose the next area to explore, given an incomplete traversal of the graph.
- Analyze the logic: Use additional details of the graph/item placement rules to predict where useful items are likely to be.
- Exact measurement of distances, especially of nearby Locations in a particular node.
- Micro-optimizations, such as which order to check Locations at a particular node.
For full details of how to make a game graph, see games/README.md.
The player's state at a given point has two major components: items, which are usually powerups but really can be any permanent item or accomplishment; and context, which contains everything that could be reversed or changed later.
The main graph components are: Spots which are the graph nodes, Locations which contain items or permanent event markers and can be accessed at most one time, Exits which connect Spots together, and Actions which may modify player state in repeatable ways. Exits that contain Locations are called Hybrids; these are used for situations where the player is given an item when moving between Spots. Additionally, there are global Actions that can be performed from many places, and global Warps which move the player to particular fixed or contextual positions.
Spots are grouped together into Areas that connect all Spots together based on a per-Area coordinate system; Exits don't need to be defined between these Spots. The actual time taken to move between Spots in an Area is calculated based on global movement definitions, as applied to the distance between the Spots. This greatly reduces the number of measurements that would have to be taken.
Areas are further grouped into Regions, which have no default special behavior tying Areas together.
The top-level game definition also includes:
- rules, which describe the rulesets available, particularly the victory conditions (a search will choose one of each)
- settings, which can modify traversals by allowing new tricks or options, and their defaults or ranges
- initial context values
- default times for different kinds of Locations
- helper definitions for the logic rules used throughout
- context modifier rules for item collection
In games/sample we've defined a small version of Ocarina of Time, based on the access graph logic from https://github.com/TestRunnerSRL/OoT-Randomizer. It is not meant to be an accurate representation; several liberties have been taken to ensure the sample graph covers most of the above concepts.
Python 3.12, Rust, Cargo. Optional: Java (for rebuilding the grammar).
Run pip install requirements.txt to install necessary python libraries, including ANTLR4's Python3 runtime, which will also install ANTLR4 for you.
To rebuild the grammar, run python grammar/build.py --recompile.
To generate the Rust code specific to a game, place its Game.yaml and Region yaml files in a folder games/GameName and run python Compiler.py GameName. Then, from games/GameName, you can run the generated program via cargo run or cargo run -r, optionally providing a yaml-style settings file.