gdalgorithms-list

Re: [Algorithms] Generating the ith permutation of N elements

[<pad...@ob...>]

One mapping is to convert your index i to base-e for e elements.
That's surjective/onto.
But IIR discrete maths there's more than one definition of ith permutation

 

On 01 June 2010 at 18:57 Yannick Letourneau <yan...@ub...>
wrote:

> I'm looking for a way to generate the ith permutation of N elements, at
> approximately O(N) cost.
>
> All algorithms I've seen need the (i-1)th permutation in order to derive the
> ith permutation from it (e.g. they work incrementally).
>
> I would just like to give it a number in the range
>
> 0 <= i < N!
>
> and it would spit out the ith permutation, without requiring to compute the
> ones that come before it (which would be O(N!) ).
>
> Is that possible ?
>
> Any pointers appreciated.
>
> Yannick

Re: [Algorithms] Generating the ith permutation of N elements

[Robin G. <rob...@gm...>]

There is a recursive pattern used to generate each iteration which can
be used to generate the iterations directly. Check out this CS lecture
on permutations:

http://www.math.ust.hk/~mabfchen/Math232/Generating-Permutations.pdf

- Robin Green.


On Tue, Jun 1, 2010 at 9:57 AM, Yannick Letourneau
<yan...@ub...> wrote:
> I’m looking for a way to generate the ith permutation of N elements, at
> approximately O(N) cost.
>
>
>
> All algorithms I’ve seen need the (i-1)th permutation in order to derive the
> ith permutation from it (e.g. they work incrementally).
>
>
>
> I would just like to give it a number in the range
>
>
>
> 0 <= i < N!
>
>
>
> and it would spit out the ith permutation, without requiring to compute the
> ones that come before it (which would be O(N!) ).
>
>
>
> Is that possible ?
>
>
>
> Any pointers appreciated.
>
>
>
> Yannick
>
> ------------------------------------------------------------------------------
>
>
> _______________________________________________
> 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
>

[Algorithms] Generating the ith permutation of N elements

[Yannick L. <yan...@ub...>]

I'm looking for a way to generate the ith permutation of N elements, at approximately O(N) cost.

All algorithms I've seen need the (i-1)th permutation in order to derive the ith permutation from it (e.g. they work incrementally).

I would just like to give it a number in the range

0 <= i < N!

and it would spit out the ith permutation, without requiring to compute the ones that come before it (which would be O(N!) ).

Is that possible ?

Any pointers appreciated.

Yannick

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

Re: [Algorithms] Truncate then average? Or average then truncate?

[Tom F. <tom...@ee...>]

Not sure I understand what answer you want out of the last example. The
value is 63.5 +/- 0.5. You can either get back 63 or 64, but no matter how
you filter it, that value will still oscillate slightly at some ADC setting.

If you literally want no change if there's only a noise variance, just do a
threshold trick - do the filtering the way you're doing it, and then if the
filtered result is within some epsilon of the previously-returned value,
keep returning that previous value. Otherwise, send the new value. It's a
standard trick for things like analogue joysticks. It works OKish, but has
bizarre stair-step response to slow movement (whereas a properly-filtered
answer will also move slowly). 

TomF.


> -----Original Message-----
> From: Robin Green [mailto:rob...@gm...]
> Sent: Friday, May 28, 2010 10:02 AM
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Truncate then average? Or average then
> truncate?
> 
> OK, imagine this. We have a noisy two lowest bits, so we're removing
> the bottom three bits of the value and averaging four samples. If the
> value is around 180 we get:
> 
>         10110101b
>       + 10110100b
>       + 10110110b
>       + 10110101b
>   ---------------
>       1011010100b >> 2
>   ---------------
>       = 1011010b
> 
> But if the value is close to a power of two, e.g. 64, we get unstable
> values:
> 
>       1000000b
>     + 0111111b
>     + 1000001b
>     + 0111111b
>   ------------
>      11111111b >> 2
>   ------------
>     = 0111111b
> 
> The noise in the LSBs ends up bits flipping bits high up in the number
> in a way that truncating doesn't solve. Mr Bunnell is right, I should
> probably look more into numerical filtering rather than bit tricks.
> Duh.
> 
> - Robin Green.
> 
> 
> On Fri, May 28, 2010 at 9:06 AM, Jeremiah Zanin
> <Jer...@vo...> wrote:
> > Broken divider? I don't see how the noise bits can bleed into the
> other bits after dividing unless it's rounding up. Have you tried
> taking a power of two samples and shifting instead of dividing?
> >
> 
> -----------------------------------------------------------------------
> -------
> 
> _______________________________________________
> 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
> No virus found in this incoming message.
> Checked by AVG - www.avg.com
> Version: 8.5.437 / Virus Database: 271.1.1/2861 - Release Date:
> 05/28/10 06:25:00

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] Truncate then average? Or average then truncate?

