Jump to content
  • Advertisement
Sign in to follow this  
AuthenticOwl

Maze Trimming

This topic is 1093 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I (like so many others here) am working on some procGen maps.
I stumbled upon this example: https://paginas.fe.up.pt/~ei12085/misc/dungeon-generator/?w=64&h=24&mazeType=random&roomAttempts=100&roomMinSize=1&roomMaxSize=5&connectiveness=0.02

Now, I understand the majority of the algorithm (or at least can replicate the effects)... but the last step is where I was hoping for some help.

As the demo shows, it selects placement for some rooms, then builds a maze around it.
Then using a connectiveness value it cleans up the majority of the maze, leaving only a few laborinthesc hallways.

I was trying to come up with a similiar algorithm, but i don't think my idea is as efficent as the method the demo uses.

My Idea was to label each room with a unique RoomId, then the maze path would not have a roomIds. Then I would iterate marking any square without a roomId with the roomId of an adjacent cell. If there are multiple adjacent RoomIds then:
If the RoomIds are distinct-> Do nothing (Indicates the hall connects to a different room)
If the RoomIds are the same, randomly choose to remove one of the halls or not.
If the choice is made to remove a hall randomly choose one of the halls to remove.

But I don't think the demo uses that algorithm... the algorithm used looks to be O(n) as cells in the top left are trimmed before cells in the bottom right regardless of room proximity and etc...

Share this post


Link to post
Share on other sites
Advertisement

If you want to trim everything not connected to the rooms, start a flood-fill from any room, marking all cells you reach as reachable from that room (including all other rooms).

 

Everything you did not reach, is not connected to the rooms. Either you can move visited cells to a "connected" collection, or you can do a second pass to remove the ones that were not marked as visited, result is the same.

 

It seems you are already using flood-fill, but possibly an inefficient algorithm? Instead of iterating over ALL cells to find the border cells, instead you should maintain an explicit list of the border cells so no such search is ever necessary (use that list to construct the new list for the next iteration).

Share this post


Link to post
Share on other sites

Just to clarify, are you trying to implement the same algorithm used by the demo? Or are you trying to implement a slightly modified variation? Because the demo you posted has a link to the article upon which it is based, which itself contains a link to the code used by the demo and the author's game.

Share this post


Link to post
Share on other sites
@Waterlimon: My current algorithm creates a map where every cell that is open is accessible.

@Zipster: I am not trying to use the alg used by the demo, the article linked points to a different (very similiar generator). The algorithm I am using works much differently in the room placement step, but the part I want emulate is where it takes the maze that fully fills non-room area and trims many branches such that the resulting maze still has all rooms connected, but not every bit of open space is filled with maze corridors.


I think the issue is that my maze paths Through the rooms, where the one in the demo doesn't connect the rooms to the maze until the next step... but once that is done, the last step is simple trimming dead ends? (Pathing through rooms leaves no dead ends)

Share this post


Link to post
Share on other sites

Filling in dead-ends is fairly straightforward, since dead-end cells are well-defined -- any open cell that is surrounded by walls on exactly three sides is a dead-end.

 

There are multiple ways to do this. The first, and easiest to implement, is to iterate every cell on the map and fill in those that match the dead-end criteria. Repeat this over multiple passes until no more cells are filled in, and you're done. Optionally, if you want to keep a few dead-ends for variety's sake, you can define a max number of passes so that not all dead-ends are removed.

 

The second approach uses pathfinding techniques and is closer to what you see in the demo. Iterate the map as before, but once you find and fill in a dead-end cell, look to see if there are any adjacent dead-end cells. If there are, fill those in too, and repeat the process on all those cells. You're essentially flood-filling dead-end cells with walls. Again, you can define a threshold value past which to stop filling if you want to leave some dead-ends.

Share this post


Link to post
Share on other sites


any open cell that is surrounded by walls on exactly three sides is a dead-end.

True enough, but that doesn't catch cases where larger segments are are inaccessible.

 

Some areas may connect only to each other but be disconnected from the rest of the maze.  A direct flood fill Waterlimon suggested is still likely the easiest solution.  There are likely more mathematically-based graph algorithms to find segments that are not connected together, but a flood fill is easy to describe, to implement, and adequate for the solution.

 

Another option is to have objects in the game that can cut through walls: pickaxes, wands of digging, or whatever. Then the rooms are bonus areas. :-)

Share this post


Link to post
Share on other sites

True enough, but that doesn't catch cases where larger segments are are inaccessible.

It was my understanding that the OP already had a map where all areas were accessible to all other areas, as per their response to Waterlimon, and that they just wanted to prune excess hallways. However I concede that I could be misinterpreting their reply, and that "accessible" means something else to them.

Edited by Zipster

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!