DEV Community: Will Ricketts

Rhea's Galaxy Map

Will Ricketts — Sat, 15 Feb 2020 18:21:17 +0000

In the last post, I covered the various game titles and mechanics they utilize that I've drawn inspiration from for the design of Rhea. In covering Rhea's galactic map, I'd like to focus upon two of them heavily-- Eve Online and Stellaris.

Inspiration

Eve Online and Stellaris have very similar map systems. Both have solar systems represented in a DAG-like structure. The DAG's nodes represent solar systems. In the case of Eve Online, this structure's edges are representative of Stargates, and in Stellaris, warp lanes between solar systems.

In any case, both systems function in a similar way, in that players and their fleets traverse a large DAG to move around the galaxy.

Stellaris

Based on a system of ephemeral matches, Stellaris's game maps are generated uniquely for each. Thus, each time the player creates a new empire or species and starts a game, a new map is generated and configured via the player's selected settings when creating the game.

One of the major strategies when starting a game of Stellaris is to rapidly expand to claim and build defenses around choke-point systems, or systems that have many connections as to control the flow of traffic through that portion of the map. This is a side-effect of this galactic map model that I'm intent upon creating.

Eve Online

Eve's map is persistent, in that the game has no concept of "rounds" or "matches." The game map, save for additions by their publisher, has and will remain the same since the release of the game in 2003. Being that the intent of Rhea is to be a single persistent game world, this is the path I've elected to follow.

Some very desirable but non-obvious effects arise from this kind of model for a galactic map. With a static map, various regions or sections of it become known within the playerbase for being better or worse to own from a strategic perspective. Eve has regions of the game that are notoriously difficult to invade, and has a few that are notoriously favorable for an invading military to stage their assets.

Generating the Map

Creating a map of this size and detail was a challenging problem to solve, and at the time of this writing, still presents obstacles to overcome to achieve an optimal map structure.

First Attempts

When I first sat down to work on figuring out the most immediate challenges in building Rhea, my intent was to get something simple working and then expand upon the idea later. Upon researching how I would go about generating a map of this nature with DAG-like properties, I found Astrosynthesis, a piece of software used for generating celestial structures primarily for role-playing games and hobbyist world-building. This program had a bunch of great features that'd be useful for my needs, but two features stood out in particular. Astrosynthesis has a user-created plugin ecosystem and an XML exporter.

Before long, I had a galaxy containing ~20 solar systems and connections between them, which I exported to a large XML document, which I was able to load into the Elixir-based backend of Rhea with elixir-XML-to-map.

Using the Data

From this very large map, I perform a series of mutations on the data to order it into a list of Solar Systems and one of Gates. With these lists, I first created a DB record for each of the solar systems within PostgreSQL. With a SolarSystems table populated with data, I would need to represent the data somewhere that graph-oriented data feels right at home. This is where Neo4j comes into play.

If you're unfamiliar, Neo4j is a graph database. This turned out to be the perfect tool for Rhea. It was immediately apparent that its Cypher query language had the features needed to power several in-game systems for Rhea. Namely its ability to find the shortest path between nodes, or in the domain of Rhea, solar systems.

Claiming victory over my first set of development goals, I took a 2-month break from working on Rhea to focus on a large project I was leading at work, a large web service responsible for creating and marshaling Twilio conference calls in parallel-- also built using an Elixir umbrella, also structured with the intent of utilizing BEAM's distribution features in the future.

When I finally had time to devote to Rhea again, I revisited the map I'd generated and simply wasn't happy with the result. After generating entirely new map data, this time for 2000 solar systems, I was dismayed to learn that the XML schema for my new map data was fundamentally different than that of my previous map. This would require me to write an entirely new parser and process for loading the map data into PostgreSQL and Neo4j. This was unacceptable to me.

Not being comfortable with the idea of such a pivotal piece of the system relying upon a proprietary dependency, I started exploring ways of generating my own map from scratch, but how?

Enter Diffusion Limited Aggregation

A while back, I was reading about Brownian Motion and the aggregation of particles to form a structure. After diving back down that rabbit hole, I discovered Diffusion Limited Aggregation. This seemed to be the ideal method for generating a structure akin to the galactic maps of both Stellaris and Eve Online.

