Slightly different topic than above... It has to do with a custom structure that we are using to track unit locations, and making finding close units extremely easy...
Basically, we have a list of our Entities (we have a class structure with inheritance for different times of Entities, units, buildings, resources, etc) and they are added by reference to the list. This "array" holds references to the units and not copies of them.
We are sorting this list initially, and then periodically by the units X positions and then by the Y positions using a quicksort. Here is the code for the sorting:
Code:
public void SortList()
{
QuickSortX(this.m_EntityList, 0, this.m_TotalItems);
QuickSortY(this.m_EntityList, 0, this.m_TotalItems);
}
#region Quick Sort (Sorting array A[size])
private void QuickSortX(WorldEntity[] m_EntityList, int first, int last)
{
int middle;
//As long as the first position is less than the last,
// continue sorting with recursive calls
if (first < last)
{
//Partition the array and return pivot point
middle = partitionX(m_EntityList, first, last);
QuickSortX(m_EntityList, first, middle - 1);
QuickSortX(m_EntityList, middle + 1, last);
}
}
private void QuickSortY(WorldEntity[] m_EntityList, int first, int last)
{
int middle;
//As long as the first position is less than the last,
// continue sorting with recursive calls
if (first < last)
{
//Partition the array and return pivot point
middle = partitionY(m_EntityList, first, last);
QuickSortY(m_EntityList, first, middle - 1);
QuickSortY(m_EntityList, middle + 1, last);
}
}
private int partitionX(WorldEntity[] m_EntityList, int first, int last)
{
int middle, i, j;
middle = m_EntityList[last].X;
i = first - 1;
//Go through the array
for (j = first; j < last; j++)
{
//Swap the current value if it is less than the choosen pivot value
//So it is in the lower part of the array (below the pivot).
if (m_EntityList[j].X <= middle)
{
i++;
swap(ref this.m_EntityList, i, j);
}
}
swap(ref this.m_EntityList, (i + 1), last);
return i + 1;
}
private int partitionY(WorldEntity[] m_EntityList, int first, int last)
{
int middle, i, j;
middle = m_EntityList[last].Y;
i = first - 1;
//Go through the array
for (j = first; j < last; j++)
{
//Swap the current value if it is less than the choosen pivot value
//So it is in the lower part of the array (below the pivot).
if (m_EntityList[j].Y <= middle)
{
i++;
swap(ref this.m_EntityList, i, j);
}
}
swap(ref this.m_EntityList, (i + 1), last);
return i + 1;
}
public static void swap(ref WorldEntity[] m_EntityList, int a, int b)
{
WorldEntity oTemp = m_EntityList[a];
m_EntityList[a] = m_EntityList[b];
m_EntityList[b] = oTemp;
// Update Units Index in the list
m_EntityList[a].ProximityID = a;
m_EntityList[b].ProximityID = b;
}
#endregion
The m_EntityList is an array that is a member of the class, holds the references as mentioned above. The WorldEntity is an abstract class, the parent of all of the Entity classes in the game.
I have a swap function written; and this is where the main issue comes in.
Code:
public static void swap(ref WorldEntity[] m_EntityList, int a, int b)
{
WorldEntity oTemp = m_EntityList[a];
m_EntityList[a] = m_EntityList[b];
m_EntityList[b] = oTemp;
// Update Units Index in the list
m_EntityList[a].ProximityID = a;
m_EntityList[b].ProximityID = b;
}
oTemp now contains the reference to the unit referenced in array position a. Position A, now has the reference to B. And then oTemp should be put into location B. Seems fair enough...
Does this mean, that now:
oTemp -> A -> B? Meaning that oTemp has the same reference as A, and then A gets the same reference point as B, so oTemp references B?
Or will this swap function actually change the references correctly so that we have A2 = B1 and B2 = A1?