[Robin G. <rob...@gm...>]

OK, imagine this. We have a noisy two lowest bits, so we're removing
the bottom three bits of the value and averaging four samples. If the
value is around 180 we get:

        10110101b
      + 10110100b
      + 10110110b
      + 10110101b
  ---------------
      1011010100b >> 2
  ---------------
      = 1011010b

But if the value is close to a power of two, e.g. 64, we get unstable values:

      1000000b
    + 0111111b
    + 1000001b
    + 0111111b
  ------------
     11111111b >> 2
  ------------
    = 0111111b

The noise in the LSBs ends up bits flipping bits high up in the number
in a way that truncating doesn't solve. Mr Bunnell is right, I should
probably look more into numerical filtering rather than bit tricks.
Duh.

- Robin Green.


On Fri, May 28, 2010 at 9:06 AM, Jeremiah Zanin
<Jer...@vo...> wrote:
> Broken divider? I don't see how the noise bits can bleed into the other bits after dividing unless it's rounding up. Have you tried taking a power of two samples and shifting instead of dividing?
>

Re: [Algorithms] Truncate then average? Or average then truncate?

[Michael B. <mi...@fa...>]

You probably need to filter the ADC results. I suggest a gaussian filter 
approximated using a moving average. Search for "Gaussian and Other Low Lag 
Filters" and you'll find tables of coefficients for different order filters. 
You won't need a ring buffer for a 1st order filter, but you will have to 
use the interrupt timer to get evenly spaced samples.

-michael


----- Original Message ----- 
From: "Robin Green" <rob...@gm...>
To: "Game Development Algorithms" <gda...@li...>
Sent: Friday, May 28, 2010 12:24 AM
Subject: [Algorithms] Truncate then average? Or average then truncate?


> Got a bit of a brain block, and I'd welcome someone with a clearer
> picture of what's the correct thing to do.
>
> I have a hardware controller that I'm writing firmware for,
> specifically debouncing button presses. That's gone fairly well by
> using a word for each sample of the keystate. An interrupt timer fires
> and I sample the button states, one bit per key, dumping the current
> state into a ring buffer of N words. At key scanning time I AND all
> the words in the buffer together and if any of the bits in each
> "column" are set I register it as a keypress. So I get instant
> reaction to a keydown and an N-iteration delay before the columns
> clear so I can register a keyup. This deals with noisy bounces on key
> depressions and releases just fine.
>
> I am now attempting to "debounce" an analog input. The issue is that
> the ADC reads the input and returns a 10-bit value, the bottom two
> bits of which are subject to noise, but that's fine as I only need a
> value in the range 0..127. So my current effort is to read the ADC
> value several times, sum them, divide by the number of samples and
> then lose the bottom 3 bits. This works great for most values in the
> range, except for the smallest values - 0, 1, 2, ... As you move the
> controller through the range down to the smallest values, they exhibit
> the noise and become like an unordered list. Other values where a lot
> of bits flip, like the boundary between 63 and 64, also allow the
> noise to propagate up to affect the value. Technically, there should
> be no reason for even the smallest numbers to show the noise - only
> the bottom two bits exhibit noise and we're removing three bits of the
> final value.
>
> What order should I be doing this and why? Why am I amplifying the
> noise to the point where it's a problem?
>
> - Robin Green.
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> 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] Truncate then average? Or average then truncate?

[Jeremiah Z. <Jer...@vo...>]

Broken divider? I don't see how the noise bits can bleed into the other bits after dividing unless it's rounding up. Have you tried taking a power of two samples and shifting instead of dividing?

-----Original Message-----
From: Robin Green [mailto:rob...@gm...]
Sent: Friday, May 28, 2010 2:24 AM
To: Game Development Algorithms
Subject: [Algorithms] Truncate then average? Or average then truncate?

Got a bit of a brain block, and I'd welcome someone with a clearer
picture of what's the correct thing to do.

I have a hardware controller that I'm writing firmware for,
specifically debouncing button presses. That's gone fairly well by
using a word for each sample of the keystate. An interrupt timer fires
and I sample the button states, one bit per key, dumping the current
state into a ring buffer of N words. At key scanning time I AND all
the words in the buffer together and if any of the bits in each
"column" are set I register it as a keypress. So I get instant
reaction to a keydown and an N-iteration delay before the columns
clear so I can register a keyup. This deals with noisy bounces on key
depressions and releases just fine.

