I enjoy coding, but doing it for a living can be very taxing. Therefore, I decided to start a project of my own, to keep coding, but do something that’s more stimulating to me. Also, there’s Miska Fredman’s #mapvember to which this can be my own special contribution.
Note that this is more about brainstorming and writing about the problems and possibilities this approach presents. I’ll try to return with something that works before the end of the month.
Types of Maps
I was thinking about many possibilities. There’s a heuristic on how cities grow based on waves of development, which I’ve been thinking about doing for a long time, but that would require more research than I’m willing to commit to during the month. I could do that in a smaller scale, say a village, which grows organically around a few features, like a stream and a road, where someone first founds an inn or a farm and others follow.
The most ambitious idea I had was to simulate how these caves actually come about. I would have made a three-dimensional model of a random bedrock with variations on thickness and put some pressure on it (simulating water) and see what happens. Would have required some understanding of chemistry I definitely don’t possess, but it was an interesting idea.
On a similar vein, there’s always maps of nature, which I could have done, or maybe maps of nations. Either could use similar natural approaches, as human (or other) settlements always follow natural boundaries in some way (well, unless some dictator simply decides to settle an area to suit his own needs, whatever those might be).
In the end, I settled on “RuneQuest style dungeon”. This might be only in my head, but as my early experiences with RPGs were largely with D&D Red Box and the Finnish version of RuneQuest, I remember the exact lines from the D&D Modules and more natural lines of the RQ Scenarios. So, basically this means a natural cave, which has been co-opted by someone, even if I don’t think these could actually occur in nature.
So, how to do this automatically? The secret here is that it doesn’t need to be perfect, it just needs to look good enough. So, my idea is this (in steps):
1. Put enough random ellipses to represent the rooms in the caverns.
2. Draw random lines around these ellipses to make it seem more “natural”
3. Assume overlapping ellipses are the same room and thus don’t need a further connection.
4. Find rooms that need connecting and draw connections using a series of overlapping polygons and drawing random lines around them to again make them seem more natural.
5. Fill the ellipses and polygons with white get rid of lines drawn in the rooms and the tunnels. This will leave some rubbish on the map, but you can chalk it up to clutter within the caverns.
I’ve done some tests and I think I can get everything to work, except with one little problem: finding overlapping ellipses. Initially I though this can’t be very hard, because finding overlaps with circles is easy. You just check the distance between the center points of the two circles. If its less than the sum of the radii, the two overlap. I was thinking this could be easily generalized into ellipses, but not so. I was reading through an 11 page paper on the subject and couldn’t really understand it, as I haven’t been reading such materials since I left University seven years ago.
Well, I hope I can find a heuristic of some sort to make this easier. There must people out there struggling with the same problem. What I can probably do is some sort of Monte Carlo system, which tests a bunch of random points on a selected arc of both ellipses and … do something. We’ll see.
This is a naive attempt, as I have little experience with coding.
Ellipses are convex sets. Two two-dimensional convex sets are disjoint if and only if you can draw a line between them. (In three dimensions, you would need to draw a plane.)
In fact, you can do even better: you only need to consider the tangent lines of one ellipsis.
An algorithm. Assume you have two ellipses, e1 and e2:
1. For e1 select a sufficiently dense set of boundary points.
2. For each boundary point…
2.1. Consider the tangent line of the boundary of e1 at the point.
2.2. If the tangent line intersects e2, then consider the next boundary point.
2.3. Otherwise, select any point p1 from e1 and p2 from e2.
2.4. If the line segment between p1 and p2 intersects the tangent line, then the ellipses do not overlap.
2.4. If the line segment between p1 and p2 does not intersect the tangent line, then the ellipses are on same side of the tangent line; consider the next boundary point.
3. If no tangent line separated the ellipses, then they intersect.
I think the only difficulty is checking if the tangent line intersects e2.
Considering this, here’s another generic algorithm for checking if two convex sets intersect. The basic idea is that convex sets are (countably infinite or sometimes finite) intersections of half-spaces and can be approximated well by convex polygons.
Suppose c1 and c2 are two convex sets.
1. Select a sufficiently dense set of boundary points for c1.
2. For each pair of points consider the line segment between them. (You only need to considering neighbouring boundary points and line segments between them, if you find such neighbours easy to identify.)
3. Repeat for c2.
4. If any line segment of c1 intersects any line segment of c2, then c1 and c2 intersect. Otherwise they are disjoint.
Thanks. I’ll try that.
Pingback: Automated Map Generation, Version 0.1 | Guild Blog
Pingback: Review: A Dozen Dungeons by Miska Fredman | Guild Blog