Log in to reply
 

[Tip/Code] Optimised GetNearbyVehicles/Ped process



  • One of the last comments I got on my Helicopter Effects mod before I had my hiatus, was that the impact on performance was excessive. I knew that the probable cause of that was the World.GetNearbyVehicles() function and the subsequent processing. To that end I had two choices, reduce the range, or find an alternative. Over the course of several days, I developed my alternative, which I am going to share here in case anyone finds it useful. I use it for vehicles but it can work for any entities, Peds, Vehicles or Props.

    As you all know, the World.GetNearbyVehicles() function just gathers up everything it finds and you then have to filter out the stuff you don't need. You basically have this as your collection pattern.

    0_1483624148857_collection-ring.png
    Over a decent range, that can result in a huge number of entities.

    So that got me thinking about flowers, and the thought about how their overlapping petals were arranged. That led me to this idea...

    0_1483624250950_collection-pattern.png

    What you have, is a number of smaller zones, that are collected over a period of time, then sequentially processed... also over a period of time. You can see by the comparison on the right how much smaller the collection zone is but you can also see on the left, that the overall collection area is the same. The overlaps, whilst they might seem like a bad idea, are very good for catching anything slipping from zone to zone. You could probably reduce the zones to 5 and just about get away with it.

    So the way it works, is that on any given frame, the mod creates a zone at one of the locations (after creating this image, I did realise my collection pattern could be better but this matches the code I will post, so it will do for the example). So all vehicles in that zone are collected and added to a List<Vehicle>. In the mod you define a check rate and this is the number of frames the processing will occur over, in my Random Dirty Cars mod, it's set to 4. The code gets the total number of vehicles that have been collected, divides them by the check rate figure and this gives you the number of vehicles that will be processed in a single frame.

    So for example, if you collected 100 vehicles, you would only in fact be processing 25 per frame. If the number of vehicles collected is smaller than the check rate figure (i.e. less than 4 in my cars mod), it processes them all at once. Anything greater than that figure, gets spread across several frames, even if it just results in 1 per frame. If no vehicles are collected, then the zone moves on and another collection is performed on the next frame. The aim was to try and maintain consistency of performance, rather than isolated boosts.

    So what does this actually look like in the game? Well it just so happens that after adding a radius display to my debugging classes, I can demonstrate that. The yellow circle is the ring the zone origin points are all located on, the cyan circles are the collection zones.

    Does it work I hear you ask? To give you an idea, using just my helicopter effects mod in certain situations was resulting in up to a 10fps loss... I couldn't believe it until I checked it myself... and I have two mods using the same system. :( This video shows the FPS figure with neither mod running, just my helicopter effects mod and then the dirty cars mod as well. The figure in the top left (which isn't very clear) is always in the 80+ region, no matter how many of the mods are running. This was the proverbial proof in the pudding so to speak.

    In the next comment, I will be posting the full code for this process, so that anyone who wants it, can use it.



  • Okay, so here's part 2 which contains all the code required for this to work.

    Variables:

    private List<Vehicle> CollectedVehicles = new List<Vehicle>();
    private int CollectedVehicleCount;
    private int CollectedVehicleSplit;
    private Vehicle LastPlayerVehicle;
    		
    private int CheckRate;
    private int CheckRateCounter;
    private int CheckZone;
    private float CheckRadius;
    private float[] CheckAngles = new float[] { 0, 120, 240, 60, 180, 300 };
    

    Initialise()

    private void Initialise()
    {
    	CheckZone = 0;
    	CheckRadius = MaxSearchRange / 2;
    	CheckRate = 4;
    	CheckRateCounter = 0;
    }
    

    Edit: I have just realised something I didn't explain in this code snippet above. In the ini file I define the search range (MaxSearchRange), which is defined as the range you want to check from the player's locations. In the code I halve that because the radius is measured from the centre to the edge of each zone and the origin point is already halfway across that range. So a search range in the ini of 100, equates to a radius of 50 in the collection process.

    onTick()

    private void onTick(object sender, EventArgs e)
    {
    	// If we have collected some vehicles, process them
    	if (CollectedVehicleCount > 0)
    	{
    		ProcessCollectedVehicles();
    	}
    	else
    	{
    		// If we have no vehicles to process, try collecting some new ones... this can only run when there are no existing vehicles waiting to be processed
    		CollectVehicles();
    	}
    }
    

    CollectVehicles()

    private void CollectVehicles()
    {
    	// Clear the collected vehicles list
    	CollectedVehicles.Clear();
    
    	// Get the required angle from the array
    	float _angle = CheckAngles[CheckZone];
    	
    	// Create an origin point for the collection zone, that is rotated by the fixed angle, at a distance equal to the checking radius, using the player X and Y as an origin point
    	// Basically a simple rotate a point through an angle calculation
    	double xx = (CheckRadius * Math.Sin(Deg2Rad(_angle))) + Game.Player.Character.Position.X;
    	double yy = (CheckRadius * Math.Cos(Deg2Rad(_angle))) + Game.Player.Character.Position.Y;
    
    	// Create the final origin
    	ZoneLocation = new Vector3((float)xx, (float)yy, Game.Player.Character.Position.Z);
    	
    	// Collect the vehicles within the check radius range from that origin
    	CollectedVehicles.AddRange(World.GetNearbyVehicles(ZoneLocation, CheckRadius));
    
    	// Move onto the next zone for the next time round, wrapping at the last checkangle
            CheckZone = (CheckZone + 1) % CheckAngles.Length;
    
    	// Check the player's vehicle every time, just to make sure we're not dealing with a vehicle already
    	// being sat in, after a scripts reset
    	if (Game.Player.Character.IsInVehicle() && Game.Player.Character.CurrentVehicle != LastPlayerVehicle)
    	{
    		CollectedVehicles.Add(Game.Player.Character.CurrentVehicle);
    		LastPlayerVehicle = Game.Player.Character.CurrentVehicle;
    	}
    
    	// Store the number of vehicles found
    	CollectedVehicleCount = CollectedVehicles.Count;
    	
    	// Create a split number based on the total vehicles found, divided by the check rate
    	CollectedVehicleSplit = CollectedVehicleCount / CheckRate;
    }
    

    and finally, ProcessCollectedVehicles()

    private void ProcessCollectedVehicles()
    {
    	// _minRange will be the first vehicle collected this time round
    	int _minRange = CheckRateCounter * CollectedVehicleSplit;
    	int _maxRange = 0;
    	bool _endOfCollection = false;
    
    	// If we are on the last segment of the list, or we don't have enough to vehicles to cause a split...
    	if (CheckRateCounter == CheckRate - 1 || CollectedVehicleSplit == 0)
    	{
    		// Set the max range value to the end of the list and set the end of collection flag
    		_maxRange = CollectedVehicles.Count;
    		_endOfCollection = true;
    	}
    	else
    	{
    		// otherwise set the max range to be the min range plus the split number
    		_maxRange = _minRange + CollectedVehicleSplit;
    	}
    
    	// Go through each vehicle in turn
    	for (int i = _minRange; i < _maxRange; i++)
    	{
    		Vehicle _veh = CollectedVehicles[i];
    		// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
    		// Do any processing code here...
    		// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
    	}
    
    	// Increment the check rate counter
    	CheckRateCounter++;
    
    	// If we have processed all the vehicles, clear the vehicle counter and the check rate counter, so a new set of vehicles can be collected
    	if (_endOfCollection)
    	{
    		CollectedVehicleCount = 0;
    		CheckRateCounter = 0;
    	}
    }
    


  • I don't know if anyone else will find any of that useful, or you may even have a better system... I just thought it was worth posting as it made a huge difference to how my mod runs.

    I know this code does seem very literal and I should use modulo but for some reason, I can never get modulo to work properly, so I have to go with literal.

    Stupid mistake that I eventually fixed. :blush:



  • @LeeC2202 good to see u back buddy!


  • MODERATOR

    @LeeC2202 So it goes through each zone and processes the entities in the list, then moves on to the next zone which is calculated using angles from the origin point? Amazing. Assigning tasks to peds in a large radius is one example where this would be very helpful. Thank you, and welcome back!



  • @stillhere said in [Tip/Code] Optimised GetNearbyVehicles/Ped process:

    So it goes through each zone and processes the entities in the list, then moves on to the next zone which is calculated using angles from the origin point?

    Yeah, that's pretty much it in a nutshell. It's pretty much like sending out 6 recon drones with their own area to report back on. It allows you to reach that bit further out into the distance, without carrying the overhead of suddenly trying to grab a massive area of entities.

    My original idea had the zone points pushed slightly further out, with a final zone located at the player's location to fill in the hole in the middle. Where this will prove less than ideal, is if you really need all that data right now, so to speak.

    This works perfectly for my mods because everything is collected at the limit of your vision, they have no immediate requirement. Because of the way it works, you can also dynamically control the collection rates and radius values to adapt it to different situations.

    Define a set of structs, something like this:

    struct ZoneCollectionDef
    {
        public float ZoneRadius;
        public int ZoneCheckRate;
        public float[] CheckAngles;
    }
    

    ...and you can store a collection of definitions that you can switch in or out as required. Make sets that only collect in a pattern in front of the player, or both sides etc...

    And on a plus side, it makes pretty patterns on the ground at night when I have my debug classes running. :D It's like watching a Spirograph.

    Edit: In case anyone is wondering what the better pattern for this should have been, it's this:

    private float[] CheckAngles = new float[] { 0, 120, 300, 180, 60, 240 };

    That more evenly spreads the collection around the whole perimeter.


  • MODERATOR

    @LeeC2202 Does this work solely when the origin is an entity? I guess what I'm asking is if the angles are determined by the rotation of the entity, ex: an angle of 90 is on the right of the entity. Or are the angles based on world coords?



  • @stillhere The angles are purely world based. The origin point of the whole collection can be any location and the angles (and distances) simply work relative to that.

    I do have additional code that could be used to make the angles relative to an entity's rotation, it's the same code that I use for the probes in my camera and helicopter mods. Saying that, you could just add the player's rotation onto the _angle in double xx = (CheckRadius * Math.Sin(Deg2Rad(_angle))) + Game.Player.Character.Position.X; and that should do it anyway. The other code I am thinking of handles rotating an elliptical orbit on a secondary rotation, which this doesn't need.

    I think this might be useful as well, seeing as the code calls it: :blush:

    protected float Deg2Rad(float _deg)
    {
        double Radian = (_deg * Math.PI / 180);
        return (float)Radian;
    }
    

  • MODERATOR

    @LeeC2202 I see, thank you. You say you are not good at math, but I disagree :grin:
    I have another question but it is not related to the topic, so I will write you a private message!



  • @stillhere One thing I would say though, is making it follow the rotation of the player will compromise the collection process. Consider the scenario where a collection has just occurred and caught 5 entities. During the next 4 frames, you rotate by a certain amount that then places the next collection point in the same place as the last collection occurred... you just collect the same 5 entities and completely miss a zone.

    So yes it is possible, but I would advise that it may cause more problems than it might appear to solve... so be wary of the consequences.

    I am okay with maths as long as I am purely dealing with numbers. I am pretty good with using numbers to solve problems but hopeless at using formulas to do the same things. I have to get creative with using values to achieve something. The zooming during the melee camera on my camera mod is a prime example. I am sure there is a way to calculate an exponential curve that matches the distance between two positions, with an FOV value that keeps an object within the screen boundaries. I have read and read and read, page after page on exponential curves and nothing sinks in. So I had to resort to this.

    float _meleeDistance = World.GetDistance(Position, Target);
    ProbeFOV = Math.Max(65f - (_meleeDistance / .15f), 14f);
    

    And I can literally spend hours tweaking values to get it as close as I can. I hate that zoom though because when it zooms in, it comes to a jarring halt, it's not adaptive enough. But I can't retain enough information, to make it work like I need it to work. Even just last week I tried again and failed, because I had added a new delayed-zoom camera. I have to settle for second best and hope that it is good enough for the job. :(

    I can think like a programmer, but I write code like an artist. :blush: I just enjoy coding too much to not do it.


  • MODERATOR

    @LeeC2202 Yes I realized that too; there wouldn't be much point to do it that way. I'm not sure why I asked in the first place haha.

    You seem to have a good understanding of what kind of mathematical calculation you need to achieve whatever you are looking for. I'm sure many people would be lost without a formula to follow; you just skip that formula and do it!



  • @stillhere There are situations where it could work, so it was definitely a valid question to ask. You could cut the zones down to 4, set them at 90 degree angles, collect from all 4 zones in rapid succession (even in a single frame) and then process them after collecting all 4 over a sequence of 4 frames.

    You could even collect each zone into its own list and you would know exactly where each entity is relative to the player, simply by which list it was in.


  • MODERATOR

    @LeeC2202 Ah you are right. I've had a similar situation where I needed to get the front/back/sides of a vehicles, but I ended up running four separate GetNearby functions manually. Your optimised code would have definitely helped :sweat_smile:



  • @LeeC2202 I was trying to using your optimised code. But i got alot of errors. Alof of things that are not defined. Can you upload it?



  • @MrGTAmodsgerman That's not a complete mod, it's a set of variables and functions. You need to incorporate that into your own mod template for it to work.

    You have to already have your class defined, the contructor built, all the required using statements etc... already in place.

    I can probably upload a complete mod with it all in but you'd just end up having to pull out the same parts to put it into your own mod. I just presumed that posting it like that, would be easier for people to incorporate into something they already had as a partial mod.

    I always build my mods on Visual Studio templates that have all the skeleton code already in place, so that would just drop into the relevant sections of the template and simply work. I can provide a full mod-base but I would need a bit of time to put it together as my ongoing mod is eating up most of my time. Let me know if that's what you need.



  • @LeeC2202 I only looking for a performence stable method to get ally nearby vehicles.



  • I love seeing people being concerned about performance. Great method to get an updated list of the existing vehicles.

    I usually use World.GetNearbyWhatever() so I'm probably guilty of some frame killing in the player's game, I'll probably try to implement this system next time. Didn't know it was so resource-intensive!

    (However I make most of my scripts run every 500ms rather than OnTick(), to give the CPU time to recover)



  • @Eddlm It's something I've always been conscious of, ever since the days we would try and cram small routines into zero page on a Commodore 64, because it was the fastest 256 bytes of memory in the system... you just couldn't do that much with 256 bytes though. :)

    I think there are two approaches, either spread the load, or spread the frequency of collecting that load. All the mods I have done up to now have required me to use the former method for one reason or another. In an ideal world, I would combine the two mods that need this into one, so only one collection takes place... but they're very different mods so it might limit their appeal.



  • Why have I just found this now... Interesting how a flower can inspire someone to write optimized code! And I like a programmers philosophy where he goes like "Well I might have an overclocked i7, but nah I m not just gonna fuck it, I ll optimize the hell out of this, like we did it back in the days with the Commodores". Awesome work!

    Would be interesting to test it with a script setup where you create a huge flat area in the ocean and spawn vehicles and then measure the frame difference.

    I think I m gonna use it with my Jet HUD mod, where I check for vehicles in the distance of 10000 meters and still filter them... As you can imagine, one hell of CPU load!



  • @Kryo4lex Sorry I didn't reply to this... I have been on and off the site so didn't notice all of the comments made.

    If you've come from the days of C64 programming, then you'll know the effort we had to put into optimisation. Trying to lever small functions into zero page because it had the fastest 256 bytes of ram in the sytem. Or generating in-line scroll routines, to do full screen scrolling on the fly. Even more important if you did PAL to NTSC porting because you lost so much VSync time with the faster update frequency.

    Optimisation was king and that's a philosophy I have always held true. I think it's even more critical in a situation where you are just one mod in a pool of many. Any cycles I can save, are cycles another mod can use and that benefits the end user.

    Implementing this gained me a significant amount of processing time, especially as I had two mods that did the same thing. It was one of the things that motivated me to merge them. It got to the point where I could run both mods, with a significantly reduced hit on performance.

    I check for vehicles in the distance of 10000 meters and still filter them... As you can imagine, one hell of CPU load!

    Wow, checking over that distance is going to be some task... that's a big area. This might definitely help with that.


  • TRANSLATOR

    @LeeC2202 i will check this out tonight!!



  • @Eddlm could you please tell me how to let scripts run every 500ms?



  • @husseinh
    Either a WAIT(500); inside your update loop if you're using SHV or set Interval to 500 for shvdn.


Log in to reply
 

Looks like your connection to GTA5-Mods.com Forums was lost, please wait while we try to reconnect.