I am now attempting to "debounce" an analog input. The issue is that
the ADC reads the input and returns a 10-bit value, the bottom two
bits of which are subject to noise, but that's fine as I only need a
value in the range 0..127. So my current effort is to read the ADC
value several times, sum them, divide by the number of samples and
then lose the bottom 3 bits. This works great for most values in the
range, except for the smallest values - 0, 1, 2, ... As you move the
controller through the range down to the smallest values, they exhibit
the noise and become like an unordered list. Other values where a lot
of bits flip, like the boundary between 63 and 64, also allow the
noise to propagate up to affect the value. Technically, there should
be no reason for even the smallest numbers to show the noise - only
the bottom two bits exhibit noise and we're removing three bits of the
final value.

What order should I be doing this and why? Why am I amplifying the
noise to the point where it's a problem?

- Robin Green.

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

_______________________________________________
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

This message, including any attachments, may contain privileged and/or confidential information. Any distribution or use of this email by anyone other than the intended recipient(s) is strictly prohibited. If you are not the intended recipient, please notify the sender immediately and delete all copies. Thank you.

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] Truncate then average? Or average then truncate?

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

Are you reading the ADC three times a frame and averaging, or are you 
reading once per frame and then averaging over the last few frames?  Is 
there a deadspace for the source input that you should be taking into 
consideration too?  (Most analogue inputs have some form of dead space 
towards zero you should ignore, if possible.)


Robin Green wrote:
> Got a bit of a brain block, and I'd welcome someone with a clearer
> picture of what's the correct thing to do.
>
> I have a hardware controller that I'm writing firmware for,
> specifically debouncing button presses. That's gone fairly well by
> using a word for each sample of the keystate. An interrupt timer fires
> and I sample the button states, one bit per key, dumping the current
> state into a ring buffer of N words. At key scanning time I AND all
> the words in the buffer together and if any of the bits in each
> "column" are set I register it as a keypress. So I get instant
> reaction to a keydown and an N-iteration delay before the columns
> clear so I can register a keyup. This deals with noisy bounces on key
> depressions and releases just fine.
>
> I am now attempting to "debounce" an analog input. The issue is that
> the ADC reads the input and returns a 10-bit value, the bottom two
> bits of which are subject to noise, but that's fine as I only need a
> value in the range 0..127. So my current effort is to read the ADC
> value several times, sum them, divide by the number of samples and
> then lose the bottom 3 bits. This works great for most values in the
> range, except for the smallest values - 0, 1, 2, ... As you move the
> controller through the range down to the smallest values, they exhibit
> the noise and become like an unordered list. Other values where a lot
> of bits flip, like the boundary between 63 and 64, also allow the
> noise to propagate up to affect the value. Technically, there should
> be no reason for even the smallest numbers to show the noise - only
> the bottom two bits exhibit noise and we're removing three bits of the
> final value.
>
> What order should I be doing this and why? Why am I amplifying the
> noise to the point where it's a problem?
>
> - Robin Green.
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> 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
>
>   

[Algorithms] Truncate then average? Or average then truncate?

[Robin G. <rob...@gm...>]

Got a bit of a brain block, and I'd welcome someone with a clearer
picture of what's the correct thing to do.

I have a hardware controller that I'm writing firmware for,
specifically debouncing button presses. That's gone fairly well by
using a word for each sample of the keystate. An interrupt timer fires
and I sample the button states, one bit per key, dumping the current
state into a ring buffer of N words. At key scanning time I AND all
the words in the buffer together and if any of the bits in each
"column" are set I register it as a keypress. So I get instant
reaction to a keydown and an N-iteration delay before the columns
clear so I can register a keyup. This deals with noisy bounces on key
depressions and releases just fine.

I am now attempting to "debounce" an analog input. The issue is that
the ADC reads the input and returns a 10-bit value, the bottom two
bits of which are subject to noise, but that's fine as I only need a
value in the range 0..127. So my current effort is to read the ADC
value several times, sum them, divide by the number of samples and
then lose the bottom 3 bits. This works great for most values in the
range, except for the smallest values - 0, 1, 2, ... As you move the
controller through the range down to the smallest values, they exhibit
the noise and become like an unordered list. Other values where a lot
of bits flip, like the boundary between 63 and 64, also allow the
noise to propagate up to affect the value. Technically, there should
be no reason for even the smallest numbers to show the noise - only
the bottom two bits exhibit noise and we're removing three bits of the
final value.

What order should I be doing this and why? Why am I amplifying the
noise to the point where it's a problem?

- Robin Green.

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

> 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

[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

[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

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

[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

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

[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

[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

[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

[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

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

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