MistDominion Map Demo

An exercise in rebuilding an Infinite World Generator for RPGs and 4X games by KaynSD for Procjam 2016

Controls

WASD; Move Character / Camera
Mouse; Click to Create a new Zone under pointer
Q; Switch from Camera to Player Control

What is this?

An example of the finished result that this generator currently produces

This is a Javascript port of a prototype infinite world generator that I am intending to use for an empire building strategy game named MistDominion

MistDominion

In MistDominion the player is a monarch of a small nation that has been in it’s entirety spirited away to a shadowy realm of endless shadowy mists that create barbaric monsters led by the Forces of Evil.

As the player sends their agents to explore the mists, they uncover new areas and fortresses controlled by the Forces of Evil, and by liberating these locations with their slow moving armies or quicker moving parties of Heroes they can attain the items required to return them home.

Further exploring the mists they will uncover other nations that have been swallowed into the Mists, and will be able to ally with them to fight against the Forces of Evil, or may find they have already been subverted and must conquer them.

Challenges

The fundamental appeal of a traditional Empire Building or 4X game is to conquer an entire map, or to carve an empire of your design into the game world. But for this kind of game, the main challenge is defending your ever expanding frontier whilst racing to find the next story treasure that will grant you a reprieve from the invading armies.

This means that a world that has conventional borders or could be entirely conquered is not going to be adequate for this game; if a player can conquer the entire world, there would be no places to place new unknown territory for the player to explore for the next part of the story, or for monsters to be spawned from. This will mean the world needs to take place in an infinite plane that can not feasibly be explored by a player in a single play through.

However, a conventional infinite world generated with height-map created from a noise function would not give fine control over elements of the world, finding areas that can be defined as new countries, districts or subcontinents to explore. In addition, a noise function may not be able to generate locations that are practically reachable by a player’s forces.

Proposal

What is needed for this kind of game is a solution that can build a world of indefinite size, but also generate blocks of it at a time, bolting new wholly formed countries and areas (that most importantly, can always be reached by the player) as the player explores them, or when the world needs to generate them. I define these wholly formed areas as Zones, and liken them to areas in an MMO; a Zone should be an area with limited exits, possibly a coastline, and of a similar climate throughout with a few cities and connected roads that connect it to other Zones.

The smallest area of the world is defined as a Tile; a single integer point on the world with knowledge of it’s terrain, resources, forces within it. These tiles are then gathered into Chunks which form the general molecule for world generation. I’ve found that a Chunk of 8 x 8 tiles works well for the following system. These Chunks then can be assigned to a single Zone, and inherit its behaviours, climate and landscape from there.

How does it work?

Tiles, Chunks and Zones are stored in a hashmap in memory. If the game requires a new Zone generating, be it because it is spawning a plot device in a “distant kingdom many days travel to the West”, or because the player has sent an agent into territory that is currently unknown, the world adds a Zone at that location, starting whichever generation it needs to with a new Chunk at that Tile’s location. It then goes through a series of steps to carve an entire landscape into being, starting with rough shapes, determining its coastline and mountains, applying some noise to those and attempting to sculpt geological features into it.

Since these steps are modular and alter Zones from a less definite to more definite step as they progress, any step can be removed and replaced as they need be, allowing different Zones types to be generated, predefined ones to be spawned into being during stories, and for anything that is generated that doesn’t match the game’s requirements to be rejected and the process to be restarted.

Zone Creation by Recursive Quadflake

The first step needs to assign at least one Chunk to a Zone. Whilst any step could be used (simply carving out a square block, or pasting in a pre-existing design that will fit could work), to give organic feeling zones, in this demo I am creating fractal patterns with Koch Curve implementation named a Quadflake.

Starting with the center Chunk and an n value, the new Zone attempts to assign itself a square of new Chunks with the initial Chunk in the center (or on one of its edges if that would be more suitable), of an area of n x n chunks. All possible new Chunks are added to this zone, and then on each edge of this square, this assignment of new chunks run again, with an n - 1 value.

This creates a fractal pattern in a snowflake design of four smaller squares attached to a larger square that in itself is one of four patterns attached to a larger square, all the way down to n = 1. Chunks that were already part of other zones are not assigned here, and as the world expands and turns back in on itself there will be times when the algorithm stops early as it finds itself expanding into already defined areas. This recursive algorithm can be performed at any n value, but generally sizes of 3 - 5 fine tune the balance from allocating interesting areas, without creating Zones that are unfathomably large

Finally, to stop there being many small leftover areas, every prospective new Chunk not yet assigned that would border any of the eight cells along any of the new Chunks are checked for how many existing Chunks there are as neighbours; any of these hypothetical Chunks with six or more existing neighbours are also added as part of this Zone

A quad-flake allocation example — In the above image (at 50% size), a starting area has been built with the above koch-curve quad-flake process, recursively adding squares. Starting from red with a size of 3 chunks and travelling through the spectrum to purple, squares of smaller chunks are added to the edges of their parent squares at a random point along their edge where possible. Squares in grey are then added through the orphan adding process also added above.

Geology assignment and Border Controls

As part of the game's overall design, chokepoints between these Zones are important, as is designing the world to be a series of islands in the mists, and for this effect it's important that mountains and coastlines are developed

For the sake of simplicity, Zones are allocated one of four types of Geology, which determines its borders and its geometry, as well as the Geology of future Zones created that border it

Upland Zones are entirely bordered by impassable tiles representing mountains that tower into the sky. They can not be created if any Zone bordering it is of the Ocean or Coast I type, and do not like spawning next to each other (80% chance of rejection). The starting Zone is generally an Upland Zone, as is any Zone created in isolation that is not specifically requested otherwise.
Coast I Zones are the most common, and are generally created bordering Upland Zones. Edges of tiles in these Zones tend to be water. They can be created under any circumstance next to any neighbour.
To give a little space in the map between islands, Ocean II Zones are fundamentally the same as the Ocean Zones but are built only when their neighbours are entirely Ocean I.
Coast II Zones are landing spurs that look and behave identically to Coast I, but because they are named differently allow for Upland Zones to be built neighbouring them. They are only allowed to be built next to Ocean II Zones, and take priority over Coast I Zones meaning they'll be the first place encountered after trekking across the ocean.

The new Zone analyses all of it’s Chunks, and checks for the status of their neighbours. After checking what Zone types already border it, it assigns its geology based on the rules above, or by specific fiat if something is demanded by the game (a Zone featuring an underwater palace, for instance, would always have to be built as Ocean, regardless of what the logic of this system would dictate)

Example of the Geology allocation as stated above — An example of the basic rules above, with the player travelling from Uplands, to Coast I, to Ocean I, to II, to Coast II and finally back to Uplands. These are fairly simple cases that only have to deal with a single neighbour; a majority of cases will need to analyse every single neighbouring Zone a new Zone is in contact with

By tweaking which geology can be positioned next to each Zone, the world naturally creates an archipelago that is unveiled as the player explores, creating parts of an island as they explore

A more complex illustration of the geology forces at play — From a further explored map, showing how some of the Zones can be built against each other forming long, Caribbean chain style archipelagos. Since the order of these Zones creations are entirely at the whim of how the player explores the game, they can have a direct influence on the map of the game they explore in this prototype. Uplands zones are in green, ocean and ocean II in blue and dark blue respectively, and coasts are in brown and dark brown.

Borders are then assigned on a per-chunk, per-border basis. For any chunk that borders any previously made Zone, the appropriate border of it mirrors its neighbour. Any chunk border that borders another chunk in the same Zone sets its border to an internal flag.

Colour coded border configurations — Zones colour coded by spawn order (Red through Purple), with their borders of mountains (brown) and coastline (blue) obviously highlighted

For Uplands or Coast II Zones, a list of edges of chunks that border no current Zone is made, and from each of the four lists (one for top, left, right and bottom), a candidate (or in some cases, the candidate or no candidate) is chosen to remain open. For shore Zones, any chunk that is bordering a mountain tile already and knows that it too has a border that no Zone is currently filling leaves that slot open as well, allowing the island to be circumnavigated around it's mountainous regions. Ocean Zones (both types) simply force themselves to be oceanic borders regardless of where they are.

Finally borders for anything not assigned yet assumes its default; mountainous and impassible for Uplands, water for any other Zone.

More refined edge creation — Borders shown and allocated for areas per zone type

Roughing Up the Borders

Roughing out the edges of Chunks so that they do not simply resemble squares in space with single thickness Impassible Mountains or Coastlines is a fairly simple process; along each edge that is defined as sea level in height or an impassible mountain, extend the borders out along a 1D Perlin or Simplex noise function; extend the border out to (Half the Chunk Size - 1) x (Perlin Noise at that tile’s point)

Border roughing at low and high chunk sizes — Adding extra mountain tiles to borders of cells with similar simplex noise functions. On the left, with a chunk size of 8, on the right, a chunk size of 20. Regardless of chunk size, the effect looks smooth.

Afterwards, along any chunk modified in this way ensure that none of these new extra Tiles forced to be mountains or ocean are getting in the way of Chunk borders that lead to other zones; the easiest way to do this would be to simply carve any cells back but this looks artificial. I settled on carving in an hourglass shape - wider perfect borders at the actual border, and then tapering down the accessible area as it progresses into the center of the zone.

