Back to Main Page

A couple of pages explaining the Quadrant Search manager I use in several mods.

Like the petal collection system I designed for the Random Dirty Cars mod, this is all done with the aim of keeping performance down to a minimum.

While other people seem to like throwing instances of Script around like candy, I prefer to try and maintain a compact and efficient system instead. Just because it runs fine on your system, doesn't mean it will run fine on someone else's... the aim is to make it run fine on everyone's system.

Page 2 explains the code in more detail, breaking down the QSM to show each section.

Sample Mod Project Download HERE

The dll file is in the bin/Release folder inside the project download. The project is built against SHVDN 2.10.7, so it should be compatible with most game installs.

Do NOT copy the ScriptHookVDotNet2.dll from that folder if you are already using a newer version in your game!

I use VS2015, so the project should also be compatible with any recent Visual Studio release.

Quadrant Search Manager - Boxes, boxes, everywhere!!

Many of my pages contain references to the QSM (Quadrant Search Manager), so I have decided to create a page discussing more about it and giving people access to it, if they want to use it.

What is the idea behind its function?

At its core, it's a crude Binary Space Partitioning system. The aim of those systems is to manage large numbers of locations, by breaking them down into smaller compartments (or partitions) that contain them. That way, you are only ever searching inside a small box, instead of the whole map.

So how does this help?

Take my World Guide System mod, it has 2014 locations, imagine the performance hit from doing a World.GetDistance() on 2014 locations. And yet WGS can provide a constantly updating nearest location with an almost zero hit on FPS... all thanks to the QSM.

Okay, so how does it work?

In each mod, the QSM is given a different struct that represents a location, depending on what the mod is doing. In WGS it's given a WorldLocationStruct that contains a whole host of information about position, entry heading, type of location, opening times etc... the CCTV Watcher mod gives it a much smaller struct. QSM doesn't care what the struct is, or what it contains, as long as it has a Position property, that's the only thing it cares about.

When you create an instance of the QuadrantSearchManager class, you tell it what quadrant size it will be working on, the bigger the quadrants, the more locations there might be in each quadrant. Smaller quadrants restrict the number of locations to deal with but that also limits the range that they become visible to the player. The reason for that is the player sits in the centre quadrant of a 3x3 collection of quadrants, so they can only ever see what is in those 9 quadrants during normal gameplay.

That might sound restricting but in reality, it's not a problem. Setting a quadrant size to 50, means that things are accessible at least 50m from the player, which is more than enough if you only want to deal with things the player is going to interact with. WGS uses a quadrant size of 25 because it has many locations, often packed in close proximity to each other.

Along with a QuadrantSize, you also give it a SearchDistance value. This is the furthest distance a location can be away from the player, for it to be considered a ClosestLocation. Obviously, this can't be bigger than the size of a quadrant, because any bigger than that and the location might not even be in the NearbyLocations collection to begin with.

So once the QSM has been instanced, you can send it a set of locations in the form of a List<LocationStruct>. It goes through that list, takes each position and converts that to a quadrant number. That location is then stored in a Dictionary<int, List<LocationStruct>> collection, with the quadrant number as the key. That's all that is required to get the QSM set up.

At any point, you can change the set of locations, or you can add more to the collection as required. One of the enhancements I made to WGS, was the ability to accept additional locations from any mod at runtime. That way, custom mod locations can all be accessible from the WGS, if required.

So now that the QSM is set up, all you have to do is call QSM.Update() from the controlling mod's onTick event and it does the rest.

What does that actually mean, does the rest... what is the rest?

During gameplay, QSM is constantly getting the player position and converting that to a quadrant key. From that quadrant key, it gets the 8 surrounding keys and uses those to populate a NearbyLocations collection. When the player moves into a new quadrant, those NearbyLocations are updated. It populates the collection by simply retrieving the locations stored under that quadrant key, from the Dictionary<int, List<LocationStruct>> collection, which makes it fast and simple to keep things updated.

If the NearbyLocations collection has any locations in it, they are run through a distance-squared check to determine the closest location. Distance-squared is a very fast 2-Dimensional check that is great for getting the closest point from a collection. Once the closest location has been determined, a more precise GetDistance() check is done, to get the actual distance to the location and that is stored, along with the location as the ClosestDistance and ClosestLocation.

Each frame, you check if the QSM.ClosestDistance < QSM.SearchDistance and if it is, then you know there is a valid location in QSM.ClosestLocation. You can then retrieve that location and do whatever you need to do with it.

It's a very simple process and as you'll see on the next page, it's also a very simple class.

Here's a short demo video of me moving around with the quadrants visualised as boxes.


Continued on Page 2