1
\$\begingroup\$

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

enter image description here

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

\$\endgroup\$
  • \$\begingroup\$ It is not clear to me what you want exactly. I think the paths are the narrow bridges marked in red and the open regions should be the land ares between them. Should the algorithm detect the paths automatically? That's nigh impossible - For example, how should the algorithm know that the yellow area with the pool is one big square and not eight small ones with water in the middle. Likewise for the grey area: the part where the green star is will be considered a path. \$\endgroup\$ – M Oehm Jan 22 '14 at 9:28
  • \$\begingroup\$ The narrow red marks are entrances/exits to be detected by the algorithm. The pathways have a limit to how big a path region can be. If there is one long pathway like gray and light blue combined, then it would automatically start a new path region after a certain number of tiles which is does by cutting of gray when that limit is reached and starting a new region. \$\endgroup\$ – Faahmed Jan 22 '14 at 9:43
  • \$\begingroup\$ For the open regions (red, black, pink), the algorithm should be able to identify them since they have no obstacles unlike the yellow region does. Since the yellow region has an obstacle, it was turned into a path region. \$\endgroup\$ – Faahmed Jan 22 '14 at 9:45
  • \$\begingroup\$ Since the yellow region has an obstacle, it was turned into a path region. Another option would be to divide an open space with a small obstacle in-between into two open regions, but in yellow's case, the pathway is narrow so path region is better. I guess there could also be a path width that should be defined. If width is greater than that, then it's an open space. I guess I'm looking for a good solution that someone has already come up with or maybe a starting point. \$\endgroup\$ – Faahmed Jan 22 '14 at 9:51
2
\$\begingroup\$

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:

map with paths (reddish) and regions (bluish/greenish)

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.