views:

107

answers:

4

I have built a gameboard that consists of a grid, the grid is then randomly assigned, "Walls" to a cell. Once the cells are built, how can I check to see if a certain cell is 'locked in' so that I don't place a player there.

I have thought about this and the first ago I came up with check all sides for four walls, but obviously, a cell could be surrounded by open cells, which are then surrounded by walls.

The other is a "escape to outside" algo, which basically tries to find a path to an outside wall, which would then mean it is not locked in, but if the block is on an outside wall and surrounded by blocks it would be locked in.

How is this typically handled? I'm using python if that matters for any code examples.

Thanks!

+2  A: 

You basically want a floodfill algorithm.
http://en.wikipedia.org/wiki/Floodfill

edit
I think I misunderstood your definitions of 'locked' and 'escape'.
If you have limited game board, every cell there is locked in some space. If I understand you correctly, you just want that space to be big enough. Well, you compute its area easily with flood fill algorithm.

Nikita Rybak
I think this will work, however, I have a finite board.
NoahClark
@NoahClark Yeah, I edited to clarify it.
Nikita Rybak
As I think about this more, what I should do is use floodfill on every open cell (For increased efficiency, if the cell is already in a floodfill skip it) and the flood fill with the biggest number should be left open, all other cell(s) filled in.
NoahClark
The flood fill solution would be good if you just wanted to find out the extent of a *single* area. If you want to discover all different areas, there is a tweaked version of the flood fill that is more efficient (which I have described in my answer).
Jérémie
@NoahClark You're absolutely right, that's how it's usually done if you want to count all connected areas of a map.
Nikita Rybak
@Jérémie It can't be 'more efficient', at least in terms of time. Flood-fill (Noah has described how to change it to consider all areas) has O(m) complexity where 'm' is amount of cells. It, obviously, can't be done faster, because you have to consider each cell at least once.
Nikita Rybak
@Jérémie And upon reading, it looks like idea is the same :)
Nikita Rybak
@Nikita: Flood fill is a bit of a fuzzy idea because the specific "flooding" algorithm is never specified; but beside that, the "more efficient" I was referring to is that using flags to determine whether a cell has already been visited is less efficient than knowing you will only visit it once---not to mention, the flood fill algorithm has to make several tests on adjacent cell at each visited cell to determine whether it can continue. In essence, of course both solutions are O(m) but the one you inspired has a greater constant, of the order of 8 or something like that.
Jérémie
+1  A: 

It really depends on the size of your game board. If we are speaking of small boards, a quick path finding algorithm can give you the distance between every cell and each other. This might have a double use if you do not want to place the player too close to other players or other features.

A second option is to design a wall generator that by principle cannot create locked rooms. The roguelike community has done a decent amount of research into the topic of generating random (dungeon-sized) maps without closed rooms.

Finally, using a level of detail approach can help you if you have to find a suitably large empty space on a huge map. Find an interconnection graph for a set of sparse points distributed over your map (this can be a direct result of your map generator). That should be sufficient to place a player. But if you need more detail on a specific point, finding a path to one of these points can tell you if a room is locked in. This might not work in extremely dense labyrinths.

relet
+1  A: 

I'm not sure exactly what your game board can look like, but if you have something like this:

+----------------------+
|      +-----+         |
|      | c   |         |
|      |     |         |
|      +-----+         |
|                      |
|                      |
|                      |
+----------------------+

And you want to avoid putting the character on the c because it's 'walled in', even though it's it's not exactly surrounded by the walls, you could easily implement the Left-or-Right Hand algorithm - only instead of trying to get out of the maze you're checking to see if you make it back to the same coordinate.

Wayne Werner
This solution also would work very well.
NoahClark
A: 

Maybe this previous post is what you are looking for. In that post, I answered how to count the number of different areas of dots there was on a grid on which dots could be placed. Your problem is similar, except instead of having "dots", you have walls. The algorithm given in that post will give you a version of your grid G, where

G[x1][y1] == G[x2][y2]

only if it is possible for a player to get from (x1,y1) to (x2,y2), i.e., if there is a clear path with no walls from that first point to the second point.

Is this what you are looking for? Do you want additional details, or do you want me to adapt that code to your particular problem?

Jérémie