2
\$\begingroup\$

How do I get all areas surrounded by a certain color in a multidimensional array?

For example, this map has three regions that are fully enclosed by red tiles. They are highlighted enclosed in pink.

enter image description here

I'd want the algorithm to return three regions, with the positions of the tiles inside them.

How can I do this?

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

I would use this algorithm (in pseudocode):

iterate your whole playing field to create a list of all non-red tiles called LIST
while LIST has entries
    flood-fill from the first entry of LIST
    remove the results of the flood-fill from LIST
    if no result of the flood-fill is at the edge of the map
        add floodfill result to surrounded areas
\$\endgroup\$
5
  • \$\begingroup\$ Thanks, seems like a great solution, but how would i do the "flood-fill from the first entry of LIST" ? \$\endgroup\$
    – Andries
    Dec 4, 2015 at 15:04
  • \$\begingroup\$ I assumed you already know how flood-fill works. Do you need an explanation of the flood-fill algorithm? Or do you want to know how to get the first element of an array in Javascript? \$\endgroup\$
    – Philipp
    Dec 4, 2015 at 15:26
  • \$\begingroup\$ I'm not sure how i would do the flood-fill and return the results to check if they're at the edge of the map. \$\endgroup\$
    – Andries
    Dec 4, 2015 at 15:40
  • \$\begingroup\$ A tile is at the edge of the map when its x- or y-coordinate is either 0 or maximum. To return a list of results from a flood-fill, you need to pass said list between recursive calls and add any newly visited tile to it. \$\endgroup\$
    – Philipp
    Dec 4, 2015 at 16:32
  • \$\begingroup\$ @AndriesvandenBerg An answer would be too long for a comment. Please post a new question. \$\endgroup\$
    – Philipp
    Dec 4, 2015 at 16:34
0
\$\begingroup\$

If I understood what you are asking, for every non-red, border tile, flood red. At last the non-red tiles are surrounded by red.

In the example starting from top-left corner going anti-clockwise...

enter image description here

\$\endgroup\$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .