Turning a 2D map into a 3D mesh

Recommended Posts

Outliner    3

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
Brain    18906

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
frob    44975

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
Outliner    3

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
Outliner    3
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

  • Similar Content

    • By Outliner
      In ordinary marching squares, we're trying to find isolines on a height map for some particular height. It's a delightfully simple algorithm because we can use a look-up table to determine the structure of edges and vertices within each grid cell based on whether each corner is above or below the desired height.
      In multi-material marching squares, each point on the grid has some proportion of several materials and we're trying to draw the boundaries between the areas where each material is dominant. This is less simple, since there are more than two options for each corner of each cell; at worst each corner could have a distinct dominant material. Even so, it's not too hard to approach this problem with a look-up table based on the corners of each cell.
      Finally, we have constrained multi-material marching squares, which is much like other constrained triangulation problems. In addition to the multi-material grid, we now have pre-defined boundary edges in some of the grid cells, and the multi-material marching squares must respect those pre-defined edges as if they accurately represent the boundary between two materials. I'm finding it hard to wrap my head around this problem. It seems that a look-up table will be of no use because the pre-defined edges create too many possibilities, even if those edges are restricted to the kinds of edges that marching square would naturally produce, but doing this without a look-up table also seems daunting.
      Motivation: In principle the goal seems quite simple. Take a 2D grid and use it to define terrain as a height map and as a material map that will form the foundation for a procedurally constructed mesh. Aside from the usual hills and valleys of a plain height map, the multi-material aspect of the grid allows us to define swamp, forest, desert regions on the map and apply particular procedural meshing for each. In addition to that, we want vertical cliffs that get their own special meshing and define the region boundaries. The cliffs are the constraints of constrained multi-material marching squares because when there is a cliff running through a grid cell, that should always act as the boundary if the material at the top of the cliff is different from the material at the bottom, even if marching squares would have naturally put the boundary somewhere else.
    • By Luigi Lescarini
      i’m trying to build an effective AI for the Buraco card game (2 and 4 players).
      I want to avoid the heuristic approach : i’m not an expert of the game and for the last games i’ve developed this way i obtained mediocre results with that path.
      I know the montecarlo tree search algorithm, i’ve used it for a checkers game with discrete result but I’m really confused by the recent success of other Machine Learning options.
      For example i found this answer in stack overflow that really puzzles me, it says :
      "So again: build a bot which can play against itself. One common basis is a function Q(S,a) which assigns to any game state and possible action of the player a value -- this is called Q-learning. And this function is often implemented as a neural network ... although I would think it does not need to be that sophisticated here.”
      I’m very new to Machine Learning (this should be Reinforcement Learning, right?) and i only know a little of Q-learning but it sounds like a great idea: i take my bot, making play against itself and then it learns from its results… the problem is that i have no idea how to start! (and neither if this approach could be good or not).
      Could you help me to get the right direction?
      Is the Q-learning strategy a good one for my domain?
      Is the Montecarlo still the best option for me?
      Would it work well in a 4 players game like Buraco (2 opponents and 1 team mate)?
      Is there any other method that i’m ignoring?
      PS: My goal is to develop an enjoyable AI for a casual application, i can even consider the possibility to make the AI cheating for example by looking at the players hands or deck.  Even with this, ehm, permission i would not be able to build a good heuristic, i think
      Thank you guys for your help!
    • By ramirofages
      Hi, I came across this udk article:
      that somewhat teaches you how to make the volumetric light beam using a cone. I'm not using unreal engine so I just wanted to understand how the technique works.
      What I'm having problems is with how they calculate the X position of the uv coordinate, they mention the use of a "reflection vector" that according to the documentation (https://docs.unrealengine.com/latest/INT/Engine/Rendering/Materials/ExpressionReference/Vector/#reflectionvectorws ) it just reflects the camera direction across the surface normal in world space (I assume from the WS initials) .
      So in my pixel shader I tried doing something like this:
      float3 reflected_view = reflect(view_dir, vertex_normal); tex2D(falloff_texture, float2(reflected_view.x * 0.5 + 0.5, uv.y)) view_dir is the direction that points from the camera to the point in world space. vertex normal is also in world space. But unfortunately it's not working as expected probably because the calculations are being made in world space. I moved them to view space but there is a problem when you move the camera horizontally that makes the coordinates "move" as well. The problem can be seen below:

      Notice the white part in the second image, coming from the left side.
      Surprisingly I couldn't find as much information about this technique on the internet as I would have liked to, so I decided to come here for help!
    • By Outliner
      Consider how one makes terrain using marching cubes. By having a grid of floats we can represent a continuous field that marching cubes will interpolate and turn into a nice smooth isosurface for the player to walk around on. This is easy and excellent for creating mountains and valleys and so on, but what if we want more variety in our game? A game is not normally made of just grass and sky. Maybe some places should be sand, or water, or road. How could that be worked into the mesh that we're getting from marching cubes?
      The obvious approach seems to be to have multiple fields, so each point on the grid has a certain level of sand, soil, rock, water, and so on. Then we modify the marching cubes algorithm to look for transitions between materials, so it puts a surface between areas of mostly one material and areas that are mostly other materials. We'd also want to keep track of when these surfaces touch the air, because that's the only time when we'd actually want to triangulate and render the surfaces.
      Suddenly the delightfully simple marching cubes algorithm is looking a lot less obvious. Has anything like this ever been done? Does anyone have any tips? Is this the right approach?
      Edit: Embarrassing mistake! I didn't think of phrasing the problem as "multiple materials" until I went to post this question, but now that I have I see there are plentiful google results for marching cubes with multiple materials. I'm still interested in any tips and advice, but now I have other resources to help with this problem.
      From the Google results, this paper looks especially interesting: Automatic 3D Mesh Generation for A Domain with Multiple Materials
    • By 51mon
      I want to try shade particles by compute a "small" number of samples, e.g. 10, in VS. I only need to compute the intensity of the light, so essentially it's a single piece of data in 2 dimensions.
      Now I want to compress this data, pass it on to PS and decompress it there (the particle is a single quad and the data is passed through interpolators). I will accept a certain amount of error as long as there are no hard edges, i.e. blurred.
      The compressed data has to be small and compression/decompression fast. Does anyone know of a good way to do this?
      Maybe I could do something fourier based but I'm not sure of what basis functions to use.
  • Popular Now