Courageous' "True" LOS

[Courageous]

COURAGEOUS' "TRUE" LOS

0.9.1-A---WARNING ALPHA RELEASE

In response to a request, about six weeks back or so, for a "TRUE" LOS system that would hide mobiles that went out of sight due to obstructions, I built up a highly performance tuned implementation of LOS using a compressed binary shadow casting technique. The short story is that I have a huge matrix of precalculated "shadows" that can determine in very low O() time whether or not any entity is visible to the viewer.

There are many dirty coding tricks in this source code; if you are not a l33t coder, I think you're probably out of luck in trying to understand it. However, if you find hard problems to be interesting challenges, note that the code is fairly well commented, even in this early release, and I'll also be happy to explain it in further detail if you are interested.

How the system works and performs: what you need to know:

1. When a player mobile is being tested to see if it can see another mobile, the system checks to see if there is a previously-cached VisibilityMatrix for that location on that map.

2. If there isn't, the Matrix is generated. If there is, the matrix is fetched from a MRU cache that holds as many as mapsize/96 matrices in ram. This cache has O(1) performance for the Hit and Store methods. I.e., it's quick.

3. Just after the matrix is fetched from the cache or created, it's given a second processing pass, the account for items that may block LOS. The initial pass only considers land and statics. The initial pass is relatively expensive. The second pass is very very cheap.

4. The fact of a mobile's visibility is tested against the matrix.

Some notes. After the first generation of the matrix, it's quite likely that a player will be tested several times for more LOS. This follow up checks are "almost free," due to the nature of the matrix. Furthermore, because of the cacheing, any test that occurs where another player has been is likely to be a "cache hit". If it is, it likewise is almost free. What this ought to mean is one wicked-fast LOS system. However.

I have not actually tested this system on any large shard. What I have done is enter in big loops in a variety of locations, to verify the performance of the system under load. The biggest restriction is that I can't know how often a cache hit will occur. If you assume that 95% of the players go to 5% of the places, this system will work like wild fire. If it's the other way around, I wouldn't expect more than 300 or so simultaneous players to work out on some good computer equipment.

Finally, one last note:

The current system uses "dead reckoning" for mobiles that go out of LOS. You'll see a mobile for a while, standing there, doing nothing, when you can actually "no longer see it". A future release may remove the dead reckoning, but for now it's there, so keep an eye out for it. That's what you're supposed to see.

Now. Hooking up the system:

THIS IS A CORE MOD.

First. It only works with DOTNET 2.0.

Second, all the files that you need are attached in the zip. There is one directory called "LOS" that should be compiled into your server. There are two files, Map.cs and Mobile.cs that you can either use to replace your own, or you can look for the XXX LOS comments to find the (few) changes and merge them into your own versions. Finally, you have to do the same thing with PlayerMobile.cs

THIS IS AN ALPHA RELEASE.

Bugs are a possibility. I don't know of any, and have tested it quite a bit, but there may be things I didn't know to test. Caveat emptor.

CORE MOD ATTACHED.

[TEMPORARILY REMOVED PENDING RESOLVING A COPYRIGHT MATTER]

0.9.A Initial Release
0.9.1A Fixed bug at edges of map

[Nochte]

I haven't scanned every single line yet, but have more than half of it and have this to say:
bra-freaking-vo. it looks excellent so far, Courageous! I don't have an active server to test it on, but the code looks very sound. Congratulations.

[Irian]

Really nice job.

[arul]

Impressive, thanks

[Jeff]

Awsome and congrats man

[Courageous]

Updated to 0.9.1A. Note I am still calling it "alpha". In any case, I added the fix for the edge-of-map bug. I am actively seeking feedback for the system, as well as requests for improvement. Note that if you are testing it out as staff, you may want to use ArteGordon's handy StaffCloak. Staff isn't limited by LOS at all.

Note: in this minor update, only the main LOS system has been updated. Your prior edits still function as is. All future minor releases of LOS will warn you regarding any required additional edits in your core.

C//

[Arahil]

well, making your system able to handle the third dimension as well would definitely be a good improvement, but i think the amount of resources used for caching would increase rapidely then...

nevertheless, great job. a nice pool of ideas for los and some cool programming techniques and hacks to learn as well

[Courageous]

It actually does that now. The cache position includes Z. Otherwise the LOS system would be all messed up for LOS calculations for people in multiple levels of a house and what not. Granted, this is only "pseudo" 3D, in the sense that what is calculated is not a true line to the target, but rather a sort of visibility plane. The consequence of this plane is that someone at a high point may be able to see someone at a low point, but not vice versa--advantage to the higher ground... PK'er beware.

C//

[sicron]

You probably shouldnt really call it a consequence as opposed to a feature... anyone that would want to use this line of sight system should be thrilled about the fact that there would be an added bonus to having the high ground... after all isnt the whole concept of this to be more realistic

[Courageous]

Well. You have to think this out. The system has its appeal, but it's not perfectly realistic. Lets see if I can do this with line art:

A
____________
            |
            | B

In the above diagram (seen from the side), using the current LOS system, A will see B, but B will not see A. This is because in A's planar field of view, there are no obstructions. That's a limitation of the current system. It will stay this way unless there is a very strong call to fix it.

C//

[sicron]

ah, I was just thinking more along the lines of...
.................A
____________
..................|
..................| B

and not your example... one more reason Im not a coder

I know this would probably cause performance to take a huge nosedive, but what if there was also a check for players A and B if their z is +/- (insert any amount here) when checking A's line of site to player B, then check player B's los to A, if B cant see A, then dont allow A to see B. So it would only be a conditional check when there is a large difference in z.

[Courageous]

In your example, I coded it so that both A and B can see eachother. I.e, if A is standing on the obstruction, A is not obstructed from B.

C//

[Greystar]

Originally Posted by Courageous

In your example, I coded it so that both A and B can see eachother. I.e, if A is standing on the obstruction, A is not obstructed from B.

C//

So I see you cache it in memory, does that mean the shard would require more memory to use for each player or does it use if for a short time then clear out the cache storing it somewhere else. (Sorry havent downloaded the code to take a look at it, since I probably won't be compiling a new server.exe anytime soon). But im just curious about overall server affects. I know you said you only tested on a small shard, but what kind of extra memory/cpu usage did you notice, is really my question.

[Courageous]

It's configurable, but once the cache grows to a current size, it gets no smaller. This could be fixed, theoretically, by having a timer prune very old entries from it periodically. Anyway, in the base release, the system is set to configure the width*height of the map divided by 96 LOS matrices per MAP. Each matrix is 124 bytes. If I'm doing the math right, that's 31 megs for Map0. You can always try a different divisor.

C//

[Jarrod]

If you dont have LOS to Chuck Norris, chances are he probably already has LOS to you, and you are only seconds away from wearing a death shroud...

Thanks for the contribution. Ill check in on this one regularly.

[Jeff]

Originally Posted by Jarrod

If you dont have LOS to Chuck Norris, chances are he probably already has LOS to you, and you are only seconds away from wearing a death shroud...

Thanks for the contribution. Ill check in on this one regularly.

You know i gotta deal with this Chuck Norris chat crap on WOW, please dont bring it here ....... please....

[PerfectWing]

You should see Eve Online's "newbie" corp chat. :|

Oh, and congratulations Curageous. I won't be compiling a binary anytime soon either, at least, not until RunUO goes 2.0 solidly, but I can only imagine how much went into this. Uhm, *high-five*!

[floppydisc]

In the PlayerMobile's CanSee method, there should be a check for the targets accesslevel too.

if ( this.AccessLevel < m.AccessLevel ) return false;

Otherwise every player can see hidden GMs

[Courageous]

Holy crap! My first bug report! And here I thought I'd left every person baffled, and not a soul was using it!

So... how is it working, would you say?

I'm about to come back to this, after having handled some bug reports and feature requests for random encounters. First on my list is... err, bugs (1), and getting the dead reckoning out such that mobs disappear when they go out of sight. Any other thoughts or experiences?

C//

[floppydisc]

It definately has it's glitches currently. Overall it is a very cool implementation but there are problems when for example there is a static between mobiles that should be "invisible". Two examples I encountered on my shard:
The bank of britain does have a small wall in front of the desks for the bankers. It is small enough that you should be able to look over it and directly into the banker who sit's in front of you. But you don't see him and therefore can't even access the drop down menu of the banker
Another thing was: a group of players stood around a well and did not see each other.
I see the technical problems behind this, as for the system there is just an obstacle. But for a player it would be able to look through/over. I guess the only reliable way is to have a white-list of tiles and/or calculate the height of the tiles that are in between the mobiles. But probably both will be very intensive checks (regarding the necessary memory access) ...

But still - very great job and really impressive.

[Courageous]

Ah, no, not at all. Actually, the whitelist would be a very cheap calculation, and if you knew what to put in it, by item-id, I'd gladly code it. Keep in mind that the cacheing algorithm for the tiles, in the default 1/96th size resolution, produces an enormous datastructure that would be far in excess of the size of any tile whitelist.

How about this: for the next release, I'll set up a runtime xml config file that establishes the white list. You can then play around with whitelisting tiles.

Any other problems? My main subliminal worry is that there might be situations in the code proper--some specific thing--where I might not have hooked code in the right places. As in with your example of being able to see GMs...

When you get more experience with it, I'd like to hear how well it performs. A very good basis in thought says the cach'er ought to make it a screamer under load. But still... that's a theory.

C//

[Twice]

So, having this True LOS would it cause your shard to lag more? How does it handle with lots of mobiles in one spot, with lots of objects? Can people see people behind trees?

-2x

[Gembone]

I have a couple questions for this. first how does it affect the cicle of transparency if at all. and also can it be set to work with races so some have a further los than others? this is something I am really looking forward to trying. will work on implementing it today as I have time.

[Courageous]

Originally Posted by Gembone

First how does it affect the cicle of transparency if at all. and also can it be set to work with races so some have a further los than others? this is something I am really looking forward to trying. will work on implementing it today as I have time.

Neither one. There were some performance related reasons why I couldn't go down the route of doing something based on the specific qualities of the player (race, rangering skills, and so forth). Not gonna happen.

As for the other question, this system will lag your shard more than a standard UO server. It causs a very much lot less lag than turning on "true" LOS in any other way. The only way to see if the hit is acceptible to you is to try it. For lightly loaded shards, one may not notice the hit.

C//

[Solinari555]

Before I implement this on my testing server, are Staffmembers still able to see creatures outside of LOS?