Show Posts
1
Programming / Re: Connecting rooms
« on: June 11, 2009, 07:19:31 PM »
If you want to minimize the amount of long corridors you end up with, try creating a minimum spanning tree.
Start by figuring out all the separate areas you have (if you don't know, a flood fill will do it), then figure out the distance between each pair of areas. Take all of those distances and sort them by length.
Take the shortest of those distances and join the two areas linked by that distance, then mark those areas as being the same group. Then take the next shorted distance and check that the two areas are different groups: if they are, link those and mark them as the same group. If they're not, ignore it. Either way, go to the next one.
Repeat that (going through the shortest remaining distance and connecting if they're not already connected to eachother) until you only have one area remaining. Once you do, you have a fully connected level with a minimum number of corridors.
There's a few weaknesses to that approach. It does tend to make lots of dead-ends, and never creates a loop, so you'd be wise to sometimes connect two rooms even if they're already in the same group. Additionally, it's possible to make an even shorter set of corridors by allowing branching corridors, which this algorithm doesn't handle. But you can scatter some 1x1 "rooms" around your level to give branches a chance to form and possibly make the level more interesting. Just be careful because that can end up creating dead-end corridors as well.
Start by figuring out all the separate areas you have (if you don't know, a flood fill will do it), then figure out the distance between each pair of areas. Take all of those distances and sort them by length.
Take the shortest of those distances and join the two areas linked by that distance, then mark those areas as being the same group. Then take the next shorted distance and check that the two areas are different groups: if they are, link those and mark them as the same group. If they're not, ignore it. Either way, go to the next one.
Repeat that (going through the shortest remaining distance and connecting if they're not already connected to eachother) until you only have one area remaining. Once you do, you have a fully connected level with a minimum number of corridors.
There's a few weaknesses to that approach. It does tend to make lots of dead-ends, and never creates a loop, so you'd be wise to sometimes connect two rooms even if they're already in the same group. Additionally, it's possible to make an even shorter set of corridors by allowing branching corridors, which this algorithm doesn't handle. But you can scatter some 1x1 "rooms" around your level to give branches a chance to form and possibly make the level more interesting. Just be careful because that can end up creating dead-end corridors as well.