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

[Sebastian S. <seb...@gm...>]

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?


-- 
Sebastian Sylvan