Hi there, I’m making a top down RPG (similar in perspective to the old final fantasy games or StardewValley) and I’m having some issues with setting up a simple procedural dungeon generator.
I want the generator to be room based, so I’m making room prefabs that get instantiated onto connection points. The issue I’m having is that the way I’m checking to see if a room location is valid (i.e. check to see if the new room is overlapping any other room) is happening after all the rooms get generated rather than when each room is first generated. I’m using OnTriggerEnter2D and I’m guessing what’s happening is that this is only getting called at the end of the frame, and that the rooms are all being generated too quickly.
Here is my room generation code:
public void GenerateRooms()
{
ClearRooms();
GameObject starterRoom = null;
// Generate starter room here
SetRoomParent(starterRoom);
starterRoom.transform.localPosition = Vector3.zero;
roomList.Add(starterRoom);
// Now generate adjacent rooms based on the rooms in the starter room
DungeonRoom starterDungeonRoom = starterRoom.GetComponent<DungeonRoom>();
for (int i = 0; i < starterDungeonRoom.roomWaypoints.Count; i++)
{
if (starterDungeonRoom.roomWaypoints[i].open)
{
for (int j = 0; j < starterDungeonRoom.possibleRooms.Count; j++)
{
GameObject adjacentRoom = (GameObject)PrefabUtility.InstantiatePrefab(starterDungeonRoom.possibleRooms[0]);
SetRoomParent(adjacentRoom);
adjacentRoom.transform.localPosition = Vector3.zero;
DungeonRoom adjacentDungeonRoom = adjacentRoom.GetComponent<DungeonRoom>();
Transform targetTransform = starterDungeonRoom.roomWaypoints[i].waypoint.transform;
float xOffset = adjacentRoom.transform.localPosition.x - adjacentDungeonRoom.roomWaypoints[0].waypoint.gameObject.transform.localPosition.x;
float yOffset = adjacentRoom.transform.localPosition.y - adjacentDungeonRoom.roomWaypoints[0].waypoint.gameObject.transform.localPosition.y;
adjacentRoom.transform.localPosition = targetTransform.localPosition + new Vector3(xOffset, yOffset, 0);
if (!adjacentDungeonRoom.validLocation)
{
DestroyImmediate(adjacentRoom);
}
else
{
starterDungeonRoom.roomWaypoints[i].open = false;
roomList.Add(adjacentRoom);
break;
}
}
}
}
}
The DungeonRoom script attached to every room prefab has a OnTriggerEnter2D that changes the validLocation variable if another room overlaps, but like I said, I think it’s happening too late.
Now this is a super basic method, only generating 1 starter room and 4 adjacent rooms right now, not much of a dungeon, but I want to make sure I have a good way to determine valid location before I keep moving forward.
If there’s another option of checking if rooms are overlapping feel free to suggest it, this just seemed like the best option for me when I thought about it, but I’m pretty flexible as to what to use.
What shapes do rooms have? You could always do manual detection based on geometry.
If you want to stick to your solution, you can move your code into a coroutine and do something a bit like
private IEnumerator Foo()
{
while (generatingRooms)
{
SpawnOneRoom();
yield return new WaitForFixedUpdate(); // Waits for the physics update
CheckForCollisions();
}
}
Downside is the generation will be done over multiple frames. Quite a bunch if you’re getting a bunch of overlaps I guess. However, if you need to use the physics system to check after every instance, I don’t think you have much of a choice. If there’s a way to force update of physics manually, I’m unaware of it.
Hey thanks a lot for the reply! I was actually in the middle of experimenting with a coroutine when I saw this! I was trying to use WaitForEndOfFrame() but I found that a single one of those wasn’t working perfectly, I tried two and that seemed to be working better, but your suggestion of WaitForFixedUpdate() is working as intended so that seems cleaner for sure!
This does seem to be working now, not sure if there are any cases in which it will be a problem using physics for this, like you mentioned. It’s going to be slower I guess, which is a shame, but I’m not sure I know of another way to do this frankly. You mentioned checking with geometry? Not sure how to do that, right now all my rooms are rectangular, but I wouldn’t mind adding other types of shapes.
Can the rooms be mapped to a grid? For instance, can you say this room is 4x8, this one is 12x1, this one is 8x2, or is it more of a this one is 12.235x4.23 type of deal? There’s easy detection for both, but if you can map to grid, it’ll be easy to extend when adding different shapes.
If it can be mapped to a grid, do it! When spawning a room, check against an array to see if all the units needed are available.
If it can’t be mapped for a grid, just search for rectangle overlap detection. It’s very easy to implement. However, this gets a bit harder when implementing rooms shaped like unusual polygons.
Interesting, yeah I would say my rooms will fit into the category of simple measurements like 4x8, or 12x1, even if some are circular or rectangular.
So, I guess if I’m understanding you correctly, you’re saying I could build a large array (maybe of bools?) to represent the dungeon and then mark them to true, or false based on if their spot is occupied?
That seems interesting, but I guess I would need to specify a dungeon size first for that right? So a 50 dimensional array could hold 5 10x1 rooms horizontally for example?
Maybe I’m misunderstanding what you mean, but that’s my interpretation. Seems interesting but also more complicated haha
If you want to keep it stupid simple, you can map your dungeon like this.
private Dictionary<Vector2Int, bool> map = new Dictionary<Vector2Int, bool>();
And then you can add this to your room class
public class Room : MonoBehaviour
{
[SerializeField]
private Vector2Int roomSize;
public Vector2Int RoomSize { get { return roomSize; } }
}
Then all you need to do is determine the starting position of the room. Say it’s in the bottom left, then you iterate through the positions, starting at 0, 0.
Perhaps the room starts at 14, 22? Then it goes a bit like this
private bool WillMySuperRoomFit(Vector2Int startPosition, Vector2Int roomSize)
{
for (int x = 0; x < roomSize.x; x++)
{
for (int y = 0; y < roomSize.y; y++)
{
Vector2Int position = new Vector2Int(startPosition.x + x, startPosition.y + y);
if (map[position])
{
return false; // This spot is already taken
}
}
}
return true;
}
If you decide to implement different shapes of room later on, then maybe pass a list of positions used by the room, instead of the roomSize, and iterate through those.
You could still use rectangle overlap detection algorithms instead of iterating through all the positions. This will prove a bit faster, but then you’ll need to implement different overlap detection algorithm for all the shapes you add, as you add more. This may or may not be what you want.
Thanks for taking the time to explain this in detail! Super interesting implementation, and now that I see it, I’m sure I’ve played games that use this technique before! I think for right now at least, I’ll stick with the physics shapes because (now that it’s seemingly working!) it does seem a bit more design friendly when I try to add new rooms and such, but if the performance becomes too slow as the dungeon grows (I’m only instantiating about 5-10 rooms right now) I’ll consider switching to something like the array system, it does seem nice for huge dungeons that could be slow to calculate physics for.
