Outliner

Turning a 2D map into a 3D mesh

Recommended Posts

I'm being plagued by a desire to make a game where the player has a level editor that allows the player to draw a 2D level map and then it will pop up into a 3D level. Of course that sounds much like a height map, but sadly I have ambitions beyond what a height map alone can offer. I want the player to be able to draw a curve on the map and have that curve become a vertical cliff. I want the player to be able to draw a thick line and have that line become a road, its vertices lined up with the vertices of the surrounding landscape, but horizontal from side-to-side and with UV coordinates set to allow its texture to follow the direction of the road. If the player draws a road across a chasm, I want that to become a bridge.

That may seem like it's asking too much, and it's true that for as long as I've been thinking about this problem I have yet to find an approach that works to my satisfaction, but there are limits to the goals of this project. Just like a height map, this project doesn't attempt any sort of cave or overhang. The final level needs nothing that cannot be represented in a 2D map. Aside from bridges, no part of the level ever needs to cross over itself. Aside from vertical cliffs, the landscape is restricted to being smooth slopes or flat land; there is no desire for the kind of jagged detail that's possible in a height map for this project. Aside from the cliffs that are specifically drawn in the level editor, there should be nothing blocking the player from moving around the level, so everything except the cliffs ought to be relatively smooth.

I've tried starting from a regular mesh of equilateral triangles and adjusting the positions of the vertices to match the player's map. I appreciate the regular mesh because it makes it easy to give every vertex, triangle, and edge a number and store the level in an array. It also forms a graph structure that makes it easy to create smooth slopes and know when those slopes ought to be interrupted by cliffs. Unfortunately I have never been able to overcome the technical challenges of making the mesh and the player's drawings line up.

I've tried starting from the player's drawn map and building a mesh around it. Unfortunately, computational geometry has never been one of my strengths, so figuring out where to put the vertices and edges to smoothly fill out the rest of the map is daunting. I've considered simulating the vertices as if they were electrons so they can form a minimum energy distribution around the fixed vertices specified by the player, but I'm not sure how to maintain the smoothness of the slopes if the vertices keep moving as the player draws.

The bottom line is that I'm really not sure how to even begin solving this problem. I'm willing to put effort into implementing a complicated system, but first I need an idea for how that system ought to work. I really need the wisdom of someone more experienced than myself.

Share this post


Link to post
Share on other sites

Have you considered that perhaps a 2d image isn't the right representation of a 3d map?

 

I wouldn't do it that way, and if you look at most 3d level editors they're 3d in nature with a three coordinate system x, y and z, so that it's easier to visualise height and depth and adjust in real-time.

 

What you're asking for means the level designer can't visualise in real-time what they're creating which makes the creation process awkward.

 

Hope this helps!

Share this post


Link to post
Share on other sites

On the editors I've worked on like that, there are layers.

Generally they start with the terrain's heightmap coupled with layers for viewing items on the terrain. That can viewing terrain's graphics texture, or viewing tree, grass, or water layers. It can mean viewing markers for navigation information, and so on.

One layer view can be items placed on the ground.  A level designer might place a building, or spawn points, or bridges as you mentioned.  Some objects could modify the heightmap if necessary, as defined by code and data. The system might say a building must have flat heightmap and level it out around the building's base.  The system might say a bridge needs to have a flat heightmap at both endpoints and must be equal height on both ends, and automatically adjust the heightmap accordingly.

Most major engines have moved away from that style of map editor. There is often more to game maps these days so level designers want more comprehensive views of the world.  

Share this post


Link to post
Share on other sites

The motivation behind this level editor is not for level designers, but rather for players. By that I mean I want the level design process to be fun and easy, not something someone would do as a job. That's why the fundamental goal for the level to be designed as a 2D image that the player can paint with the mouse. I'm trying to deliberately simplify the level design process and the resulting levels. So there are only three times of land: flat land, smooth slopes, and impassable cliffs. I'm trying to keep the third dimension simple, but still leaving room for depth and creativity.

1 hour ago, Brain said:

What you're asking for means the level designer can't visualise in real-time what they're creating which makes the creation process awkward.

I like to think of it as saving the level designer from needing to visualize the third dimension. In an outdoor setting, most of the interesting design choices are going to be horizontal. For example, the main gameplay impact of a hill is to block horizontal visibility when you're standing beside the hill, and expand horizontal visibility when you're standing on top of the hill.

49 minutes ago, frob said:

There is often more to game maps these days so level designers want more comprehensive views of the world.

I'm trying to keep my game map deliberately simple. Solving this technical challenge is a learning experience, but creating elaborate game maps would require a team of 3D modellers. I feel like compelling game maps can be created without detailed models just by putting thought into what goes into the map,

8 minutes ago, h8CplusplusGuru said:

I think age of empires 2 has a cliff system similar to what you describe as well.

That sounds very promising. Thanks! I will need to take a look at those editors.

Right now I'm working on a computational geometry approach by using Ruppert's algorithm to fill in the mesh details between the details that are drawn by the player. That should cover the landscape with an irregular grid, and then I plan to use cellular automata in that grid to create a smooth landscape in the blank areas where the player hasn't drawn anything.

 

Share this post


Link to post
Share on other sites
1 hour ago, h8CplusplusGuru said:

I think the Starcraft two map editor is what you might be looking to get inspired by, are you familiar at all?

I've never played Starcraft 2, but I found a video of the map editor on youtube and I see what you mean!

