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.

  • 3
    \$\begingroup\$ 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. \$\endgroup\$ Jul 9, 2012 at 1:08

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .