gdalgorithms-list

[Algorithms] 2d circular union nav-mesh

[<Pau...@sc...>]

-----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.

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBS/0BJ3ajGqjtoMHxAQg3qwf/Tm6Az23UjEAY74p59oYl/orGaER6D8e+
5fIBti3CPtE6S0+BgwA5r9BRmh4gEC8D67ZloK4C+XuGIHhdJ5VOf4lvr/dtT8FZ
YwrDbAi7lWMsZQc8eEzTzNWMhay530ZoCT185yRD2EvPnqQPWvKDw4gW+LbK+FlB
Cuefhck6JWG24qLZLnnbU5r8NBMjDYKJLf8AuBguR9zsNvNas0SWjwPWAiUPYYgd
9cw7lEM6rATI84Bpp+emZGWy8nasK+9MfLOcOtXF7bbUo+x2QSkOC6JzDAq56eHZ
pK8tDhcfX3iH2s1+Tf6GORIiHvockZKxYZ5jt/vNoSuVOfawQlSNgw==
=mS+v
-----END PGP SIGNATURE-----

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

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

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

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

[<Pau...@sc...>]

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

Hi Sam,

Yeah, i'm familar with the minkowski difference :) I was hoping for a 
simple solution where i didn't have to construct it as its quite complex 
for the interior of the union of circles.

> 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. 

Thanks, i'll give that some thought :)

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: UTF-8

wsBVAwUBS/0nMXajGqjtoMHxAQiekAf/UxdGAK3XICz6BrLzXS24UNfOc8oovCiw
YZghIDLrxDC87/DE3jBXT5URSh3XaG8Q81f7Dz2qKGc9e2a5E7wFZ9DmVqvphXC8
1VsWQDDD2x89aBF3ZqP1qQxjKFZIQ11Kb6HMjEljpBlwoZa7TsVKumCeYXSmciaH
z1zG3LVN9hXiUFmIOh3GfWguVz5YwXLk5mc9AUn6RS8bW56AD7iefWyL1ndWdC+J
CyAfmhTRj7U5xuO2J0Y33uyrPNqGZwj30AcxvllXyoj9QC580f3MhvHJ74K7rIzx
kSYlmMdBKtwCrklatWJCEbTgMSD49G9OVsKwvj+n7ghDFhgFq15OnQ==
=xCLl
-----END PGP SIGNATURE-----

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

[<Pau...@sc...>]

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

> 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?

Hi Sebastian,

That fails for the case in my 2nd diagram; what happens is, the land 
circles end up separated by an empty region which is unpassable by the 
character:

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

Thats equivalent to my 1st rule as well, i think :)

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBS/0RcnajGqjtoMHxAQivvwf+OcDmO8BcrtqXmfyOvNETByLx3AfmDbVs
oFzDpDSwcxIpj0xbXM2sw4eVJXTyt+meWrsHfdLj7INMgUJcsEDix/Uvq2RXyiUE
fVlHe1YU3a0NHAqkdH9LLyt9dGDnXB+0RWu0CeeSN3qMhq/ZX0NUtPLq3KcTSvAV
vG4HTHkKIGmacn+fNZ87QNUjRb5UgAvuGf2BmvNegm7HtYdXFS3urLQvDp3UKY8C
DEElmuZp1s1rCAlE5NvU5AvqxShTmXF/u5Yf1/JzNSVONBaqky3Ozb9nAERe/sY8
jXr/qqT4tlGg/q460Wmy0iqb2rtVgLJ7HYT0aMjWHUX+r3Wdj2pb0w==
=yETN
-----END PGP SIGNATURE-----

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

[Simon F. <sim...@po...>]

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.    


I'm probably missing something entirely obvious here, but since your
items are all circles, can't you reduce the problem to just testing if
the exact centre of your character (with radius R) is entirely contained
in region circles whose radii have been reduced by R?

Simon

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

[Simon F. <sim...@po...>]

