Re: [Algorithms] 2d circular union nav-mesh

[Sam M. <sam...@ge...>]

Hi guys,

 

The trick with this particular problem is you need to expand the set of
obstacles by your circle, not shrink the set of available space. They
aren't quite the same. 

 

Let's call the set of points on the boundary of the union of your free
circles as the "border points". Intuitively, in order for your circle to
not cross over them you need to stay a circle's width away from all of
them. So if you put a circle of suitable radius on top of each of these
border points and union the lot together, you'll get a description of
the space you need your centre point to stay away from (this is
essentially a minkowski sum - the keyword you normally need to answer
these kinds of questions). Now, a lot of this space will look very
"circular", but at intersections on the boundary you'll get rounded
corners. If this messes with your head a bit, try considering the
intersection of a box and a circle. This might be an easier example to
work with first as it's probably easier to draw and reason with.

 

Now, I haven't thought this through, but... if you converted your
union'd circles into a set of boundary curves (e.g. say, circles each
with a set of valid angle regions) and had a function that allowed you
to project your circles centre point to the closest location on the
boundary curves (say, search overlapping circles for nearest points in
viable regions and then pick closest), you would be able to do a
straight forward circle-point check with that point pair to get the
right answer. It is doable, but not exactly trivial. 

 

Alternatively, you could swap to modelling your obstacles with circles,
at which point this really does become a "fatten the circles" operation.

 

Hope that helps.

 

Cheers,

Sam

 

From: Sebastian Sylvan [mailto:seb...@gm...] 
Sent: 26 May 2010 13:10
To: Game Development Algorithms
Subject: Re: [Algorithms] 2d circular union nav-mesh

 

 

On Wed, May 26, 2010 at 1:01 PM, Sebastian Sylvan
<seb...@gm...> wrote:

 

On Wed, May 26, 2010 at 12:11 PM, <Pau...@sc...> wrote:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Hi guys,

Does anyone have any references or pointers for how to constrain a small
character (represented by a circle) within the interior of the union of
a
set of larger circles?

The background is, the larger circles define regions of land where the
small circle can navigate around (like a nav mesh), and the union of the
these circles defines the entire nav-mesh. The character is not allowed
to
leave the interior of the nav-mesh and must remain wholly inside it at
all
times.

Some diagrams:

The general case, the filled circle represents the character and the
hollow circles the land

http://www.pfirth.co.uk/ex1.png

My first attempt was to ensure the character was wholly inside at least
one land circle, but that fails in this case:

http://www.pfirth.co.uk/ex2.png

In that example, if the character moves any further up, it will not be
wholly contained in either circle and will fail, yet it should be able
to
navigate between them.

 

Maybe I'm missing something. But could you not shrink the circles of
your "navmesh" by the radius of your character, and then check the
centre *point* of the character against those?

 

 

Ah, that won't work for your second example. Ignore me. 


-- 
Sebastian Sylvan