I found a simple C++ implementation of DLA and quickly generated a set of 2000 particles. This algorithm has a CSV output of the following schema:

id, parent_id, x, y, z
0,-1,0,0,0
1,0,0.934937,0.354814,0
2,0,0.0525095,-0.99862,0
3,1,0.989836,1.35331,0
4,3,1.92472,1.70826,0
5,3,0.65572,2.29584,0
...

EUREKA!

That was precisely what I needed to generate a fully original map! I built out each point as a Solar System in Postgres and Neo4j with its coordinates. After reducing the list down to a collection of IDs and Parent IDs, I was then able to build the stargates that connect the various solar systems together.

Originally, I built a name generator to automatically name each Solar System, but this was quickly outgrown and I was once again searching for a solution to unblock my map work.

After finding a super slick name generator built in Javascript, I was able to give each solar system a unique name that doesn't sound like a Heroku deployment.

Below: the final structure of my fractally generated galaxy map:

Below: a closer view of a group of solar system:

Future Plans

Having a totally original galaxy map with a predictable and repeatable process for generation opens up all sorts of possibilities for new features and clever tricks. Having tied all of the generation and persistence process to a single function in the backend, rebuilding the map and trying generation with different inputs takes a matter of seconds::

def build_universe do
  construct_map_db()
  construct_graph()

  IO.puts "Universe created"
end

# I couldn't resist writing a function called "destroy universe"
def destroy_universe do
  [{:ok, _}, _] = [Task.async(&Main.destroy_map_db/0), Task.async(&Main.destroy_graph/0)] |> Enum.map(&Task.await/1)

  IO.puts "Universe destroyed"
end

Wormholes

If you're familiar with graphs, then you were probably left wondering why I refer to Rhea's map as a directed acyclic graph as opposed to an undirected acyclic graph. Rhea's stargates are represented in its persistence layer as pairs of gates, each unidirectional. This enables me to, at some point, build a wormhole system in which a player's fleets can travel from one part of the galaxy to another instantly, but perhaps not return home through the same wormhole.

Tactical Structures

Perhaps I'll introduce a player owned structure that prevents enemy fleets from leaving a Solar System once they've traveled through a stargate. This would lead to a much more robust system of player combat tactics and provide an overall more engaging experience, possibly allowing the few to overcome the many in a fleet engagement.

Next Steps

The map is far too linear, and this needs to be fixed before proceeding. This is my primary development item on the project, and I'm currently working on an algorithm that utilizes Solar System coordinates to create connections between solar systems that share a geographic region with one another. I assure you that will get its own blog post :)

For now, I'm happy enough with my work to begin sharing the obstacles I've overcome in building the game I've always wanted.

Thanks for reading, and I'll see you in the next post.

Introducing Rhea

Will Ricketts — Fri, 14 Feb 2020 06:01:23 +0000

Over the last several months, I've been working on the backend for a lofty project. While not that much of a PC gamer, I generally focus on two types of games:

Grand Strategy / 4x (explore, expand, exploit, exterminate)

Sci-fi Sandboxes

Eve Online
[the idea of] Star Citizen (lol if it ever comes out)
Planetarion

Aside from Star Citizen, due to the possibility of it being vaporware, all of these titles have been staples of the last several years of PC gaming for me-- especially Eve Online, Planetarion, and Stellaris.

Each of these games have unique characteristics that I really enjoy, but I've always thought about what it would be like for a game to incorporate all of them in harmonious union. Eve Online's metagame, political intrigue, complex player-driven economy, and expansive universe create an immersive third person experience with an extremely high skill cap. Stellaris focuses more on developing and scaling an empire from the perspective of its leader. Planetarion shares with Stellaris its perspective, but is a tick-based game played largely in text within a web browser, making it extremely portable and not totally married to a client with its own specific system or platform needs. To distill these properties into those that inspire the dynamics of Rhea:

Eve Online

Persistent universe
Player-to-player political intrigue
Player-driven economy
Robust industrial system

Stellaris

Played from the context of the leader of an empire as opposed to Eve's perspective of a single pilot in a large universe
Player-driven relationships with NPC factions

