1

**Journals / Re: Merrak's Isometric Adventures -- Illumination Adventures**

« **on:**June 23, 2017, 11:26:21 pm »

**Demo 4.**My "growing squares" algorithm came together rather nicely. I probably didn't use the most efficient method, but it runs at a stage where speed isn't essential--so I went for a simpler idea that's easier to visualize. "Growing squares" is a bit of a misnomer, since it produces rectangles... but that's the name I assigned in my notebook so it stuck.

The goal is to take any polygon region, with or without a hole, and with 90-degree angles, and partition it into rectangles. I haven't thought about whether or not it finds the optimal solution, but I would be surprised. I went with the first idea that came to mind. On the small scale I'm using this on, if I have lag due to too many wall face partitions, finding the optimal solution to this problem is unlikely to fix it. So, here's my result.

It's kinda hard to read the text, but here's what it says. Click on tiles to toggle them (create and remove holes). Once you're satisfied with the terrain, press enter to generate the partitions. Press r to start over. This is only a quick test, so if you need more than 14 colors, some partitions will share the same color. Sadly, this demo took me more time to debug than the actual algorithm--but it's much easier to progress knowing this works, so it's worth it.

I realized there's another good use for this algorithm. Suppose you are using the Tile API to generate a bunch of tiles, but now you have hundreds of individual collision boxes. You can use this algorithm to compute and construct a small number of rectangle terrains to replace the tiles' individual collision boxes.

I built this on top of my own version of the AI Tools extension (because I use a graph), so I could wrap this into a future release. But the algorithm itself is a simple idea that could be implemented using the Tile API instead. Here's how it works if you want to use it for yourself or improve it.

Consider a 2D array of uncolored tiles and the goal of coloring them in such a way that tiles that make up a larger rectangle are colored similarly. Pick the next available color and color the first uncolored 1x1 tile (searching from upper left to bottom right).

If it is possible, add a new column and a new row to the current partition. To add a new column, every tile to the right of the current partition must exist (not a hole) and be uncolored. Keep adding new columns and rows until it is impossible to add either. Then start over with a new color and the first available uncolored tile.

Progression might look like this (where X is a hole):

Code: [Select]

`"Growing Squares"`

Input: a 2D array of uncolored tiles

Output: a 2D array of colored tiles, where colors represent rectangle partitions

0. Set next_color to 1

1. Starting from the upper left and searching rightward and downward,

pick the first uncolored tile at (r,c). If there are no uncolored tiles, then done.

2. Set the color at (r,c) to next_color

3. Set width to 1 and height to 1

4. If every tile to the right of the (width x height) box exists and is uncolored, then increment

width by 1. Color all the tiles in the new column.

5. If every tile to south of the (width x height) box exists and is uncolored, then increment

height by 1. Color all the new tiles in the new row.

6. Repeat steps 4 and 5 until neither width nor height can be incremented.

7. Increment next_color by 1