Back to Main Page


This page shows and explains exactly how the QSM works.

Back to Page 1

Quadrant Search Manager - The code explained.


Okay, let's just go over some map basics before I start.

The GTA V map runs from roughly -3800 to 4400 on the X and -3600 to 7800 on the Y. That gives a total map size of 8200 x 11400 metres. These values are stored as const int in the class, so they can be changed to cater for maps that extend beyond the normal bounds of the GTA V vanilla map.

        const int MinMapX = -3800;
        const int MaxMapX = 4400;
        const int MinMapY = -3600;
        const int MaxMapY = 7800;

This is the sample location struct I have used for this mod. It has a Position property and an Index property I can use to show which location it is in the demo mod.

    // Sample location for this demo
    public struct QSMLocationStruct
    {
        public QSMLocationStruct(int index, Vector3 position)
        {
            Index = index;
            Position = position;
        }

        public int Index;
        public Vector3 Position;
    }
 

Note: Just to clarify, the QSMLocationStruct is just a sample struct I created for this demo. If your mod uses something different, just change all the refernces from QSMLocationStruct, to whatever you are using instead.

Next we define some quadrant related properties, all should be fairly self-explanatory. MapWidthQuads simply divides the map width by the quadrant size, to get the number of quadrants across the map.

        public int QuadrantSize { get; private set; }
        private int MapWidthQuads;
        private int CurrentPlayerQuadrant;

Finally the rest of the class properties, again, the names should explain what they do quite clearly.

        // This dictionary will use a quadrant coordinate as the key.
        private Dictionary<int, List<QSMLocationStruct>> QuadrantBasedLocations;

        // This List is what will hold all the locations that can be distance checked against and it will usually be the contents of the
        // 3x3 quadrant grid around the player's current position.
        public List<QSMLocationStruct> NearbyLocations { get; private set; }

        public QSMLocationStruct ClosestLocation { get; private set; }
        public float ClosestDistance { get; private set; }
        public float ClosestSearchDistance = 10f;

        public bool LocationsHaveLoaded = false;

        private Ped PlayerPed;

The class constructor has a default quadrantSize in case you don't need to change anything. MapWidthQuads is calculated and this is used to get the origin of the 3x3 block of quadrants later.

        public QuadrantSearchManager(int quadrantSize = 25)
        {
            QuadrantSize = quadrantSize;
            MapWidthQuads = (Math.Abs(MinMapX) + MaxMapX) / QuadrantSize;

            QuadrantBasedLocations = new Dictionary<int, List<QSMLocationStruct>>();
            NearbyLocations = new List<QSMLocationStruct>();
        }
 

Next are the two functions that allow you to either set or add the locations to the QSM. Positions are converted to a quadrant and if that key doesn't exist, the collection for that key is created before dropping through to the code that adds the position.

        private void AddLocations(List<QSMLocationStruct> locations)
        {
            // Go through each location in the list and assign it a quadrant key
            foreach (QSMLocationStruct wls in locations)
            {
                // Get the quadrant key for the location
                int quadKey = PositionToQuadrant(wls.Position);

                // If this key does not exist in the dictionary, create it
                if (!QuadrantBasedLocations.ContainsKey(quadKey))
                {
                    QuadrantBasedLocations.Add(quadKey, new List<QSMLocationStruct>());
                }

                // Add the location to the dictionary
                QuadrantBasedLocations[quadKey].Add(wls);
            }

            LocationsHaveLoaded = true;
        }

        public void SetLocations(List<QSMLocationStruct> locations)
        {
            // Clear the current quadrant search locations and then pass the locations to the AddLocations function
            QuadrantBasedLocations.Clear();
            AddLocations(locations);
        }
 

The Update() function does very little but it controls when the other crucial functions get called. It keeps track of the player's current quadrant and updates the nearby locations when that quadrant changes.

        public void Update()
        {
            if (PlayerPed != Game.Player.Character) PlayerPed = Game.Player.Character;

            // Get the quadrant that the player is in
            int newPlayerQuad = PositionToQuadrant(PlayerPed.Position);

            // If the quadrant has changed, update the nearby location collection
            if (newPlayerQuad != CurrentPlayerQuadrant)
            {
                CurrentPlayerQuadrant = newPlayerQuad;
                UpdateNearbyLocations();
            }

            // If we have some nearby locations, check their distances
            if (NearbyLocations.Count != 0)
            {
                CheckDistances();
            }
            else
            {
                ClosestDistance = 999999;
            }
        }
 

