Target optimization code v2
matso
Master of Patches Join Date: 2002-11-05 Member: 7000Members, Forum Moderators, NS2 Developer, Constellation, NS2 Playtester, Squad Five Blue, Squad Five Silver, Squad Five Gold, Reinforced - Shadow, NS2 Community Developer
Master of Patches Join Date: 2002-11-05 Member: 7000Members, Forum Moderators, NS2 Developer, Constellation, NS2 Playtester, Squad Five Blue, Squad Five Silver, Squad Five Gold, Reinforced - Shadow, NS2 Community Developer
I added a list to allow Crags to heal infestation, and fixed a number of more or less embarrasing bugs (copy-paste bugs are a tad embarrasing). Also, I've added a number of log options to the TargetCache to allow you to see in detail how each list is changed when something happens in the game. Those are turned ON in the code right now. If you are going to run a real game, you want to turn them OFF, as otherwise the console is going to get spammed WAY too much.
[attachment=35994:ns2opt.zip]
[attachment=35994:ns2opt.zip]
Comments
In NS2 console type "profile" and you will see lots of method calls. You can hit spacebar to pause it.
Now hold forward and walk into a corner (as a marine). Notice how there is some method SweepCollidable or something being called thousands of times.
I think that this method is being called *far* too many times (I see 6000-8000 calls per tick).
Can you reproduce this? I'm not sure if it's in the Lua or in the C++.
Sorting a list in LUA may be cheaper than tracing multiple rays in compiled code. If that's the case you may wish to sort the list of viable targets(i.e. enemies within range) in order of target juiciness(apply whatever criteria is used to select a target now; I think players have highest priority, and I think closer players have highest priority among players).
Start from the juiciest target and traverse the list towards decreasing desirability. The first target that passes the line of sight test is selected and no rays are fired at any of the less appealing targets.
If you dont want to click: It basiclly just a little bit of argument of why I dont think it should sort juiciness depending on class.
Thank you all for help, this is great stuff and we have such a smart community! Great work Matso!! Now if my server catches fire I will need your address :-)
Playa_2b
Sorting a list in LUA may be cheaper than tracing multiple rays in compiled code. If that's the case you may wish to sort the list of viable targets(i.e. enemies within range) in order of target juiciness(apply whatever criteria is used to select a target now; I think players have highest priority, and I think closer players have highest priority among players).
Start from the juiciest target and traverse the list towards decreasing desirability. The first target that passes the line of sight test is selected and no rays are fired at any of the less appealing targets.<!--QuoteEnd--></div><!--QuoteEEnd-->
That's pretty much how its done. You might want to check out TargetCache:_GetRawTargetList(). It works by selecting all mobile targets inside range (from the list of all potentially valid targets; alread prefiltered for everything that doesn't depends on details of the attacker), then joining up with the list of actual static targets (normally size zero). Then it sorts them by range.
This is then used by AcquirePlayerPreferenceTarget to choose a target; prefering closest player if visible, otherwise the closest non-player. The maximum amount of visibility checking is one per possible target, and as soon as a visible one is found, the scanning stops.
The Crag uses the raw target list directly because it selects multiple targets, and it also ignores LOS.
In NS2 console type "profile" and you will see lots of method calls. You can hit spacebar to pause it.
Now hold forward and walk into a corner (as a marine). Notice how there is some method SweepCollidable or something being called thousands of times.
I think that this method is being called *far* too many times (I see 6000-8000 calls per tick).
Can you reproduce this? I'm not sure if it's in the Lua or in the C++.<!--QuoteEnd--></div><!--QuoteEEnd-->
Hmm... nice tool, but I can't replicate what you get - walking into the closest corner from the command station on tram only seems to net me about 50 SweepCollidable; at least during Player:PerformMovement().
Also, the profile command gives you a client profile. Would be _really_ nice if there were a server_profile you could call ...
If you dont want to click: It basiclly just a little bit of argument of why I dont think it should sort juiciness depending on class.<!--QuoteEnd--></div><!--QuoteEEnd-->
That is effectively a nerf to turrets and hydras. It is possible now for a fade to soak bullets to allow a lerk to snipe; you just have to be closer to the turret than the lerk.
If you wanted turrets to behave this way there are big opportunities for optimization. Just cache the last target that was fired upon; most of the time this target will still be in LoS when the time to fire comes around again; fire a ray at this target and if it's still in LoS you select this target.
It will try to target the impossible to hit skulk behind it even though it might have a juicy lerk right ahead of it, as long as the skulk is closer.
Don't know if its a bug or by design; it would be easy to filter the target list for out-of-fov targets.
It will try to target the impossible to hit skulk behind it even though it might have a juicy lerk right ahead of it, as long as the skulk is closer.
Don't know if its a bug or by design; it would be easy to filter the target list for out-of-fov targets.<!--QuoteEnd--></div><!--QuoteEEnd-->
Ah, now it makes sense why they suck so much. In that case, I think they should just give sentries 360 coverage, lower the damage and health, and call it a day.
It will try to target the impossible to hit skulk behind it even though it might have a juicy lerk right ahead of it, as long as the skulk is closer.
Don't know if its a bug or by design; it would be easy to filter the target list for out-of-fov targets.<!--QuoteEnd--></div><!--QuoteEEnd-->
If the sentry FOV is a cone it is very simple vector math: all you have to do is take a dot product and compare against a scalar.
Dot(U,V) is equal to |U|*|V|*cos(U,V). If U is the direction vector from sentry to target(calculate this), V the direction the turret is pointing(normalized, stored in memory), c the cosine of the FOV cone's half-angle(this is a constant) then if Dot(U,V) > |U|*c it is a valid target.
If you're implementing the FOV and range check in C or C++ use Dot(U/|U|,V) > c instead. You're going to calculate the square distance anyway for range checking(you don't need to calculate the distance; if dot(U,U) is greater than sentry_range^2 it's not a valid target). You have access to a fast inverse square root approximation(RSQRTSS instruction + 1 newton-raphson step gets you 22 bits of precision) so there is no divss or sqrtss instruction; you just approximate 1/|U| and multiply with U.
edited: RCPSS is "reciprocal scalar single precision", it should of course be RSQRTSS.
<!--quoteo(post=1840383:date=Apr 9 2011, 10:17 PM:name=Soylent_green)--><div class='quotetop'>QUOTE (Soylent_green @ Apr 9 2011, 10:17 PM) <a href="index.php?act=findpost&pid=1840383"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->... very simple vector math...<!--QuoteEnd--></div><!--QuoteEEnd-->
It's simple ok.
Basically taking the bounds of the map, recursively dividing the longest axes in two until some fixed depth is reached (I think they use ~6 levels). Each sector contains a linked list of entities contained. When an entity is moved or spawned, the server checks if the worldsector has changed and corrects the linked lists for it. Of course there's the downside, that if a lot of the entities are in close proximity anyways, this won't cull a lot. The upside is that it is simple and cheap.
Basically taking the bounds of the map, recursively dividing the longest axes in two until some fixed depth is reached (I think they use ~6 levels). Each sector contains a linked list of entities contained. When an entity is moved or spawned, the server checks if the worldsector has changed and corrects the linked lists for it. Of course there's the downside, that if a lot of the entities are in close proximity anyways, this won't cull a lot. The upside is that it is simple and cheap.<!--QuoteEnd--></div><!--QuoteEEnd-->
Did they? I was under the impression that quake III used binary space partitioning with precomputed PVS('VIS' part of the compile process for HL, HL2, Quake I-III games) to handle the occlusion culling and resolve most questions like "can entity X see entity Y?" without having to fire rays(if leaf A does not have leaf B in its PVS and entity X is in leaf A, entity Y in leaf B, then they cannot see each other and you don't need to bother firing any rays).
Oh for crying out loud, dot products are something you learn about in grade 10-12 after trig. Don't tell me you've forgotten one of the most basic identities of one o the most basic operations you can do on vectors: dot(U, V) = |U||V|cos(U,V) = Ux*Vx+Uy*Vy+Uz*Vz [in a 3-dimensional euclidian space]
haha, believe it or not most people don't actually use vector math anymore after school.
Then why did you bother posting about it? There really is the idea floating around here lately pasting lotsa formules\algorithms\diagrams garnishes you brownie points. It must have started when Harimau decided to airstrike us with Lua-script and got positive feedback. I too could stink up the place with C++-code so ridiculously elaborate and unreadable it will make your head splode.
It's starting to reek like pretentiousness around here. Do reply to this post with some additional vector-math to explain my idiocy, just for a laugh.
/rant
Actually, it is
e = mc^2
c squared, not 2c
e = mc^2
c squared, not 2c<!--QuoteEnd--></div><!--QuoteEEnd-->
Proof?
It's starting to reek like pretentiousness around here. Do reply to this post with some additional vector-math to explain my idiocy, just for a laugh.
/rant<!--QuoteEnd--></div><!--QuoteEEnd-->
It was a surgical strike. No civilian lives were lost.
Seriously, though. These perfectly voluntary discussions and analyses take place in one or two threads. If they bother you and yet you <b>still</b> return to them time and time again, then that's an issue you may need to take up with your counsellor.
<!--quoteo(post=1840430:date=Apr 10 2011, 04:20 PM:name=endar)--><div class='quotetop'>QUOTE (endar @ Apr 10 2011, 04:20 PM) <a href="index.php?act=findpost&pid=1840430"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->Proof?<!--QuoteEnd--></div><!--QuoteEEnd-->
See Prof. Einstein after class.
I'm sorry, and we trust this man because?
<img src="http://www.johnnycopland.com/wp-content/uploads/050405_einstein_tonguewidec.jpg" border="0" class="linked-image" />
Because there exist people who are not old enough to have been exposed to vector math and people like you who seem to take pride in supressing everything they've learned that wasn't immediately useful.
For all I know Matso could use trig to solve it, which is certainly possible, but both messier and more expensive.
<!--quoteo(post=1840425:date=Apr 10 2011, 12:42 AM:name=player)--><div class='quotetop'>QUOTE (player @ Apr 10 2011, 12:42 AM) <a href="index.php?act=findpost&pid=1840425"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->There really is the idea floating around here lately pasting lotsa formules\algorithms\diagrams garnishes you brownie points.<!--QuoteEnd--></div><!--QuoteEEnd-->
Math and code is absolutely to be expected in any thread about <b>optimization</b>, they are the most compact and readable languages for their respective applications.
<!--quoteo(post=1840425:date=Apr 10 2011, 12:42 AM:name=player)--><div class='quotetop'>QUOTE (player @ Apr 10 2011, 12:42 AM) <a href="index.php?act=findpost&pid=1840425"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->It must have started when Harimau decided to airstrike us with Lua-script and got positive feedback. I too could stink up the place with C++-code so ridiculously elaborate and unreadable it will make your head splode. It's starting to reek like pretentiousness around here.<!--QuoteEnd--></div><!--QuoteEEnd-->
I agree, stop posting pretentious twaddle and go somewhere else.
<!--quoteo(post=1840427:date=Apr 10 2011, 04:54 AM:name=Feha)--><div class='quotetop'>QUOTE (Feha @ Apr 10 2011, 04:54 AM) <a href="index.php?act=findpost&pid=1840427"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->Actually, it is
e = mc^2
c squared, not 2c<!--QuoteEnd--></div><!--QuoteEEnd-->
<3 SentrySteve left the best bait.
From what I've seen, the PVS system is mostly used for rendering and optimizing bandwidth. There's also an area/portal culling system, used in the same way. On the server-side they do the worldsector culling. On the client they don't even bother... they just build a list of solid entites at each snapshot and iterates them all at each trace. :)
Actually to be a good bait, shouldnt it have been intentionally made?
And its not good to leave incorrect math on forums, what if the dumb sheeps of the interwebz believe it?
e=mc²
mc? like mc donalds?
mc hammer?
:P
The other ones could figure he meant ^2...