views:

294

answers:

5

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

+3  A: 

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.

Noon Silk
+1. Each time you select a tile to delete, check if there's a path from each adjacent tile to each other adjacent tile.
Nick Johnson
I have run into a similar problem as the OP, and I agree that you are much better off fixing your generation code.
Dolphin
+6  A: 

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

ChrisW
This will definitely work, thank you so much.
J3nnings
[Joke: http://xkcd.com/221/ shows how to pick a tile at random]
ChrisW
This will work, but the description doesn't entirely explain the problem, particularly, "if so, they're an island". It may be that the originally chosen tile is part of the island, and the uncolored tiles are part of the "mainland". If you're regenerating the entire map if an island is found, this is okay, but if you're planning to regenerate only the affected region this could be a problem.
Imagist
@Imagist - I don't think there's any difference between 'mainland' and 'island': the intent of the question is only to ask whether or not every tiles is reachable from any other.
ChrisW
@ChrisW If you're regenerating the entire map if unreachable tiles are found, then there is no difference between "mainland" and "island". If you're only regenerating part of the map when an island is found, there is a *big* difference: you'll want to regenerate the smaller group of unreachable tiles.
Imagist
@ChrisW For the record, I did upvote your answer because it is the best way to do it. I'm just warning the OP that there may be more to it depending on how he uses the results of the detection.
Imagist
You can count the number of neighbours that you color, to find the size of the landmass. If there's an island, then you can color and count it separately, and repeat. Then after you're done, you have a list of all land-masses, and the size of each.
ChrisW
A: 

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.

Tim Williscroft
+1  A: 

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
hughdbrown
A: 

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.

Tom Woolfrey
Worst case time is likely to run in O(n log6 n) time.
jmucchiello