[Civil-devel]fast los

[Cristian S. <so...@cs...>]

Hi

I have hacked the "quick los" I have proposed 2 weeks ago ( checking the 
points in a non incrementing order)
I'll attach the source

First I modified some computings (note that the current version divides 
dy/dx also dx can be 0)

The line is "walked" as parameter t ranges from 0 to iters, by the formulas:
x=x0 + mx*t
y=y0 + my*t
z=z0 + mz*t

Then your code follows, unmodified.

But instead of for t = 1 to iters I will choose t in another order, 
keeping in mind not to give the same values more times
(it slows down the code and it puzzles the los_points, as a terrain 
cannot "blur" vision 2 times :-)

A quick choice was to use some number theory.
given a prime (503 in my sample) one can find a generator (5) s.t.
t=5
while (t!=1){
   t=(t*5) % 503
    if (t>iters) continue;
   ...  do job with t
}
will execute the "job" once for each t form 1 to iters (if iters < 503, 
of course)

Improvement: for different distances we can use smaler primes, because 
it's a waste of time to "continue" a lot ...
At this moment I use only 2 primes, 503 and 307 (for iters < 300)

***
Timing results (computed for the first turn)
the original algoritm gives an average of 14 ms / unit (as reported by 
"new total").
the modified algorithm gives an average of 4 ms / unit.

Of course, the algorithm cannot do better when 2 units can see each 
other, but statistically this will happen when the 2 units are close
to each other, so the time will be short, anyway.

I timed the code w/ the loop disabled (returning "start" instead of 
doing iterations) and the result is 3ms. So the bottleneck is no longer 
"tracelos" :-)

Hoping to be helpful,

Cristian

PS: the "limit point" of the "los line" does not say any more where the 
vision stops but says where the loop stops :-)

please comment out the "old los" call in unit.py around line 506
please modify delay() to wait() in net/connection_poller... around line 70