On Wed, Jul 30, 2008 at 9:29 PM, Hugo Arts <[EMAIL PROTECTED]> wrote:
> On Wed, Jul 30, 2008 at 6:20 PM, Knapp <[EMAIL PROTECTED]> 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
