WorldBuilder - Code Overview

Introduction

This is an introduction to and overview of the code for the WorldBuilder application. The intended audience is (ideally Java) programmers who are interested in understanding the design and operation of this tool.

The descriptions are presented in three parts:

History

The development of this tool was motivated by Christopher Kampe's observation that, in RPG development, the creation of the underlying maps had a relatively poor cost/value performance. He wanted to make it easy for game developers to start with realistic maps, atop of which they could add their more creative and interesting features and encounters.

This program is majorly inspired by the Martin O'Leary's Uncharted Atlas project. His Terrain Builder is a JavaScript Web-app to synthesize pages of a fantasy Atlas. The WorldBuilder is Java application to enable game designers to create 3D regional landscapes that can be exported as maps for a variety of computer-based Role Playing Games (starting with RPG Maker). While these goals have very different scopes, calling for rather different approaches, this program still draws heavily on several of O'Leary's insights:

The evolution of this tool has been driven by a combination of Mark Kampe's architectural thoughts (about how to structure geo-physics simulations and plug-in RPG-map exporters) and Christopher Kampe's experiences (with how to make a more usable tool for creating satisfying worlds). After studying O'Leary's work, I came up with my own (surely personal) prime directive:

I will not attempt to defend this decision, but it strongly guided all subsequent decisions.

High-Level Overview

To greatly over-simplify, this program can be divided into:

The classes that create and operate on Meshes of Voronoi points are Mesh.java, Mesh.Pointjava and MeshPointHasher.java. The set of MeshPoints that define the world are stored in a Mesh array. Their attributes (e.g. altitude, soil type, water flow) are stored in parallel arrays (e.g. Map.heightMap, Map.soilMap, Map.fluxMap) ... all of which are accessed through their common MeshPoint index.

There are several different map renderers, one for each major attribute:

The mapping from a (sparse and irregular) Voronoi mesh to a (dense and continuous) 2D map is greatly facilitated by the Cartesian.java interpolation of values from surrounding MeshPoints as chosen by (sub-classes of) Vicinity.java. The overall orchestration of creating a display from all of these independent layers is managed by (the largest and most important class in the program) Map.java.

Many decisions about resource placement or which (exporter) tiles to use to represent a region are based on MeshPoint (or tile) based bidding rules. The base class for these rules (used for Mineral, Flora, and Fauna placement) is ResourceRule.java, which can be extended by exporter-specific sub-classes like RPGMRule.java and OverlayRule.java.

All Exporters implement a standard interface, and a common export orchestrater creates a series of 2D per-tile maps which it pushes to the output-format-specific implementations.

The main-screen menus and controls are put-up and responded to by the main class (WorldBuilder.java).
Simple operations like saving updated maps and loading new ones, it handles directly. But display and update operations are handled by creating new interactive dialogs in one of the sub-dialog managers:

These put-up and respond to their own widgets, but on-map selection (e.g. of lines, rectangles or groups of MeshPoints) is handled by Map.java. The actual map/attribute updates are made by the update engines (TerrainEngine.java, AttributeEngine.java, TerritoryEngine.java), which update the per MeshPoint arrays and use Map.set functions (e.g. Map.setHeightMap() or Map.setSoilMap()) to give effect to the new values. Most of the same operations can be initiated through the script interpreter (Script.java).

The most complex (and only barely under control) modules are probably the Drainage and WaterFlow classes, which use rainfall and topology to compute water flow, erosion, deposition, and lake boundaries.

Most program parameters are read-in and accessed through the Singleton implemented by Parameters.java.
When a map is read in (or written out), this is done by the read() and write() functions in Map.java.

Key Classes and Operations

The worldBuilder application is moderately large (over 10,000 lines of code spread over a few dozen modules). The high level class structure can be (crudely) summarized by a few UML class diagrams.

Mesh and Map-related Classes

The first class diagram shows the main WorldBuilder class, the awt and swing GUI classes it builds on, and the Map and Mesh classes that support the MeshPoints on which the map is based. Note that the only Map methods shown in this figure are those involved in basic map creation.

Mesh Creation

O'Leary observed that if we create map points in a rectilinear grid, deformations tend to retain that (unnatural) rectilinearity. This problem is elimnated if the map points are placed at random. Truly random points exhibit unattractive degrees of sparse-ness and clumpy-ness. O'Leary evens this out by a few iterations of connecting points into a Voronoi mesh and then choosing, as new points, the centroids of those Voronoi polygons. We use a Voronoi library to assign three neighbors to each point and create the desired Mesh.

Simple Dialog Classes

The second class diagram shows the simpler (non-point-attribute-editing) dialogs and the primary Map class functions they use.

These are all very simple dialogs. Some of them (e.g. PointDebug) simply display the attributes of a selected point. Others simply update parameters (e.g. WorldDialog adjusts the latitude, longitude and size of the world map). The most complex is probably the ZoomDialog, which allows a sub-region of the world map to be selected, and uses the Map.setWindow function to cause the displayed map to zoom into the selected sub-region.

Point and Region Selection

The Map class is a Mouse and MouseMotion Listener, interprets mouse actions as selection attempts, and indicates the selected points/areas on the currently displayed map. Any dialog that needs to know about point or region selections can register as a MapListener and receive call-backs in response to selection actions. They can also use the Map.selectMode() and Map.checkSelection() operations to enable the desired selection mode (e.g. point, line, region) and query any selections that may have already been made.

Terrain Editing Dialog Classes

The third class diagram shows the attribute-editing dialogs and the Map selection and get/set functions they use to update the MeshPoint attribute maps.

