SA-MP Forums

Go Back   SA-MP Forums > SA-MP Scripting and Plugins > Scripting Help > Discussion

Reply
 
Thread Tools Display Modes
Old 04/09/2010, 01:04 AM   #1
Y_Less
Beta Tester
 
Y_Less's Avatar
 
Join Date: Jun 2008
Location: 629 - git.io/Y
Posts: 17,852
Reputation: 2477
Default How To Write The Best Streamer - Or, Streamer Discussion

Those of you who have seen my previous large posts may not realise that I often have many on the go at once, sometimes taking months of on and off work to write. Anyway, I am currently planning a new post on things to consider when writing streamers, especially object and icon streamers (as they can display multiple items at once). Now normally I just write my post and release it, but I thought I would try something new this time and ask for other peoples' input BEFORE posting the full thing.

There are currently three main sections:

Hooking - How to transparently hook both functions and callbacks so that users ONLY include a file. This includes hooking "CreateObject" and "CreatePlayerObject" so that you don't need any new syntax at all.

Control - This is mostly about the issues involved with objects in multiple scripts and how to solve these issues. Combining this with the previous section on hooking will allow you to download any random map filterscript, add a single line and load it, using existing streamers in other modes.

Algorithms - This is the big section and the one I'd most like input on. A streaming algorithm is WHAT your streamer does, the code is HOW this algorithm is "implemented". My main motivation behind this post was that I figured if other people understood the issues involved they would write better streamers and hopefully introduce a good competition in the market.
  • Most streamers (in fact, AFAIK, every one except YSI/Y_Objects) use the most basic algorithm there is - loop through all objects and show the closest ones. YSI uses a zoning algorithm - it finds which zone the user is in and loops through all the objects in that zone and the neighbouring zones to find the closest ones. The advantage of this is that objects on the far side of the world are not compared to the current player as there's no way they can be seen - this is the reason why YSI could do 1,000,000 objects and most others can only do 5000 (it took C++ plugins to beat YSI).

  • Adaptive timers - If a player is in an area with not many objects (you would need to use zones for this to know how many objects were in an area) then they don't need to be streamed as often, because the streamed objects will be over a wider area, it will take longer for a player to reach the edge of that area. So if a player is in a "sparse" area, stream objects for them less frequently, saving processing time.

  • Predictive streaming - Currently object streamers show the objects nearest the player's current location. I'm sure everyone has experienced problems with this in fast cars - you can literally fall off the edge of the world if the streamer isn't fast enough, and fast streamers require more CPU and bandwidth. We can get a player's current velocity, and we know when the timer will next be called (or called next for that player if using adaptive timers):

    Distance = Speed * Time

    The speed is the player's velocity and the time is the time till next streamer call, so we can APPROXIMATE where the player will be next call (assuming a straight line - which I *think* should be good enough given the difficulty of turning at high speeds and the low distance travelled at low speeds), given a distance and direction from current location. If we draw a line between these points (the current and predicted location) we can find the objects closest to this LINE and show those, doing it this way will mean that after half a second or a second of driving fast, you will still be in range of plenty of objects. You can even try get clever and search arcs in front of the player to account for turns etc.

  • Blocking - Given the higher number of objects now you could divide the world up into tiny squares (much smaller than in the zoning method) and just stream those. Objects are placed in groups according to location and those groups are streamed, individual objects are ignored. If you only put five objects in a block that still means a five fold increase in the number of objects you can stream, with very little effort.

  • Cities - This is a variation on the zoning method. If you only have objects in certain areas (for example the cities), yo ucan separate these areas and only stream the ones in a player's current area. Zones use neighbours because if you're near the edge of a zone you need to be able to see objects in the next zone too, city areas are a special case were groups of objects are very localised, so if you're on the edge of an area, you don't need to see objects in the next area as there's no other area near by. Note that this algorithm is very mode dependent, you can't really implement it in a generic streamer.

  • Intelligent reshow - Keep a track of say the last 500 MODELS shown to a player. When streaming objects to them, if there's an object they've not seen before slightly closer than an object in the cache (the list of models), show the seen object, not the new object. Hopefully if you do this the model will still be in memory in San Andreas, which will make it show up much faster, giving time in the next streamer call to possibly display the object model they've not seen before. Obviously you need to show some things they've never seen before or they will never see anything - if there's something new close by and something old far away, show the closer thing - determining the ratio, when to show close and when to show old, would require experimentation.

  • Size streaming - This is another thing I tried to implement in YSI. One issue with ONLY showing the closest objects is that they may be the wrong objects. If there's a flower 200 units away and a skyscraper 201 units away - which should you show? I streamed things based on a RATIO of view distance to real distance. If the skyscraper had a view distance of 400, it was about 50% of its view distance away, if the flower had a view distance of 50 (being a small object, it doesn't need to be seen from a long way away) it is 400% of its view distance away. Clearly in this case 50<400 - so we show the skyscraper, despite the fact that it is technically further away. I'm pretty sure ANY user would rather see a building than a plant (in terms of streamer response and view distance, they may think the flower looks better, but it's a detail, not a feature).

  • LOD speed - LOD = Level Of Detail. This is a combination of the "size streaming" and the "predictive streaming". If you're driving along fast, are you more likely to care about the road a way ahead, or the flower you're speeding past less than a meter away from you? This relies on very good view distance knowledge related to object size, but the idea is to use a sliding scale with speed, view distance and real distance. Lets go back to the skyscraper/flower example. If you're not moving, everything needs to show up and that's important. If you're going fast large distant items are more important, small items don't matter so much (don't forget the predictive streaming does things relative to a line, not a point). If the flower is 5 units away and the skyscraper 300 units away, then those are ratios of 10% and 75% respectively, so the flower gets shown. However, the higher your speed, the higher the CURVE of the ratio line (I don't know exactly how this would work having only just thought of it). Anyway, you're going MUCH faster and the flower is now 20 units away, with the building still 300 away - this gives ratios of 40% and 75%, which SHOULD still show the flower, however the curved scale gives greater weighting to the objects with the longer view distance, so again the building shows.

    Example curve:

    pawn Code:
    pow = (speed / 100) + 1; // Stopped = 1, 100 MPH = 2, 200 MPH = 3
    new_view_distance = old_view_distance ** pow; // ** = To the power of (floatpower)
    ratio = distance / new_view_distance;

    Using this code at 0 MPH (stopped) the flower will get 40% and the skyscraper will get 75% - showing the flower. At 100 MPH the flower will get 0.8% and the skyscraper will get 0.2% - showing the skyscraper instead. The net result is that only larger things get show at high speeds as they are more important and will be in view longer.

  • Multiple timers - Not really an algorithm, but you may decide that 5 timers, one every 200ms, each one doing one fifth of all players may be better (note that you will need to spread players evenly - don't do one for players 0-99 or the first 100 players to join the server will all be on the first timer while the others do nothing).

  • Teleportation - I know some people have this already, but when you use SetPlayerPos, restream instantly.

  • Linked objects - Another YSI feature. You could link objects together with offsets, so moving the parent moved the children as well, very good for moving and manipulating large object sets. You could also group them in streaming - if the parent is in range just assume all the children are and show them all (remembering that that will add more than 1 object to the visible list). Note to self: Update the list normally, but keep track of true number shown when running through the list.

If people can think of any other ways of getting better performance (or any other issues with streamers) please do post here! I may also add a section on implementation - YSI uses lists to keep track of the nearest objects, which I do think is the best way in terms of speed, but others may disagree.

This post was WAY more in depth than I intended, and I can still expand a LOT on all the points here - oops.
Y_Less is online now   Reply With Quote
Old 04/09/2010, 01:23 AM   #2
RoBo
Huge Clucker
 
RoBo's Avatar
 
Join Date: Jan 2008
Posts: 460
Reputation: 12
Default Re: How To Write The Best Streamer - Or, Streamer Discussion

Quote:
Originally Posted by Y_Less View Post
Multiple timers - Not really an algorithm, but you may decide that 5 timers, one every 200ms, each one doing one fifth of all players may be better (note that you will need to spread players evenly - don't do one for players 0-99 or the first 100 players to join the server will all be on the first timer while the others do nothing).
As with any pawn script, you need to return execution back to the server as soon as possible, it's considerably more important than how efficient the code is. If it takes 1ms to stream the objects for 1 player (a hell of a long time) * 100 and you have 100ms during which there be no sync. Compare this to using OnPlayerUpdate, even if it takes 5ms to stream the objects for that player, it would still be much better for the server lag-wise. In short, timers suck.

Quote:
Originally Posted by Y_Less View Post
If people can think of any other ways of getting better performance (or any other issues with streamers) please do post here!
Thread the streaming algorithm. Loop through all the players in a seperate thread and update the objects that need to be streamed in / out, then poll that thread from pawn and all it'll have to do it Create/DeletePlayerObject for any updated objects. It's harder than it sounds and thread synchronisation becomes a problem, but works well in the end.
RoBo is offline   Reply With Quote
Old 04/09/2010, 01:57 AM   #3
MrDeath537
High-roller
 
Join Date: Nov 2009
Location: Argentina
Posts: 2,082
Reputation: 29
Default Re: How To Write The Best Streamer - Or, Streamer Discussion

Excellent. Thanks you so much.
__________________
Trabajando en 3 includes, ny_INI, ny_XML y ny_Handling.
MrDeath537 is offline   Reply With Quote
Old 04/09/2010, 06:15 AM   #4
Incognito
Huge Clucker
 
Join Date: May 2006
Posts: 459
Reputation: 410
Default Re: How To Write The Best Streamer - Or, Streamer Discussion

Nice post!

The latest version of my streamer (as you're probably aware if you've checked the thread) uses a form of the "zoning algorithm" you described. My primary motivation behind this actually came from YSI, although our implementations are totally different. You can read up on the different methods of spatial partitioning (usually implemented in the form of a tree, although mine is not quite like that) if you want some more ideas.

Predictive streaming sounds interesting, although that would probably be quite expensive. I personally think the streamer should not make any assumptions beyond which objects should be created and which ones should be destroyed. Anything else is likely to just result in wasted CPU cycles, especially if it's something the mapper or server owner can customize to prevent from happening.

My method of ensuring that the closest objects are always shown (I think you gave this a couple of different names) checks if the internal object limit has been reached, and then destroys objects further away to make room for closer ones. This seems to work best, and it doesn't require any additional loops since every discovered object is already sorted by distance.

Here's the problem with threading (and something RoBo alluded to but didn't quite explain well enough): concurrency. Multithreaded code does not necessarily mean faster code. Eventually, you are going to need to implement some concurrency mechanisms like mutexes, semaphores, or condition variables in order to safely share data across threads and prevent race conditions. This may very well defeat the purpose of parallelizing a small bit of time-critical code. What will be gained if the main thread is blocked entirely while waiting to take ownership of some data that the other thread is using? Not much!
Incognito is offline   Reply With Quote
Old 04/09/2010, 08:07 AM   #5
RoBo
Huge Clucker
 
RoBo's Avatar
 
Join Date: Jan 2008
Posts: 460
Reputation: 12
Default Re: How To Write The Best Streamer - Or, Streamer Discussion

Quote:
Originally Posted by Incognito View Post
Multithreaded code does not necessarily mean faster code. Eventually, you are going to need to implement some concurrency mechanisms like mutexes, semaphores, or condition variables in order to safely share data across threads and prevent race conditions. This may very well defeat the purpose of parallelizing a small bit of time-critical code.
I seem to find that "pthread_mutex_lock" (unix) returns instantly provided that the secondary thread is running and not already locked - I haven't had much time to fiddle around with it tho.

Quote:
Originally Posted by Incognito View Post
What will be gained if the main thread is blocked entirely while waiting to take ownership of some data that the other thread is using? Not much!
I read that your new plugin can stream 1,000,000 objects in 2ms, assuming a server has 10,000 objects, 500 players and is updating the objects 3 times a second, it'll only end up using around 30ms/second of CPU time, practially nothing for an object streamer, so yes, there would be very little gained from threading it.

But if we look at a far more radical approach, 10,000 objects, 500 players, a streamer that streams the closest 400 objects to the player (basically xStreamer, doing away with draw distances totally), streaming objects each time OnPlayerUpdate is called we get something along the lines of 10,000*500*20 = 100,000,000 objects/second = 1,000,000 objects in 10ms, 10x slower than your current streamer, but considerably faster ingame and virtually no load on the main thread. Inefficient as hell, yes, laggy, no.
RoBo is offline   Reply With Quote
Old 04/09/2010, 10:32 AM   #6
Y_Less
Beta Tester
 
Y_Less's Avatar
 
Join Date: Jun 2008
Location: 629 - git.io/Y
Posts: 17,852
Reputation: 2477
Thumbs up Re: How To Write The Best Streamer - Or, Streamer Discussion

Arrgh - I just lost a huge post!

Anyway, threads are (relatively) quite slow - they're kernel functions and even if they return instantly in some cases, it's the other cases which are the issue. Additionally, your maths for the "extreme" case doesn't make sense. You argue that that requires 100,000,000 objects per second, which is true, but there's no reason why those objects take the full second to stream. If 10,000 objects takes 10us, that's only 100ms in every second, if they take 1ms to stream, that's 10s in every second - which is clearly impossible.

Alternate zoning algorithms are important, though I was really trying to look at higher level algorithms for streaming. Threading is also a very important consideration, I am trying to (slowly) write an advanced stremer using lock-free concurrent queues, which should mean good data access and no locks overhead.

Quote:
Originally Posted by Incognito View Post
The latest version of my streamer (as you're probably aware if you've checked the thread) uses a form of the "zoning algorithm" you described. My primary motivation behind this actually came from YSI, although our implementations are totally different. You can read up on the different methods of spatial partitioning (usually implemented in the form of a tree, although mine is not quite like that) if you want some more ideas.
I admit I've not been following version 2 of your plugin, I should probably do that!

Quote:
Originally Posted by Incognito View Post
Predictive streaming sounds interesting, although that would probably be quite expensive. I personally think the streamer should not make any assumptions beyond which objects should be created and which ones should be destroyed. Anything else is likely to just result in wasted CPU cycles, especially if it's something the mapper or server owner can customize to prevent from happening.
That is what it's doing, just in a different way (that's what algorithms are). Given a player's speed, there's a fairly limited set of areas where they can be in half a second or 200ms, because it's really not a lot of time on a human scale. However if they're going fast that limited set of locations could well be beyond the range of circles of objects - hence predictive streaming. I would argue that it is just deciding which objects to show, based on as much knowledge of the player as possible. The other algorithms, especially the LOD ones, are making more assumptions about what players would rather see, yes, but I still think they're valid. Also, it occurs to me that your direction can change VERY abruptly if you fall of something - though using g=9.8 units/s^2, you would only travel around 1.25 units in the half a second before the streamer updated, not very far and enough time for the stremer to adjust to your new vector. Unfortunately it would then do predictive streaming based on the next 1.25 units of movement, wheras you would infact move over 3.5 units in the next half a second (still actually tiny).

