[SVN:r3254] LoS Check Manager

A place to submit .patch fixes for the DOL SVN

Moderator: Developer Team

Re: LoS Check Manager

Postby Leodagan » Mon Sep 16, 2013 5:22 pm

OK I spend the evening testing, there was a lot of small bugs.

Caching helps a lot in EvE situation, like guards vs mobs, I didn't even thought of this one ;)
in PvE with a 2500 ms cache, it hardly makes two swing, but making it longer will allow to shoot mobs easily by playing with boulder or walls, it will help more with skills and spells LoS check it could trigger during attacks.

I don't expect much of pvp caching (100ms) except in crowdy situations. I even think player could notice a short caching like this.


The throttling wasn't working because player aren't added to ClientChecks dictionary ;)

without throttling it tend to launch all LoS check at the same time, the reply are pretty quick in local and this prevent from running into an "LosUnavailable" exception which are hard to handle !!

I don't think most of the code is prepared for LosUnavailable and "try again next time" exception handling, I don't think there is try again in most loops ;)

And that make me think throttle can't be handled this way, the code itself already handle kind of timeout (with previous check sending a false value when it needs to send a new one) but try again later I don't think so ;)

I already handle a PvP check to launch LoS checks anyway !

This leads me to the queue, but how long can it be ? Only for PvE matters ? Need a Timer to try again if hardly any code handles it ?

LoS packet are pretty small, and connection Lag could handle the throttling :)

Maybe it's better without too much throttling ;)
User avatar
Leodagan
Developer
 
Posts: 1350
Joined: Tue May 01, 2012 9:30 am
Website: https://daoc.freyad.net
Location: Lyon

Re: LoS Check Manager

Postby Leodagan » Tue Sep 17, 2013 3:28 pm

As I expected with throttling there are much LoS check that aren't Done...

I have no other way than catch LosUnavailableException and return in most of LoS handler

Mob Brain "Think" tend to come all in the same millisecond which makes LoS Packet Burst.

A solo player using an Animist will be FLOOD by LoS checks every 2500ms !

Throttling can't be done efficiently on the base of Checks Frequency, with low number of player I'm afraid even some PvP LoS check could fail in exception !

I'm not even sure the previous throttling algorithm are working well ;) All I've seen is something to prevent a player from making more than 10 LoS checks at once !

I still don't know how I'll throttle LoS checks, with a high number of player I'm thinking on a distributed algorithm (just need to make some stats on Clients LoS checks and sort that well then pick a player) to take advantage of faster LoS checker, but in solo to have the same level of Environment behavior I'll have to rely to a fast queue and caching.

That could give advantages to client playing solo in an area...
User avatar
Leodagan
Developer
 
Posts: 1350
Joined: Tue May 01, 2012 9:30 am
Website: https://daoc.freyad.net
Location: Lyon

Re: LoS Check Manager

Postby Graveen » Tue Sep 17, 2013 4:20 pm

i see, this is a wide area of optimisation :)
Image
* pm me to contribute in Dawn of Light: code, database *
User avatar
Graveen
Project Leader
 
Posts: 12661
Joined: Fri Oct 19, 2007 9:22 pm
Location: France

Re: LoS Check Manager

Postby Leodagan » Tue Sep 17, 2013 5:34 pm

Forgot to tell...

I fired this script on Freyad with no limits to LoS checks... (the best way he works for now)

There is a 2500ms cache for PvE, a 100 ms Cache for PvP and 5000 ms cache for EvE.

There is debug activated and Logs are simply flooded !

I've done that to parse it after some days and make stats...

From what I can tell with some minutes with 40 ppl in PvE is that cache miss on the 2500ms cache is about 60% (2500 ms is too low for PvE, most swing or cast will just need this timeout to make new checks)

I see also Animist pet swarm, each shroom needs his LoS, I'm wondering about "Area" cache for PvE (this can't be used for PvP where low latency is needed)

