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
>