[vJASS] Performance Issues

[Almia]

I have this Flocking system that I made hours ago and It has a very terrible performance issue.

I tried the system with only 12 units and it worked fine, but when I tried 15+ units, fps drops so bad D:

The test map is in here:
http://www.hiveworkshop.com/forums/lab-715/flock-swarm-system-265860/index2.html#post2688637

Hope you can help me solve this thing

 

[Ezekiel12]

*looks at code*, mhm so you got


a 0.03125 s loop with a lot of declarations and code which contains

a forgroup loop with declarations and some code which calls
a function 3 times and that function calls
another function

*slowly looks at you*

 

[Xonok]

ForGroup!? Don't use this monstrosity

 

[PurgeandFire]

I'm guessing it is a result of your algorithm's complexity. When you create an instance, you add that unit to a group. Let's say you have N instances of boids. In each timer tick, you end up looping N times (that is fine). In each loop iteration, you iterate through all N - 1 other boids (within the ForGroup). So you end up with N^2 order of growth. To put that into perspective, 12 boids will end up doing 12*11=132 iterations per tick whereas 15 boids will do 15*14=210 iterations. And it gets worse as you add more--even adding just one more will add an extra 30 iterations.

If you can try to do all the group management within a single iteration, that'll make things a lot better. As for minimal optimizations--you may want to consider using natives like IsUnitInRange and IsUnitInRangeXY, no need to make your own functions.

And getId() should use a hashtable instead of doing a linear search. As it is, the algorithm may even be approaching N^3, which is a scary thing that no cpu should have to experience.

 

[Xonok]

About ForGroup, use a FirstOfGroup loop instead of it. It scales much much better. Even better, use an array if viable.(might not be in this case)

 

[Almia]

Yeah. I think the problem here the ForGroup. I might just create another method of enumeration

Update: Now I used Linked List instead, and boosted the performance a little bit
(The system can now process 25~ boids)

I think this system is not suitable for the Warcraft 3 environment because of it's complexity ( O(n*(n-1)) to O(n^2) )

 

[Wietlol]

Your biggest problem is... well... Cos() and Sin() probably.
15 units in a group shouldnt matter that much.

When I made my missile system, I used a for group as well and used Sin() and Cos() too.
When I replaced the Sin() and Cos() with datasets of velocity, I suddenly had my limit increased from 440 to 1250 (max missiles).
I think that it helps... a lot.

 

[PurgeandFire]

I don't know the exact details of the system so I can't offer suggestions on improving the complexity. But it isn't just a wc3 thing--any system that runs on N^2 every 0.03125 sec would have issues after a decent amount of units (not to mention whatever gpu requirements to process that many units--speaking of which, that may naturally limit the number of units you can have before the fps degrades).

What happens in the ForGroup loop exactly? I assume you're doing some sort of distance checks and orienting the boids to travel together? You might be able to simplify the whole thing by constructing a minimum spanning tree.

 

[Almia]

I don't know the exact details of the system so I can't offer suggestions on improving the complexity. But it isn't just a wc3 thing--any system that runs on N^2 every 0.03125 sec would have issues after a decent amount of units (not to mention whatever gpu requirements to process that many units--speaking of which, that may naturally limit the number of units you can have before the fps degrades).

What happens in the ForGroup loop exactly? I assume you're doing some sort of distance checks and orienting the boids to travel together? You might be able to simplify the whole thing by constructing a minimum spanning tree.

Just forget the ForGroup thing. I might as well use a Vector lib to get rid of the Cosines and Sines. O(n^2) is already the system's basic complexity as stated here: http://en.wikipedia.org/wiki/Flocking_(behavior)
but as stated, it can have improvements, which is the bin-lattice. Tho I think I should study it.

 

[Almia]

Bump!

Sorry for double-posting.

I have updated the map and now uses Vectors. I also got rid of the Sines and Cosines(well, most of it) and also got rid of Unit coordinates(0 of them)

http://www.hiveworkshop.com/forums/lab-715/flock-swarm-system-265860/#post2686067

The system now is capable of processing 40-60 boids. I also tested this so many times and I found out that one of the main reasons of it's performance issues is the range values for neighbor detection, which is, the smaller the range, the better the performance.

Also, i found out that some time later the map is tested, fps drops. I think there are some leaks here.