• Create Account

## Finding tiles that touch in 2D array

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.

5 replies to this topic

### #1Breiny Games  Members

Posted 24 August 2012 - 07:52 AM

Hey guise, I have been working on a Map Engine for my 2D RPG. The game takes place on an island, and a brand new random island each time you start a new game. So I wrote an Island Generator that produces maps that look something like this:

It's pretty easy to tell which areas of the map are deep/shallow water, beach, grassland, forest, or mountain. The map stores a 2D array of 'tiles'. Each 'tile' stores it's location on the map, the type of tile it is, etc. So now I want to be able to access each individual forest area from that 2D array.
There are six separate forest areas in the above picture. How could I access each area individually from the map? I'd like to do this so I can name each forest, make one or two haunted, or just play around with each one so they're each different from each other. It just makes the game that much more interesting if you understand what I mean. Any help is greatly appreciated. And for any of you who are interested in how I did the island generator, I have a blog post on what I did here, and the source code here under the downloads tab.

### #2SiCrane  Moderators

Posted 24 August 2012 - 09:44 AM

Well the brute force method would go something like this:

1. Create a 2D array the size of your map, initialize each element to -1 if the corresponding map element is not a forest tile, and 0 if it is a forest tile. Set number of forests to 0.
2. Find an array element with a 0 value. If there is no such element, then you're done. If there is such an element, increment the number of forests.
3. Change the value of that element to the number of forests, and then use flood fill to set all adjacent 0s to the same value.
4. Repeat from 2.

### #3Lightness1024  Members

Posted 24 August 2012 - 04:41 PM

that is some great start !
also on a separate issue, you can try to fit place circles randomly, that you grow until they touch a border of a different region, this could locate the largest region and give a hint as where to place the text of the name.. just a thought

### #4Servant of the Lord  Members

Posted 24 August 2012 - 05:27 PM

I agree with SiCrane about Flood Filling, though depending on the results you want, maybe if a "Forest" is less than 'n' pixels, don't count it as a distinct forest, but match it to the nearest real forest. If the small patch of trees is too far away from any real forest, or if it's divided by some other type of terrain besides grass, it should count as it's own forest anyway (maybe calling it a grove instead of a forest), unless it's really small and probably shouldn't be named at all.

There are several ways to add this: One way is to keep the 'total size' of each forest, and if a forest is too small, find the closest forest less than a max distance, and head in a straight line between them to check if you encounter any non-grass tiles.

Also, if one large forest narrows to a point less than a certain amount before widening out again, it should maybe count as two separate forests. That might be harder to calculate though (but doable with some thought), and it depends on what you're actually wanting.

It's perfectly fine to abbreviate my username to 'Servant' or 'SotL' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames -

### #5jwezorek  Members

Posted 24 August 2012 - 05:27 PM

This old thread is on the same topic:
http://www.gamedev.net/topic/615697-finding-enclosed-tiles/

Basically, do what SiCrane says above or if you want to get fancy and not do floodfills, do the Two-pass algorithm here:
http://en.wikipedia.org/wiki/Connected-component_labeling

### #6Breiny Games  Members

Posted 25 August 2012 - 06:25 AM

I really appreciate all of your answers guys, thank you! I actually put a lot of thought into what was said, and I did implement what SiCrane mentioned. I used the floodfill algorithm to find the seperate forests, mountains, lakes, etc. and I also made it so the program cleans up the areas that are too small to be an actual forest, lake, mountain, etc.. So now if a 'forest' is small but not too small, it's a grove instead. If it IS too small, then we get rid of it. I did the same thing with the lakes and mountains too, so now the game not only has forests, lakes, mountains, but also groves, ponds, and caves, in addition to no more small patches of tree or rock areas that are wayy to small to be anything, resulting in a much cleaner, more realistic map. Thanks again for all of your ideas.

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.