How can I find islands in a randomly generated hexagonal map?

Question

I'm programming a Risk like game in Codigniter and JQuery. I've come up with a way to create randomly generated maps by making a full layout of tiles then deleting random ones. However, this sometimes produces what I call islands.

In risk, you can only attack one space over. So if one player happens to have an island all to them self, they would never be able to loose.

I'm trying to find a way that I can check the map before the game begins to see if it has islands.

I have already come up with a function to find out how many adjacent spaces there are to each space, but am not sure how to implement it in order to find islands.

Each missing spot is also identified as "water."

I'm not allowed to use image tags: http://imgur.com/xwWzC.gif

Answer 1

How do you do the random generation? Probably the best way is to solve it at this time. When you're generating the map, if you notice that you just created is impossible to get to, you can resolve it by adding the appropriate element.

Though we'll need to know how you do the generation.

Answer 2

There's a standard name for this problem but off the top of my head the following might work:

• Pick any tile at random
• Color it
• Color its neighbours
• Color its neighbours' neighbours
• Color its neighbours' neighbours' neighbours, etc.

When you're done (i.e. when all neighbours are colored), loop through the list of all tiles to see whether there are any still/left uncolored (if so, they're an island).

Answer 3

Run a blurring kernel over your data set.

treating the hex grid as an image ( it is , sort of)

value(x,y) = average of all tiles around this (x,y)

this will erode beaches slightly, and eliminate islands.

It is left as an exercise for the student to run an edge-detection kernel over the resulting dataset to populate the beach tiles.

Answer 4

Here's your basic depth-first traversal starting at a random tile, pseudo-coded in python-like language:

visited = set()
queue = Queue()
r = random tile
queue.add(r)
while not queue.empty():
    current = queue.pop()
    visited.add(current)
    for neighbor in current.neighbors():
     if neighbor not in visited:
      queue.add(neighbor)
if visited == set(all tiles):
    print "No islands"
else:
    print "Island starting at ", r

Answer 5

This hopefully provides another solution. Instead of "island" I'm using the term "disconnected component" since it only matters whether all tiles are reachable from all others (if there are disconnected components then a player cannot win via conquest if his own territories are all in one component).

• Iterate over all 'land' tiles (easy enough to do) and for each tile generate a node in a graph.
• For each vertex, join it with an undirected edge to the vertices representing its neighbour tiles (maximum of 6).
• Pick any vertex and run depth-first search (or bread-first) from it.
• If the set of vertices found by the DFS is equal to the set of all vertices then there are no disconnected components, otherwise a disconnected component (island) exists.

This should (I think) run in time O(n) where n is the number of land tiles.