The operations in this richer set of dialogs (a) update point attributes and (b) drive refreshes of the displayed map to show the updated information.

Attribute Maps

As random points in a 2D space MeshPoints are not very exciting. What makes them interesting is the collection of attributes associated with each point. As mentioned previously, each MeshPoint has a stable index in the Mesh array, and the MeshPoint attributes are stored in series of parallel arrays:

The attribute update engines load the appropriate attribute maps from the Map class, update them according to the specified operations, and then pass the updated values back to the Map class.

Displayed Map(s)

Whenenver attributes are changed the awt.repaint() method invoked, causing a call to Map.paintComponent().

There are many different attributes for each MeshPoint. Which will be displayed is controlled by calls to Map.setDisplay().

When the call is made to repaint the map, Map.PaintComponent will:

  1. decide on the dimensions of the (to be updated) map.
  2. create a Cartesian interpolation matrix to compute the values at every pixel from the nearest/surrounding MeshPoints.
  3. go through the display-enabled attributes, using the appropriate map-rendering class (e.g. AltitudeMap or RiverMap) to compute the attribute values for every pixel on the map and generate the appropriate display updates.
  4. if any selection areas are to be highlighted, add appropriate rectangles, lines or point-halos to indicate them.

Export Classes

The final class diagram shows the Export related classes. (that handle raw JSON, RPG Maker, Object and Foundation maps).

Notes on hydrological simulations

The classes involved in hydrological simulation are:

I started out trying to use real physics for erosion and sedimentation:

but the results were disappointing:

I have seen much higher resolution erosion/deposition simulations, performed by GPUs on a much denser Cartesian grid. The results were very beautiful, but require many orders of magnitude more computer power (to do anything), and lack the (very satisfying) irregularity that emerges from points on our (very sparse) Voronoi mesh. The erosion/deposition models used by those simulations were much simpler than mine:

I was impressed by the simplicity of these models, and incorporated some of those lessons into the above solutions. But (O'Leary's insight) performing all topographic operations on a (manageably small number of points) Voronoi grid is fundamental to how this program works, and moving to an entirely (much finer grained) Cartesian model is a different program.

Issues

MeshPoint to Cartesian Conversion

A Cartesian map specifies, for each square in a Cartesian grid, a list of surrounding MeshPoints and their distances from this square. This enables us to interpolate per-Cartesian-square values from a list of per-MeshPoint values. The interpolation process is trivial (simply the inverse-distance-weighted average of the values for the surrounding MeshPoints). The hard part is figuring out which MeshPoints are the surrounding ones.

The most obvious answer, the nearest N points, works well for (relatively continuous) functions like altitude and rain-fall, but poorly for lake boundaries (which are a discontinous function of altitude). For these, a better result is obtained by using those MeshPoints that define the Voronoi polygon within which the Cartesian point lies. But, sadly, values inferred from the enclosing polygon experience significant discontinuities at the polygon boundaries. After considerable frustration I decided to:

The Polygon constructor and nextPoint methods attempt to enumerate the surrounding points by:

This works reasonably for points that are within the Voronoi mesh. But for points outside the edges of the mesh, there is no surrounding polygon, so the above works badly. This results in attempting to interpolate values from (poorly chosen) non-neighbors, giving rise to strange altutudes and water bodies near the edges of the map.

If we knew that a point was outside of the mesh, we could probably interpolate reasonable values by considering only the one or two nearest MeshPoints. But how can we know whether or not a point is outside the mesh (or inside a computed polygon)? The problem of point in polygon determination turns out to be a fairly expensive one ... and we need to solve it for a very large number of points (every time we zoom, sub-region, export, or define a new mesh). The Vicnity.outsideMesh function uses a few cheap heuristics to recognize more obvious cases ... but there are points near non-convex outer borders that are not recognized, and therefore still interpolate badly.

The problem is relatively minor, in that it only happens to non-ocean points at the outer-most edges of the map ... and is only then noticable if there is wide range of altitude and land/water variation among the dozen nearest MeshPoints. Most people will never encounter it, and those who do are unlikely to notice it. But, in the interests of correctness ...

Musings

A reasonable map will be based on thousands of MeshPoints. Computations on those (relatively few) points are simple and efficient (thank you Martin O'Leary). But ...

A lesson I seem to have learned (from a cruel Hydrological master) is that more realistic world simulations add a level of detail that will (in most cases) never be noticed when the resulting world is exported for use in an RPG. Would this really justify another few thousand lines of code, making the rule-sets even more complicated, and making rendering and export even slower? The answer surely depends on our audience and their goals ... which at the moment, are purely hypothetical :-)

My greatest regret about the current code is the combination of complexity and difficulty of testing ... which often results in unexpected consequences of seemingly simple changes:

But ... Thus, we can do a fairly reasonable job of base engine testing by:
  1. writing scripts to perform all of the various types of terrain and attribute editing operations.
  2. save the resulting map, and then read it back in.
  3. carefully examine the graphical output and point attributes resulting from each of these tests to ensure that the correctness of the restored map.
  4. use that saved map as Golden Output, against which we compare the results of future test runs.
  5. divide tests across multiple scripts so that the addition of a new test does not invalidate golden output for previous tests.
We can similarly test exports, by starting with a fixed and content-rich map, exporting it in various formats, and manually confirming the correctness of each export.

This process isn't ideal, but it will warn us whenever code changes result in a different set of per MeshPoint attributes, or a different translation of those attributes into a Cartesian grid.