The nodes I'm planning on using cover a rectangular area; a single one covering a 1x1 area is placed for every tile on the map. I've got an algorithm which expands the nodes down and to the right until they hit an unwalkable tile (they try to go south-east, then east, then south). If the node ends up containing another node, then a merge is done. It all works fine, except I end up with nodes that overlap.

I need either a way to keep them from overlapping or a way to slice them up so they don't overlap.

Thanks.

In Axis & Allies (and also Kohan 2: Kings of War), we had a map that was up to 512x512 tiles, were each tile was either mountains, water, or land. For most units, land was traversable, water and mountains were not. Obviously, ships and airplanes had slightly different rules.

We would divide the entire map into rectangles, where each rectangle was homogeneous - that is, every tile in a rectangle was of the same terrain type. Every tile on the map was in exactly one rectangle.

To accomplish this, we used a greedy algorithm which would start with the bottom left tile on the map. We would then try to construct the largest homogeneous rectangle that we could be alternately expanding the rectangle up and to the right. Each time we expanded to the right by one column or up by one row, we would check the resulting rectangle and make sure that it was still homogeneous. If it was not, we would stop expanding in that direction. Once we had expanded in both directions as far as we could, we would store that rectangle, and then do the same thing again with the new bottom-left tile. We kept doing this until the entire map was divided into rectangles (even if some rectangles contained only one tile).

We actually executed a follow-on step where we would take the very small rectangles and attach them to an adjacent rectangle. The resulting regions were not necessarily convex, but we were still able to path-plan over them effectively, and this prevented us from having a large number of tiny rectangles along the borders between terrain types.

Incidentally, I'm going to be giving a talk during the AI Summit at GDC this year that talks about all of this, as well as some of the ways that we used it.

P.S. I'm not sure that this is the best approach, or the fastest. On a the largest, most complex maps, on 2003-era min spec hardware it could take 20 seconds or so. I suspect that there are flood-fill algorithms that would work better. However, this had the benefit of simplicity, and it got the job done. Since we only did it once when creating the map, we were willing to take the processing hit (and on modern hardware it might not be an issue).

Also, if you are working on pre-drawn maps, it might make more sense to create the regions by hand, rather than computing them. We needed to do this because we had random maps.

Intended use is a Roguelike, with thought given to future use, so I don't exactly want to add much more time to map generation. :)

Might be able to hack up something tomorrow, but it won't be pretty.

So Rogue (and Nethack) had map generators that would create rooms connected by corridors. If your map generator does the same, a corridor is anything 1 tile wide. A room is anything not 1 tile wide. Should be pretty easy to find those, no?

Quote: Original post by Kevin Dill
So Rogue (and Nethack) had map generators that would create rooms connected by corridors. If your map generator does the same, a corridor is anything 1 tile wide. A room is anything not 1 tile wide. Should be pretty easy to find those, no?

Since I find making a game that only creates room-and-corridor maps deadly boring, it'll be rather more diverse than that. :)