Итак, в основном я хочу создать сцену, где около 50K астероидов появляются с позицией и AABB (Axis Aligned Boundry Box) и перемещать каждый из них в случайном направлении, которое генерируется в начале. Переместив их, я должен проверить, сталкивается ли какой-либо из Астероидов.
Я использую структуру данных Quad-Tree для вставки и проверки на столкновение.
Я сохраняю массив из 50 тыс. Точек, перебираю и обновляю их, затем вставляю в Quad-Tree и снова перебираю более 50 тыс. Точек и запрашиваю через QT, чтобы выяснить, не сталкивается ли какая-либо из точек.
Я много читал здесь и там около 2 недель и перепробовал столько источников, сколько смог, но я не могу выжать максимальную производительность. В большинстве источников используется c ++ или другие более производительные языки, но мне нужно сделать это с помощью C #. Буду признателен за любые советы по улучшению производительности.
Вот мой код:
public struct Point
{
public float x,y;
public int ID;
public void MoveTowards(float posX, float posY)
{
position.x = position.x + posX;
position.y = position.y + posY;
}
}
public class Controller
{
Point[] asteroids = new Point[50K];
Point[] speed = new Point[50K];
QuadTree qt = new QuadTree();
//Runs every frame
void Update()
{
qt.ClearAllNodes();
for loop asteroids(50K)
{
asteroids[i].MoveTowards(speed.x, speed.y);
qt.Insert(astetoids[i]);
}
for loop asteroids(50K)
{
int collidingAsteroidID = qt.Query(astetoids[i]);
if(collidingAsteroidID != -1) {
print(collidingAsteroidID + " is colliding with " + i);
}
}
}
}
class QuadTree
{
public Rectangle boundry;
Point[] nodes;
bool root = false;
bool divided = false;
int numberOfNodesInserted = 0;
QuadTree northEast, northWest, southEast, southWest;
public QuadTree(Rectangle boundry)
{
nodes = new Point[4];
this.boundry = boundry;
}
#region Methods
//Clear all the nodes in the Quad-Tree
public void ClearAllNodes()
{
if(numberOfNodesInserted == 0 && !root) return;
numberOfNodesInserted = 0;
root = false;
if(divided)
{
northEast.ClearAllNodes();
northWest.ClearAllNodes();
southEast.ClearAllNodes();
southWest.ClearAllNodes();
}
divided = false;
}
public bool Insert(Point point)
{
//Checking if the position is in the boundries.
if(!boundry.Contains(point)) return false;
if(numberOfNodesInserted < 4 && !root)
{
nodes[numberOfNodesInserted] = point;
numberOfNodesInserted++;
return true;
}
else if(root)
{
if(northEast.Insert(point)) return true;
if(northWest.Insert(point)) return true;
if(southEast.Insert(point)) return true;
if(southWest.Insert(point)) return true;
}
else if(!root && numberOfNodesInserted == 4)
{
//Making this node a branch and moving all the to sub-leafs
root = true;
numberOfNodesInserted = 0;
if(!divided)
SubDivide();
for (int i = 0; i < 4; i++)
{
if(!northEast.Insert(nodes[i]))
if(!northWest.Insert(nodes[i]))
if(!southEast.Insert(nodes[i]))
if(!southWest.Insert(nodes[i])) { }
}
if(!northEast.Insert(point))
if(!northWest.Insert(point))
if(!southEast.Insert(point))
if(!southWest.Insert(point)) { }
return true;
}
return false;
}
public int Query(Point point, float radius)
{
if(numberOfNodesInserted == 0 && !root) return -1;
if(!boundry.Contains(point)) return -1;
if(!root && numberOfNodesInserted != 0)
{
for (int i = 0; i < numberOfNodesInserted; i++)
{
if(DoOverlap(nodes[i], point, radius))
return nodes[i].ID;
}
}
else if(root && numberOfNodesInserted == 0)
{
int result;
result = northEast.Query(point);
if(result != -1) return result;
result = northWest.Query(point);
if(result != -1) return result;
result = southEast.Query(point);
if(result != -1) return result;
result = southWest.Query(point);
if(result != -1) return result;
}
return -1;
}
#endregion
#region HelperMethods
private void SubDivide()
{
//Size of the sub boundries
if(northEast == null)
{
float x = boundry.x;
float y = boundry.y;
float r = boundry.radius / 2;
northEast = new QuadTree(new Rectangle(x + r, y + r, r));
northWest = new QuadTree(new Rectangle(x - r, y + r, r));
southEast = new QuadTree(new Rectangle(x + r, y - r, r));
southWest = new QuadTree(new Rectangle(x - r, y - r, r));
}
divided = true;
}
#endregion
}