The algorithm is simple. Start with the entire area covered in path tiles, then and remove tiles one by one until only a thin path remains. When removing tiles, you cannot remove any tile that will cause the ends of the path to become disconnected. These are called articulation points (or cut-vertices). I use a fast algorithm based on DFS to find the articulation points. I had to modify the algorithm slightly so it only cares about articulation points that separate the ends, rather than anything which cuts the area in two. After identifying articulation points it’s just a matter of picking a random tile from the remaining points, and repeating. When there are no more removable tiles, you are done. Or you can stop early, to give a bit of a different feel.
I call it “chiseling” as you are carving the path out of a much larger space, piece by piece.
How to create a sharp mesh from a function without even trying
In part 1 and part 2 of the series, we looked at the Marching Cubes algorithm, and how it can turn any function into a grid based mesh. In this article we’ll look at some of the shortcomings and how we can do better.
In Minecraft, you can dig in any direction – removing a block at a time with well defined edges. But other games manage to destruct terrain smoothly, without all the blockiness of Minecraft.
The following tutorial in Marching Cubes, a technique for achieving destructible terrain, and more generally, creating a smooth boundary mesh to something solid. In this series, we’ll cover 2d in this first article, follwed by 3d in the next , and Dual Contouring in the third. This last is a more advanced technique for achieving the same effect.
Quick follow up to my previous post, I found the same technique is pretty good at generating organic looking random paths. You simply start with an empty room, and keep randomly filling points until it is no longer possible to add any more without disconnecting the room. What’s left is a nicely wiggly pathway.
I’ve been playing around with procedural generation recently, and one question has repeatedly been nagging at me.
How can you randomly spice up a level while making sure you don’t accidentally block off the exit?
I’ve released a plugin generates a random arrangement of particles with a blue noise distribution. This is also known as Poisson Disk Sampling.
This distribution of particles guarantees no two particles are very near each other. It’s often considered a higher quality particle arrangement than Blender’s default uniform sampling. It’s particularly useful for organic arrangements, and randomly arranging meshes without collisions.