I implemented Reynold's Boid Algorithm. The problem is one of speed. I put the flocking code in a flock timer set to 1500. So it doesn't even occur that often, and when it does, it brings my 1.2ghz nearly to its knees.
The Algorithm in a Nutshell:
Quote:
1. Attempt to move to the center of the mobs in the neighborhood.
2. Attempt to match speed with other mobs in the neighborhood.
3. Attempt to maintain a minimum distance from all other mobs and objects on the screen.
|
Consider the first rule. Each mob needs to "know" where the perceived center within her flock is. To get this, you have two options. One, is to sum the current vector position of each mob and then divide by the number of mobs. This works, but the problem is one of performance.
Consider now the way the server is setup:
ZoneLoop
MobLoop
For A Mob in MobLoop
Compare Mob A to All OtherMobs in MobLoop
Keep in mind that you have all the other checks going on. I smell my processor cooking, how about you? In actuality, the zoneserver lags so bad that it just isn't viable.
Option two is to calculate a running vector average as we step into the process for each mob. IN THEORY, you would keep a global vector total, in addition to a global mob count. When its the mobs turn, you do the math on the totals, and presto, no more lookup problems. To find the perceived center, just take the global vector and global total, divide, and boom you're done.
That would work well enough for rule one. But what about rules two and three?
Getting the nearest mob without causing a massive dent in performance is a strategic problem looking for an answer. You have to lookup who is your nearest neighbor for each mob in the zone for every tick.
I considered having a quicklookup matrix that had all the vectors of the mob in the zone in it. But then I realized that there is a fundamental underlying challenge here:
What is an effective way to compare one mob to all the other mobs in a zone without it being costly?