Courageous
Wanderer
Courageous True Line of Sight
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.
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:
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:
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:
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:
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:
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:
KNOWN DEFECTS, WORK IN PROGRESS, & PLANS
Reported and verified:
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//
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.
- 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 ).
- 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.
- 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:
Code:
[FONT=Courier New]_____________A_
|
|___________________B____________[/FONT]Now note the subtle change in the arrangement below:
Code:
[FONT=Courier New]______________A
|
|___________________B____________[/FONT]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:
Code:
// {{-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,#},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,#},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,#,#},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,#,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,X,#,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,O,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
// {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-}},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:
Code:
# # # # # # # # - - - - - - - - # # - - - - - - - - - - - -
# # # # # # # # # - - - - - - - # # - - - - - - - - - - - -
# # # # - # # # - - - - - - - - # # - - - - - - - - - - - -
# # # # # # # # # - - - - - - - # # - - - - - - - - - - - #
# # # # # # # # - - - - - - - - # # - - - - - - - - - - # #
# # # # # # # # # - - - - - - - - - - - - - - - - - # # # #
# # # # # # # # - - - - - - - - - - - - - - - - - # # # # -
# # # # # # # # # - - - - - - - - - - - - - - - # # # - - -
# # # # # # # # - - - - - - - - - - - - - - - # # # - - - #
# # # # # # # # - - - - - - - - - - - - - - # # # - - # # #
# # # # # # # # - - - - - - - - - - - - - # # - - # # # # -
# # # # # # # # - - - - - - - - - - - - - # - - - # # - - -
# # # # # - # # - - - - - - - - - - - - - - - - - - - - - -
# # # # # # # # - - - - - - - - - - - - - - - - - - - - - -
- - # # # # # # - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - # # # -
- - - - - - - - - - - - - - - - - - - - - - - - - - # # # #
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - # - - - - - - - - - - - - - - - - - - - - - - - - - #
- # # # - - - - - - - # # - - - - - - - - - - - - - - - - #
# # - - - - - - - - # # - - - - - - - - - - - - - - - - - -
- - - # - - - - - # # # - - - - - - - - - - - - - - - - - #
- - # # - - - # # # # - - - - - # # - - - - - - - - - - - #
- # # - - - # # # # # - - - - - # # - - - - - - - - - - - -
# - - - - # # # # # - - - - - - # # - - - - - - - - - - - -
- - - - # # - # # # - - - - - - # # - - - - - - - - - - - -
- - - # # - # # # - - - - - - - # # - - - - - - - - - - - -
- - # # - - # # # - - - - - - - # # - - - - - - - - - - - -This matrix was created using bits of code like this:
Figure-3:
Code:
// 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;
// },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:
Code:
// delegate ( ulong[,] shadow )
// {
// if( ( shadow[13,0] & 16777216ul ) == 16777216ul ) return true; else return false;
// },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:
- 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).
- Extract the LOS zip file (somewhere).
- Put the "LOS" subdirectory of the zip into the core source directory.
- 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.
- 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.
- Recompile your server and redeploy the excutable.
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.
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//
