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

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

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