Jump to content
  • Advertisement
  • 07/10/19 12:34 PM

    Tiles to Curves: Fun With Voronoi Graphs (part 1)

    General and Gameplay Programming



    This is a blog about our development of Unexplored 2: The Wayfarer's Legacy. This game features state-of-the-art content generation, generative storytelling, emergent gameplay, adaptive music, and a vibrant art style.


    The content generator of Unexplored 2 generates tile maps. Typical output looks like this (you can read more about our level generator here😞



    These tile maps are stacked, using different tiles to indicate tiles ground types (grass or dirt in this example) and various decorations. In this case there are some bushes (large green circles), Rocks (black circles), plants (small green circles), flowers (white circles), and decorative textures (grey squares). There also are special tiles that indicate gameplay data such as the spawning point marked with an 's'. In addition, tiles can be tagged with additional information such as elevation or special subtypes.

    Tile maps are a convenient data structure for generators to work with. But they also are quite rigid, and often the grid has a tendency to be visible in game. Yet, in our case when the data is loaded into the game and assets are placed the result looks like this:



    I like to think we did a pretty good job at hiding the tiles, and here's how we did it.


    Voronoi Magic

    The trick is that individual tiles are matched to the cells in a Voronoi diagram. Which can be used to generate shapes that are much more natural looking. A Voronoi diagram is created from seeding a plane with random points and partitioning off cells so that each point in the plane belongs to the cell that corresponds to the closest seed point. There are quite a few interesting applications of Voronoi diagrams for procedural content generation (PCG).

    A typical Voronoi diagram created from a random but fairly even distribution of seed points looks something like this:



    For Unexplored 2 we use a different type of distribution of seed points. To start with, we seed one point for each tile. That way we are certain every tile in the tilemap can be mapped to one cell in the Voronoi diagram.

    Now, if you place the seed points in the middle of each cell you end up with straight grid that looks exactly like a tile map (for this image and the others below I also made a checkered version where half of the tiles are rendered yellow so you can see the patterns a little bit better):



    A simple way of making this look better is to simply randomize the position of each seed point. When shifting the points it helps to make sure the point does not move outside its original tile.

    The result looks something like this:



    Better, but very noisy, and you don't get nice flowing lines in this way. It can be improved by 'relaxing' the Voronoi diagram (a standard technique associated with Voronoi diagrams I won't go into here). But it will always stay a little noisy, and it is difficult to effectively suggest shapes on a scale that surpasses the scale of the individual tiles.

    To get around this you need to do is to move the points around smarter than simply using random displacement. Different types of movement have very different effects. For example, using Perlin noise can create interesting curved tilemaps. Or you can turn the whole thing into hexagonal shaped tiles simply by moving every other row of seed points to the left:




    The real breakthrough comes when we start moving around the seed points in particular patterns to create rounded corners. The first step of this process is already taken inside the level generator. Corners are detected between ground types and the corner tiles are marked with different shapes, indicating how they should be deformed to generate a better-looking environment:



    In this case, elevation differences also cause corners to appear in the tilemap. That's the reason you see the extra rounded corners in the grass in the top right and bottom left where slopes were generated.

    The game uses this information to displace the seed points of the Voronoi graph. Each rounded corner shifts the location of the seed point (see image below). In addition, it also shifts the seed points of its four orthogonal neighbors. This process is cumulative; seed points can be shifted multiple times if they are near several corners. However, after all displacement are processed, the seed points are randomized a little (about 10% of the width of a tile in either direction), and the final displacement is restricted to a maximum of 40% of the width of a tile.



    The result is already pretty astonishing:



    But we're not there yet...


    Smart Decoration

    The overall shape is better, but the edges are still very straight and somewhat ragged in appearance. The way we cover that up is by using curved assets placed along the edges where the colors are different. The real trick, however, is that one curve is often placed over two edges, using their relative angles to determine the direction of the curve.



    The result looks like this:



    Next, we use 3D assets to give extra texture to the cliffs:



    And finally, we add the other assets to fill out the level. The placement of these assets is dictated by the level data generated earlier, and in general follows a simple philosophy. We use smaller assets to surround larger ones creating natural and nice transitions. Of particular note is the rocks added to the bottom of cliffs to create more variety and to visually dampen the vertical slopes dictated by the gameplay:


    Local Variation

    The corners are not the only type of displacement we use. For example, near artificial structures (such as the ruined walls below) you want the edges to be straighter:



    In our system, this effect is easy to achieve. We simply introduce a different displacement rule that makes sure that tiles featuring artificial structures are not displaced. The generator uses smaller squares to mark these tiles and the game simply makes sure that all displacements are ignored:



    If you look at the ground you can clearly see how specific areas can be made straight while others curve more naturally:



    Isn't that neat?

    There are a few other rules you can use easily mix in with this technique. For example, we occasionally force the tiles into a hexagonal pattern to make sure narrow paths are wide enough to be traversed. And I am sure we will find other uses for other patterns as well.

    This is one of the many reasons I really love Voronoi diagrams. Another time I will write about how we use them to generate and decorate Unexplored 2 world maps.


    If you are interested in learning more about the game please check us out on Fig.co or on Steam.


    Note: This article was originally published on the Ludomotion website, and is reproduced here with the kind permission of the author.

      Report Article

    User Feedback

    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement
  • Advertisement
  • Latest Featured Articles

  • Featured Blogs

  • Advertisement
  • Popular Now

  • Similar Content

    • By Boris The Brave
      I recently discovered the source code to Diablo 1 has been reverse engineered to a readable state: https://github.com/diasurgical/devilution
      I did a write up of how the levels are procedurally generated: https://www.boristhebrave.com/2019/07/14/dungeon-generation-in-diablo-1/
    • By GameDev.net
      This is a blog about our development of Unexplored 2: The Wayfarer's Legacy. This game features state-of-the-art content generation, generative storytelling, emergent gameplay, adaptive music, and a vibrant art style.
      Part 1
      Unexplored 2 is a roguelite action adventure game where the hero is tasked to travel the world in order to destroy a magic staff. It features perma-death, but when your hero dies you get a chance to keep the world, so you can uncover its many secrets over the course of several runs. In a way, the world is one of the most important and persistent characters in the game. In this article, I'd like to share how we generate it.
      There are several ways in which you can approach world generation for fantasy games. For example, you can use simulation techniques to generate a realistic topography and populate the world from there. Instead, we choose a different approach for Unexplored 2: we used a process where we sketch a rough outline first and try to fill in the map with in a way that optimizes the affordances and gameplay opportunities the map has to offer.
      Rough Outline
      It all starts with a random Voronoi graph with 80 cells placed on a map with a 3:2 aspect ratio:

      Figure 1 - The initial Voronoi
      We use a Voronoi because it has a fairly natural distribution of cells and because the structure can be treated as a graph with each cell being an individual node and each edge a connection between nodes. This is useful as we use graph grammar rules to generate the map.
      In the first step, the cells on the western edge are set to ocean. Then we grow the ocean a little creating a more interesting coastline, and set the remaining cells to be land mass. A starting location is picked along the coast and a goal location is picked somewhere on the eastern side. Each cell in the graph marked with its distance to the start and the distance to the goal. Distance in this case is measured in the number of cells between two locations.

      Figure 2 - Land and Sea
      Obviously placing the ocean always on the west is just a choice (Tolkien made us do it). It is easy to make the whole map an island or have the ocean cover other edges of the map. What matters for us, is that this creates a consistently large playing area. But we don't rule out adding other templates and variations in the future.
      The next step is to make sure that the journey will not be too easy. After all, 'one does not simply walk into Mordor'. The way we achieve is also lifted directly from The Lord of the Rings: we simply make sure there is a mountain range between the start and the goal:

      Figure 3 - A Tolkienesque mountain range
      The mountains are started somewhere close to the goal and then allowed to grow using the following graph grammar rule, which basically changes one open cell into a mountain for an open cell that is next to one (but no more) mountain cell, relatively close to the goal, and relatively far from the starting location:

      Figure 4 - Graph grammar rule to grow the initial mountain range
      Unexplored 2 has a journey from the start location to the goal. In order to tempt the player to divert from the most direct route and explore the rest of the map a number of 'adventure sites' are placed at some distance of the start and goal location. Creating a nice spread of potential interesting travel destinations. Each site is placed inside a region of a different type. In this case, the goal is placed in swamp (s), a haven (green h) is placed in a hill area close to the start, and other sites are placed in a desert (d), forest (f), and a barren area (b). Orange edges indicate the borders between the regions.

      Figure 5 - Adventure sites
      Adding Topography
      The remaining cells are randomly grouped into additional regions until every cell is assigned a region on the map. The terrain types for these regions are left undetermined for now.

      Figure 6 - Regions and rivers
      Next rivers are added to the map. Initially, rivers are allowed to grow along the borders of regions. Unlike a realistic world generation process, we choose to start growing rivers at the ocean, selecting a new edge to grow into at random, favoring to grow alongside mountains as the go along.

      Figure 7 - Graph grammar rule that changes a region border next to an ocean into a river
      After rivers have been added, the region types are filled in and reevaluated. In this case, more forests are added and the desert area in the south is changed into a plain because it was next to the ocean and far to the south (our map is located in the southern hemisphere, hence the south is cold). At a later stage, we might take the opportunity to change the desert into something more interesting, such as a frozen waste.

      Figure 8 - Complete topography
      Once the regions are set, rivers are allowed to grow a little more, especially through terrains like hills and swaps. Depending on their length rivers be narrow, wide, or very wide. Only narrow rivers are easy to cross, for the wider rivers certain edges are marked to indicate points where the river can be crossed.

      Figure 9 - Graph grammar rule to grow a river through a swamp
      Adding Opportunities
      The topography is fairly basics and we still need to fill in a lot of details. From a design perspective regions (not cells) are the best unit to work with in this respect as we want regions to form coherent units in the experience of the game. To make working with regions a little bit easier, the Voronoi graph is reduced to a graph representation where all cells of each region are combined into one single node.
      Based on the relative distance to the start and the goal regions are assigned a difficulty and a number of opportunities and dangers are generated accordingly.

      Figure 10 - Region graph
      At this stage, the generator starts to look for interesting gameplay opportunities. Using several graph grammar rules a large forest with high difficulty will be assigned different attributes than a small, low difficulty swamp harboring an adventure site.
      At this stage, special terrains, such as purple 'obscuri' forests or red sand desert are also added to the mix. When generating the game in the world we have the option to request certain special features such as special rare terrain, or special quest content. These are processed first. To the best of the generator's ability, it might be that no good fit is found, at which point either we need to generate a new or continue without the requested feature.
      One interesting effect is that if certain special terrains require slightly rare conditions to emerge then the terrain type automatically becomes rare content. For example, a special quest might require a large swamp area with a river which will not be present in every world. The downside is that sometimes rarity becomes hard to control or design as there literally is no simple slider to push up if we want to make such a terrain type or quest more frequent.
      Creating Visuals

      Figure 11 - The map as it appears in the game
      Up until this point, the map is all data. The next step is to create the visual representation based on the map. To this end, we generated a new Voronoi diagram with a higher resolution (about 1200 cells) and map each smaller cell to the cells of the original map data. This creates a better resolution of details. Figure 10 shows how to original cells map to the visual map:

      Figure 12 - Original cells projected onto the map
      Individual cells can be raised and lowered to create elevation, and colored and decorated to suggest different terrains. Some of these decorations are assets such as trees which can vary in size and density based on the relative temperature and humidity of each cell. For now, we're using a very simple algorithm to approximate individual climate using longitude, latitude (it gets dryer towards the east), elevation and closeness to water.
      Other decorations are build from simple geometry based on the high-resolution Voronoi graph. This can be easily seen in image 13 below. This geometry includes slightly sloped mountain peaks, elevated patchwork to create the impression of a broken, barren landscape, and sunken centers to create pools.

      Figure 13 - Map detail showing how decorations use geometry based on the Voronoi graph
      Regions and their associated terrain types play an important role in the generation of these details. As can be observed in the figure above, forest rise towards their center, as do hills and mountains. Rivers are never elevated (to save us the trouble of trying to do so consistently). Terrain is blended a little so that height difference are not too pronounced where not intended, and interesting borders are created. In many cases, these blended terrains offer ample opportunities to liven op de map with rare features.
      Setting Up Nodes
      The world is of Unexplored 2 is not a continuous world. Players travel from node to node and can choose (or are forced) to explore gameplay areas each node represents. Connection between nodes determines where the player can travel. To place the nodes on the map we use to original low-resolution Voronoi diagram. A node is placed on each cell and on each border between cells, as can be witnessed in the image below:

      Figure 14 - Network of nodes placed on the Voronoi graph
      Certain connections are special. As mentioned above wide rivers can only be crossed at certain points, and mountains also create barriers. For uncrossable rivers the node that would have been placed on the river is split in two and each node is moved away from the river a little. Where a crossing is needed the node is actually split in three so that a bridge node is created that conveniently only has two connections (and exits) on each side of the river. For mountains and passes across mountains something similar is done.

      Figure 15 - Detail of the node network showing rivers and mountains
      Some of the nodes are already marked out as special sites in the generated data. The area templates associated with these sites often indicate special features to appear on the map (for example a volcano, a village, a mud pool, or a group of trees). Although, in some cases these features are only added after the player has visited the area and found its secrets. All other nodes are assigned templates based on the region they belong to and their relative position within that region.
      Each region has a number of types of locations. Typically a region has one 'heart' location assigned to a node quite central in the region, or a 'smallHeart' location if the region is relatively small. A number of 'rare' locations are scattered out across the locations not on the region's edge, and finally, all other locations are drawn from a random destination table associated with the region's terrain. Figure 16 shows sample entries from the table we use to populate forest and plain regions (the 'locations' in this table are the random encounter location the game uses when travelling between each node).

      Figure 16 - Random destination table
      Wrapping Up
      At the moment of writing the map generation is still a work in progress. We are constantly adding details as the game's content keeps growing. But I don't expect the general approach to change much.
      We are quite happy with the results, as in our humble opinion the maps are quite beautiful. But what's more important, they are readable: players can predict where barriers and dangerous terrains are to be found. A lot of information is there and we don't hide it behind a fog of war. The map facilitates anticipation and foreshadowing which are two key gameplay design features. We hope that when the game is released in full, players will enjoy simply pouring over the map and plan their journey.
      If you are interested in learning more about the game please check us out on Fig.co or on Steam.
      Note: This article was originally published on the Ludomotion website, and is reproduced here with the kind permission of the author.
    • By Swiss Cheese
      Hi Volks
      I'm stuck since weeks with my Gameproject because the Path Calculation. (programming in C)
      The Game is 4096x4096 divided by tiles of 64x64. How can I find the shortest Path from green point to red point (attachment Image)

    • By CelticSir
      I am trying to create simplistic model for boats floating in water in Unity using PhysX but i am not understanding how to get it work properly.
      I use a single rigid body with a centre of mass as the red dot. Its below the ship's mesh as i read having a lower centre of mass made it more stable. Though i cannot get it to be stable anyway.
      Each green sphere is a buoyancy force calculation which has this code, and it applies the force upwards at the spheres position:
      _volumeUnderPlane = VolumeBelowPlane();         if (_volumeUnderPlane > 0)         { // P = 1027 (approx density of water at sea level)             var force = -_volumeUnderPlane * Physics.gravity * P;             _parentRB.AddForceAtPosition(force, transform.position,ForceMode.Force);         } Where Volume below the plane is calculated as:
      private float VolumeBelowPlane() { //water level is always 0 for now //math based on https://en.m.wikipedia.org/wiki/Spherical_cap var dist = -transform.position.y + _radius; dist = Mathf.Clamp(dist, 0, 2 * _radius); var dist2 = dist * dist; var frac = Mathf.PI * dist2 / 3f; var volume = 3 * _radius * frac - frac * dist; return volume; } But the result is totally unstable, this is how it looks with a lowish mass:


      With a high mass it looks like this:

      I am trying to replicate how assassins creed does it, they used spheres to approximate the buoyancy without it being too computationally heavy, yet they didn't go into any details on how they did the math for it but they did post this image of it:
      Am i doing any thing wrong with my math here? I don't know why its so unstable for me.
    • By Dante3085
      I want to implement a Tekken-Style Combo-/ Input-System.

      The basic system i want to realize is, processing a timed sequence of inputs. Example: In Tekken, I have 4 Input Buttons(excluding directional Buttons). Each of them corresponds to a basic Character Action.
      Square = Left Jab
      Triangle = Right Jab
      Circle = High Kick
      X = Low Kick
      When pressing one of those Buttons the Action executes. For a short period of time after that, the Character is in a state in which each of the Input Buttons (or only a subset of them, depending on the Character's move list) corresponds to a different Character Action. If I manage to press a Button in time the Combo and this Pattern continues until the end of the Combo. If i fail to push a Button in time, the Character returns to it's idle state.

      I had the idea of using a Tree to represent all Combos of a Character as a Datastructure.
      The buliding blocks are the following...

      1. Input(Type: enum): For example the square on a PS4 Controller.
      2. Action(Type: enum): A command that is send to the Character when an Input is given.
      3. Timing(Type: float or int): A time window for a specific Input of a ComboNode.
      4. ComboNode(Type: user defined): Several Inputs where each Input maps to a Triple.
      5. Triple (Type: user defined): An Action, a Timing and a set of ComboNodes(ChildComboNodes).

      How the Tree would update itself:
      1. Check for inputs in current ComboNode while at least one timing is still valid.
      2. Pressed Input.
      3. Send corresponding Action to Character.
      4. Set current to ChildComboNode.
      5. Repeat until Combo ends or no timings are valid. In those 2 cases, return to root.
      I would appreciate advice or comments :)

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!