# 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 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.

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.

private int MapWidthQuads;

private int CurrentPlayerQuadrant;

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

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.

{

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.

{

// 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.

{

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.

{

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.

{

// 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.**

{

// 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.