Scanning a 2D tile map and detecting regions?

Question

I have access to all points/tiles on the map with top-right most point being (0,0). Simplest way to traverse the map would be using for loops, one nested within the other to traverse the x axis, and then y (going through rows). But to solve this problem, I would probably need to scan the map in a more intelligent fashion. The important thing to note is that I'm only able to check one tile at a time and see what type it is. So t.getCoordinates() would return something like (32,54) and t.senseTile() would return: WALL, ROAD, OFF_MAP, etc.

I wanted to scan the entire map and divide it up into regions. The regions would be of two kinds: "open" and "paths". For open regions, I just want to fill the entire region until it starts hitting boundaries, walls/obstacles, etc and stop the fill when appropriate. A rule for an open space is that a player should be able to get from one edge to another edge taking any path, angle, etc without bumping into some wall/obstacle.

For paths, there's certain number of tiles a region is limited to, then a new region starts (see lightBlue and gray).

Also, the paths should have entrances/exists also stored and to which regions they connect to. For example, scanning through a map like this (see pic), these regions should be generated. Not sure which data structure to use to connect them, but maybe a tree/graph would look like this:

  Gray
    |
 LightBlue
    |
   Pink
    |
  Yellow
    |   \
   Red  Black

Edit: I think Dijkstra's search algorithm could be a good starting point although I've never implemented it before. That only solves a small part of the problem. It still doesn't solve how it's going to detect regions. Also, I'm afraid Dijkstra's would be too costly in terms of time/performance (both are extremely important).

Answer 1

I'm a bit skeptical whether the auto-detection of paths will work for any map. I've come up with a heuristic to find paths, but it will subdivide your yellow region into various regions.

A horizontal path is a line of land that is bordered by land north and south of it. It has water to the west and east. These water tiles may be bordered of at most one other water tile to the north and south. Bridges should not exceed a maximum length. Likewise for vertical paths.

Scan your map for paths and set the tiles to a path id. (They are then no longer considered "land".) Then scan the map again and flood-fill each tile of open land with region ids. This will give you something like this, paths are marked in reddish colours:

You can then derive a graph with regios as vertices and paths as edges.

You'll note that the heuristic for finding paths is not very sophisticated. There should be a path subdividing the pale yellown region west near the L-shaped water patch. There shouldn't be paths around the central square pool.

I think it is very hard to find a satifying algorithm that can account for such cases in general. Maybe you can have an aggressive path algorithm that creates too many paths and then find a way to join the regions according to another heuristic, but I doubt it.

I think that it is better to define the paths by hand and then just find the regions. Or you have to mark the original map with possible locations for paths.