With the ground height and color tree searching moved into Python, that leaves the nearest-actor calculation as the single biggest time sucker in BlenderPeople. I know I'm not supposed to be working on this right now, but I think I've come up with a way to do this significantly more efficiently than I have in the past.

The way it works now is that every time an Actor needs to know who is closest to him in the simulation, a distance calculation is done against every other current Actor. An Actor may ask for nearest person up to four different times in a single round. This means that the average number of distance calculations (followed by a non-indexed proximity sort) is (Actors^2)*2 (two times the square of the number of Actors). The "squared" part means that as the number of Actors goes up, efficiency declines not linearly, but as a square. That's bad.

Here's my brainstorm, and what I'm working on (it may turn out to be crap, and not work, but my ideas like this usually pan out): When it moves, an Actor gives itself a three-numeral score, based on the distances from three constant, strategically chosen points within the ground area. These three values locate the actor discretely within the field of play. Then, a sort is done against the whole Actor set three times, using each of the current Actor's values in turn as the zero point for the sort, the difference from the main sort value is cached. The Actor with the lowest cumulative cache after the third round should be the closest, if my mental model is correct. With this model, Actors are required to make three distance checks (Actors*3), then four indexed sorts. On queries, no new distance calculations need to happen -- just the triple-sort.

My guess is that the difference will not be noticable on requests with smaller actor pools (100 actors with old method = 10,000 distance calcs + 200 sorts; new method = 300 distance calcs + 400 sorts), but on larger pools (2,000 actors old = 2,000,000 distance calcs + 4,000 sorts; new = 6,000 distance calcs + 800 sorts).

If this works it will dramatically increase the speed of BlenderPeople, and in turn making it a viable tool for larger and larger numbers of Actors.

The way it works now is that every time an Actor needs to know who is closest to him in the simulation, a distance calculation is done against every other current Actor. An Actor may ask for nearest person up to four different times in a single round. This means that the average number of distance calculations (followed by a non-indexed proximity sort) is (Actors^2)*2 (two times the square of the number of Actors). The "squared" part means that as the number of Actors goes up, efficiency declines not linearly, but as a square. That's bad.

Here's my brainstorm, and what I'm working on (it may turn out to be crap, and not work, but my ideas like this usually pan out): When it moves, an Actor gives itself a three-numeral score, based on the distances from three constant, strategically chosen points within the ground area. These three values locate the actor discretely within the field of play. Then, a sort is done against the whole Actor set three times, using each of the current Actor's values in turn as the zero point for the sort, the difference from the main sort value is cached. The Actor with the lowest cumulative cache after the third round should be the closest, if my mental model is correct. With this model, Actors are required to make three distance checks (Actors*3), then four indexed sorts. On queries, no new distance calculations need to happen -- just the triple-sort.

My guess is that the difference will not be noticable on requests with smaller actor pools (100 actors with old method = 10,000 distance calcs + 200 sorts; new method = 300 distance calcs + 400 sorts), but on larger pools (2,000 actors old = 2,000,000 distance calcs + 4,000 sorts; new = 6,000 distance calcs + 800 sorts).

If this works it will dramatically increase the speed of BlenderPeople, and in turn making it a viable tool for larger and larger numbers of Actors.

Comments:

Hey thanks, so much for working on this... I have been checking out the progress and trying to learn as much as I can of the new features coming out. Glad to see the progress you are making even if its just in the thought relm. Looking forward to trying this out again when all the new feature are in the cvs. does the new NLA features, and group features help alot? Are you going to make another build? Let the community know if they can help you. Make characters, code, etc. trying to get my coding up to speed so I might be of use. Anyhow thanks....

ibkanat@gmail.com

ibkanat@gmail.com

Wooooow!!!

I didn't follow this project for long time (probably since end of 2004); I watch the last video (last one I seen before contain the levitating bots) and was amazed!!! It's seems realistic (except the killing is a bit fast).

I also think your idea of simulate every day life (city life), is really good idea to make present the use of it and will make the project more appealing and functional to variety of 3D artists/ productions.

It's very good to know that something like that exists.

Will continue follow and hope to get involved some time later (need to set it up first and play abit)

I didn't follow this project for long time (probably since end of 2004); I watch the last video (last one I seen before contain the levitating bots) and was amazed!!! It's seems realistic (except the killing is a bit fast).

I also think your idea of simulate every day life (city life), is really good idea to make present the use of it and will make the project more appealing and functional to variety of 3D artists/ productions.

It's very good to know that something like that exists.

Will continue follow and hope to get involved some time later (need to set it up first and play abit)