Even so, it has a very noticeable grid underlying its levels and that makes it hard to do natural formations. I could save myself much trouble by using a grid, but I think I'd get much better results with free-form levels. I am seeing great promise in using a quadtree to structure the levels, because that allows it to get more detailed as necessary in response to whatever the player draws.

Share this post


Link to post
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


  • Forum Statistics

    • Total Topics
      628277
    • Total Posts
      2981776
  • Similar Content

    • By sidbhati32
      I am working on a game in which we control a rectangular box at the bottom of the screen. Three sphere which has alphabets in it fall down. When the game starts, a word is generated from the predefined list of words(which I'll give) and we are supposed to touch the correct sphere having the alphabet based on that word. The question is how to detect if I have touched the correct sphere. 
      secondly, if I have touched a correct sphere before and there is no recurrence of that alphabet in that word then during the second wave the game should not proceed if I touch the same alphabet again.
      Looking forward to your answers, i have to submit this project in a couple of days. please help! (Working on Unity 3D)
      Thanks
    • By Yarden2JR
      Hi there everyone! I'm trying to implement SPH using CPU single core. I'm having troubles in making it stable. I'd like some help in order to understand what is wrong and how could I fix it. Please, take a look at the following videos:
      Water inside sphere using Kelager's parameters
      Water inside big box
      Water inside thinner box
      I've already tried using XSPH, the hash method to find the neighbors (now I'm using the regular grid, because the hash method didn't work for me) and two different ways of calculating the pressure force.
      I'm using mostly the following articles:
      Particle-Based Fluid Simulation for Interactive Applications, Matthias Müller, David Charypar and Markus Gross
      Lagrangian Fluid Dynamics Using Smoothed Particle Hydrodynamics, Micky Kelager
      Smoothed Particle Hydrodynamics Real-Time Fluid Simulation Approach, David Staubach
      Fluid Simulation using Smoothed Particle Hydrodynamics, Burak Ertekin
      3D Langrangian Fluid Solver using SPH approximations, Chris Priscott
      Any ideas? Thanks!
    • By Sam Mason
      Hi all,
      I have written a nice(ish) looking game of solitaire in Windows Forms, using VB.NET and Visual Studio 2015. It allows the player to play the game, and if their score is in the top 10, it saves the username and score o a leaderboard (saved in a text file so it is non-volatile). My next goal is to let the user know if the hand they are dealt is playable, but I'm not sure on the most efficient way of achieving this. I'm working on time complexity over space complexity! It's a simple game to code, but not an easy one to find the solution.
      Do you know of any algorithms that may achieve this goal that I would be able to look at?
    • By QuesterDesura
      Hello,
      I'm a trainee for software development and in my free time I try to do various things. I decided I wanted to figure out how "Dual Contouring" works, but I haven't been successful yet. I could find some implementations in code which are very hard to follow along and same sheets of paper "explaining" it written in a way that I have a hard time even understanding what the input and output is. All I know that it is used to make  a surface/mesh out of voxels. Is there any explanation someone can understand without having studied math/computer science? The problem is also that most of the words I can't even translate to German(like Hermite Data) nor I can find a explanation which I can understand. I know how Marching Cubes work but I just can't find anything to Dual Contouring also I don't quite get the sense of octrees. As far I'm aware of this is a set of data organized like a tree where each element points to 8 more elements. I don't get how that could be helpful in a infinite 3D world and why I shouldn't just use a List of coordinates with zeros and ones for dirt/air or something like that.
      Thanks
      A clueless trainee ^^
    • By Outliner
      Lately I've been working on building up a game's terrain from grid-aligned pieces. We might call these pieces metatiles because each piece is made of a collection of grid tiles that work together to create a unified feature in the game world. The beauty of this approach is that it fits neatly within the grid of a height mapped terrain. The difficulty is determining how to maximize the flexibility of the system using very few metatiles. Not only does a metatile require time and effort to design and model, but having a vast library of metatiles to choose from would complicate the world editing process.
      In my experience, most complicated metatiles boil down to arrangements of a few fundamental types of pieces. My idea is to simplify the whole process by restricting the game to features built up out of these six metatiles, plus flips and rotations:

      The red lines represent the feature that is drawn through the grid cells, and the gray lines represent how the cell is triangulated around the feature. For example, the red line might represent a vertical cliff or the boundary between one area and another, like the edge of a road or the shore of some body of water.
      These pieces, plus the flexibility of a height map, should be enough to create a wide variety of game terrains. The question is how does one build build an easy-to-use editor around assembling such small metatiles? For example, you can build up a curve out of these pieces by starting at a point and dragging the mouse in the desired direction. The editor would automatically choose the piece that most closely matches the direction from the current point to the mouse cursor. We can preview the next piece and perhaps wait for a mouse click to accept it, then continue with yet another piece until the curve catches up with the mouse. If the next piece would overlap with an existing piece, we display the preview in an error color and refuse to place the piece.
      Has anyone ever seen a system like that?
      While the above seems technically sufficient, there are a few details that would make editing awkward without additional automation. For example, a road would usually tend to have two parallel edges, and manually creating two parallel edges along a curved road in a system like this would be tedious and tricky. There is also a question of UV-mapping and how the user would specify the UV-coordinates of things like cliff walls and road surfaces. Ideally UV-coordinates would be handled entirely automatically.
  • Popular Now