Create a Random 2D Concave Polygon Landscape JavaScript

Question

I'm writing a simple lunar lander clone in JavaScript (http://www.isogenicengine.com/demos/1.1.0/lander/) and instead of a basic landscape that just has highs and lows, I'd like an algorithm to generate random cave-like spaces. Given a rectangular area to work with [0, 0, 1920, 1200] the algorithm should be able to generate something like the image below. Ideally any "entrance" to a cave area should have a set width so that the lander can get "inside" it.

I've considered that this might not be possible and that I could instead just draw a bunch of images like the one above and convert pixel data into rough polygon data, but it would be way cooler to have randomly generated levels!

For super-hardcore bonus points, the ability to specify how many cave-like structures there are would be even more awesome.

The output of the algorithm would be an array of points, each point being an object containing an x and y property {x: val, y: val} that when you sequentially draw lines between the current point and the next, makes up the polygon.

If someone has a JavaScript implementation of something similar that would also help a lot!

Answer 1

Start with learning what a bubble diagram is as it's used in architecture. It's a topological diagram of a space, with bubbles as the spaces and lines to represent passageways. I didn't find any single great web page to recommend quickly, but doing an image search yields lots of examples.

A bubble diagram can be thought of as a graph with bubbles as vertices. In your example, model the "sky", the blob including the top edge, as a vertex. The cave is another vertex and the entrance is an edge. With this perspective, it's easy to generate as much cave-like complexity as you want.

The next trick is turning it into geometry. Essentially, you want to push out from the skeleton of the graph and make voids where the player can navigate. At the same time, you want to make sure that these voids don't push out too far and thin out or eliminate the walls. So you also need to model the solid area, and that's done with a dual graph. The dual graph goes "underneath" the original, in the sense that edge crossings represent conflict which is resolved in favor of void over solid.

Summarizing: (1) Make a topological graph with the features you want. (2) Create geometry for graph, assigning a location to each vertex and a path to each edge. (3) Construct a dual graph, and assign its geometry. (4) Flesh out the space associated with each graph by growing them outwards, resolving conflicts in favor of passage rather than blockage.

You might want to convince yourself that the perimeter list of the final geometry can be generated by a half-edge traversal of the graph, much like walking a maze with one hand on a wall.

Answer 2

Marching Squares can be used, if you're interested, to turn a 2D field of scalar values (probably acquired from Perlin or Simplex Noise) into a set of edge lines. Of course, what that ends up looking like will depend on exactly how you get the 2D field scalar values (how you manipulate the Perlin or Simplex Noise).

This is the best site I could find that goes over the details well. (It's not as well-documented out there as Marching Cubes, its 3D twin)

Actually, the Wiki page on it is pretty good.