Quote:
Originally Posted by Incognito View Post
My method of ensuring that the closest objects are always shown (I think you gave this a couple of different names) checks if the internal object limit has been reached, and then destroys objects further away to make room for closer ones. This seems to work best, and it doesn't require any additional loops since every discovered object is already sorted by distance.
What do you mean by "destroy"? I do something similar, only I just remove the furthest item from a list to make room for the new item.
Y_Less is online now   Reply With Quote
Old 04/09/2010, 05:25 PM   #7
Incognito
Huge Clucker
 
Join Date: May 2006
Posts: 459
Reputation: 410
Default Re: How To Write The Best Streamer - Or, Streamer Discussion

Quote:
Originally Posted by RoBo View Post
I seem to find that "pthread_mutex_lock" (unix) returns instantly provided that the secondary thread is running and not already locked - I haven't had much time to fiddle around with it tho.
Yes, but what if the second thread owns the lock? The main thread will have to wait, which is the point!

Quote:
Originally Posted by Y_Less View Post
Threading is also a very important consideration, I am trying to (slowly) write an advanced stremer using lock-free concurrent queues, which should mean good data access and no locks overhead.
I thought about mentioning lock-free queues in my last post. That is probably the best way to do it.

Quote:
Originally Posted by Y_Less View Post
That is what it's doing, just in a different way (that's what algorithms are). Given a player's speed, there's a fairly limited set of areas where they can be in half a second or 200ms, because it's really not a lot of time on a human scale. However if they're going fast that limited set of locations could well be beyond the range of circles of objects - hence predictive streaming. I would argue that it is just deciding which objects to show, based on as much knowledge of the player as possible. The other algorithms, especially the LOD ones, are making more assumptions about what players would rather see, yes, but I still think they're valid. Also, it occurs to me that your direction can change VERY abruptly if you fall of something - though using g=9.8 units/s^2, you would only travel around 1.25 units in the half a second before the streamer updated, not very far and enough time for the stremer to adjust to your new vector. Unfortunately it would then do predictive streaming based on the next 1.25 units of movement, wheras you would infact move over 3.5 units in the next half a second (still actually tiny).
My point was that once you did perform those additional calculations, the streamer would still need to do what it normally does (i.e., stream the closest objects, but at an extrapolated player position). I suppose that if you had a very efficient algorithm it wouldn't make any difference, but you would still need to observe the results and profile your code very carefully.