Planetarion

Can be played in the browser
Tick-based

Whew. There's a lot to unpack there. Suffice to say, I've had a bit of difficulty describing the project in a brief way that's easy to understand for someone who's unfamiliar with these three titles, so I've taken to describing Rhea as "a tick-based 4x space conquest strategy MMO." Most people are familiar with terms like "MMO" and "space conquest," though a bit of this might take some explanation.

The tick system of Planetarion is very different than the temporal systems of most strategy games, in that a "tick" takes place every hour. A tick consists of all of the calculations required to update the game's state for the next hour. Player resource balances are updated, fleets are moved based on their course, and combat outcomes are calculated. This allows the game to be played over a longer period of time in which the players are able to set up actions to be performed, and the system will execute them over time. The player is able to note when their attention will be needed next, and can return to the game upon a tick in which they want to perform their next action.

The Game

Map

Rhea's map is in essence, a giant DAG (directed acyclic graph) with solar systems represented as nodes and the stargates that connect them represented as the edges between those nodes.

This is not unlike the maps of all three games I've used as examples and inspiration for Rhea. In my view, it's a great system, so I'll borrow from their developers' wisdom. The interesting difference in Rhea is that the Galaxy, in its current working model, contains 2000 distinct solar systems.

Check out an extremely early-stage rendering of Rhea's game map here (edit: temporarily removed, under rework). Also to note is that this is not the final structure of the galaxy, as it's simply the initial result from being fractally generated. There's still plenty of work to be done in transforming the structure to have more interconnectedness and to be less of a corridor and chokepoint heavy layout.

The Player's Position in the Galaxy

When the player creates a character and enters the game, as of the time of this writing, they are provided a basic ship, are given some basic resources for expanding their wealth and influence, and are dropped into the game in a central area of the map in which they cannot be attacked by other players. This is a concept that was inspired by Eve Online's idea of "high security space" or "hisec." This is essentially an area of the game that's PVE (player versus environment) only in which attacks on other players are disabled. The player has the freedom to exploit the very basic resources in this area and eventually equip themselves to venture further away from the galactic center in pursuit of greater wealth or conquest.

Players are able to claim space as their own, colonize planets, build facilities on orbital bodies that exploit their resources, and build defensive structures to stave off attacks and raids from other players or groups of players.

Players can form organizations with other players, are able to claim solar systems on their behalf, and can go to war with other player organizations for any number of reasons-- from conquest and annexation of their enemies' sovereign space to a simple raid over an enemy's borders to pillage resources from an orbital facility.

The Codebase

I've chosen Elixir for the backend implementation of the various game services due to its wonderful ability to handle i/o bound operations with great efficiency. I also believe using a functional language is wise for building a "tick" system as a tick itself is basically a process of performing a large mutation of externally held state (PostgreSQL) in a predictable and repeated way.

Structure

Rhea's backend, in its current state, is built as an Elixir umbrella with a few sub-apps handling various aspects of the game, such as its public api, persistence layer, galactic map (more on this part of the project in later posts), and a general orchestration layer, main.

Aside from main, each of these sub-apps exposes an interface to its various public functions as to prevent cross-application coupling:

defmodule GalaxyMap.Interfaces.Importers.MapGraph do
  @moduledoc """
  Interface for Map Graph importer
  """
  alias GalaxyMap.Importers.MapGraph

  defdelegate run(solar_systems), to: MapGraph
  defdelegate clear_graph_data(), to: MapGraph
end

Temporal Features

Rhea leverages the Quantum library to handle its various timed jobs, the majority of which take place when a tick is executed (every 20 minutes). Other various temporal features include scheduled statistics gathering, fleet combat precalculation, etc.

Wrapping Up

Rhea is a large project. For a single developer working on it in their spare time, it's a really large project, but it's a game that combines my favorite mechanics of my favorite titles as well as adding mechanics and systems I've always wanted to see in the 4x strategy genre. In essenece, I feel like I'm building the game I've always wanted.

I plan on releasing more comprehensive posts regarding game mechanics, technical implementation, and game lore in the future.

Thanks for taking a look :)