Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's say I have the following area in a top-down map:


The circle is the player, the black square is an obstacle, and the grey polygons with red borders are walk-able areas that will be used as a navigation mesh for enemies. Obstacles and grey polygons are always convex.

The grey regions were defined using an algorithm when the world was generated at runtime.

Notice the little white column. I need to figure out where any empty space like this is, if at all, after the algorithm builds the grey regions, so that I can fill the space with another region.

Basically what I'm hoping for is an algorithm that can detect empty space next to a polygon.

share|improve this question
Why did your algorithm stop at just 3 sides of the square blockage? That's the root of the problem, trying to find gaps afterwards will be far more difficult than not leaving gaps in the first place. – Patrick Hughes Jul 9 '12 at 1:08

Do you specifically need rectangles for walkable areas?

I ask as you could reverse this - take a 2D grid of boolean values and mark all grid squares as walkable (true) and then check all points on your polygons to find the grid squares they inhabit, and mark those squares as unwalkable (false).

This will produce a 'mask' of walkable areas, but the mask will be as grainy as your grid. If you're wanting a pixel-perfect solution then you may want to investigate kd-trees.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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