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

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

    General and Gameplay Programming
       (1 review)



    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

    Absolutely love this kind of stuff, thank you for sharing!

    Share this comment

    Link to comment
    Share on other sites

    Big thanks to you Joris for your wonderful article. It's so interesting and your words with the pictures to illustrate it's a great job!

    Congrats and I hope to read more from you in future!

    Share this comment

    Link to comment
    Share on other sites

    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 RidiculousName
      I have a class for the NPCs in my game. Each NPC has an athleticism attribute that ranges from zero to one-thousand. I am randomly generating this value. I want 70%-80% people to have a roughly average amount of athleticism, somewhere close to 500.
      Is there some algorithm I can apply that will skew the randomly determined athleticism score so that it's usually close to 500, but always returns a few scores that are either much lower or a lot higher?
    • By DiligentDev
      I recently added a new Diligent Engine tutorial that demonstrates the usage of compute shaders and may be useful on its own. The example app implements a simple GPU particle system that consists of a number of spherical particles moving in random directions and encountering elastic collisions. The simulation and collision detection is performed on the GPU by compute shaders. To accelerate collision detection, the shader subdivides the screen into bins and for every bin creates a list of particles residing in the bin. The number of bins is the same as the number of particles and the bins are distributed evenly on the screen, thus every bin on average contains one particle. The size of the particle does not exceed the bin size, so a particle should only be tested for collision against particles residing in its own or eight neighboring bins, resulting in O(1) algorithmic complexity.
      The full description of the implementation of the method is here.

    • By WeedWilly
      Hey smart people. I'm trying to understand server replay/server reconciliation where the server keeps a list of inputs and game snapshots and goes "back in time" to apply inputs that should have been applied back then, then re-simulates to the present (I think that's all correct, that is my current understanding of it).
      So my biggest confusions about it aren't necessarily how to implement the algorithm, but more what the purpose of the algorithm is (what problems does this prevent?) and when should the algorithm kick in.
      My current understanding of server replay is based on this article https://medium.com/@qingweilim/how-do-multiplayer-game-sync-their-state-part-2-d746fa303950 , and it's really the only one I can find on it.
      So my questions:
      - what is the purpose of server replay? My guess is that it makes sure player1's inputs at tickX are executed before player2's input at tickX+1 despite player1's much greater ping. Or does the server always reconcile, not just when inputs are received out of order?
      - when should the server reconcile? I think the answer to the first question will kind of answer this one, but I guess I'm just confused, because couldn't the server just constantly reconcile, since the server is going to receive inputs a few ticks late always just because of ping?
    • By Sword7
      I am developing my orbital flight simulator (space simulator) myself.
      I am figuring how to write a routine to generate/create Gaussian star/glare texture for starry sky.  I googled for that but can't find any source so far.  I only found it in open-source Celestia code but it did not explain clearly.
      Does anyone know any good source in books or website that provides coding for creating Gaussian star/glare texture?
    • By congard
      Hello! I created a camera based on quaternions, but when I turn the camera, an unwanted roll appears. I would not like to lose my freedom of movement using, for example, Euler angles, since there is a need to add roll from time to time. If I use Euler angles, then, as far as I know, I can get a gimbal lock.
      struct FreeCamera : public BaseCamera { float pitch = 0, yaw = 0, roll = 0; void updateView(); private: glm::quat qCamera; }; struct FreeCameraController: public BaseCameraController { float sensitivityPitch = 0.0025f, sensitivityYaw = 0.0025f, sensitivityRoll = 0.0025f; void mouseMove(const float x, const float y, const float z = 0); inline void setMousePos(const float x, const float y, const float z = 0) { lastMousePos = glm::vec3(x, y, z); } private: glm::vec3 lastMousePos = glm::vec3(0.0f); }; void FreeCamera::updateView() { // temporary frame quaternion from pitch, yaw, roll glm::quat qPYR = glm::quat(glm::vec3(pitch, yaw, roll)); // reset values pitch = yaw = roll = 0; // update qCamera qCamera = qPYR * qCamera; qCamera = glm::normalize(qCamera); glm::mat4 rotate = glm::mat4_cast(qCamera); glm::mat4 translate = glm::mat4(1.0f); translate = glm::translate(translate, -pos); view = rotate * translate; } void FreeCameraController::mouseMove(const float x, const float y, const float z) { glm::vec3 dCoord = glm::vec3(x, y, z) - lastMousePos; ((FreeCamera*)camera)->yaw = dCoord.x * sensitivityYaw; ((FreeCamera*)camera)->pitch = dCoord.y * sensitivityPitch; ((FreeCamera*)camera)->roll = dCoord.z * sensitivityRoll; lastMousePos = glm::vec3(x, y, z); } Is it possible to reset unwanted roll? Thanks in advance for the help!

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!