Я работаю над простой демонстрацией для обнаружения столкновений, которая содержит только кучу объектов, подпрыгивающих в окне. (Цель состоит в том, чтобы увидеть, сколько объектов может обрабатывать игра одновременно, не отбрасывая кадры.)
Существует гравитация, поэтому объекты либо движутся, либо сталкиваются со стеной.
Наивное решение было 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;
}
Сейчас я должен перебирать каждую ячейку - даже пустые. Возможно, это может быть улучшено каким-то образом, но я не уверен, как проверить, что ячейка пуста, не глядя на нее каким-то образом. (Может быть, я мог бы реализовать что-то вроде спящих объектов, в некоторых физических двигателях, где, если объект будет все еще некоторое время, он переходит в режим сна и не включается в вычисления для каждого кадра.)
Что я могу сделать, чтобы оптимизировать это? (Кроме того, я новичок в С# - есть ли какие-либо другие вопиющие стилистические ошибки?)
Когда игра начинает отставать, объекты, как правило, упаковываются довольно плотно, так что движения не так много. Возможно, я могу как-то воспользоваться этим преимуществом, написав функцию, чтобы увидеть, может ли с учетом текущей скорости объекта оставить свою текущую ячейку перед следующим вызовом 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 Я отказался от последнего подхода. Теперь я пытаюсь сохранить пул collidables (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;
}
Это дает лишь незначительное улучшение, а не 2x или 3x, которые я ищу.
ОБНОВЛЕНИЕ 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;
}
Я думал, что это улучшится - теперь мне нужно только перебирать коллибельные, а не все ячейки collidables *. Вместо этого игра теперь отвратительно медленная, обеспечивая только 1/10 ее производительности с помощью моих подходов.
Профилировщик указывает, что теперь основным методом является другой метод, а время получения соседей для объекта тривиально короткое. Этот метод не изменился раньше, поэтому, возможно, я назову его ПУТЕМ больше, чем раньше...