Quote:
Originally Posted by Y_Less View Post
What do you mean by "destroy"? I do something similar, only I just remove the furthest item from a list to make room for the new item.
That is exactly what I mean. I remove the furthest one from a list and destroy it with DestroyPlayerObject so that the next call to CreatePlayerObject will not return INVALID_OBJECT_ID.

Last edited by Incognito; 05/09/2010 at 02:44 PM.
Incognito is offline   Reply With Quote
Old 04/09/2010, 11:50 PM   #8
Y_Less
Beta Tester
 
Y_Less's Avatar
 
Join Date: Jun 2008
Location: 629 - git.io/Y
Posts: 17,852
Reputation: 2477
Default Re: How To Write The Best Streamer - Or, Streamer Discussion

Yes it would require extra code, but any more advanced streamer would. If you write a better streamer, it may well be slower (though some of the algorithms there are designed to make them faster through more code) but the point is it's better. If you have a streamer which players will never drive off the edge of, and someone else doesn't - which do you think will be used? Too many streamers are the same thing coded by different people, with no improvements or advantages to any of them - I'm trying to show that innovation is possible.
Y_Less is online now   Reply With Quote
Old 05/09/2010, 03:57 PM   #9
Incognito
Huge Clucker
 
Join Date: May 2006
Posts: 459
Reputation: 410
Default Re: How To Write The Best Streamer - Or, Streamer Discussion