Simon Fenney wrote:
> 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.
> 
> 
> I'm probably missing something entirely obvious here, but since your
> items are all circles, can't you reduce the problem to just testing
> if the exact centre of your character (with radius R) is entirely
> contained in region circles whose radii have been reduced by R?   
> 
> Simon
> 

Ignore that - it's rubbish. 
Sorry for wasting your time.

Simon

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

[Marius E. <mar...@go...>]

Hey,

I'm pretty sure you cannot get away without clipping the test circle against
the container circles, tho I do not have proof.
You can probably use a slightly modified polygon clipping routine, storing
the edges as circle-arcs or NURBs and test for intersection with those.

Regards,
Marius



On Wed, May 26, 2010 at 1: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.
>
> Cheers, Paul.
> **********************************************************************
> This email and any files transmitted with it are confidential and intended
> solely for the use of the individual or entity to whom they are addressed.
> If you have received this email in error please notify pos...@sc...
> This footnote also confirms that this email message has been checked for
> all known viruses.
> Sony Computer Entertainment Europe Limited
> Registered Office: 10 Great Marlborough Street, London W1F 7LP, United
> Kingdom
> Registered in England: 3277793
> **********************************************************************
> P Please consider the environment before printing this e-mail
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGP Universal 2.9.1 (Build 287)
> Charset: US-ASCII
>
> wsBVAwUBS/0BJ3ajGqjtoMHxAQg3qwf/Tm6Az23UjEAY74p59oYl/orGaER6D8e+
> 5fIBti3CPtE6S0+BgwA5r9BRmh4gEC8D67ZloK4C+XuGIHhdJ5VOf4lvr/dtT8FZ
> YwrDbAi7lWMsZQc8eEzTzNWMhay530ZoCT185yRD2EvPnqQPWvKDw4gW+LbK+FlB
> Cuefhck6JWG24qLZLnnbU5r8NBMjDYKJLf8AuBguR9zsNvNas0SWjwPWAiUPYYgd
> 9cw7lEM6rATI84Bpp+emZGWy8nasK+9MfLOcOtXF7bbUo+x2QSkOC6JzDAq56eHZ
> pK8tDhcfX3iH2s1+Tf6GORIiHvockZKxYZ5jt/vNoSuVOfawQlSNgw==
> =mS+v
> -----END PGP SIGNATURE-----
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

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

[James R. <ja...@fu...>]

You can reduce the tests to a point within smaller circles, as long as 
you also test corridors between each circle.  (Where the width of the 
corridor is the distance between the two points of circle intersection 
minus the character's diameter.)

http://www.osodata.com/stuff/circles.png


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.
>
> Cheers, Paul.
> **********************************************************************
> This email and any files transmitted with it are confidential and intended 
> solely for the use of the individual or entity to whom they are addressed. 
> If you have received this email in error please notify pos...@sc...
> This footnote also confirms that this email message has been checked for 
> all known viruses.
> Sony Computer Entertainment Europe Limited
> Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
> Kingdom
> Registered in England: 3277793
> **********************************************************************
> P Please consider the environment before printing this e-mail
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGP Universal 2.9.1 (Build 287)
> Charset: US-ASCII
>
> wsBVAwUBS/0BJ3ajGqjtoMHxAQg3qwf/Tm6Az23UjEAY74p59oYl/orGaER6D8e+
> 5fIBti3CPtE6S0+BgwA5r9BRmh4gEC8D67ZloK4C+XuGIHhdJ5VOf4lvr/dtT8FZ
> YwrDbAi7lWMsZQc8eEzTzNWMhay530ZoCT185yRD2EvPnqQPWvKDw4gW+LbK+FlB
> Cuefhck6JWG24qLZLnnbU5r8NBMjDYKJLf8AuBguR9zsNvNas0SWjwPWAiUPYYgd
> 9cw7lEM6rATI84Bpp+emZGWy8nasK+9MfLOcOtXF7bbUo+x2QSkOC6JzDAq56eHZ
> pK8tDhcfX3iH2s1+Tf6GORIiHvockZKxYZ5jt/vNoSuVOfawQlSNgw==
> =mS+v
> -----END PGP SIGNATURE-----
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>   

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

[Manuel M. <m.m...@wa...>]

Hi Paul,

checking for full containment seems like a good early-exit
strategy (always check against the last circle fully containing
the player).

The second case, i.e. the case where the player is fully contained
in the union of "land" circles (disks actually), but not fully contained 
in any single land disk, can probably be solved by circle->circle
intersection.

	For each land circle intersecting the player:

	1) Find the two intersection points of player and land circle
        (ignoring the special case of circles touching in one point) 
        
        The two intersection points are the start- and end-point of
        a segment on the player circle.

     2) Use an appropriate data structure to store the union of all the 
        segments spanned by the intersections of player<->land circles

     3) If the full circumference of the circle has been marked as
        intersected, the circle is fully contained in the union of land 
        disks.
        This, however, does not guarantee that the player _disk_ is
        fully contained! But if you start at a valid position (i.e. full
        containment of player), I don't think the player circle can hit 
        this case.

just based on a few back-of-the-envelope drawings, so take with a grain
of salt :-)

cheers,

   Manuel

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

[Jeremy <jsw...@gm...>]

Assuming you have a choice in the method, would it not be easier to use the
interior of any circles as walkable space, rather than the unions, and
construct 'portals' between the line formed between the intersection points
of each overlapping circle? Alternatively to reduce the number of circles
significantly, circles can represent walkable space, circles can be
explicitly linked together, and it could be assumed that the corridor built
between the circles along their tangents is valid walkable space as well.

On Wed, May 26, 2010 at 8:16 AM, Manuel Massing
<m.m...@wa...>wrote:

> Hi Paul,
>
> checking for full containment seems like a good early-exit
> strategy (always check against the last circle fully containing
> the player).
>
> The second case, i.e. the case where the player is fully contained
> in the union of "land" circles (disks actually), but not fully contained
> in any single land disk, can probably be solved by circle->circle
> intersection.
>
>        For each land circle intersecting the player:
>
>        1) Find the two intersection points of player and land circle
>        (ignoring the special case of circles touching in one point)
>
>        The two intersection points are the start- and end-point of
>        a segment on the player circle.
>
>     2) Use an appropriate data structure to store the union of all the
>        segments spanned by the intersections of player<->land circles
>
>     3) If the full circumference of the circle has been marked as
>        intersected, the circle is fully contained in the union of land
>        disks.
>        This, however, does not guarantee that the player _disk_ is
>        fully contained! But if you start at a valid position (i.e. full
>        containment of player), I don't think the player circle can hit
>        this case.
>
> just based on a few back-of-the-envelope drawings, so take with a grain
> of salt :-)
>
> cheers,
>
>   Manuel
>
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

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

[<Pau...@sc...>]

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

> Assuming you have a choice in the method, would it not be easier to 
> use the interior of any circles as walkable space, rather than the 
> unions, and construct 'portals' between the line formed between the 
> intersection points of each overlapping circle? Alternatively to 
> reduce the number of circles significantly, circles can represent 
> walkable space, circles can be explicitly linked together, and it 
> could be assumed that the corridor built between the circles along 
> their tangents is valid walkable space as well.

Hi Jeremy

I think the trouble with this idea is the shape of the corridors - in 
actual fact, they're not rectangular they're strange curvy funnel shapes. 
I'd be worried that simplifying assumption would lead to problems :)

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBS/026XajGqjtoMHxAQhlrAf/SFbgEfUJawCUCjUDaPy8iclnULVocJR2
GvHVoM6NKwB0ssoByS3fFDfk8c7yVqxXS4dhStdMJq1vFiNVAfUUUZ76UUHCxW66
fEMurQ3nXAEEiJJryU8ucUYfu4K+1ImXqG1vdgRmysQGJVdrYm1TGDbqrAkWGqa+
/wziZ+WoK2yjZDsP/87/9QNB0i1UK93yW8tYj4wDeHl0Vd+lAWzqZn+Q2ivofiXb
wzYaKDcd8sD4r7Gmti0bH/5CBScLbReaSx3FDnk7cxnjZe6nxSxkWhjhBdCMpRKK
xnYVJliQYSovK0QRJE2UCIYeK201ZvSzAQXHb4PTGndGbRLjl+Cc8w==
=UUXx
-----END PGP SIGNATURE-----

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

[Marius E. <mar...@go...>]

In fact, the shape should not be that strange at all. It's just a
half-circle per intersection point, is it not?
I suppose you could use an in-rectangle test (rectangle around the two
intersection points, expanded by the radius of the test sphere) combined
with a not-in-circle test (around each of the two intersection points) to
build a somewhat simple in-corridor test.
Combined with some early out tests, that should be quite efficient.

Regards, Marius

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

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> > Assuming you have a choice in the method, would it not be easier to
> > use the interior of any circles as walkable space, rather than the
> > unions, and construct 'portals' between the line formed between the
> > intersection points of each overlapping circle? Alternatively to
> > reduce the number of circles significantly, circles can represent
> > walkable space, circles can be explicitly linked together, and it
> > could be assumed that the corridor built between the circles along
> > their tangents is valid walkable space as well.
>
> Hi Jeremy
>
> I think the trouble with this idea is the shape of the corridors - in
> actual fact, they're not rectangular they're strange curvy funnel shapes.
> I'd be worried that simplifying assumption would lead to problems :)
>
> Cheers, Paul.
> **********************************************************************
> This email and any files transmitted with it are confidential and intended
> solely for the use of the individual or entity to whom they are addressed.
> If you have received this email in error please notify pos...@sc...
> This footnote also confirms that this email message has been checked for
> all known viruses.
> Sony Computer Entertainment Europe Limited
> Registered Office: 10 Great Marlborough Street, London W1F 7LP, United
> Kingdom
> Registered in England: 3277793
> **********************************************************************
> P Please consider the environment before printing this e-mail
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGP Universal 2.9.1 (Build 287)
> Charset: US-ASCII
>
> wsBVAwUBS/026XajGqjtoMHxAQhlrAf/SFbgEfUJawCUCjUDaPy8iclnULVocJR2
> GvHVoM6NKwB0ssoByS3fFDfk8c7yVqxXS4dhStdMJq1vFiNVAfUUUZ76UUHCxW66
> fEMurQ3nXAEEiJJryU8ucUYfu4K+1ImXqG1vdgRmysQGJVdrYm1TGDbqrAkWGqa+
> /wziZ+WoK2yjZDsP/87/9QNB0i1UK93yW8tYj4wDeHl0Vd+lAWzqZn+Q2ivofiXb
> wzYaKDcd8sD4r7Gmti0bH/5CBScLbReaSx3FDnk7cxnjZe6nxSxkWhjhBdCMpRKK
> xnYVJliQYSovK0QRJE2UCIYeK201ZvSzAQXHb4PTGndGbRLjl+Cc8w==
> =UUXx
> -----END PGP SIGNATURE-----
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

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

[Jeremy <jsw...@gm...>]

Curvy? They aren't rectangular, but they are still a relatively simple 2
boundary lines that can pretty easily be avoided whether they taper or not.
As soon as the agent enters the destination radius(and/or the next corridor
on a path) he is free to set up to exit via the next corridor, which will
always be a pretty direct route once inside the circle.

http://tinypic.com/view.php?pic=sg28ue&s=6

On Wed, May 26, 2010 at 9:58 AM, <Pau...@sc...> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> > Assuming you have a choice in the method, would it not be easier to
> > use the interior of any circles as walkable space, rather than the
> > unions, and construct 'portals' between the line formed between the
> > intersection points of each overlapping circle? Alternatively to
> > reduce the number of circles significantly, circles can represent
> > walkable space, circles can be explicitly linked together, and it
> > could be assumed that the corridor built between the circles along
> > their tangents is valid walkable space as well.
>
> Hi Jeremy
>
> I think the trouble with this idea is the shape of the corridors - in
> actual fact, they're not rectangular they're strange curvy funnel shapes.
> I'd be worried that simplifying assumption would lead to problems :)
>
> Cheers, Paul.
> **********************************************************************
> This email and any files transmitted with it are confidential and intended
> solely for the use of the individual or entity to whom they are addressed.
> If you have received this email in error please notify pos...@sc...
> This footnote also confirms that this email message has been checked for
> all known viruses.
> Sony Computer Entertainment Europe Limited
> Registered Office: 10 Great Marlborough Street, London W1F 7LP, United
> Kingdom
> Registered in England: 3277793
> **********************************************************************
> P Please consider the environment before printing this e-mail
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGP Universal 2.9.1 (Build 287)
> Charset: US-ASCII
>
> wsBVAwUBS/026XajGqjtoMHxAQhlrAf/SFbgEfUJawCUCjUDaPy8iclnULVocJR2
> GvHVoM6NKwB0ssoByS3fFDfk8c7yVqxXS4dhStdMJq1vFiNVAfUUUZ76UUHCxW66
> fEMurQ3nXAEEiJJryU8ucUYfu4K+1ImXqG1vdgRmysQGJVdrYm1TGDbqrAkWGqa+
> /wziZ+WoK2yjZDsP/87/9QNB0i1UK93yW8tYj4wDeHl0Vd+lAWzqZn+Q2ivofiXb
> wzYaKDcd8sD4r7Gmti0bH/5CBScLbReaSx3FDnk7cxnjZe6nxSxkWhjhBdCMpRKK
> xnYVJliQYSovK0QRJE2UCIYeK201ZvSzAQXHb4PTGndGbRLjl+Cc8w==
> =UUXx
> -----END PGP SIGNATURE-----
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

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

[<Pau...@sc...>]

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

> Curvy? They aren't rectangular, but they are still a relatively 
> simple 2 boundary lines that can pretty easily be avoided whether 
> they taper or not. As soon as the agent enters the destination 
> radius(and/or the next corridor on a path) he is free to set up to 
> exit via the next corridor, which will always be a pretty direct 
> route once inside the circle.
> 
> http://tinypic.com/view.php?pic=sg28ue&s=6

Ahhh, i see what you mean - you're talking about changing the problem? 
Unfortunately thats not an option for me :)

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBS/1MRXajGqjtoMHxAQjPcggApxqCg7fNA7l08wbfFKM3oEM0fgoa085h
zbDqlt9wy27zCSZXp1vSMyKnRzHxbtD+lPDQN1csgZQjukJuU+mpEMdg5Z7tAo0B
9e9SH9zglnVCEo1jUn3fmbwohBaaEqkRco73utRZwXsTgshpfqK115PNTeyKR7Uy
E9VrP+G9dKYHlGZ/GWQPmOO6yg6Z3IRZQVxTaOerF1AmWbpCnKIvC4yncdWUc7zO
4MHRxHfwkgyQdhpQBaXafwpH2u1XeV+5dDpukewFjmtqWX5ZeguGT5OGJImsC8nF
N4/6VLq0RIs9V2jUaVOIoZoCgLjpj4jpwG/yPxjLqWENKHriyeraHw==
=zyTM
-----END PGP SIGNATURE-----

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

[Samuel M. <sam...@go...>]

I would really go for an arc-wise representation of the boundary of
your union, maybe even pre-processed, if you have a very large amount
of overlap between circles.
The benefit would be that the algorithm is quite simple and it is
independent of the size of your character.


An algorithm for this could be like this:
 - An "arc" is defined by two angles which define the start- and
endpoint. The arc goes clockwise from start- to end-angle.
 - In the end, we want for every circle a list of arcs that define the
border of this circle.
So we start with an full arc for every circle (from 0° to 360°). Then
we find for every circle X the intersecting circles.
 - For every intersecting circle Y we do:
   - For every arc already in the list of X, we clip Y from the arc,
and add the resulting arc(s) to the list in X

Now we only need an algorithm to clip circles from an arc. The result
is either zero, one or two arcs. This involves a bit of trigonometry
that can probably be found on the net or so...

For collision detection you would just check the character against all
arcs (or those of all circles he's intersecting...)


Greets,
Samuel


On Wed, May 26, 2010 at 6:30 PM,  <Pau...@sc...> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
>> Curvy? They aren't rectangular, but they are still a relatively
>> simple 2 boundary lines that can pretty easily be avoided whether
>> they taper or not. As soon as the agent enters the destination
>> radius(and/or the next corridor on a path) he is free to set up to
>> exit via the next corridor, which will always be a pretty direct
>> route once inside the circle.
>>
>> http://tinypic.com/view.php?pic=sg28ue&s=6
>
> Ahhh, i see what you mean - you're talking about changing the problem?
> Unfortunately thats not an option for me :)
>
> Cheers, Paul.
> **********************************************************************
> This email and any files transmitted with it are confidential and intended
> solely for the use of the individual or entity to whom they are addressed.
> If you have received this email in error please notify pos...@sc...
> This footnote also confirms that this email message has been checked for
> all known viruses.
> Sony Computer Entertainment Europe Limited
> Registered Office: 10 Great Marlborough Street, London W1F 7LP, United
> Kingdom
> Registered in England: 3277793
> **********************************************************************
> P Please consider the environment before printing this e-mail
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGP Universal 2.9.1 (Build 287)
> Charset: US-ASCII
>
> wsBVAwUBS/1MRXajGqjtoMHxAQjPcggApxqCg7fNA7l08wbfFKM3oEM0fgoa085h
> zbDqlt9wy27zCSZXp1vSMyKnRzHxbtD+lPDQN1csgZQjukJuU+mpEMdg5Z7tAo0B
> 9e9SH9zglnVCEo1jUn3fmbwohBaaEqkRco73utRZwXsTgshpfqK115PNTeyKR7Uy
> E9VrP+G9dKYHlGZ/GWQPmOO6yg6Z3IRZQVxTaOerF1AmWbpCnKIvC4yncdWUc7zO
> 4MHRxHfwkgyQdhpQBaXafwpH2u1XeV+5dDpukewFjmtqWX5ZeguGT5OGJImsC8nF
> N4/6VLq0RIs9V2jUaVOIoZoCgLjpj4jpwG/yPxjLqWENKHriyeraHw==
> =zyTM
> -----END PGP SIGNATURE-----
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

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

[<Pau...@sc...>]

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

> I would really go for an arc-wise representation of the boundary of
> your union, maybe even pre-processed, if you have a very large amount
> of overlap between circles.
> The benefit would be that the algorithm is quite simple and it is
> independent of the size of your character.

Hi Samuel,

You are absolutely right, i think this is the way forward. Combined with a 
distance to arc segment from point function, i should have everything 
needed to get this working :)

Thanks again for everyone's input :)

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBS/9/dnajGqjtoMHxAQimdAf/XTz0Visj2PTH7NDWr9Pr2KMzBdNfzzFT
9+flwfa3kZGkRPNTVDzYucCc+YsIYhE1yX2xxnOfWZ6RuQLtVCMd66ZBUEk8kBbf
5/mmznfeyipJCpoqxDz1/kFkiXBpLz0ayEqPDLQb6p20/HiJ2VPI946Z+dw6nzBs
Ex3GXxSAwDNkLweiHvg5/g0RIhMx+kgqss64OaDjDSN0TTIZ1yhofUP+Rzx7WQy0
GvEZAMcwomHBbHeP7ce+4cnBvfX/ZvosVNkri8yiWvADwM2yJfpSXoWDFO8mW3+G
D4By6EnRh6ou3FV6BG7NdElHWpBqdOKJU5wsNRPx3fwC1EElBEhBow==
=4C52
-----END PGP SIGNATURE-----

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

