Constrained Multi-Material Marching Squares

Recommended Posts

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.

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
      628730
    • Total Posts
      2984423
  • Similar Content

    • By MeowBounce
      Hello all! I just created a new game for the App Store called Meow Bounce. You collect FishCoins by bouncing on platforms, adopt cats, and customize them. I've attached some of the art here. I would love to hear any feedback on anything about the app, especially since it's my first app!
      Link - https://itunes.apple.com/us/app/meow-bounce/id1313160656?ls=1&mt=8
      I plan on adding features in the future such as simple animations for the world scenes, goals for gameplay, special items cats give you, and music in the shop. 
      Thanks for reading and thanks in advance for any feedback! 




    • By ferreiradaselva
      There are a bunch of path finding implementations online. But, to be honest, I wasn't much satisfied with  most of them, for one of these reasons:
      Dynamic memory allocation in the middle of the algorithm Algorithm that does too much (more than what is needed) Too many files for just a single task So I made this two-files (`uastar.c` and `uastar.h`) library: https://github.com/ferreiradaselva/uastar
      No memory dynamic allocation. Straight to the point (the README.md explains how to use).
      It's nothing biggie, but certainly useful.
      Path finder at work:

      I'm leaving this in announcements, because I probably won't add more features (it's pretty much done).
    • By NeverSay
      I think I might be with a team that is deep within development hell and they are all in denial about it. I have been working on a project with a small group and we all have no previous experience or educational background. The guy who had pulled us altogether had an idea for a game but the story is so confusing and convoluted after 3 years of working on this project... I still have no idea whats going on with the story. All I can say is its a platformer with a large explorable map and systems and mechanics dreamed up so grand out of all the 100 things he wants in the game we still only have 2 mechanics down. Every time I have tried to throw my voice in and suggest maybe we should put a pin in this idea and focus on smaller experiences so we can build our skills up and tackle it later when we know more of what we are doing, I get shot down. I'm told, "oh it will only take a year to make this game" of which both I and the artist look at each other very doubtful each time he says that. 
      So leaving out the backstabbing power plays a certain member of the team kept using which blocked me from having access to the game so I couldn't test out my work for myself, phage requests on what they wanted animated which lead to me redoing animation more time then I think was needed. I mean I redid the run animation over 60 times and in the end, they chose to use the very first freaking one I made! Whenever I tried to think logically and ask for a group meeting to talk about characters and how they move so I could get a better idea of what to do I was told "No, no, no this back and forth is a faster way of working"....again run animation took 60 attempts before they used the first run cycle I made. 
      In the end, we weren't working towards making the whole game, it took us 2 years and 5 months to make a demo of the game. Then our programmer disappeared and also took with him the code for the game. We should have stepped away from that game and accepted, for the moment that it might be time to take a break from it and focused on crafting smaller experiences to build up our skills and our group's portfolio but no that wasn't to be. We where to start again from scratch, new programmer, new textures and level designs and new rigs and animations. 3 years of work has gone down the drain and now I have to start again... the only problem is I can't bring my self to do the work. 
      I have become stagnant where I am and I feel like its time I should move on. I want to try and do things my way and start small and work my way up and not plunge headfirst into a project that feels like an ocean in scale for a small team. I want to focus on my own skills and learn new ones and understand more than just one trait in the spectrum of game design. Though since I have been with the team for so long and put so much time and money into this venture...I'm scared to walk away. Though on the other hand how long are we gonna spend on this game, is it gonna be another year like the lead designer said (again and again) or will it be another 3 and all we will have to show for it is a shiny new demo and none of the full game...
      Should I suck it up and try and kick my butt back into gear or is this the time to step away and look into new possibilities?
    • By DogmaStudios
      What techniques do you use to help develop the plot alongside gameplay when you finally have an idea for a story down?
    • By Dafu
      FES Retro Game Framework is now available on the Unity Asset Store for your kind consideration!
      FES was born when I set out to start a retro pixel game project. I was looking around for an engine to try next. I tried a number of things, from GameMaker, to Fantasy Consoles, to MonoGame and Godot and then ended up back at Unity. Unity is just unbeatable in it's cross-platform support, and ease of deployment, but it sure as heck gets in the way of proper retro pixel games!
      So I poured over the Unity pipeline and found the lowest levels I could tie into and bring up a new retro game engine inside of Unity, but with a completely different source-code-only, classic game-loop retro blitting and bleeping API. Months of polishing and tweaking later I ended up with FES.
      Some FES features:
      Pixel perfect rendering RGB and Indexed color mode, with palette swapping support Primitive shape rendering, lines, rectangles, ellipses, pixels Multi-layered tilemaps with TMX file support Offscreen rendering Text rendering, with text alignment, overflow settings, and custom pixel font support Clipping Sound and Music APIs Simplified Input handling Wide pixel support (think Atari 2600) Post processing and transition effects, such as scanlines, screen wipes, screen shake, fade, pixelate and more Deploy to all Unity supported platforms I've put in lots of hours into a very detail documentation, you can flip through it here to get an better glimpse at the features and general overview: http://www.pixeltrollgames.com/fes/docs/index.html
      FES is carefully designed and well optimized (see live stress test demo below). Internally it uses batching, it chunks tilemaps, is careful about memory allocations, and tries to be smart about any heavy operations.
      Please have a quick look at the screenshots and live demos below and let me know what you think! I'd love to hear some opinions, feedback and questions!
      I hope I've tickled your retro feels!



      More images at: https://imgur.com/a/LFMAc
      Live demo feature reel: https://simmer.io/@Dafu/fes
      Live blitting stress test: https://simmer.io/@Dafu/fes-drawstress
      Unity Asset Store: https://www.assetstore.unity3d.com/#!/content/102064

      View full story
  • Popular Now