World pathway planning
After generating the base terrain, paths must be placed through the world leading park guests from one section of the park to another. Guests don’t really need to do much other than wander, so there is not much complexity there. The real challenge is in generating decent-looking pathways through the world which don’t look “robotic.” Using some flow fields, I was able to achieve some decent path layouts running through the world.
There are a couple elements involved in how paths are determined through the world:
A portal is a doorway/connection to another section of the world. These are basically anchor points in the world which we build paths from, and tell the wandering guest AI to wander towards.
A flow field (or vector field) is a 2D map of arrows pointing towards a particular target (see this image example). After calculating the field, an AI agent can be placed anywhere within that field and can effectively navigate to the target.
Each step in the path planning process is outlined below.
1. Portal Placement
Four portals are placed on the edge of the given section, one for each side. A portal will aim to never be too close to another, though is not placed if the chosen piece of land has water or mountains.
These portals are also useful in that they can later be used to transfer guests to different park sections, they provide a logical spawn point for new AI agents, etc.
2. Generate Flow Fields
The FlowFieldManager class handles both generating flow fields for sections and storing those fields for later lookup. Given a section, the FFM uses the positions of the portals as targets when generating flow fields. For each portal, the manager:
- Calculates a cost field for the given terrain by flood-filling an array and noting each node’s collective distance from start point (the current portal). Mountains are given the max cost possible, which creates fields that properly avoid them.
- Calculates the actual flow field by iterating over each cost node and pointing that node towards its neighbor with the lowest distance towards the target.
By the end of this process, four flow fields are generated, each one leading to a different section portal.
3. Simulate Flow Field Agent
Once the section’s flow fields have been calculated, an AI agent is created (in memory, not in world space) and simulates traversing the flowfield. By starting the agent at a portal and targeting another portal, it inherently generates direct path spanning from one section edge to another.
As the agent moves across the world, its positions are tracked, and that trail in turn becomes the path actually placed in the world. Each section is guaranteed to have at least one intersection, though there is an element of randomness applied to which portals are connected leading to some variation.
4. Generate Paths using Marching Cubes
Using the path data collected from the simulated agents, a Marching Cubes algorithm produces the final path mesh for the section. Vertices are altered according to the underlying terrain height, in order to slightly follow the terrain.
Plot Discovery
Plot creation ties directly into section path planning. After the proper paths have been found for the section, the remaining non-path areas of the map are ‘discovered’ and used for ride plots. To discover plots, an algorithm flood fills the map/array until each cell is full, tracking when a new/unconnected area of land has been found.
The image below demonstrates what the 2D representation of the section looks like after placing paths and identifying a handful of plots (indicated by varying colors):
Once plots are found, grids are spawned in world space accordingly, to denote to the player that those areas are for placing rides:
Plot Validation
This general discovery approach works pretty well, though as with all procedural generation, there were some weird quirks for some seeds. For instance, in the below screenshot, there is a small section of a generated plot which is just a little bit weird.
Beyond unexpected shapes, occasionally a plot would not have enough area to actually be built on. In order to use a bit of math on whether not a plot was buildable, the plots are converted from their 2D map/array representation into appropriate Polygon classes. The Polygon class handles calculating a shape’s perimeter distance, its area, etc. This allowed us to simply filter out plots that were too small to be built on.
In order to determine how “strange” the polygon shape was, I relied on using some formulas that are actually used to determine the degree of gerrymandering in a given political district, which I thought was pretty neat. The following graphic gives a quick visual summary of how the Polsby-Popper formula can be used in our situation:
Using a handful of rules based on the polygon area, Polsby-Popper measure, and Schwartzberg score, we are able to quickly determine if a plot is able to be built on, or if it matches the general design aesthetic/compactness we were aiming for. Invalid plots can be filled using the Foliage Manager to produce areas that look a bit more ‘environmentally interesting’:
Handoff to Foliage + AI systems
From here, the Foliage Manager and AI Manager begin working in tandem to wrap up the world generation and prepare it for the player to enter the game.
Related Posts
-
TPS: Terrain Generation
Generating a 3D terrain utilizing layered Perlin Noise and Marching Cubes. -
TPS: Foliage
Using the Poisson-Disc algorithm to place grass and trees into a virtual world. -
TPS: Park Guest AI
Utilizing flow fields as a means for pathfinding to support hundreds of agents at a time. -
Catan, Tablet Edition
Highlighting some work on UI interactions and juice for a digital version of the popular board game.