Marching Squares - Procedural cave generation

I Present Marching Squares!

So as always it’s time for… drumroll please! I make things out of my reach!

You can play it here If you want to see it freely you can press shift+p in-game!

If you want to know how it works:

Making the map

First, we make a 2d array of 0 and 1:

``````local Map = {}
local ran = Random.new(tick())

local Fill = 45

for x = 1,50,1 do
Map[x] = {}
for y = 1,50,1 do
Map[x][y] = Ran:NextInteger(1,100) < Fill and 1 or 0
end
end
``````

We apply smoothing:

``````for indexX,x in pairs(Map) do
for indexY,y in pairs(x) do

local Count = GetSurroundingWalls(Map,indexX,indexY)
-- Just make a function that find all walls in a 3 x 3 or follow the tutorial listed above
if Count > 4 then
x[indexY] = 1
elseif Count < 4 then
x[indexY] = 0
end
end
end
``````

(The smoothing should be applied multiple times)

And that’s the basics of the Map Generation. If you want more features (Which I highly recommend) you can see the tutorial or add some yourself. (Just remember to return a 2d array of 1 for walls and 0 for nothing)

Meshing the map

It’s here we use the Marching Squares algorithm to convert a 2d array into a beautiful mesh.

If you want to learn how to make the mesh: Part 1 and Part 2

But here is the idea:

1. Make points in 3d space from the map.

2. Use the points to make squares.

3. Find the configuration from the points using binary. fx: if top right and bottom left were walls then you get 1010. Then you can use `tonumber(1010,2)` and get the configuration in decimal.

4. Draw triangles between configurations of points. Here I would highly recommend the draw3dtriangle function from @EgoMoose - Read it here

A lot of optimizing can be done:

1. Draw squares instead of triangles.

2. Use greedy meshing. I didn’t use it as I had some problems implementing it but it’s still worth mentioning. - Theory and Code Example

3. Caching the objects instead of cloning and/or `Instance.new`.

By the way, it’s open-sourced now…

8 Likes

Hey, this is amazing! Will you ever open source this?

1 Like

This is really cool. I really like this. Noice

1 Like

Hello,

Late update but i decided to open source the project! You can get it here: Game (roblox)

Also posted the next episode in the series (please check it out): Post (devforum)

1 Like

Its open sourced now. Post (devforum)

1 Like