[RunUO 2.0 RC1] Courageous True Line of Sight

[Courageous]

Courageous' (aka Joe Kraska's) True LOS

Version: 1.4B (BETA) -- 30 Sep 2007

ABOUT THIS SOFTWARE

This is a "true" Line of Sight system for RunUO. In the core distribution (and OSI itself), a player can see mobiles which they shouldn't be able to see, such as in the case of players and monsters on the other side of a wall. The reason that this is the case is that the traditional calculations for LOS on the scale of a multiplayer server are too expensive. This system remedies that.


UPDATES

30 Sep 2007. Uploaded the 1.4B "beta" version.

• Resolves an issue with items in packs being inappropriately displayed when Visible=FALSE.
  

1 Oct 2006. Uploaded the 1.3B "beta" version.

• Enhanced in game support for walls
• Made it so that you have to be within a certain distance of the edge of the roof to see down.
• Fixed an issue with uneven terrain tiles.
• Added support for mixed mode walls marked Impassable and Wall, but not "NoShoot"; these walls no treated like windows and obey window range.
• Fixed a bug where some items were not properly lossed.
• Added support so that corpses are properly lossed.
• Worked some additional protocol fixes, including possible "stutter" problems.
• Implemented partial support for "warmup," however this is not yet functioning on automatic( type [los warmup to test it, but do so before players are online; watch your console window ).
  

22 Sep 2006. Uploaded the 1.2B "beta" version.

• Fixed a problem where some things would be in view along the diagonal areas, when they should be obstructed.
• Fixed an issue with land terrain, changed to "only mountainous land tiles block LOS".
• Fixed a problem with addons.
• Fixed a problem where mobs would be denied LOS and lose track of the player too easily.
• Fixed a problem where house signs and doors were being LOSsed when the houses were not.
• Fixed a source of "stutter" do to duplicate packet flow.
• ADDED: configurable range to windows in order to see thru them.
• ADDED: configurable range to trees in order to see thru them.
• ADDED: configurable cache ratio.
• ADDED: configure which facets LOS will function on.

9 Sep 2006. Uploaded the 1.1B "beta" version.

• Applies a (configurable) squelching mechanism to suppress the all-names chatter using razor (non razor users won't need this).
  
• Fixes some packet issues. Fixes a problem with item support in the previous version, where multis couldn't be seen.
• Fixes some issues with some windows, due to UO itself not flagging them properly.
• Adds a (configurable) feature where you have to be close to a window to see thru it.
  

WHAT HAPPENS WHEN YOU INSTALL IT

When installed:

Players should not see other players or mobiles, if a wall, tree, or other visual obstruction is in the way.

There is nothing particularly innovative about this. What is innovative about this is the performance. What you are currently looking at may be the fastest implementation of 2D line of sight in the world. Some shards have tried LOS before, the obvious way, and encountered terrible lag. This system should be very, very fast.

Is it fast enough for a "production shard"? In truth, I don't know. I have tested it under synthethetic load, and got it to support 100's of player mobiles on my dual core computer with 1G of RAM.

So onward:

Trees block line of sight. Houses, land terrain, and items with the appropriate flags set block line of sight. Other mobiles do not block line of sight. Only player mobiles use the line of sight system. AI mobiles do not use this LOS system.

As you explore and play with the software, one should understand a bit about how it is expected to work. The software cuts a 2d plane from the player's eyes, and anything intersecting that plane will block LOS to the target, even if the target is not in the plane.

By and large, this phenomenon is mostly not noticeable, but does lead to some interesting inbalances regarding who can see whom when one player is at a higher terrain level than another. The advantage is to the higher ground.

An example where the higher ground might get an advantage that is a little weird:

_____________A_
               |
               |___________________B____________

Here, A can see B, but B cannot see A. This is happening because in the plane that B is in, there is a LOS blocking obstruction (the wall) between it and A. However, in A's plane, there is no obstruction between A and B.

Now note the subtle change in the arrangement below:

______________A
               |
               |___________________B____________

In the above figure A is now on top of the abstruction in B's plane. In this case B can see A. That brings me to an obvious point. Obstructions do not block view of themselves or anything in the same cell. That's really the way it ought to be.

As far as the imbalance in the first example goes, gm's might find this imbalance unfair or potentially exploitable. If that is the case, there is an option in the config file to use "symmetric" LOS. In symmetric LOS, each viewer uses the worst of both their view and the viewees view of eachother: if one party can't see the other, neither can.

Finally, another word about the config file. There is a "White List" and a "Black List". The white list is for items and statics that are flagged as LOS blocking in the muldata files, but you don't want to block LOS. The black list is vice versa: add things here you want to block LOS. The values already present are for the trees.

DETAILS... for the MASOCHISTICALLY CURIOUS

This system was inspired originally by some notes collected by Amit Patel, who has done the world a favor in introducing some programming notes on pathfinding and LOS and other such at his home page here:

http://www-cs-students.stanford.edu/~amitp/gameprog.html

The basic idea is to record the fact of a "shadow" (an area that cannot be seen) for any obstruction one might find in the field of view. One could then combine these shadows together for the sum of obstructions, in effect moving the cost of LOS over to the obstructions instead of the LOS checks. In theory, if one can create the sum of shadows quickly enough, every LOS check in the same position would be "free" thereafter.

What follows is a long series of optimizations and hacks in order to make this work.

Let's look at the main idea:

Figure-1:

// {{-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,#},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,#},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,#,#},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,#,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,X,#,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,O,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
//  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-}},

In the above, we have the Observer, marked as "O", an obstruction, marked as "X", and the area in the "shadow" of the obstruction, all marked as "#". In this simple case O has no line of sight to anything in the shadow. So if I look up the position of a target in the matrix, and they are in the shadow zone, they are not in LOS. This beats the ordinary way by a large magnitude, as the ordinary way involves drawing a line between the observer and the target for every possible target. That's expensive.

Compare that with this method, where for any given obstruction, in any given relative position, the shadow is known once and for all, and never needs to be calculated more than once! (In fact, LOS never actually calculates shadows, but rather uses a special code generator to produce them in a binary compact "precompiled" form, for performance reasons).

Now lets look at this:

Figure-2:

# # # # # # # # - - - - - - - - # # - - - - - - - - - - - -
 # # # # # # # # # - - - - - - - # # - - - - - - - - - - - -
 # # # # - # # # - - - - - - - - # # - - - - - - - - - - - -
 # # # # # # # # # - - - - - - - # # - - - - - - - - - - - #
 # # # # # # # # - - - - - - - - # # - - - - - - - - - - # #
 # # # # # # # # # - - - - - - - - - - - - - - - - - # # # #
 # # # # # # # # - - - - - - - - - - - - - - - - - # # # # -
 # # # # # # # # # - - - - - - - - - - - - - - - # # # - - -
 # # # # # # # # - - - - - - - - - - - - - - - # # # - - - #
 # # # # # # # # - - - - - - - - - - - - - - # # # - - # # #
 # # # # # # # # - - - - - - - - - - - - - # # - - # # # # -
 # # # # # # # # - - - - - - - - - - - - - # - - - # # - - -
 # # # # # - # # - - - - - - - - - - - - - - - - - - - - - -
 # # # # # # # # - - - - - - - - - - - - - - - - - - - - - -
 - - # # # # # # - - - - - - - - - - - - - - - - - - - - - -
 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 - - - - - - - - - - - - - - - - - - - - - - - - - - # # # -
 - - - - - - - - - - - - - - - - - - - - - - - - - - # # # #
 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 - - - # - - - - - - - - - - - - - - - - - - - - - - - - - #
 - # # # - - - - - - - # # - - - - - - - - - - - - - - - - #
 # # - - - - - - - - # # - - - - - - - - - - - - - - - - - -
 - - - # - - - - - # # # - - - - - - - - - - - - - - - - - #
 - - # # - - - # # # # - - - - - # # - - - - - - - - - - - #
 - # # - - - # # # # # - - - - - # # - - - - - - - - - - - -
 # - - - - # # # # # - - - - - - # # - - - - - - - - - - - -
 - - - - # # - # # # - - - - - - # # - - - - - - - - - - - -
 - - - # # - # # # - - - - - - - # # - - - - - - - - - - - -
 - - # # - - # # # - - - - - - - # # - - - - - - - - - - - -

In the above, what we've done is found all obstructions in the area, and rapidly or'ed in the obstruction masks into a single matrix. The result is all areas in the field of view, given the obstructions that are there, that we cannot see. Any mob in a cell marked "#" is invisible to us. That's an instantaneous lookup!

This matrix was created using bits of code like this:

Figure-3:

//    delegate( int[,] shadow )
//    {
//        shadow[0,0] |= 510;
//        shadow[1,0] |= 1022;
//        shadow[2,0] |= 1022;
//        shadow[3,0] |= 2046;
//        shadow[4,0] |= 2046;
//        shadow[5,0] |= 4094;
//        shadow[6,0] |= 4094;
//        shadow[7,0] |= 8190;
//        shadow[8,0] |= 8188;
//        shadow[9,0] |= 16368;
//        shadow[10,0] |= 16320;
//        shadow[11,0] |= 32512;
//        shadow[12,0] |= 31744;
//        shadow[13,0] |= 61440;
//        shadow[14,0] |= 16384;
//    },

In the above, we are using a system of anonymous delegates that record in effect a "compiled sprite" for the shadow. Compiled sprites are an old idea, from years back, when something similar was done in assembly to blit graphical sprites to the screen. Every ounce of performance counted back then, and so that's what they did. That's close to what I'm doing now, sans the (unnecessary) assembly.

Note how there is no unecessary code to stride through the matrix. In cases other than this, the strides aren't always by +1, and would require other bits of code to execute. This is avoided by using a code-generated set of commands for every possible obstruction in the field of view. This is very, very fast.

The last bit of optimization is the lookup. Here it is:

Figure-4:

//    delegate ( ulong[,] shadow )
//    {
//        if( ( shadow[13,0] & 16777216ul ) == 16777216ul ) return true; else return false;
//    },

Like with the shadow creator, this is a code-generated entity. There is a lookup for every possible cell position that tells me whether or not a cell in the matrix is obstructed.

An astute observer will note that the cost of establishing the mask is directly proportional to the number of obstructions, and has little indeed to do with the number of things being obstructed. This is true. The cost of establishing the mask is approximately 9 X the number of obstructions. This '9' is the average number of shadowmask commands in the generated code for a matrix of 37x37. The Figure 3 also happens to be (about) the worst case. That's a pretty good worst case!

The above figures describe the main idea of True LOS. In addition to the main ideas, there are a number of interesting optimizations attached. This is the main one:

The most notable optimization is a cache. The base world of UO doesn't change very much. That being the case, if a player has tried a LOS from particular location on the map, it is likely that future LOS attempts in the same location will produce the same results. It is further likely that other players will attempt to LOS from the same position. An MRU "most recently used" cache was developed that stores the most frequently used LOS matrices and reuses them. This further increases performance of the system by a good order of magnitude.

There are a few other optimizations related to runuo itself, which will mostly only be of interested to core developers. They are commented in the code, and I encourage you to take a peek if you're into this kind of stuff.

FREE SOFTWARE

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

INSTALLING

THIS IS A CORE MOD. PLEASE PAY ATTENTION!

Steps:

1. Make sure you have 2.0RC1 core source (although it appears it also works with recent SVN, you'll have to merge and not replace the files if you want this).
2. Extract the LOS zip file (somewhere).
3. Put the "LOS" subdirectory of the zip into the core source directory.
4. Find the files in the "Mods" directory of the zip. Replace your core files with these files (Map.cs, Mobile.cs). If any of yours are themselves modified, please note that the comment "// XXX LOS" is always next to a modification of these files, which are otherwise 2.0RC1 originals.
5. In your runtime Data directory, create a directory called "LOS". Copy the file "Config.xml" and put it in this directory. You may also wish to edit the config after you put it here.
6. Recompile your server and redeploy the excutable.

DONE. Your system is installed, and should work. Please let me know how it goes.

KNOWN DEFECTS, WORK IN PROGRESS, & PLANS

Reported and verified:

• There is a known issue where mobs aren't removed from view when doors close. The sprite remains in the last known position until the mob is seen again (or moves). NOT YET FIXED.

NO CRASHES FROM THIS SYSTEM HAVE BEEN REPORTED

I have some thoughts and ideas regarding players with high Detect Hidden skills perhaps getting the ability to escape the LOS system for a limited range, perhaps dependent on the Hide/Stealth skills of the target.

One user recommended that all players in a common party be able to see eachother. This is being considered.

C//

[Cheetah2003]

Wow this sounds cool, I'm going to try it out!

[Courageous]

Reload the zip in a second, it's missing some things....

(okay now the zip should be fixed;; sorry about that)

[Cheetah2003]

I have one suggestion, still havn't got it into my server yet, but it immediately came to mind.

Make it so it's appliable optionally on a per facet basis. So I could for example say, on Trammel, you get old style LOS, but on Felucca, you get this new style.

[Courageous]

Make it so it's appliable optionally on a per facet basis

Duly noted, and easily done (it so happens that the LOS system is already instanced for each map, I just have to do a little twiddling). I'll put this in the next round of updates, as users report in on their status.

C//

[Prohor Meletevich]

Is your LOS system the same like on OSI?

[Mideon]

Once again, a masterpiece, I'll be checking this out shortly. Thanks for the major contribution, I was waiting some time to see this puppy ;D

Thanks again!

[Liacs]

wow, this looks amazing...!

Thanks

Lia

[Cheetah2003]

Well, either I installed it wrong, or it has a really annoying problem.

When you walk around, stuff spams coming into view (Showing names of Incoming Mobiles.) Makes mobs walk in place, and just generally looks very bad. But it does seem to work.

Any thing you can do about this problem? Or did I mess up installing it?

[Irian]

You could try to add make a "Ready" animation (Animate(4, 3, 1, true, false, 0)) OnAosSingleClick. This should override the moving animation.

[Courageous]

Originally Posted by Cheetah2003

Well, either I installed it wrong, or it has a really annoying problem.

When you walk around, stuff spams coming into view (Showing names of Incoming Mobiles.) Makes mobs walk in place, and just generally looks very bad. But it does seem to work.

Any thing you can do about this problem? Or did I mess up installing it?

Hmmmmm. That's odd. I've never seen the problem you are talking about. Can you tell me how you produce it? Either I have some modification somewhere that I haven't patched you with, or you have a test case I haven't seen. My test shard doesn't have many mobiles in it. I take it yours does?

[I often test with PlayUO; a quick double check in the ordinary client ruled out a problem there]

C//

[Irian]

Isn't it the normal behavior, that a mobile (at least with a human body) that comes into view for the first time is display "walking"? Try placing a vendor and change your map. If you change it back, the vendor will be displayed with a part of the "walking" animation...

[Courageous]

I added maybe 15 vendors in a forrest, and walked around. It all looks good... as it is supposed to. Do I misunderstand something?

C//

[Irian]

I'm not not sure myself: Try to change the map. Then go back, so that all the vendors are sent to the client again. When I try this, all the vendors look like they are moving on the step for a short period of time...

[Courageous]

Hmm. But I can only change the map if I am Admin. If I am Admin, LOS ought not be working. How are you changing the map?

I can turn LOS on for Admin's to test this, but this is a rather odd test.

[addendum]

I *think* I see what's being referenced. If I run around a tree, the vendor is in the walking position. Isn't this the ordinary consequence of the MobileIncoming packet? I'm doing nothing unusual here, just either permitting or denying the server the ordinary code. Is this not the expected behavior?

C//

[Irian]

Yup, it is the expected behavior, but perhaps it looks more odd with TrueLOS... But as I said, with an animate directly in OnAOSSingleClick this should be solved.

[LordHogFred]

Hmm, would this be possible to incorporate into A_Li_Ns Completely Custom instead of required a recompile of the core?

[Courageous]

Hmm, would this be possible to incorporate into A_Li_Ns Completely Custom instead of required a recompile of the core?

There are certain sections of Mobile.cs and Map.cs that must be modified. The core recompile is easy, and the mods are prominently marked. Most of the code is in fact in the LOS directory.

Perhaps after some testing and validation by the community, I can make the system so that is configurable as "on or off". If I did this, perhaps it could be put into the core, as a configurable option.

C//

[LordHogFred]

Ok then, I'll compile an exe and give it a go.
I think it would be a brilliant idea to have an option for turning it on or off, plus it would probably be a good idea to allow staff members to not be affected by the LOS checks.

[Courageous]

Anyone above Player is unaffected (which means if you are an Admin or what not, you need a Staff Cloak or some such to see the system in action). Read the PlayerMobile.cs mod. You can temporarily disable a line there to make it so that Staff are affected if you'd like to test it that way.

That should work "correctly," which is to say a hidden staff member of higher level than another should stay hidden. And so forth.

Many of these defects were encountered during the alpha. The only known defect at this point is the one Cheetah is referring to. I didn't quite understand Cheetah's remarks regarding the all-names display, so I'm waiting on a screenshot.

Addendum:

During a code review comparing and contrasting Mobile.CanSee() to my new PlayerMobile.CanSee(), I see there are some minor details regarding hidden players and so forth that I need to attend to. Expect an update soon.

Further Addendum:

I believe I have replicated the described problem. If you quickly run in and out of LOS, all names can replicate, with "Jed the Baker" appearing several times above the mob's head and so forth. While the little stepping thing I regard as mostly unnoticeable, I see the duplicated name would be quite annoying. Looking into it.

C//

[Cheetah2003]

In your further addendum, Couragous, you describe what's happening on my server, but it doesnt matter if I lose line of sight or not, every step I take, the mob's name is shown AGAIN above it's head. I'll get you a screen shot in prolly an hour or two from this post. Have to go to work where my PC is.

I hope we can fix this, cuz this system ROXXORS!!