Keywords: interval search tree, random number, brute force, dungeon, game, main, circle, code, runtime, article, construction. Powered by TextRank.
The basics of any roguelike dungeon crawling game is the dungeon. What makes these types of game infinitely replayable is their use of procedural generation to produce a new dungeon and artifacts for each game. Some one in the internets came up with the idea of generating dungeons based on "pushing out" random rectangles generated with in a circle. To get more realistic results it's best to use a Gaussian random number generator, as rarely anything natural is uniformly randomly created.
So create some random rectangles with in a cirlce:
for i in range(0, num_cells):
var xy = get_xy()
var wh = get_wh()
var type = "hall"
if wh.x * wh.y > mean_width * mean_height * 0.9:
type="room"
cells.append({"id": i, "xy": xy, "wh": wh, "topleft": xy, "bottomright": xy + wh, "type":type})the get_xy makes sure that the top left lies in a circle:
func get_xy(): var r = 100 * randf() var theta = randf() * 2 * PI var x = r * cos(theta) + 300 var y = r * sin(theta) + 300 return Vector2(x,y)
make sure that the width, height is acceptable:
func get_wh(): var w = gaussian(mean_width, width_dev) var h = gaussian(mean_height, height_dev) if w < 10 or h < 10: return get_wh() return Vector2(w,h)
now push the rectangles outwards:
while touching: touching = false for i in range(0, num_cells): for j in range(i+1, num_cells): var a = cells[i] var b = cells[j] if touches(a, b): touching = true var dx = min(a["bottomright"].x - b["topleft"].x + padding, a["topleft"].x - b["bottomright"].x - padding) var dy = min(a["bottomright"].y - b["topleft"].y + padding, a["topleft"].y - b["bottomright"].y - padding) if abs(dx) < abs(dy): dy = 0 else: dx = 0 var dxa = -dx/2 var dxb = dx + dxa var dya = -dy/2 var dyb = dy+dya shift_cell(a,Vector2(dxa, dya)) shift_cell(b,Vector2(dxb, dyb))
Now some of the rectangles are designated as rooms if there are bigger than an average value in area. We want to use these as the main nodes for joining the rooms together.
cells.sort_custom(AreaSorter, "sort") var num_rooms = 0 for c in cells: if c["type"] == "room": num_rooms += 1 for i in range(0, min(num_rooms, num_corridor)): var c = cells.pop_back() rooms.append(c)
Now connect the main rooms using Relative Neighborhood Graphs (RNG)
# connect main rooms var ab_dist = 0 var ac_dist = 0 var bc_dist = 0 var skip = false for i in range(0, rooms.size()): for j in range(i+1, rooms.size()): skip = false ab_dist = pow(center_x(rooms[i]) - center_x(rooms[j]), 2) + pow(center_y(rooms[i]) - center_y(rooms[j]), 2) for k in range(0, rooms.size()): if i == k or j == k: continue ac_dist = pow(center_x(rooms[i]) - center_x(rooms[k]), 2) + pow(center_y(rooms[i]) - center_y(rooms[k]), 2) bc_dist = pow(center_x(rooms[j]) - center_x(rooms[k]), 2) + pow(center_y(rooms[j]) - center_y(rooms[k]), 2) if ac_dist < ab_dist and bc_dist < ab_dist: skip = true if skip: break if not skip: if not rooms[i]["id"] in graph: graph[rooms[i]["id"]] = [] graph[rooms[i]["id"]].append(rooms[j]["id"])
The RNG construction and the overlap checking code is the brute force way of solving these problems. The overlap checking can be done using an interval search tree for a better runtime performance, and the wikipedia article mentions a paper with an algorithm to do it in linearithmic time. But since the number of rooms in a dungeon are relatively small, it's not worth the added code complexity
492 words
Powered by TF-IDF/Cosine similarity
First published on 2017-05-13
Generated on 13 Dec 2024 at 12:11 AM
Mobile optimized version. Desktop version.