Я работаю над простой демонстрацией для обнаружения столкновений, которая содержит только кучу объектов, подпрыгивающих в окне. (Цель состоит в том, чтобы увидеть, сколько объектов игра может обработать одновременно, не пропуская фреймы.)
Существует гравитация, поэтому объекты либо движутся, либо сталкиваются со стеной.
Наивным решением было O (n ^ 2):
foreach Collidable c1:
foreach Collidable c2:
checkCollision(c1, c2);
Это довольно плохо. Поэтому я настроил CollisionCell объектов, которые хранят информацию о части экрана. Идея состоит в том, что каждый Collidable должен только проверять наличие других объектов в своей ячейке. С ячейками 60 на 60 пикселей это дает почти 10-кратное улучшение, но я бы хотел продвинуть его дальше.
Профилировщик обнаружил, что код тратит 50% своего времени на функцию, которую каждая ячейка использует для получения своего содержимого. Вот оно:
// all the objects in this cell
public ICollection<GameObject> Containing
{
get
{
ICollection<GameObject> containing = new HashSet<GameObject>();
foreach (GameObject obj in engine.GameObjects) {
// 20% of processor time spent in this conditional
if (obj.Position.X >= bounds.X &&
obj.Position.X < bounds.X + bounds.Width &&
obj.Position.Y >= bounds.Y &&
obj.Position.Y < bounds.Y + bounds.Height) {
containing.Add(obj);
}
}
return containing;
}
}
Из этого 20% времени программы тратится на это условие.
Вот где вызывается вышеуказанная функция:
// Get a list of lists of cell contents
List<List<GameObject>> cellContentsSet = cellManager.getCellContents();
// foreach item, only check items in the same cell
foreach (List<GameObject> cellMembers in cellContentsSet) {
foreach (GameObject item in cellMembers) {
// process collisions
}
}
//...
// Gets a list of list of cell contents (each sub list = 1 cell)
internal List<List<GameObject>> getCellContents() {
List<List<GameObject>> result = new List<List<GameObject>>();
foreach (CollisionCell cell in cellSet) {
result.Add(new List<GameObject>(cell.Containing.ToArray()));
}
return result;
}
Прямо сейчас я должен перебирать каждую ячейку - даже пустую. Возможно, это можно как-то улучшить, но я не уверен, как проверить, что ячейка пуста, не глядя на нее как-то. (Может быть, я мог бы реализовать что-то вроде спящих объектов в некоторых физических движках, где, если объект еще какое-то время будет неподвижен, он перейдет в режим сна и не будет включен в вычисления для каждого кадра.)
Что я могу сделать, чтобы оптимизировать это? (Кроме того, я новичок в C # - есть ли другие вопиющие стилистические ошибки?)
Когда игра начинает отставать, объекты, как правило, упаковываются довольно плотно, поэтому не происходит большого движения. Возможно, я смогу как-то воспользоваться этим, написав функцию, чтобы увидеть, может ли, учитывая текущую скорость объекта, покинуть свою текущую ячейку до следующего вызова Update()
ОБНОВЛЕНИЕ 1 Я решил сохранить список объектов, которые были найдены в ячейке при последнем обновлении, и сначала проверить их, чтобы убедиться, что они все еще находятся в ячейке. Кроме того, я сохранил area переменной CollisionCell, когда, когда ячейка была заполнена, я мог перестать смотреть. Вот моя реализация этого, и это сделало демо намного медленнее:
// all the objects in this cell
private ICollection<GameObject> prevContaining;
private ICollection<GameObject> containing;
internal ICollection<GameObject> Containing {
get {
return containing;
}
}
/**
* To ensure that `containing` and `prevContaining` are up to date, this MUST be called once per Update() loop in which it is used.
* What is a good way to enforce this?
*/
public void updateContaining()
{
ICollection<GameObject> result = new HashSet<GameObject>();
uint area = checked((uint) bounds.Width * (uint) bounds.Height); // the area of this cell
// first, try to fill up this cell with objects that were in it previously
ICollection<GameObject>[] toSearch = new ICollection<GameObject>[] { prevContaining, engine.GameObjects };
foreach (ICollection<GameObject> potentiallyContained in toSearch) {
if (area > 0) { // redundant, but faster?
foreach (GameObject obj in potentiallyContained) {
if (obj.Position.X >= bounds.X &&
obj.Position.X < bounds.X + bounds.Width &&
obj.Position.Y >= bounds.Y &&
obj.Position.Y < bounds.Y + bounds.Height) {
result.Add(obj);
area -= checked((uint) Math.Pow(obj.Radius, 2)); // assuming objects are square
if (area <= 0) {
break;
}
}
}
}
}
prevContaining = containing;
containing = result;
}
ОБНОВЛЕНИЕ 2 Я отказался от этого последнего подхода. Сейчас я пытаюсь сохранить пул объектов для сопоставления (orphans) и удалять объекты из них, когда нахожу ячейку, в которой они содержатся:
internal List<List<GameObject>> getCellContents() {
List<GameObject> orphans = new List<GameObject>(engine.GameObjects);
List<List<GameObject>> result = new List<List<GameObject>>();
foreach (CollisionCell cell in cellSet) {
cell.updateContaining(ref orphans); // this call will alter orphans!
result.Add(new List<GameObject>(cell.Containing));
if (orphans.Count == 0) {
break;
}
}
return result;
}
// `orphans` is a list of GameObjects that do not yet have a cell
public void updateContaining(ref List<GameObject> orphans) {
ICollection<GameObject> result = new HashSet<GameObject>();
for (int i = 0; i < orphans.Count; i++) {
// 20% of processor time spent in this conditional
if (orphans[i].Position.X >= bounds.X &&
orphans[i].Position.X < bounds.X + bounds.Width &&
orphans[i].Position.Y >= bounds.Y &&
orphans[i].Position.Y < bounds.Y + bounds.Height) {
result.Add(orphans[i]);
orphans.RemoveAt(i);
}
}
containing = result;
}
Это дает лишь незначительное улучшение, а не 2х или 3х, которые я ищу.
ОБНОВЛЕНИЕ 3 Снова я отказался от вышеуказанных подходов и решил позволить каждому объекту поддерживать свою текущую ячейку:
private CollisionCell currCell;
internal CollisionCell CurrCell {
get {
return currCell;
}
set {
currCell = value;
}
}
Это значение обновляется:
// Run 1 cycle of this object
public virtual void Run()
{
position += velocity;
parent.CellManager.updateContainingCell(this);
}
Код CellManager:
private IDictionary<Vector2, CollisionCell> cellCoords = new Dictionary<Vector2, CollisionCell>();
internal void updateContainingCell(GameObject gameObject) {
CollisionCell currCell = findContainingCell(gameObject);
gameObject.CurrCell = currCell;
if (currCell != null) {
currCell.Containing.Add(gameObject);
}
}
// null if no such cell exists
private CollisionCell findContainingCell(GameObject gameObject) {
if (gameObject.Position.X > GameEngine.GameWidth
|| gameObject.Position.X < 0
|| gameObject.Position.Y > GameEngine.GameHeight
|| gameObject.Position.Y < 0) {
return null;
}
// we'll need to be able to access these outside of the loops
uint minWidth = 0;
uint minHeight = 0;
for (minWidth = 0; minWidth + cellWidth < gameObject.Position.X; minWidth += cellWidth) ;
for (minHeight = 0; minHeight + cellHeight < gameObject.Position.Y; minHeight += cellHeight) ;
CollisionCell currCell = cellCoords[new Vector2(minWidth, minHeight)];
// Make sure `currCell` actually contains gameObject
Debug.Assert(gameObject.Position.X >= currCell.Bounds.X && gameObject.Position.X <= currCell.Bounds.Width + currCell.Bounds.X,
String.Format("{0} should be between lower bound {1} and upper bound {2}", gameObject.Position.X, currCell.Bounds.X, currCell.Bounds.X + currCell.Bounds.Width));
Debug.Assert(gameObject.Position.Y >= currCell.Bounds.Y && gameObject.Position.Y <= currCell.Bounds.Height + currCell.Bounds.Y,
String.Format("{0} should be between lower bound {1} and upper bound {2}", gameObject.Position.Y, currCell.Bounds.Y, currCell.Bounds.Y + currCell.Bounds.Height));
return currCell;
}
Я думал, что это улучшит ситуацию - теперь мне нужно только перебирать элементы, которые могут встречаться, а не все элементы, которые могут встречаться *. Вместо этого игра теперь ужасно медленная, обеспечивая только 1/10 своей производительности с моими вышеописанными подходами.
Профилировщик указывает, что в настоящее время основным горячим местом является другой метод, и время на поиск соседей для объекта тривиально мало. Этот метод не изменился раньше, поэтому, возможно, я называю его ПУТЬ более, чем раньше ...