I don't disagree that it would be useful. It sounds like a very interesting idea, but I simply wanted to point out there may be some trade-offs involved (not just in terms of speed—you want your algorithm to produce meaningful results as well, otherwise it's totally worthless). Anyway, GetPlayerVelocity and GetVehicleVelocity would probably help quite a bit here. That saves you from having to calculate it yourself, so all that you really need is the average time between updates to get a reasonably accurate projection of where the player will be in the near future. This will probably be most noticeable if the player is driving in a fast car.
Incognito is offline   Reply With Quote
Old 05/09/2010, 05:15 PM   #10
Donny_k
High-roller
 
Donny_k's Avatar
 
Join Date: May 2006
Posts: 1,066
Reputation: 4
Default Re: How To Write The Best Streamer - Or, Streamer Discussion

I no longer script Pawn so I'm not upto scratch with the latest streamers and stuff but something I always noticed was that they never consided the players view point, it was just a radius check but if I'm off the object and it's behind me (out of view) then no matter if it's in my area or not it doesn't need streaming because I can't see it/use it.

Also hidden objects like:

& << me
--- << wall
& << object

I can't see it as the wall object blocks it from my view so why stream it if it's not the ground or whatever even if it is in my radius ?

It's extra checks but less streaming so I don't know the pros and cons, just a thought.

PS. sorry if you mentioned this already and I missed it.
__________________
We don't stop playing because we grow old, we grow old because we stop playing.
Donny_k is offline   Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[Include] [INC] TSS - tAxI's Streamer Systems: full Streamer + HOUSING SYSTEM Utillity cptnsausage Includes 101 24/08/2012 12:05 AM
Need 3dtextlabel Streamer And Gangzone Streamer !! Please Help . Not streamer plugin . jame42 Scripting Help 4 30/05/2012 07:33 AM
[Include] [INC]YCP - Yaheli's Checkpoint Streamer - OnPlayerUpdate CP Streamer! Yaheli_Faro Includes 46 20/04/2010 02:53 PM
Dominator's Object Streamer - a wize and new streamer - invisible objects fix tsha Filterscripts 23 19/09/2009 08:37 PM
Object Streamer - Looking for a little streamer! ~300 obj. BeCometA Help Archive 1 26/06/2009 05:47 PM


All times are GMT. The time now is 07:37 AM.


Powered by vBulletin® Version 3.8.6
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.