Narrow passages and water pools are just some of the motion planning challenges
Note: this page is currently just the final report I made for COMP768: Physically Based Modeling. It will be slowly morphed over time into something less report-like.
Q3Plan is a tool for Quake III level designers that measures approximate player travel times between directed pairs of items in a level. Computing timings is equivalent to solving a motion planning problem with differential constraints, where a Quake III player is a robot to be moved from a starting state to a goal region. While it would be ideal that timings be as close to minimal as possible, finding time-optimal paths is only computationally feasible within highly restricted settings [1]; finding even approximately time-optimal paths can be difficult for motion planners to achieve when faced with systems involving complex dynamics.
Background
Quake III already contains a motion planning system that allows the game AI (“bots”) to navigate through each environment [2]. The system is a good example of a decoupled approach to handling dynamics: a geometric cell decomposition technique subdivides regions of free configuration space into areas, and bot dynamics are considered when determining reachabilities between neighboring areas. Areas form vertices in an unweighted graph, and are connected with reachabilities. A breadth-first search of the graph provides a macroscopic characterization of the “shortest path” between locations.
The current technique ensures that bot navigation will be kinematically valid and makes an attempt to choose faster paths. Timings aren’t explicitly computed for bot movements, but a first approximation to answering directed pair time queries could be achieved as follows:
- Spawn a bot at the source item
- Override all AI logic and order the bot to move to the destination item
- Query times at the beginning and end of the movement and report the difference
This method would provide a rough estimation of human timings, and an exact value for bot timings. While this may be useful to a level designer in some circumstances (e.g. tweaking bot behavior), it seems reasonable to assume that more accurate estimations can be achieved by using planning algorithms that fully account for dynamics. The fact that we are interested in reporting times in an offline process strengthens this assumption since the current method was concerned with routing AI in real time.
An offline process also corresponds nicely with sampling based planning algorithms which have probabilistic guarantees for finding valid paths and can only produce better paths as the number of samples increase. In the same way that level designers trade off lighting quality for compilation time when building their levels for in-game use, they can similarly choose how long to let timing computations run based upon how much they desire an accurate answer.
Progress as of November 15th
- Code can be found on my Github repository.
- Starting from a source state, I can randomly select inputs and apply them over a given number of simulation steps.
- I can save and restore player states, then continue expansion from the restored state.
- Currently, I’m saving the entire player state structure, which is going to become prohibitive as sample sizes become even moderately large. Identifying which parts of the player’s state is relevant to a motion planner is less difficult than identifying which parts of the state will crash the program if they aren’t restored correctly. In other words, saving and restoring only a subset of the state quickly leads to program inconsistencies, especially as it relates to timing.
- Since I’m using the simulation as a black box, and saving the entire state, motion plans will automatically account for environmental factors such as water. Currently, weapons aren’t used to provide speed increases, but randomly sampling weapons should not be too difficult.
- I tried to use the Open Motion Planning Library (OMPL) to compute plans, but found it’s actually more difficult than implementing a planning algorithm from scratch:
- I initially thought I could port a relevant subset of Q3 player physics to OMPL since it supports importing the Q3 BSP format. However, the physics is too complex to do anything other than treat it as black box, given the time frame.
- I thought I could import OMPL as a library into the Q3 code, but OMPL is written in C++ and Quake III is written in C. Fixing this incompatibility isn’t feasible for a library as large as OMPL.
- OMPL’s GUI only works on unix machines; Quake III supports unix development but is not particularly stable on my computers.
- I’ve explored a variety of related literature:
- Chapters 13 and 14 of LaValle’s Planning Algorithms provided a coherent overview of motion planning with robot dynamics.
- van Wavaren’s thesis provided in-depth information about Q3’s existing motion planning system.
- Canny and Reif’s paper on time-optimal paths for a particle-like robot in 3 space was theoretically interesting, but too restricted to be of practical use in my situation.
- KPIECE provided an interesting alternative to RRT, but I’d be interested in investigating other methods that I’m only superficially familiar with such as RRT*.
Progress as of December 12th
- Accomplishments
- RRT implemented in Quake3. The implementation accounts for player physics up front, and produces physically valid paths and traversal times between two locations.
- RRT visualization. Blue dots represent the origin of the bot configurations produced as the algorithm progresses. Once the goal state is reached, the dots along the solution trajectory are turned red. Important note: Although the visualization only shows kinematic information, the algorithm itself is exploring state space, not just configuration space.
- Challenges
- RRT metric. Defining a metric on the Quake3 player’s state space is difficult and crucial to RRT’s space coverage. A plain Euclidean metric is a poor measure of state distance, especially in situations involving vertical height differences.
- Visualizing solution trajectory traversal. The timing system in the Quake3 source code makes correctly executing precisely timed control sequences a difficult task. The systematic way the algorithm produces new states guarantees that the paths it produces are valid, but re-playing them exactly is an engineering challenge due to the software’s intricacies.
- Algorithm Overview
- Spawn a dummy AI bot that has its logic disabled, with a flag that removes it from the game’s physics update.
- Initialize a state tree by fully copying the bot’s state into the root node.
- Generate a random point within the level’s free configuration space.
- Use the point in a Euclidean nearest neighbor query on the state tree to select a node for expansion.
- Restore the bot’s state to the state saved in the node.
- Randomly select input controls.
- Run a single frame of game logic (i.e. integrate physics and advance the bot forward) for 50ms in order to calculate a new state.
- Create a directed edge from the old state to the new state, and store in it the controls used during the update. The edge structure contains a field to allow for non-constant applications of controls, but currently this is a constant 50ms.
- Store this new edge in the old state’s node in the tree, and add the new state to the tree.
- If the new state is contained within the goal region, stop and trace edges backward, accumulating time until you reach the root node.
- Otherwise, goto 3.
Future Work
- It would be very interesting to visualize the time-reachable set of states from a given starting location. This could provide a useful tool for designers seeking to maintain player interest in some regularized fashion, or who aim to engineer situations where incentives are located along the time-reachable boundary (i.e. they are extremely difficult to reach).