[Mat N. <mat...@bu...>]

For interior arcs, you can reduce those to lines, since the arc should be fully contained within two circles; if it weren't, it would be an exterior arc.

MSN
-----Original Message-----
From: Pau...@sc... [mailto:Pau...@sc...] 
Sent: Friday, May 28, 2010 1:34 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] 2d circular union nav-mesh

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

> I would really go for an arc-wise representation of the boundary of
> your union, maybe even pre-processed, if you have a very large amount
> of overlap between circles.
> The benefit would be that the algorithm is quite simple and it is
> independent of the size of your character.

Hi Samuel,

You are absolutely right, i think this is the way forward. Combined with a 
distance to arc segment from point function, i should have everything 
needed to get this working :)

Thanks again for everyone's input :)

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBS/9/dnajGqjtoMHxAQimdAf/XTz0Visj2PTH7NDWr9Pr2KMzBdNfzzFT
9+flwfa3kZGkRPNTVDzYucCc+YsIYhE1yX2xxnOfWZ6RuQLtVCMd66ZBUEk8kBbf
5/mmznfeyipJCpoqxDz1/kFkiXBpLz0ayEqPDLQb6p20/HiJ2VPI946Z+dw6nzBs
Ex3GXxSAwDNkLweiHvg5/g0RIhMx+kgqss64OaDjDSN0TTIZ1yhofUP+Rzx7WQy0
GvEZAMcwomHBbHeP7ce+4cnBvfX/ZvosVNkri8yiWvADwM2yJfpSXoWDFO8mW3+G
D4By6EnRh6ou3FV6BG7NdElHWpBqdOKJU5wsNRPx3fwC1EElBEhBow==
=4C52
-----END PGP SIGNATURE-----

------------------------------------------------------------------------------

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

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

[<Pau...@sc...>]

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

> For interior arcs, you can reduce those to lines, since the arc 
> should be fully contained within two circles; if it weren't, it 
> would be an exterior arc.

Hi Matt,

Actually, i think i can contribute something here :) If the arc segment 
plus the centre of the circle the segment is from form a virtual slice of 
pie, then for any given point you can calculate the distance to the arc 
segment in one of two ways:

1) For any given point which lies within the angle range defined by the 
edges of the pie, form a vector from the pie centre to the candidate 
point, normalise and then scale by the circle radius - this gives the 
point projected onto the arc segment. You then just do a length op to find 
the distance

2) For any point outside of the pie (i.e. outside the angle range), the 
closest distance to the arc segment is the length of the vector defined by 
nearer of the two vertices which lie at the pie extremes subtracted from 
the candidate point.

Mmmm, pie :)

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBTATKw3ajGqjtoMHxAQhcEwf+LCAxZ38n3UFVcjjOsGRJ2TAs7p1IkroJ
E2I+LdVWyAs/UJTxJ80U4e2mPoElNmKMxw2JSuZinsOIWHXbOX7h1KDKv9J9Ljxw
5l9NUskbzMY6RxIq+MlYuSmXxwGJmpsFipkqa7KbEZGuLxukecxABTKAvX44gpA/
LUBv6+lQlnphpU4YdzRf08E6E7BngVbHoMQKs2o957+MT1WjGkzKAzdU/m+p1ci5
8t3bY9pQ+ZxSVVqo2z/qZiH0FYwNpdepd9jkFGDUEu9GAM4wyM6f646VvbsvCJd0
EDW6XosGvTfaJYmRxAT9iQuOH2s0Lzyuvxql0BOFNynhIPWulzXFBg==
=kpsR
-----END PGP SIGNATURE-----