• Content count

  • Joined

  • Last visited

Community Reputation

2 Neutral

About Outliner

  • Rank

Personal Information

  • Interests
  1. 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.
  2. Text Based RPG

    The most important thing in any challenging project is to write down exactly what your goals are so every step of the way you know what you're trying to achieve. Any effort you put into a project when your goals are fuzzy is potentially wasted effort. It often happens that people will start work on a game and never finish because they end up wasting their effort working toward fuzzy goals. To avoid that fate, write down in full detail exactly what you expect from the game, and that process will focus your mind on the specific problems you must overcome and help you find ways to implement your design. Here's a link to a guide to writing game design documents: How (and Why) to Write a Great Game Design Document
  3. I'm far from an expert, but the most useful bit of advice that I've ever gotten was to know exactly what you want. If a problem seems huge and intractable, then it is only because you don't fully understand what you're trying to do. In reality any challenge can be overcome with enough work; true problems only arise when we start working in circles because we don't really know what we're trying to achieve. Therefore, for any large or difficult project the most important thing is to have a design document. Decide exactly what you want and write it down in full detail. Imagine that you're going to pay someone else to make the game, and they'll only do the absolute minimum to get their check, so anything you don't put in the design document won't end up in the game. The process of making that document will clarify countless issues that you never even realized were issues. All the relationships and interactions between entities will be laid out explicitly, and all the mysteries and confusion will be gone, and all that's left will be to straight-forwardly implement the plan. The abstractions and names that you create for things while explaining what you're trying to achieve will serve you well during implementation because they will become the data structures and classes, and so it will be obvious which classes must naturally talk to which classes based on their role in the design. In other words, it's easier to tell Visual Studio what your game should be if you first tell it to Word.
  4. Marching Cubes with Multiple Materials

    If I understand this correctly, then the issue isn't about floating point errors or deterministic behavior. Even with absolute precision there would still be no way to avoid clipping except by having large gaps between materials. For example: On the left we have a Marching Squares square with three materials inserted with three separate single-material marching squares passes. Unfortunately there is a gap, so picture grass, sand, and water meeting at a point that includes a hole to infinity. If we want to fill that gap, we're forced to do something like shown on the right, where we increase the magnitude of one of the materials, but if we increase any of the materials even slightly it will not only start to fill the gap, but also start to overlap with the other materials.
  5. Marching Cubes with Multiple Materials

    Finding a good index for the lookup table is tricky. There are 4140 cases for a cube with various materials on its corners, but how should we number those cases? There are 28 comparisons we could do between the corners of a cube, and if we give each comparison a bit in the index, then we end up with an array of 268,435,456 elements, of which only 4140 will ever be used. Here's a blog entry about generating lists of set partitions. It generates partitions in a particular order, but it's not clear how to reverse the process and generate a number when given a partition. Enumerating set partitions with Bell numbers and Stirling numbers of the second kind.
  6. Marching Cubes with Multiple Materials

    Just running the marching cubes algorithm for each material doesn't seem like it would work. Hard transitions are exactly what I want, since that's easier to render than fading between materials, but if we just do 8 separate marching cubes, then what would prevent the materials from clipping into each other? Suppose we have three materials on the corners of a cube, then it seems they ought to divide the cube among themselves around a point in the middle. Using three separate marching cube procedures the materials might end up leaving an empty space in the middle, or they might end up clipping into each other so some parts of the cube are claimed by more than one material, but it seems impossible for the cube to be properly partitioned among the materials. The geometry of the situation is more complicated than single-material marching cubes ever needs to deal with. As it happens, I think I've found the actual number of possibilities for multi-material cubes. It's called the 8th Bell number, and it is 4140. It's roughly 16 times the 256 possibilities of single-material marching cubes, but still well within the range of a 16-bit integer.
  7. Marching Cubes with Multiple Materials

    This paper? Dual Contouring of Hermite Data by Tao Ju et al. If I have this right, then the essence of the problem is to convert the marching cubes algorithm from an algorithm where the corners of each cube can only be positive or negative, into an algorithm where the corners of each cube can take anywhere up to 8 distinct values. If I have this right, then while ordinary marching cubes deals with 2^8 possibilities, the multiple material marching cubes needs to deal with a far greater number of possibilities. It's not as many as 8^8, but it's still quite a few. Hopefully one of these papers will go into a way to enumerate the possibilities. Supposing that we're dealing with sand, rock, and air, then each corner has three numbers, one for each material, and the material of the corner is whichever has the greatest number. When two adjacent corners have distinct materials, then the algorithm will put a vertex somewhere on the edge between the corners. Supposing that the one of the corners is sand and the other is rock, we can linearly interpolate the values of sand and rock between the two corners, and the position of the vertex should be the point at which we switch from sand having the greatest value to rock having the greatest value. It's possible that if we interpolated the air value we'd find that air has the greatest value somewhere along the edge, but it's probably fair to just ignore that. I should focus on implementing a multiple material marching squares as a starting point, then move up to marching cubes once I'm confident I've got all the details worked out for the 2D version. Unfortunately it's not so easy to find resources for the 2D case.
  8. 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
  9. That's because of a few other features that I'm trying to implement. I'd really like to have sharp vertical cliffs in just the way that height maps do poorly. With a little extra fiddling, a regular grid would still work for cliffs, but they would need to be axis aligned. That's why I've been aiming for a data structure that allows me to insert arbitrary edges into my mesh, so I can have cliffs aligned to whatever angle I like. Much like cliffs, I would also like to put roads into the mesh, with UV coordinates setup so I can render the road's texture aligned with the direction of the road. Again, I hope to achieve this by inserting arbitrary edges into the regular grid so I can give the roads dedicated triangles with custom UV coordinates. Even so, my difficulty with this approach has lead me to seriously consider using Marching Cubes to generate my mesh. By carefully choosing the grid values, it should be possible to create cliffs at any angle, and it would be a regular grid so it eliminates my current problems. I still haven't figured out a way to make the roads work with Marching Cubes, but I imagine I could do it with some adjustment to the triangulation algorithm.
  10. How would you use marching cubes for terrain design? The obvious approach would be a 3D grid of voxels where each voxel is either 0 or 1, but in that case marching cubes would produce mostly axis aligned polygons and a few diagonals across the voxels. It wouldn't have a smooth or natural look. Marching cubes applied to voxels always seems to have the lumpy look of plastic stretched over piles of dice. On the other hand, marching cubes can produce amazing images. Metaballs are a great example of marching cubes producing smooth lines and curves, but in that case the cubes use a continuous field of values based on their distance from the center of each metaball, so it's not just 0 or 1. It's not hard to imagine using metaballs for rolling hills. A hand-drawn curve could perhaps form a cliff by blocking the influence of metaballs on one side from affecting the other side, but it would have to do it in a way that reflects the shape of the curve rather than just creating another jagged 0 and 1 situation. Does anyone have any tips or resources on this type of terrain mesh generation?
  11. I have a few key features that I want for my game's terrain mesh, but putting it all together into an terrain editor is becoming a headache. I need some advice from someone more experienced than myself. Perhaps there is some design pattern or object-oriented trickery to add some abstraction and turn this mess into something manageable. I am creating my terrain mesh as a problem of dynamic constrained triangulation. I start with a regular triangulation of a 2D plane into equilateral triangles, and then as I draw the game's map the existing edges and vertices are automatically removed to make room for the edges and vertices I'm drawing, and naturally the reverse happens when I erase. There are fairly simple algorithms for inserting individual vertices and edges into a triangulated plane. Using a half-edge data structure to represent the triangulation makes it quite manageable. Unfortunately there are a few additional important features. For one, a game map should be an infinite plane in all directions. The obvious solution to this is to break up the mesh into regular pieces, each one separately triangulated but sharing common points along their edges so that the multiple meshes fit together seamlessly in the game. The user should be able to draw map features across the boundaries of the map pieces seamlessly, without needing to care where one map piece begins and another one ends. An ordinary half-edge data structure doesn't have anything to deal with that and it would be nice if I could manage that complexity so it doesn't seriously affect my triangulation algorithms. Perhaps I'm asking for trouble, but I also want the terrain mesh to be able to change while the game is playing. I'm not so greedy as to try to implement animated terrain, but I would at least like to be able to remove a designated region of the map and substitute an alternative map of the same shape. We might think of it as having a hole in the map that can be filled by any one of several appropriately shaped meshes. Once we've got these meshes it will be trivial to pop them in and out during the game, but again it's another complication of the editor. Keeping the boundaries of the designated regions aligned with the rest of the map and allowing new edges to be drawn across that boundary is making the editor too complicated for comfort. What are the appropriate abstractions to use for this kind of situation? These seem like relatively simple features, but my design is turning into a tangled mess. What am I doing wrong? An ordinary half-edge structure doesn't seem to be the right tool for this job, but what would be the right tool?
  12. Turning a 2D map into a 3D mesh

    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.
  13. Turning a 2D map into a 3D mesh

    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. 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. 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, 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.
  14. I want to make game terrain using something like a heightmap, but I want vertical cliffs and none of the usual artifacts that go along with the limited resolution of a heightmap. So why not use marching squares to turn the heightmap into a contour map? Next we can triangulate the contour map to generate a 3D mesh with smooth lines at any angle and no difficulty with vertical cliffs. Here is a youtube video summarizing an algorithm for triangulating contour maps: Contour Map Triangulation, Visualization & Pathfinding Unfortunately it looks quite complicated and computationally intensive. Is there any hope of being able to recalculate that mesh frame-by-frame as the user draws the heightmap? Does anyone know of a way to simplify this problem?
  15. 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.