The function that updates the locations is again, very simple. It calculates the origin and then loops through the quadrants, getting the collection from the dictionary if the key exists.

        private void UpdateNearbyLocations()
        {
            NearbyLocations.Clear();

            // Make sure the origin quadrant is never less than zero
            int origin = Math.Max(CurrentPlayerQuadrant - (MapWidthQuads + 1), 0);

            for (int y = 0; y < 3; y++)
            {
                for (int x = 0; x < 3; x++)
                {
                    int newQuadKey = origin + ((y * MapWidthQuads) + x);

                    if (QuadrantBasedLocations.ContainsKey(newQuadKey))
                    {
                        NearbyLocations.AddRange(QuadrantBasedLocations[newQuadKey]);
                    }
                }
            }
        }
 

Next comes the distance checking functions. The FastCheckDistance() is the distance-squared check and that does the bulk of the work to narrow down the closest location. Then I call the normal GetDistance() to get the final distance in normal metre units. I use my own GetDistance() function instead of the SHVDN function, because SHVDN doesn't allow you to use the useZ parameter. So by the end of this function, I will have a closest location and the distance to it, if there is one and it will have only used the processor intensive GetDistance() function once.

        private void CheckDistances()
        {
            // Pre-set a far distance
            float closestDistance = 999999;

            // Go through each location and perform a fast-distance check on it,
            // which is much quicker than a standard check
            foreach (QSMLocationStruct wl in NearbyLocations)
            {
                float distance = FastCheckDistance(wl.Position, PlayerPed.Position);

                // If the fast-check distance is below the current closestDistance,
                // save the location and make the new distance the closest distance
                if (distance < closestDistance)
                {
                    ClosestLocation = wl;
                    closestDistance = distance;
                }
            }
            // Get the real distance of the closest location.
            ClosestDistance = GetDistance(ClosestLocation.Position, PlayerPed.Position, false);
        }

        private float FastCheckDistance(Vector3 origin, Vector3 Target)
        {
            float dx = (Target.X - origin.X);
            float dy = (Target.Y - origin.Y);
            return (dx * dx) + (dy * dy);
        }

        private float GetDistance(Vector3 from, Vector3 to, bool useZ)
        {
            return Function.Call<float>(Hash.GET_DISTANCE_BETWEEN_COORDS, from.X, from.Y, from.Z, to.X, to.Y, to.Z, useZ);
        }
 

The remaining functions are conversion functions between quadrant and position values. I don't use the QuadrantToPosition() function but it's there in case I ever need it.

Note: I did actually use QuadrantToPosition() in conjunction with some other debug code that I have removed, to draw the quadrant boxes into the map in a previous test mod. I stored the active quadrants into another List<int> and then drew boxes based on the converted positions of those quadrant keys.

        public int PositionToQuadrant(Vector3 position)
        {
            // Convert the position into an int pair of 0 - map-limit values
            int xPos = (int)position.X + Math.Abs(MinMapX);
            int yPos = (int)position.Y + Math.Abs(MinMapY);

            // convert those to quadrant based values
            int quadX = xPos / QuadrantSize;
            int quadY = yPos / QuadrantSize;

            // finally convert those to the actual quadrant key value
            return (quadY * MapWidthQuads) + quadX;
        }

        private Vector3 QuadrantToPosition(int quad)
        {
            // this should get us column and row
            int quadY = quad / MapWidthQuads;
            int quadX = quad - (quadY * MapWidthQuads);

            // Convert those values back to map coordinates (which will be 0 - value) then subtract
            // the min values to offset them into -val to +val numbers
            float posX = (quadX * QuadrantSize) - Math.Abs(MinMapX);
            float posY = (quadY * QuadrantSize) - Math.Abs(MinMapY);

            return new Vector3(posX, posY, PlayerPed.Position.Z);
        }
 

That's it... that's the Quadrant Search Manager in a nutshell.