Jump to content

  • Log In with Google      Sign In   
  • 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.

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

#1 shadowgamesco   Members   -  Reputation: 326

Like
0Likes
Like

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:

Posted Image

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.

Sponsor:

#2 SiCrane   Moderators   -  Reputation: 9119

Like
3Likes
Like

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.


#3 Lightness1024   Members   -  Reputation: 663

Like
1Likes
Like

Posted 24 August 2012 - 04: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

#4 Servant of the Lord   Crossbones+   -  Reputation: 14848

Like
1Likes
Like

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.

Posted Image

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.

Posted Image

It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.

[Fly with me on Twitter] [Google+] [My broken website]

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.                                                                                                                                                       [Need free cloud storage? I personally like DropBox]

Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal


#5 jwezorek   Crossbones+   -  Reputation: 1596

Like
1Likes
Like

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

#6 shadowgamesco   Members   -  Reputation: 326

Like
0Likes
Like

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.



PARTNERS