Allocating Heights and Topologies in Zones

The most difficult problem I face with this method of subdividing a concave, arbitrary but fixed sized area is ensuring that the areas meet when height maps are carved into them. Following a self imposed rule that every tile that is not specifically marked as impassable MUST be connected and reachable by the player means that randomly allocating a height map with perlin noise runs into a similar problem described by Rune Skovbo Johansen on this Gamasutra article on Functional, Simulational and Planned approaches to Procedural World Generation; namely that given random generation, unless great planned care is taken there will come points where topologies will be generated that can not be navigated to by the player.

A basic rule I wanted to follow was that a character in the game can path to any adjacent tile that is either one unit higher, one unit lower, or the same height as the tile they are currently standing on. But given that rule, how can I ensure that all Tiles are connected and traversable, and that all zones can be connected to each other at their fixed Traversable points? And as an added constraint, how can I ensure that all Coastal zones flow to at least one sea level height tile at the water, allowing for the player to reach the sea to deploy boats from?

This problem has for the most part had this generator sit in limbo for about two years, and this Procjam period was meant to be used to find a solution to the task. The first revelation I had was that I could force all Coast and Coast II borders to path to one point on the shoreline, and have all of it’s borders to other Zones (be they Uplands or other Coast or Coast II at a fixed integer height. However, I could not find a way that reliably allowed a smooth pathing from this fixed height borders to the shore line or to each other. Arbitrary room splitting and pathing with Prim's Algorithm, Drunkard's Walks, Gradient Flood fills; all have been considered but none quite get it correct 100% of the time or work within a Polynomial timeframe, and this reliability is mandatory for a game that can not afford to have any malformed zones.

For now for this 2D implementation I have simply split the Zone randomly, connected each of these splits with Prim’s Algorithm. The cells on transitions to other Zones, as well as each body of water on the coastal areas is also defined as a node on this minimum spanning tree, ensuring every tile throughout the entire Zone is connected. I am actively searching for a new implementation, that will allow for a better implementation in 3D, but am running out of ideas.

If anyone has a solution, or wants to help out with it, I can be contacted on my Twitter account.

Roughly adding some "height" to the zone — Creating a new zone, and then it’s split into multiple areas that uses a Minimum Spanning Tree algorithm to connect up the borders, an allocated Shore area, and all the other areas so that it connects appropriately, but not realistically or with much grace

Future Plans?

Expanding the Algorithm

Once I have a working allocation for height allocation, building rivers that flow from high to low areas would make for an easy addition. Adding roads and city sites and fortress locations (which sit near them), and dungeons (that are far away from them) is also a necessary step.

Biomes, in the form of heat and rainfall determining the ecological landscape of the area is also something to work on. Rather than basing it on rainfall and heat maps directly however, basing the biomes on neighbouring zones would need to happen so that the world did not go straight from tropical rainforests to polar regions. Using the Whittaker diagram for Biomes as a starting point, potential biomes can be allocated based on a similar algorithm to determining Zone Geology; analyse neighbours for their current types and select one that is in common for all of them. Allocating Oceans as a Wild Card that can function as any, plus putting them all next to Temperate climates will guarantee that something is selected, and a range of values can be expected, divided by less extreme climates.

After a biome has been selected, adding vegetation and wildlife would make sense; and using some kind of cellular automaton system to spread the growth of forests inside the biomes would allow a general solution to be made that could allow for some interesting, yet natural appearing forests.

Finally after all of this, the inhabitants of the cities would need generating; their rulers and citizens and their own armies and adventurers would need to come into being, and their cultures extrapolated from the landscape. Warlike nations may also need for extra zones to be created in advance allowing them to be at war with a yet-unmet faction.

Other Games

This engine would work well in building a fixed RPG universe; placement of zones that must exist for the player to reach (such as quest objectives) can be placed arbitrarily in the infinite void, and connected together with new arbitrary zones to adventure through can be done before gameplay starts, or as they approach the as yet ungenerated zones, comfortable in the knowledge that the world will have a connection to the goal areas at some point.

Credits

Built between 28th October and - 13th November for Procjam 2016

Built by Keith Evans (@KaynSD on Twitter)
Art Pack by Chicmonster, available at Procjam 2016 Art Page
Running on Phaser and PIXI.js
Thanks to everyone in the Procjam Discord room for bouncing ideas for solving my Heightmapping problems (especially Vitally, Hectate, GrandTrainDelta, Sparrow and Thaumazo)