i just wanted to say how much i like your script. i put up a test of it on http://www.youtube.com/watch?v=GtygVdeStAA&eurl=

are you on blenderartists?

are you on blenderartists?

Hi,

Have you considered using Oracle Database Express Edition (XE)? It comes with Oracle Locator that allows you to store spatial coordinates, as well as spatial functions, such as nearest neighbour etc. Maybe handy to solve some of your performance issues.

Let me know what I can help with.

BTW Keep up the good work.

Have you considered using Oracle Database Express Edition (XE)? It comes with Oracle Locator that allows you to store spatial coordinates, as well as spatial functions, such as nearest neighbour etc. Maybe handy to solve some of your performance issues.

Let me know what I can help with.

BTW Keep up the good work.

Hmm, another related problem is one of particle/atom/etc. simulations. It also is amazingly related to the segmented radix (a modified/partial radix) sort algorythm.

Imagine this 1D scenerio:

You have 20 segments, 100 objects, and a number line between 0 and 20.

You keep track of which segment an object is in and only interact based on current and neighboring segments.

Every cycle, each object checks to see if it needs to move to a different segment after interacting.

The segments are stored as 20 lists. :)

Extend to n-Dimensions. Woot.

Imagine this 1D scenerio:

You have 20 segments, 100 objects, and a number line between 0 and 20.

You keep track of which segment an object is in and only interact based on current and neighboring segments.

Every cycle, each object checks to see if it needs to move to a different segment after interacting.

The segments are stored as 20 lists. :)

Extend to n-Dimensions. Woot.

Hello, I have faced this same problem with games in space. Say you have 28,000 stars and want to know which one is within 10 light years? There is an easy and fast running answer to this problem.

First, in your case, you don't really need to know how high someone is so drop the Z factor.

Next, take the X,Y and divide by some number that works well for your cell size.

Lets say 2 meters but whatever you need. At this point I am not sure what you are after. So you drop the fractions and then make a list of what is in each cell. IE all the actors with the same divided X.Y. Now all you have to do is check what is in your cell and maybe the other 8 around you.

If you code this in C and you are using ints then you could just right shift a few times, that would be very fast.

Anyway, does this work for you? I have some code that you can look at if you like. I don't think it is the best code but it is way better than doing Pythagorean Theorem for every actor every time!

There is another way to do distance that might work for you also, just use trig instead and use look up tables. Also don't bother with the sqrrt, who cares the real number just the relative distance between everyone.

Hope this helps

Douglas

magick.crow@gmail.com

http://journeytothestars.webhop.net/

Post a Comment
First, in your case, you don't really need to know how high someone is so drop the Z factor.

Next, take the X,Y and divide by some number that works well for your cell size.

Lets say 2 meters but whatever you need. At this point I am not sure what you are after. So you drop the fractions and then make a list of what is in each cell. IE all the actors with the same divided X.Y. Now all you have to do is check what is in your cell and maybe the other 8 around you.

If you code this in C and you are using ints then you could just right shift a few times, that would be very fast.

Anyway, does this work for you? I have some code that you can look at if you like. I don't think it is the best code but it is way better than doing Pythagorean Theorem for every actor every time!

There is another way to do distance that might work for you also, just use trig instead and use look up tables. Also don't bother with the sqrrt, who cares the real number just the relative distance between everyone.

Hope this helps

Douglas

magick.crow@gmail.com

http://journeytothestars.webhop.net/

02/01/2004 - 03/01/2004 04/01/2004 - 05/01/2004 05/01/2004 - 06/01/2004 06/01/2004 - 07/01/2004 07/01/2004 - 08/01/2004 08/01/2004 - 09/01/2004 09/01/2004 - 10/01/2004 11/01/2004 - 12/01/2004 12/01/2004 - 01/01/2005 01/01/2005 - 02/01/2005 02/01/2005 - 03/01/2005 06/01/2005 - 07/01/2005 09/01/2005 - 10/01/2005 10/01/2005 - 11/01/2005 11/01/2005 - 12/01/2005 12/01/2005 - 01/01/2006 01/01/2006 - 02/01/2006 03/01/2006 - 04/01/2006 04/01/2006 - 05/01/2006 05/01/2006 - 06/01/2006 06/01/2006 - 07/01/2006 07/01/2006 - 08/01/2006 08/01/2006 - 09/01/2006 09/01/2006 - 10/01/2006 10/01/2006 - 11/01/2006 11/01/2006 - 12/01/2006 02/01/2007 - 03/01/2007 08/01/2007 - 09/01/2007 12/01/2007 - 01/01/2008 01/01/2008 - 02/01/2008