Anonymous asked: What's up. I'm currently trying to create a 3d clone of the original cataclysm game in UE4, because I thought it would be really fun. Can you give a very high-level, big picture explanation of how you generated the roadways? I.E.: did you use an L-system, or use purely noisemaps? I'm trying to come up with a nice algorithm for doing the roadways myself, but I'm having trouble figuring out which system would give me an easier time.
Sounds awesome! I’m excited to see what you come up with - let me know once you have anything that’s working or at all interesting, and I’ll repost it here (with your permission of course).
When you say “how I generated the roadways” I assume you mean on the world map, not the player scale. The player scale generation is simple and boring.
On the world map scale, well, the way it was done in Cataclysm 1 is very different from how it was done in Cataclysm 2. I don’t know what L-systems or noisemaps are, and a quick google makes me pretty confident I didn’t use either one.
In Cataclysm 1, the first step was to generate a list of points that need to be connected by roads. The center tile of every city are the most obvious one; also included are special locations (labs, hospitals, etc) and a few points on each edge of the world map (so that roads will lead to neighboring world maps). Once we have that list of points, we iterate over it; for each point, we find the first point that’s close enough to it; or if no points are close enough, whichever is closest. For example, let’s say we have 4 points in our list. We start with point 0, and define “close enough” as 50. The distance to point 1 is 68; the distance point 2 is 43, so we stop there, even though the distance to point 3 is 28.
One issue with this algorithm is that it doesn’t guarantee that all roads will be connected in a network. But I was okay with that I guess.
To actually build the road between those two points, we start at one of them - call it the origin. Let’s say our origin is at (10, 10) and our destination is at (20, 20) - so we need to move north and east.
From our current position, we look at all adjacent (diagonals are not allowed) points. If one of them is already a road, and is closer to our destination, then we’re done. Otherwise, we randomly pick a tile that’s closer to our destination and move there - keeping track of whether we just moved horizontally (east/west) or vertically (north/south).
We then continue. At each step, we prefer to continue in the same direction - that is, if our last step was horizontal, then our next step should be too. There are two exceptions to this rule. First, once we get in-line with our destination on one axis, we ignore the direction rule. In our example, once we get to an X-value of 20, we’re going to change our Y-value no matter what - since the X-value is correct, we don’t want to change it. The other exception is random - on every step, there is a 1-in-12 chance that we’ll switch from horizontal to vertical, or vice versa.
Finally, if we ever hit a river, we just continue across it in a straight line until we reach the opposite bank. This is occasionally problematic; there’s no check for how long that will be, so if we hit the river parallel to its general direction, we could wind up with a very long bridge.
This algorithm is riddled with problems. It’s not very interesting, it doesn’t handle problems (like getting cornered somehow) very well, it may hit a road and stop without actually connecting to our destination, and we wind up with an unrealistic zig-zag structure, that never doubles back or curves around stuff.
Cataclysm 2 has a much better solution. It uses A* pathfinding. If you’re not familiar with it, A* is an algorithm that checks a lot of possible routes, and uses whichever is the shortest. This means we’re guaranteed to always wind up with a successful, often interesting, path.
To make the path more interesting, each world terrain type has a variable called road_cost. This variable represents how much we want to avoid building a road on that terrain. Our A* path multiples each step by the weight. So a path that’s 10 tiles long, and each tile has a weight of 5, is actually better (total score: 50) than a path that’s 5 tiles long, and each tile has a weight of 12 (total score: 60). Some examples here are fields - cost 100; beach - cost 110; forest - cost 150; swamp - cost 200; river - cost 500; and road - cost 1.
This produces roads that curve around small forests and swamps, but goes through large forests directly. Forests often have patches of field inside, little clearings, and that makes roads more interesting as they’ll curve a bit to take advantage of the field. Our roads will double back and serpentine as they move, all in fairly-realistic way. The ultra-low road_cost of roads themselves means that when building a road, we’ll use pre-existing roads IF they take us closer to our destination. And once we get close to our destination, we’ll branch off from the existing road to create a new one.
So all in all, I’d strongly recommend using Cataclysm 2’s A* based algortihm. Good luck!