I was inspired by Krice's post to post about the cave generation algorithm I've been using recently. Rather than hijack his thread, I thought I'd post a new thread.
This is a pretty simple algorithm. I'm sure several of you already use it, but I thought I'd post it here anyway. It's not great, but it's pretty simple and can create some pretty good results.
Here's how it works: you select a bunch of random points on the map, and assign each point a unique ID number. Then connect the closest two points that have different ID numbers using a line with a width greater than 1. After connecting the closest two points, loop over the points and change the unique ID of any point that has the same unique ID as the second point in the pair to the unique id of the first point. Wash, rinse, repeat until all points have the same ID. Here's an outline:
1. Add random points to list with unique ID numbers
2. Loop:
3. Find closest two points that have different IDs
4. Draw line between the two points
5. Loop over all points and change the ID numbers of any points that have the same ID as the second point to the ID number of the first point
6. You are done when all points have the same ID number
Using higher numbers of points gives a more satisfying and cave-like look. Because the algorithm always connects the closest points, a very large number of points can be connected in a sane and aesthetically pleasing way in very small areas. This algorithm is also useful for rivers.
This algorithm doesn't create loops. Technically it links everything together into a perfect maze, so if you want loops you have to (for each loop you want) connect two (distant/non-neighboring/not already connected) points that have the same IDs. If you connect points completely at random (instead of the closest two), you end up with a pretty crazy spiderweby thing that doesn't look very good, but may be useful to you.