Anyway I think we're in 2013 we have broadband and quad core, I'll wait for player reports ;)


EDIT :

Reports and more analyze :

Players report LoS False positive (PBAE through a wall), there is a log attached, a nice report : http://s7.directupload.net/file/d/3383/pb4kpobq_jpg.htm

I was expecting false negatives... gotta check this in PBAE LoS checks...

Analyze from log, LoS checks are pretty intensive, a warrior launching himself in a spot with dozen of mobs = 12 LoS check every 2.5 sec (or every five sec) if there is some FnF around and scanning Aggro mob LoS checking it can easily get to a rate of 10 checks / seconds in PvE

And a KO LoS cache between a player and mob could prevent him from attacking the mob during 2.5 sec, at high level it can be 2 casts, more than 2 swings, some missed instants etc...

EDIT 2 :

I just found out ! LoS check it's checking the "light" is going from A to B, it's well known that if you can see you can be seen !

LoS check should update Source to Target and Target to source Cache at the same Time !

Now I can get something out of this and get two data for one check ;)
User avatar
Leodagan
Developer
 
Posts: 1350
Joined: Tue May 01, 2012 9:30 am
Website: https://daoc.freyad.net
Location: Lyon

Re: LoS Check Manager

Postby Graveen » Tue Sep 17, 2013 9:11 pm

you can reasonnably consider a los check from A to B is valid for a 1000ms time, and use this cache to avoid bidirectionnal LOS check.

for FnF turrets, you can draw a line ax+b to nearest turret to target, and consider if LosCheck(X,E) and LosCheck(A,E) then
A B C D E loscheck are positive for X.

A B C D E X

I think theses mecanisms would be pretty nice into your manager.

Keep up the good work :)
Image
* pm me to contribute in Dawn of Light: code, database *
User avatar
Graveen
Project Leader
 
Posts: 12661
Joined: Fri Oct 19, 2007 9:22 pm
Location: France

Re: LoS Check Manager

Postby Leodagan » Wed Sep 18, 2013 5:10 am

Ok for bidirectionnal Cache,

Didn't understand about the line...

You want to cast a "ray" server side between the 2 object beeing LoS checked ?

I check object A ----- B, if object are on the trajectory they get LoS OK too ? A --- X --- B --- Y

if A sees B, then X sees A, B, Y, everyone on the line see themselves ?

I was more thinking of los check doing small area update (like getNPCinRadius(50)) but only for Mobs ;)
User avatar
Leodagan
Developer
 
Posts: 1350
Joined: Tue May 01, 2012 9:30 am
Website: https://daoc.freyad.net
Location: Lyon

Re: LoS Check Manager

Postby Graveen » Wed Sep 18, 2013 8:04 am

X is a mob, A B C D E are some turrets. the small radius trickis interesting, but i think it should be tested in a keep.
Image
* pm me to contribute in Dawn of Light: code, database *
User avatar
Graveen
Project Leader
 
Posts: 12661
Joined: Fri Oct 19, 2007 9:22 pm
Location: France

Re: LoS Check Manager

Postby Tolakram » Wed Sep 18, 2013 1:52 pm

Unfortunately the only LOS packet that can be checked must involve a player. For pets it's usually if player has LOS to target, which is exploitable, of course. We would need server side mapping in order to properly check LOS from NPC to NPC.
- Mark
User avatar
Tolakram
Storm / Storm-D2 Admin
 
Posts: 9189
Joined: Tue Jun 13, 2006 1:49 am
Location: Kentucky, USA

Re: LoS Check Manager

Postby Leodagan » Wed Sep 18, 2013 2:14 pm

In fact, I don't know if it's intended to be like this, Third Party LoS checks are working pretty well !

If it isn't most of my tests are worthless, but I'm sure it worked ;)

You can ask any client to LoS check between two ingame objects, not necessarily Client[player] to GameObject !

I did much work today :

Added an "Area Contamination" for LoS check, depending on Object Type :
Every object in a small area around LoS checker will be tested if they can receive Contaminated LoS (Player can't, Pet can if in a really short range, NPC and Guards get a wider range, and if it's EvE the range is huge)
The Contamination update cache for a Next LoS check, they don't Notify objects of a Finished LoS event !

Dual Cache Update to every LoS checks (even contaminated ones) on the basis if you can see you can be seen ! Maybe I'll update this to prevent Broadcasting too much KO LoS (these are the most annoying if they get between valid LoS)

KO LoS Cache is half shorter than OK cache, I don't know why I wanted this, but it feels good to trigger a next LoS faster on KO and don't use a KO cache too long.

Some kind of statistics for Player checkers to choose one which is a good Checker (based on latency, and losChecks count...) mostly for Vincinity based checks (NPC vs NPC)

A "retry" engine that checks pending LoS that take over 300ms and re-send them to Vincinity (based on above statistics), this will update Pendings and thus not check it as timeout every Tick.

Finally a Radius Treshold depending on object type checking LoS, I started with Player having 32 unit Threshold (found that somewhere in a Class) Pet having 50 units, Mobs having 125 units, Mob vs Mob having 250 units...

Within these range a LoS check will always reply TRUE !
User avatar
Leodagan
Developer
 
Posts: 1350
Joined: Tue May 01, 2012 9:30 am
Website: https://daoc.freyad.net
Location: Lyon

Re: LoS Check Manager

Postby Leodagan » Wed Sep 18, 2013 3:58 pm

OK It's a pain to debug this ;)

I'm getting nice results anyway :

If you're chased by a mob, run and he'll start LoS checking you (threshold), run to a guard, and the mob, LoS checking you, will contaminate the guard with an OK LoS, next brain Think the guard rush the mob :)

Edit :

Player stats are ok, but my "BestChecker" Algorithm is failing, so all third-party checks are trashed right now :p
User avatar
Leodagan
Developer
 
Posts: 1350
Joined: Tue May 01, 2012 9:30 am
Website: https://daoc.freyad.net
Location: Lyon

Re: LoS Check Manager

Postby geshi » Wed Sep 18, 2013 5:16 pm

Anyway I think we're in 2013 we have broadband and quad core, I'll wait for player reports ;)
This is nice and all but if this is really going to effect things that much then is it really worth it? I don't even think changes like this are even necessary .
geshi
Contributor
 
Posts: 1826
Joined: Tue Oct 21, 2008 9:16 pm

Re: LoS Check Manager

Postby Tolakram » Wed Sep 18, 2013 5:23 pm

It's an exercise in programming and understanding, and will be protected via a server property. IMO it's worth it asl long as the older faster system remains in place. Too few people have delved into the LOS stuff, we need more information. :)
- Mark
User avatar
Tolakram
Storm / Storm-D2 Admin
 
Posts: 9189
Joined: Tue Jun 13, 2006 1:49 am
Location: Kentucky, USA

Re: LoS Check Manager

Postby Tolakram » Wed Sep 18, 2013 5:25 pm

OK It's a pain to debug this ;)

I'm getting nice results anyway :

If you're chased by a mob, run and he'll start LoS checking you (threshold), run to a guard, and the mob, LoS checking you, will contaminate the guard with an OK LoS, next brain Think the guard rush the mob :)

Edit :

Player stats are ok, but my "BestChecker" Algorithm is failing, so all third-party checks are trashed right now :p
I am lacking any understanding as to how this can work. The only LOS packet I know about is to a client. There is a targetinview property, but I think this is player related as well. What is the communication line between mob1 and mob2 to do the LOS check?
- Mark
User avatar
Tolakram
Storm / Storm-D2 Admin
 
Posts: 9189
Joined: Tue Jun 13, 2006 1:49 am
Location: Kentucky, USA

Re: LoS Check Manager

Postby Leodagan » Wed Sep 18, 2013 5:53 pm

It's the client doing the "Third-Party" LoS check :p

I sent to Player.out.sendchecklos(Mob1.objectID, Mob2.objectID) and the client cast the ray for me then return the result...

I use client as cloud LoS computing :D

And Mob Brain are all subclass of Vincinity Brain which means they don't work without a client near them... and I need that client to make them work :)

Honestly it's been some day I'm thinking if a modified client couldn't load all regions in Wireframe and just cast Rays for my shard :D
User avatar
Leodagan
Developer
 
Posts: 1350
Joined: Tue May 01, 2012 9:30 am
Website: https://daoc.freyad.net
Location: Lyon

Re: LoS Check Manager

Postby Leodagan » Thu Sep 19, 2013 6:48 am

Anyway I think we're in 2013 we have broadband and quad core, I'll wait for player reports ;)
This is nice and all but if this is really going to effect things that much then is it really worth it? I don't even think changes like this are even necessary .
If you want a server with more LoS checks in different area (Mob Brain, Aggro checks, Pets Always checking LoS, Ranged Mob not shooting through walls, and at last PvP low latency...) you could easily flood the previous Methods without having any way to ponder LoS checks based on pendings checks right now...


As I see in Code the LoS checks are just limited to 10 at once in some part of the code, and the Server Properties (like 1 Los by player every 5 secs) have nearly no effects on all the server los checks, even property like "alway check pet los" wont have much effect when a pet cast spell, as spellhandler will do this los check without obeying server properties...

Now there is a main class LoS manager that knows every los checks queries, pending, finished, when they were made, what was the results, etc...

The heavier part of the code on server side come from all the LoS checks Manipulations (dual cache, contamination, cleanups, bestplayer query), but now that there is some caching and some "previous" data, you can use function like "LosCheckMgr.IsAvailableForLosCheck(player)" to take your own solution withing brains or spellhandler,
And if this code is heavier for a low number of player or low LoS check number, I expect it to scale rather well, the more there is player and Checks the more there is cache and distribution of LoS checks accross players.

Also, you can now code stupidly a new Script with a lot of LosChecks Queries without needing to think yourself how to throttle or cache (or even don't care at all when you don't have skills to do this...), you can put this in a short Loop, the Manager will try to do the less checks possible ! (And I intend to use this for new Mobs Brain which won't care the number of LoS checks they can handle, they will just query them or read cache)

At last my "Quad Core" comment was for Client Side ;)
I don't know if it costs a lot to the Client to cast more than 10 ray tracing by second, but since the age of DAoC I expect player have above needs hardware !
It's an exercise in programming and understanding, and will be protected via a server property. IMO it's worth it asl long as the older faster system remains in place. Too few people have delved into the LOS stuff, we need more information. :)
As I needed to have my proper callback in packetLib I made it in a way you can use both method without having even crosstalks !

And Both methods can share a same result ;) (when a LoS result is receive it notifies old callback AND new callback !)

I have many "const" which can alter LosMgr behavior (setting radius to 0 prevent contamination, cache lifetime, cleanup loops can be configured, retrying loop too, range threshold) this will make about 10-15 new server properties ;)

And each code using old callback need an explicit update to use new LosMgr (as it does much work that some Methods were trying to do, like finding a player owner to Pets for los checking, or Checking the max number of current LoS checks on this player)

To have a switch between old and new callback we would need to update Classes code with both new and old way, for now you're right it's more a programmer tool ;) (I'm replacing callbacks actually but I won't Commit it to Trunk like this !)

For Proof of Concept, on my shard All Mobs and Players uses new callbacks, All KeepGuards still use old callback, no problem with that and Shard's Custom Scripts will still be able to use them without updates.
User avatar
Leodagan
Developer
 
Posts: 1350
Joined: Tue May 01, 2012 9:30 am
Website: https://daoc.freyad.net
Location: Lyon


Return to “%s” DOL Code Contributions

Who is online

Users browsing this forum: No registered users and 0 guests