# What would be the best way to find an open space in a level?

I'm working on a 2D game where you use paint to add tiles to a level and right now I'm working to add warp tiles. I have it set up so certain direction-oriented paints use two points (a start and end) to determine which direction the tiles will point (left, right, up, down.) The warp tiles have these points, but they'll be added to two other lists (warp start and end). The way the warps work is: if the player hits one tile they'll be teleported to the corresponding warp tile. Now, if I'm going to get this to work properly, I need to make it so the player can't be teleported into a wall or off the map. So I need to move the point to an open tile exactly one space away from any walls.

What would be the best way to do this?

• Are you setting up these warp points beforehand or are they generated automatically somehow? – Richard Marskell - Drackir Aug 23 '11 at 15:32
• See my answer and description of the Packing Problem at gamedev.stackexchange.com/questions/16054/… – Engineer Aug 23 '11 at 17:33
• @Drackir The paint is just a particle trail that doesn't disappear or move and every particle has it's own point to map it's position. So I've made a for loop that checks each particles position, sees if that tile is open, changes the collision map accordingly and then removes the particle. The tile graphics are drawn according to the collision map. – IronGiraffe Aug 23 '11 at 21:59
• I'm unbelievably confused. Perhaps an image would help people see what you're trying to do and give you solid answers. – Richard Marskell - Drackir Sep 1 '11 at 18:05
• @Drackir Here's video of the game thus far. Every time you lay down tiles, you change the values at that location on the collision map (an int array.) With the warp tiles I need 9 tiles worth of open space (all 9 tiles are equal to 0) and the warp tiles are created at the end points of the purple line (where the flags appear at 1:32.) What I need is a way to use a search algorithm to look around the old point for a new point that fits my guidelines (8 empty tiles around the new point which is also empty.) Example. – IronGiraffe Sep 3 '11 at 11:08

If all you want to do is ensure that the clicked on tile has open tiles around it, I would just create a function that checks the tiles around it. And then call that on the clicked tile.

You could set it up in a (nested) loop or just create if statements for it. So, in pseudo-code:

function IsTileOpen(tile)
if tile NOT open
return false because if the clicked tile isn't open, why check any others
if tile on top row
return false because we're against the top wall
if tile on left column
return false because we're against the left wall
if tile on right column
return false because we're against the right wall
if tile on bottom row
return false because we're against the bottom wall
if top left tile NOT open
return false
if top tile NOT open
return false
if top right tile NOT open
return false
if left tile NOT open
return false
if right tile NOT open
return false
if bottom left tile NOT open
return false
if bottom tile NOT open
return false
if bottom right tile NOT open
return false
return true because all the surrounding tiles were open
end function


Edit Based On Comment

There are two ways you could handle the situation:

1. (Easiest) You can just play a sound and indicate that the position they chose is invalid and they need to choose another option.
2. Use a search algorithm to find an open tile. However, I think there should be limits on how you use this. Take, for example, a situation where they click on the left side of the map and the only open spot is far on the right side. Your search algorithm finds that open spot and places the other warp there. This does not seem very intuitive and may be frustrating. My suggestion in this case (assuming you don't want to do #1 which is my main suggestion), is to only search the tiles around the current tile (perhaps in a n-tile radius). This way the warp gate won't appear too far from where you clicked. To do a search like this (assuming a 1-tile radius), you just need to call the function above on the eight tiles around the current one (assuming the current one wasn't available). You could do this in a loop or, again, with if statements.
• I know how to do that, but I'm not sure how I can use a search algorithm to find a new point when the old point isn't open. I've been reading up on pathfinding and it seems like I could do something similar to that, where I would use Dijkstra's algorithm or A* algorithm to find the nearest open space. I'm just not sure how I could do that, because I've never programmed anything like it before. Sorry to be such a bother, I'm kind of new to programming, so I don't really know that much yet. – IronGiraffe Sep 5 '11 at 4:21
• @IronGiraffe - Oh, I see what you mean. Ok, I'll update my answer. – Richard Marskell - Drackir Sep 5 '11 at 12:17
• @IronGiraffe - Updated. – Richard Marskell - Drackir Sep 5 '11 at 13:02
• Better do that "look if the tile is open" during level load or generation, and store the result. You usually have to pass through all tiles (at least, all loaded/visible tiles if you do lazy evaluation) at this point anyway, that little extra work doesn't matter, and the extra bits of memory shouldn't matter on most platforms either. – Martin Sojka Sep 5 '11 at 13:23
• @Martin - From what I understand, the level changes as you play. See the video. And, I still recommend option 1 above, but if they have to do the second option, it's only on click so it's unlikely it will cause any noticeable hit to performance. – Richard Marskell - Drackir Sep 5 '11 at 20:50

I think you will need to find the nearest "free" rectangle to a warp tile, where the player can fit.

There is a similar question on stackoverflow. Click to see.