Jump to content

  • Log In with Google      Sign In   
  • Create Account


Cellular Automata - Remove isolated sections quickly?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
3 replies to this topic

#1 Mythics   Members   -  Reputation: 135

Like
0Likes
Like

Posted 24 January 2012 - 03:50 PM

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.

Sponsor:

#2 nobunagaota   Members   -  Reputation: 183

Like
0Likes
Like

Posted 25 January 2012 - 02:37 AM

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

#3 LorenzoGatti   Crossbones+   -  Reputation: 2663

Like
1Likes
Like

Posted 25 January 2012 - 03:36 AM

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.
Produci, consuma, crepa

#4 Mythics   Members   -  Reputation: 135

Like
0Likes
Like

Posted 25 January 2012 - 06:07 AM

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




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS