Re: [pygame] AI Module (was: Perlin Noise Function)

[Knapp <magick.crow@xxxxxxxxx>]

On Wed, Jul 30, 2008 at 9:29 PM, Hugo Arts <hugo.yoshi@xxxxxxxxx> wrote:

On Wed, Jul 30, 2008 at 6:20 PM, Knapp <magick.crow@xxxxxxxxx> wrote:
>
> That works unless you game is about space and which star out of 30,000 is
> close. Then the idea of finding the distance to everything gets a bit slow.
> To solve this you can take the position and divide by some distance that you
> think of as close in the X,Y,Z.  and take the integer quotient. If it is 0
> then the object is is your close box.
>
> 1,1,1
> 5,5,5
> 20,20,20
>
> close is a cube 10,10,10 so you get
> 0,0,0
> 0,0,0
> 2,2,2
>
> the first 2 are close.
>
> You can do this for are large bunch of objects and keep the result so that
> you only need to check small subsets of the whole and it is pre-calculated.
> If only a few are moving it is a quick check to see if they moved to a new
> cell.

Nice, but this algorithm doesn't take object sizes in consideration,
only position. Also, it only determines wether something is close to
the origin, so you'll have to calculate relative positions if your
object is not at (0, 0, 0).

Yes, that is the idea, you only need to check the objects the cells in and the 8 (3d) or 6 (2d) cells around the center. If you have thousands, then it makes sense to limit your more precise calculations to just a few. All depends on the cell size as to the number of objects that get the close look. Also what cell something is in is pre-calculated, say for stars or what ever you are checking for. If everything moves every turn then I guess you are out of luck.

 

This then becomes not very different from
finding distances, perhaps even slightly less efficient because of the
expensive modulo operation. Or am I misunderstanding something here?

Only that in most cases it is not done very often. if only one or 2 things are moving then they are the only thing that needs checking every loop.
 

Not my point, however. Closeness is a generalization of collision
detection, and pygame only handles simple cases of this. What you
describe seems like a form of binary space partitioning, which is not
a simple case.

Never looked at it like BSP but that is a good idea, I will have to look into that VS this cell system.

Yes, the pygame style checking comes in only for things that are close VS checking everything in a big system.


--
Douglas E Knapp

http://sf-journey-creations.wikispot.org/Front_Page