Typically, in a roguelike, to connect two points on a map, you see developers doing the "move horizontal and then move vertical" route, which works fine for castles and dungeons, like in the excellent little roguelike The Royal Wedding:
But that creates distinctly man-made looking tunnels. Tunnels like that would be extremely unconvincing if we were trying to imply a cavernous environment. So we need another algorithm.
So, the first order of business is to do something that isn't so obviously the "Manhattan" path between two points. This is where our good old friend Bresenham comes in useful.
The Bresenham algorithm is an algorithm that can be used to compute a "line" between arbitrary points which are constrained to a grid. (Think drawing a line with pixels.) This algorithm can be used to connect two cells in a tile-based grid by approximating the line connecting them.
This, at least, gets us direct lines between the points, and they don't follow "Manhattan" style movement.
But this still poses a few problems. First of all, now that we're not walking vertically and horizontally, we discover that (in most roguelike contexts) the player cannot move along this path, unless the game allows diagonal movement. (And even in games where diagonal movement is allowed, it may not be preferable, say, for people playing on laptops.)
This can be easily resolved by "thickening" the line so that it doesn't have any diagonal connections associated with it. We can do this in conjunction with the Bresenham algorithm if we do traditional "Manhattan" connections between each cell (i.e., move horizontally first, then vertically, to get to the next Bresenham point):
Of course, the second problem is the fact that it still doesn't look irregular and organic. It's still perfectly straight. There are (at least) two easy things we can do to resolve this. The first is to just roughen up the line a bit by simply randomly adding adjacent cells as we draw:
Already, it looks a lot better. This looks much more like an irregular cave passage than any of the previous iterations. (You could expand on this idea if you want by adding even more cells in a "radius" around the given cell, so that there are "bulges" in this path. I'll leave that as an exercise.)
But it still looks too direct. Not only does it still seem like it is directly connecting two points, it might be boring to the player to always move at essentially that same angle for a long journey through this part of the map.
The answer is to tesselate the path. Instead of just returning the Bresenham line between points (a,b) and (c,d), if the total distance is larger than some threshold, we randomize a point anywhere in the rectangle described by those two points - with the x value somewhere between a and c, and the y value somewhere between b and d - and instead take the Bresenham to those points and concatenate them. In other words, we return the Bresenham points from (a,b) to the random point, and then from the random point to (c,d).
This process is recursive, so if you pass a long enough line, it will tesselate many times:
Now we have a path that looks naturally-carved instead of human-carved! The look of the path can be adjusted by choosing the "tessellation threshold" to change how short each "leg" of a tessellated path needs to be. A small value would lead to very small pieces in the path, while a large value will guarantee large pieces (and less computation time).
This is one manner in which I generate passages in Lone Spelunker. There are other techniques which are employed as well, but this describes the core approach to how narrow passages like this are carved out of the rock.
No comments:
Post a Comment