🔒 Locked

Finding tiles that touch in 2D array

Started by CBreinholt Aug 24, 2012 at 1:52 PM 4 replies 3.3k views

Original Post

Aug 24, 2012 at 1:52 PM

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:

Screen+shot+2012-08-24+at+7.14.37+AM.png

Screen+shot+2012-08-24+at+7.14.37+AM.png

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.

SiCrane

Aug 24, 2012 at 3:44 PM

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.

Lightness1024

Aug 24, 2012 at 10:41 PM

that is some great start !
about the answer, i would have said like sicrane, provided I understood your problem correctly.
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

Servant of the Lord

Aug 24, 2012 at 11: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.

[hr]

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.

jwezorek

Aug 24, 2012 at 11: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

CBreinholt

Aug 25, 2012 at 12:25 PM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.