Jump to content
  • Advertisement
Sign in to follow this  
Mythics

Cellular Automata - Remove isolated sections quickly?

This topic is 2518 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

Hope this is the right forum, if not please point me in the right direction.


I'm working on a roguelike that does level by level design using cellular automata for cave-like dungeon generation.

My issue is that my maps are fairly large. 500x500 grid typically to start with. To have the look that I'm going for, I am still occasionally coming up with disconnected smaller areas of floor tiles.

My question, how would you go about simply removing these smaller areas in the fastest method possible?

I'm writing this in C# using XNA, 2D Sprite based. The map simply consists of wall and floor tiles.

My current method of handling this is:

1. Look through every tile on the map.
2. If the current tile is not in the array BigOList and is a floor tile, use Dijkstra's algorithm to compile a list of all floor tiles within this section.
3. Save this list as an array element within the array BigOList.
4. Go back to step 1 until every tile has been checked.
5. Check BigOList for the largest section, set all other sections to be wall tiles.


The performance issues here may be my bad coding, but if not, I'd love to hear how someone else would or has handled this sort of scenario.

Share this post


Link to post
Share on other sites
Advertisement
Sprite-based rogue-like in XNA, eh? Seems like we have similar interests, my friend.

I was recently playing with CA-based cave generation as well. My approach was to connect isolated sections to my largest "cavern" with A*. In order to do so, I had to know where all my "caverns" were, so a variation of that may help you. My approach was to use a flood-fill to fill contiguous floor areas with a number that I could then use to identify the various rooms within my cave. I'm not sure how the performance will work for you since I used much smaller caves (60x30 or so).

I detail what I did on my blog here:
http://gamedevwithoutacause.com/?p=460

Share this post


Link to post
Share on other sites
You can run a traditional union-find algorithm on your tiles to find connected components of non-wall tiles, additionally maintaining a set of connected components and a count of the tiles in each connected component.

Share this post


Link to post
Share on other sites

Sprite-based rogue-like in XNA, eh? Seems like we have similar interests, my friend.

I was recently playing with CA-based cave generation as well. My approach was to connect isolated sections to my largest "cavern" with A*. In order to do so, I had to know where all my "caverns" were, so a variation of that may help you. My approach was to use a flood-fill to fill contiguous floor areas with a number that I could then use to identify the various rooms within my cave. I'm not sure how the performance will work for you since I used much smaller caves (60x30 or so).

I detail what I did on my blog here:
http://gamedevwithoutacause.com/?p=460


Thanks a ton. It looks like you did a much cleaner version of what I was attempting. I really do appreciate the help.

I'll give this a shot and see what I can manage to break next :P

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!