I have been following several guides for procedural generation of levels and have settled on a technique that spawns rectangles of random dimensions as the initial rooms. However, I cannot figure out how to separate them. The behaviour I’m wanting has been referred to as “separation steering behaviour”.
Is there a standard or recommended way to sequentially separate actors so that none of them are overlapping? Every solution I come up with either results in having the rectangles locked to the four intercardinal direcitons or an infinite loop (as any two actors overlapping move identically).
It sounds like right now you’re spawning a set of initial room placements at the same time.
Typically this is done on a one by one basis with two functions, something like SpawnRoom and OverlapsEntities, where OverlapsEntities returns a bool if the next room to be generated would overlap with existing rooms.
I would also recommend that rooms be spawned with another room as a “root” for the new room.
Something like the following:
// psuedo
root = rooms.choose(1)
new_room = null
while(true):
new_room_location = transform_within_distance_of_location(root.transform, distance,
possible_rotational_offset = [0, 45, 90])
new_room = new Room(new_room_location)
valid = true
for room in rooms:
if overlaps_entities(new_room, room):
valid = false
if valid:
break;
Thanks very much for the answer and the source, very useful reading. I’ve been working in blueprint so I was looking to stay in blueprint if possible. I hadn’t considered a sequential spawning method, and was basing my ideas off the dungeon generation from TinyKeep (algorithm showed graphically here).
My approach so far has used collision meshes but I can’t get a cohesive pawn AI to separate them, and I imagine it would be quite processor intensive. I did have an idea to sequentially spawn in a fractal pattern from a root which would save rearranging things, but the mathematics partially eludes me and I think it could pose issues with random room size outliers throwing off the size of the fractal.
First off, it may be processor intensive to spawn hundreds of rooms maybe, but for a few dozen, I think it would be hard to tax the CPU without going into an infinite loop! So any algorithm that comes to mind, go for it! Unless maybe that algorithm requires spawning a lot of objects, which can be an intensive task. Would you be able to show the Blueprints for what you have so far? Maybe we can modify them from there to make things work. Otherwise, I may have time this Sunday to look at this properly for fun
What I actually did in one of my experiments with this was put sockets at the edge of meshes that count as connection points. I also had a struct that would contain a list of connection points and if they had been connected to or not yet. I would then spawn rooms at only the sockets. This required a little monkeying with the rooms to get the offset correct for the actor, but after I got that working it was super simple to connect them to each other without overlaps.
Hi, thanks for replying again! I’ve ended up with a couple of different methods and not entirely sure which way to proceed for any of them. I can update with a more detailed explanation later on, including blueprint screenshots, but I wanted to give a quick summary before I forget about the different methods.
TinyKeep Method - This was based on the very elegant method used in TinyKeep, linked in my first response above. It spawns rectangles of random sizes within a defined radius, separating them out with steering behaviour, selecting random large rectangles for rooms and triangulating connections between the rooms to generate the corridors from surrounding grid squares.
I made some progress with this, and managed to spawn a desired number of rectangles within a definable radius, generating overlap events. The rectangles were spawned as static meshes so there wasn’t much overhead, but I couldn’t quite put my finger on how to separate them. The main issue I can see here is that there is no defined grid or co-ordinates to work with, unlike the way the original algorithm was implemented. I would also expect the behaviour required for steering would be AI drive in UE4, which would be quite processor intensive.
Instanced Floor - based on the introduction to one of the UE4 procedural generation tutorials, this generated instanced static meshes of a floor tile to form an X,Y grid of floor tiles. Based on each tile’s corresponding value in an array, a specific tile type can be spawned at the appropriate co-ordinate.
While this is not capable of spawning specific rooms or shapes in its basic state, it is very quick to generate a random field of…stuff. Instanced static meshes, to my understanding, are very quick and cheap. Seems like it could be a good starting point for quick cheap dungeon generation.
Quadtree Generation - based on the main part of the UE4 procedural level training stream (will add a link later on) this generates quad trees before assigning rooms and digging corridors.
Very elegant and I tried my hand at this, but I have yet to finely grasp some of the concepts.
Standard Rogue-like Array - a lot of algorithms around for this, including standard maze generation and seeding of rooms, but Bob Nystrom’s articles have been really key to me being able to wrap my head around the generation.
While I have no clue where to begin with translating it to Unreal Engine, I anticipate it would require coding rather than blueprinting. Again, the main issue I can see is that there is no grid pre-defined in Unreal.
The main factor holding me back at the minute is my understanding and level of knowledge of the unreal engine. Specifically, the definition of a workable grid is (I think) where I’m falling down. The idea I’m favouring at the minute is a combination of the Instanced Floor and Standard Rogue-like Arrays. If I can generate code to produce a rogue-like dungeon in the form of an array only (e.g. tile 0,0 = corridor piece; tile 0,1 = empty) I could then feed this to an instanced static mesh loop, which would spawn the appropriate room/room piece at the corresponding tile.
Sorry if this is a bit of a long reply! I wanted to get everything down before I forgot everything. I can update later on with some screenshots of blueprints too.
Sorry for the delay in replying, I haven’t been able to get into UE4 for a little while.
I’ve started with blueprints for the Tiny Keep method, which successfully generates rectangles within a radius but separating them proved difficult. This was the problem that originally started the question - if I was able to get them separated, the next step was to work on generating corridors to link the rooms up. As mentioned above, the lack of a tangible grid seemed to be the hindering factor in tying this method with existing algorithms.
The Instanced floor blueprint works fine and can generate a dynamic floor based on the contents of an array, which is currently populated at random. It is expandable to any amount of floor tile ‘types’ but I’m not sure how limited it would be in terms of generating corridors or functional dungeons.
Although I haven’t had time to do any more scripting, the approach I’m leaning towards currently is to generate an array separately, and then use the instanced floor blueprints to build the dungeon tile by tile. I would think this array population needs to be done in C++, either for simplicity or for functionality/efficiency reasons. I think I definitely need to start learning some code!
