koobas.hobune.stream
Determining groups in a 2D array by checking neighbours (and their neighbours etc)
I am reading data from a text file which will have the layout for a level, for example:
1 1 0 0 0 0 G G G
1 1 0 0 0 0 R R R
1 1 0 0 0 0 B B B
1 1 0 0 0 0 G G G
1 1 0 0 0 0 R R R
1 1 0 0 0 0 B B B
The characters are read to determine what to place in that position in the scene, so a 1 is a standard grey platform, while R, G, and B represent coloured platforms. This works fine but each platform us made up of 1x1 squares which is later particularly inefficient when I change the platform colours as part of the game.
In order to reduce the number of platforms, I want to determine if the neighbouring characters in the text file are the same as the current one and form platforms based on that, so in the example above, there would be one standard grey platform 2 wide and 6 long.
Update:
When reading from the text file, I now check the next tile in the column to see if it is the same and scale up a 1x1 platform to whatever size is necessary, so in the example above, there would be 2 1x6 grey platforms, and 6 1x1 red, green, and blue platforms. I have done it this way because it is easy enough to check the rest of a column (I could also do rows but have started with columns) and then the shape of the platform will never matter.
My issue remains the same:
If I was the check all neighbours (so rows and columns), how would I go about determining the shape and position of the overall platform? And what if I have a non regular quadrilateral (e.g. with a hole in the middle, or perhaps a triangle, etc)? The issue here is I wouldn't be able to simply scale up a 1x1 platform. If that could somehow be created, that would be ideal, but if not, I would want to create the shape out of the fewest total number of platforms.
This sounds like a job for a recursive algorithm and a data structure.
Your data structure should contain whatever 'tileBlue', 'tileGreen', etc... are as well as a boolean (have i been checked?)
Your recursive algorithm should check the surrounding tiles of any given tile and run itsself on any that are equal and not already checked. Then your main nested loop can just skip any that are already checked and run your algorithm on any that arent.
You're missing the key point. If I check all neighbours, and there is an L shaped platform, how would you be able to deter$$anonymous$$e that shape and create a platform of that shape? You wouldn't simply be able to scale up a 1x1.
I guess you'll have to build your map out of vertical and horizontal blocks. It doesn't make much sense to design your map with tiles if it won't be represented by tiles.
Here is one algorithm. I sense is that it produces a good result, but not an optimal result, but in a quick 'napkin' sketch, I could not find a situation where it did not come up with an optimal result. I define optimal result as the fewest game objects.
Start with a nested for() loop that walks through each cell starting in the upper left corner.
If a cell has been marked as processed, go to the next cell
If a cell has not been process, it becomes an anchor cell
Check the cell below the anchor cell to see if it is a match, expand to 1 x 2 area if it is a match
If previous check succeeded, check the two cells on the right to see if you can expand it to a 2 x 2.
If the previous check failed, see if you can expaned to 2 x 1 area.
And so on
So basically you cycle back and forth between right and down. At each cycle, you see if you can expand your rectangle by testing the number that would grow the rectangle in either the down direction or the right direction. You stop when you cannot expand either right or down. The result becomes a single game object, and the cells that make that result are marked as processed.
Since you are walking the cells in a nested for() loop, you will know that everything to the left and above you will always be processed.
