Real Line Of Sight!

[Dzenn]

Hallo,

Some days ago saw something in one shard that shocked me up! I was a "real" line of sight! Working! I mean - when you step into a room you don't see anyone outside! You walk out - and there they are! You don't see around the corner, but you can see through a window!

Now, I know the guy who did it. He's like "I'm the best programmer there is! I'm the first to did this! Noone else but me! Muhahaahah!". Needles to say he don't like to share . Even if that's only worth something in a RP shard and his is not one.

I'm not a good scripter, hell I'm not even an average scripter. I just mess with things and hope the best . But I'm gona try and do this if I can. At least now I know it can be done. In fact, the guy did it in one day, so I gues for someone with experience it's not a big deal. And I know there are lot of experianced guys in here, so I'm askin for your help.

By the way if you like to see how it works - IP: 217.30.220.10,2593 auto accounting is on (this is not an ad, I don't even like the shard).

The thing is - this can't be done without changeing the core. So I gues not many people would know how to go about it. But this is a chalenge and I hope there are some skillful programmers that will take it. Or at least help me do it. All I know is that it's worth the effort. And I would sure like to see this as part of the original core. Maybe optional?

So far I've found some code in Mobile.cs, that may have something to do with it:

		public bool InLOS( Mobile target )
		{
			if ( m_Deleted || m_Map == null )
				return false;
			else if ( target == this || m_AccessLevel > AccessLevel.Player )
				return true;

			return m_Map.LineOfSight( this, target );
		}

		public virtual bool CanSee( object o )
		{
			if ( o is Item )
			{
				return CanSee( (Item) o );
			}
			else if ( o is Mobile )
			{
				return CanSee( (Mobile) o );
			}
			else
			{
				return true;
			}
		}

Please help!

P.S. I just thought of something - isn't that guy required to share anything he made from the original source under the GPL terms?

[Courageous]

P.S. I just thought of something - isn't that guy required to share anything he made from the original source under the GPL terms?

No. He's not.

This does look like an interesting problem though. I have a shadow-matrix optimization that I wrote for rapid line of site caculations a while back. I should see if I can find this.

Be advised that repeated LOS checks are pretty expensive. I'd guess that it could slow down a server that was servicing a large number of players.

C//

[Dzenn]

Well this is great for the roleplaying (anti-metagameing) and is definately worth the system resourses. And from what I can see, it works like a charm in that shard. The feeling is great. *sigh* I think thats one of the most impresive and significant mods I've ever seen. My hope is that someone with indepth knowledge of the core takes a look and figures it out. Even better - if the devs decide to include this in the base package, it would be just sweet.

Some more info that could be useful - there's some m_VisList in the scripts (not the core scripts), but I can't tell much about it. Could this be something like what the [vis command does for the GMs? A list of who can see you and who can not? Or list of who you can see?

P.S. Did I post this thread in the right section of the forum?

[WarAngel]

VisList for GMs is simply for them to determine who can and cannot see them while they are hidden. If you want a certain player to see you, but not another, you could just [vis that certain player.

[Dzenn]

Yes, I know that. My idea was since it seems that every PlayerMobile has that sort of list, is it posible to make this principle universal and automatic, with a check based on InLOS or CanSee? I'm just makein a wild gues.

[WarAngel]

You could probably look at the code for VisList for an idea on how to hide and show mobiles, and use that as a base for the system.

[XxSP1DERxX]

if you check the Core where the CanSee check determines if you see the person (packet is sent or not), there is a check for LOS also, but the packet is still sent. He just modified the LOS to be with the CanSee check, thats all.

Its just a slight movement of code in the core actually. I personally do not like this style of gameplay (I have debated it) because its not fair for strategy, and this is an bird-eye's view game (to a degree).

[Dzenn]

I just reached the same conclusion . But I did it the hard way - through the visibilitylist, the packethandler and what not . Hope it works!


I don't know if it's fair, but what in this world is? It is realistic and it's fun. That's enough for me.

Edit: Actualy, when I think about it, it's quite the oposite. It's unfair to be able to see someone when you could not posibly do so. Even from a bird's eye perspective you shouldn't be able to see someone in a building, right? I think this whole thing should be considered a "bug".

[Courageous]

I'll volunteer to put an efficient LOS algorithm as a core option after I finish my Map.cs tests and changes. This may be as long as month.

I think it likely that the RunUO core team would accept a LOS module as long as it were fast, configurable (could be turned on or off), and touched relatively few internal points in the code (i.e., where it is inserted is easily noticed and understood).

While LOS algorithms can be expensive, I can see the potential for an interesting intersection between LOS algorithm cost and savings from removing IO overhead due to not sending unseen packets to the various clients. I'm not thinking there's likely much there (origin didn't do it), but it's something worth looking into.

C//

[DaLaw66]

Is it just me or, doesnt it work with 2D?
Also, that shard is lagging like hell, to say the least

[Courageous]

It's not a bug, it's a design decision to avoid the functionality in exchange for increased performance. LOS checks are extraordinarily expensive: in the worst case you have to trace rays from the origin to the extent of the visibility range, to every cell in the possible visibility matrix. With a server with many players, all of them calculating LOS every time they move, performance will go to hell in a hand basket.

There is an optimized technique for LOS using shadow matrices, but this still involves hundreds of instructions every time the player mobile moves.

I'll look into this for fun after my map.cs mods are complete. But I'm thinking that the core team left it out for good reason, and that even if I manage a highly optimized implementation, only shards with small player bases and hefty hardware will be able to make any real use out of it.

C//

[Courageous]

Okay. So. Since my Quad Tree attempts turned out so fruitlessly, I've been working on LOS as I've promised.

I have systematically built up a shadowmask generator, taken from some well-documented ideas published by the fellow Amit, who is "famous" to us computer game programmer wannabes. Obligatory plug:

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

So what the shadowmask does for us is, given a maximum range for line of site calculations, is to precalculate all regions in a matrix that would be shadowed for every possible obstruction. Each matrix ends up being a sort of "shadow" cast by each obstruction for that position. Here's a text based example:

//  Obstruction at elem[14][16]:
 {{-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,#},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,#},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,#,#},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,#,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,#,#,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,#,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,#,#,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,#,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,#,#,#,#,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,X,#,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,O,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-},
  {-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-}},

So now that we can have a prefab "shadow" for each obstruction, the trick is to "merge" each shadow matrix together for each obstruction, forming a single unified shadow array that you can then use to test to see whether or not target objects are visible to the player. That may appear expensive (and it is), but there's more at work here.

The next trick is to compress the fact each shadow down to bits in a byte. Basically, we'll use bit positions, 0 or 1, as if they are booleans. The compression down to bits produces something more like this:

 {{ 510 },
  { 1022 },
  { 1022 },
  { 2046 },
  { 2046 },
  { 4094 },
  { 4094 },
  { 8190 },
  { 8188 },
  { 16368 },
  { 16320 },
  { 32512 },
  { 31744 },
  { 61440 },
  { 16384 },
  { 0 },
  { 0 },
  { 0 },
  { 0 },
  { 0 },
  { 0 },
  { 0 },
  { 0 },
  { 0 },
  { 0 },
  { 0 },
  { 0 },
  { 0 },
  { 0 },
  { 0 },
  { 0 }},

And then, the final evil trick in the bag of tricks. Borrowing from the idea of a "compiled sprite," this trick that game programmers did aeons ago when they needed to squeeze every last cycle out of weak dos boxes, we can do this:

//  for an occlusion at [16,14]:
    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;
    },

This last trick lets us avoid probing array elements we don't care about. We can just probe a matrix, which contains a delegate, that only processes in the shadow fields for that obstruction. This is a very efficient... probably there is no more efficient process for doing aggregated shadow testing.

So. I'm done with the LOS calculator for "true line of sight" and am now looking at integrating into RunUO. I can't say that this system will be fast enough for servers with large numbers of players. What I can say is that I don't think you're going to find any better if you want something like this.

More atcha in a while...

C//

[Mideon]

Excellent work Courageous! I can't wait to see how it performs...with all those evil tricks, it might just do better than I thought was possible :P

Keep up the good work, this topic is a very interesting one. I tried the shard posted previously...but it's super laggy..I'm assuming due to the LOS checks. I'm curious to see how this new method performs.

[Pyro-Tech]

this is awesome.....would be great to see how it works

kudos couragoues

[MeddeMarigald]

Very nice!

Im eager to see this!

One nb question, if we use that option in razor that show player names or incoming players does it spoil the surprise?


I always thought this omniscient point of view spoiled the suspension of disbelief =S

lets wait and enjoy, thank Courageous for putting yer talents at this task =D

[Courageous]

You won't see incoming, they're gone. The system is almost done, but do understand that it's experimental. Also, you won't be able to use it until, either: RunUO2.0 comes out, or you switch to DOTNET 2.0 (this implies a core recompile). Not a big deal, actually. But that's how it is. As such, it's going to be released to the public but "for developers only". Nothing to keep you from playing with it, and I'll look into all problems found, but caveat emptor.

It has a few limitations. These 'true' LOS checks are limited to a range of 15 from the player, for example. And they only work on player mobiles. Base creatures use the more ordinary LOS rules.

I'm knee deep in optimizations at the moment. Not sure when it will be ready. Maybe a couple of weeks.

C//

[xir]

Have you considered slurping up the relevant information in the tiledata into memory, it would probably make lookups faster. Are you writting the algorithm to cater for dynamic (moving) obstructions or just static ones? If it is only static you could probably cache the results of LOS calculations since the viewpoint is more or less the same for each tile for each character? How much memory would it take (compressed) to store say 100 LOS calculations? One could always store precalculated results in memory for the populated areas on the server (i.e. Britain bank.)

[Courageous]

You're thinking in exactly the sort of way a good optimizer does. Alas, the situation is worse than you think. Remember, LOS is perspective- dependent. What you are talking about is one pre-stored perspective 31x31 for each and every x,y location on the map. I did the math; not counting cruft, it's maybe 250 megabytes on map0 to do that.

And yes, I'm only doing it for stuff that doesn't move around. In fact, I haven't yet even hooked up code that makes it work 'right' when someone drops a house down (you need to mark the LOS matrix 'dirty', a single line of code).

C//

[Courageous]

Okay. I have the core of the system working now, and am ironing out some technical errata. One of those errata is that, when I kill a mobile, it dies, and drops to the ground, but also leaves a sort of "ghost," a sprite that sits there and fidgets, but has no health, nor can it be [prop'ed. I have validated that RemovePacket is actually sent, so this is all the more strange.

I'm wondering if there is something I need to know about MobileIncoming MobileUpdate and RemovePacket?

This is a wierd behavior.

Other than this odd behavior, everything is working. Anyway, I'll keep on truckin'...

C//

[milt]

Hmm, now that you say that, I can remember this one time when I killed my friend, something of the same sort happened. The only thing was, we do not beleive that it was caused by a script. But what happened was, I killed him and his ghost was still there even after I resed him. I could not props the ghost, nor do anything with it... it just stood there. I used to have some screen shots but I'm afraid they are long gone.

No idea how we caused this, but I hope you get it fixed somehow

[Courageous]

Mentioned issue is associated with a MobileIncoming packet being sent after the RemovePacket. I've resolved that.

Progress Report

The LOS system is now working quite effectively under test. I've had a variety of false starts along the way, and finally have recently turned the corner. I still don't have a good estimate of the size shard that the system will support yet, because the recent optimizations I've put in are statistical in nature, and I haven't collected the facts from a real shard. Here's the scoop.

First, generating a LOS matrix is, on average, cheaper than actually doing just one Map.LineOfSight() test. In addition to the matrix creation being faster, once the matrix is created, it is nearly "infinitely" faster to calculate LOS with the matrix than with the old LOS algorithm. This is relevant. When you are lossing from a current location, you're quite likely to be doing it more than once if there are multiple mobiles and items in range, which there most often are. In this sense, this LOS system is about double the speed of the old for just one LOS check, but then goes up in performance linearly with the number of mobiles and items checked. IOW, if you check for 23 mobiles and items, the system is about 24X faster than the old one.

In any case, what this means tis hat this system, without any further modification, would be better for "true line of sight" than the standard algorithm (which is a line drawing algorithm, based on Bresenham's original line algorithm), without any further enhancments.

And it gets better, because there are enhancements.

Since establishing the matrices and protocol hooks, I've experimented with many optimizations. The thing that seems to work is a cache of the MRU variety (keep most recently used), sized according to the size of the map. For example, keep maybe the 250,000 most recently used posiitions on the map in a cache. There are some complexities to this cache; simply put: not all information about the world can be cached, for example non static items and what not, plus new houses that might be placed at runtime and so forth.

Now here's where the unknown comes in. I really don't know how often I'm likely to have cache hits in a server. It's probably true--probably very true--that the vast majority fo the player base is visiting no more than 5% of the map regularly. But I really don't know what the figures are, so I am just guessing here. My guess: we'll have very, very high hit rates. And high hit rates means "almost free LOS". So that's pretty exciting.

Things are moving along. It's been... more complicated than I anticipated. But things are looking quite good here. While I am not promising anything, there's some chance that this system might actually be usable on a large shard. That remains to be seen.

More soon.

I'm thinking it's about maybe two weeks before I'll start looking for alpha testers. This will require a core recompile, using DOTNET 2.0.

C//

[Courageous]

"TRUE" LOS ALPHA RELEASE:

http://www.runuo.com/forums/showthre...710#post477710