the real bottleneck

[imbaczek]

I'm gonna need to dig it up... the link probably won't be in English even then. (It's from some Polish algorithm contest. Perhaps even more useful for AI threatmaps.)

Will edit this post when I find it, maybe with example code.

edit: found the code, 3.5 years old... don't remember jack shit about it except that it's pretty clever. Here it was used for artillery/tank threat mapping in a bot contest of some kind, hence tanks, friends, foes and stuff.

-1/1 in the middle was probably for some kind of territory calculation. What it is shouldn't matter.

http://pastebin.com/f5b721b7a

[Jasper1984]

Looks like a pretty cool trick, although i don't entirely understand it yet. For instance how can the LOS get (approx) spherical from this code?

Do have some questions though, since there is no mention of height in the code, how will it take into account height? How are the LOS ranges in the link (approx)spherical? Could that be done with by adding factors in those sums of map[j]?

The -+1 thing from 'if (who == FOE && what == TANK)', seems weird to me, enemies take away range? Seems to me that if you wanted to calculate LOS of multiple different teams, you could do that by giving them mutually indivisible factors when adding/subtracting to map[j], not by doing this. If it were territory calculation, that would also be weird, because it isn't symmetrical between friend/foe. Maybe some kind of influence calculation?

[imbaczek]

re TANKS and FOES: it's a leftover from the ~1KLOC i extracted the code from, you can freely ignore it; i'll have to find the proper description of the algorithm later.

as for making the thing circular, no idea if it's possible while preserving computational complexity. i'd guess yes, but not in a trivial way.

[Jasper1984]

I think i understand it now. The first part calculates the number(the area) of units in x<i,y<j in map[i,j], the area of map[i-1,j] + map[i,j-1] has overlapping area map[i-1,j-1].
The second part calculates the number of units in a smaller square using the same trick(but -r,-r instead of -1,-1). The number of friendly tanks that can see will be in frtank_cov[x,y].

So the presented code uses a square line of sight, i guess it could be made round because it calculates numbers of some unit in a square. (fi,fj from, ti, tj to)

Code: Select all

int unit_count_on_rect(int** tmp, int fi, int fj, int ti, int tj)
{ return tmp[fi][fj] - tmp[ti][fj] - tmp[fi][fj] + tmp[fi][fj]; }

int unit_count_on_vertical_shape (int** tmp, int fi,int ti, int(*low)(int),int(*high)(int))
{ int i=fi, sum=0;
  while(i<ti)
  { sum+= unit_count_rect(tmp, i,i+1,low(i),high(i),); i++; }
  return sum;
}

If the writer had used names like that, it would've been more easily readable/understandable.(Or is the compiler stupid enough not to inline that?)
That would make the 'vertical shape' O(Area*R) with R the view range. Dunno if this can be used efficiently when you want to use the actual terrain, where the area you want to count friendly units on needs to be calculated at every position before using this. Or maybe stored beforehand... (As a bunch of arrays low,high)
I do not think much can be changed with the calculation of map[i,j] to help.

Edit: One nice thing is that you can do multiple teams at a time by making the nth team count as 2^n. Until the numbers get too large, if you allow for 2^k units, you could do bit_count-k teams in one go. (2^20 units, 43 teams for 63 bits of integer.)
Edit: what is a ~1KLOC?

[koshi]

Edit: what is a ~1KLOC?

Kilo Lines Of Code

[Jasper1984]

Must have been a little confused before. This method isn't really about LOS, it is about cleverly calculating how many units there are in a rectangle. Of course it can be used for LOS, but it doesn't actually calculate where you can see. (And the second part of the code is just memoization.)

[aegis]

if you can number them, you can identify them.

[imbaczek]

the writer was me, didn't bother commenting it back then since I knew where the (long and thorough) description is could've at least put the name of the pdf... anyway, it does count units in a rectangle, but in spring's context it can be used for non-terrain-blocking LOS. if we made air units use this, i guess effect would be noticeable.

[Jasper1984]

the writer was me, didn't bother commenting it back then

I was just interested, the code just seemed so mysterious. (Although it seems so obvious now )

[Pressure Line]

if we made air units use this, i guess effect would be noticeable.

as long as it is optional (on by default?) so that low flying aircraft dont get x-ray vision

*edit* might be nice as per unit and per mod settable (modrules anyone?) to emulate circular option from the full/circular/true los selector in OTA (im thinking for the "pure" OTA mod/s, and/or any other application anyone can think of)

[lurker]

Reupload the image please; it might take a few hours for me to get an linux installed.

Oh right, already installed, but 2 or all 3...

...2 but not the expected 2. Good, I have ubuntu ready.

Wow, dist upgrade takes a while.

Do I need symbols for spring then? Got everything else working, now I just need all the dependencies...


I have charts!

Only took two days! \o/

Funtime charts:
sudo opcontrol -i /path/to/bin/spring --no-vmlinux -c 16
opcontrol --start
/path/to/bin/spring replay.sdf
opcontrol --stop
opcontrol --dump
opreport -cgf > springoprofile.txt
./gprof2dot.py -f oprofile < springoprofile.txt > springdot.txt
dot -Tpng -o spring.png < springdot.txt
./xdot.py springdot.txt

[lurker]

Any reason not to refactor LOS::moveunit to be called from unit slowupdate instead of movetype slowupdate?

[altie]

What kind of system and OS are you running on? Any idea about the anon over on the right of the top row taking up about 10%? Can you post your replay.sdf so that other people can run it?

[eyu100]

Is it possible to make sqrt() run faster? Looking at one of the streflop square root functions, it has many instructions, but there may be a square root function in x86 assembly (sqrtps? sqrtss? http://en.wikipedia.org/wiki/X86_instruction_listings) that is faster (this could be inlined into the code). Presumably, the instruction works the same on all Intel CPU's... This wouldn't work for non-x86 computers, though.

[thesleepless]

Is it possible to make sqrt() run faster? Looking at one of the streflop square root functions, it has many instructions, but there may be a square root function in x86 assembly (sqrtps? sqrtss? http://en.wikipedia.org/wiki/X86_instruction_listings) that is faster (this could be inlined into the code). Presumably, the instruction works the same on all Intel CPU's... This wouldn't work for non-x86 computers, though.

just use a lookup table for sqrt if you're not already.

[IMSabbel]

A cache miss on the look-up-table will be a lot slower than just calculating it. even a L2 _hit_ wont be that much faster.

The correct way would be using the fast sqrt provided by the common SIMD extensions (which use hardware look-up+newton-raphson)