Finding available area

ID:2820986
 
Sep 18 2022, 5:26 pm
(See the best response by Lummox JR.)
Problem description:

Making a procedural level generator, I keep running into the same roadblock if I try to make it less random and more specific.

Basically, if I pick a point on the map, I want to figure out how much space is available for a new feature - Or, at the very least, the largest rectangular area available without overlapping an existing room/hall. I've tried a few methods; the best two were sending out "Probes" in all 8 directions, and inflating a search "bubble" that fills the space (Up to a specified max room size). Nothing has really worked well for irregular spaces though.

Any thoughts on where to start going about this? Is there a library that covers a situation like this?
Sep 18 2022, 6:59 pm
Best response
You might want to pose this question in Roguelike development circles since it's basically in their wheelhouse, but the question depends on a number of factors. For instance, if your new feature is a rectangular room, you might have a maximum of 20 tiles of width available at only 5 tiles of height, but up to 10 tiles of height if you limit the width to 8 tiles.

For doing this quickly, I'd come up with a way of tracking rectangles of certain minimum sizes and keeping a list of those, then altering that list as new features were added.

For instance, say your entire level starts out as one big rectangle. After placing a room, you'd end up splitting that rectangle into four smaller overlapping rectangles around it. Every time you placed a new feature, you'd look at your existing rectangles and, if there was an overlap, split them up into smaller units. If any rectangles fall below the minimum width/height, you just remove them from the list.
Sep 18 2022, 8:14 pm
In response to Lummox JR
Huh! Thats exactly the kind of thing I was looking for, and I think it will work perfectly for my purposes! Thanks, I was a bit trapped in my own way of thinking of it, needed the external input!