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).