C# XNA: оптимизация обнаружения коллизий?
Я работаю над простой демонстрацией для обнаружения коллизий, которое содержит только набор объектов, возвращающихся вокруг в окне. (Цель состоит в том, чтобы видеть, сколько объектов игра может обработать сразу, не отбрасывая кадры.)
Существует сила тяжести, таким образом, объекты или перемещаются или иначе сталкиваются со стеной.
Наивным решением был O (n^2):
foreach Collidable c1:
foreach Collidable c2:
checkCollision(c1, c2);
Это довольно плохо. Таким образом, я настроил CollisionCell объекты, которые поддерживают информацию о части экрана. Идея состоит в том что каждый Collidable только потребности проверить на другие объекты в его ячейке. С ячейками 60 пкс на 60 пкс это уступает почти 10x улучшение, но я хотел бы продвинуть его далее.
Профилировщик показал, что код тратит 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, я отказался от того последнего подхода. Теперь я пытаюсь поддержать пул 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, не всему collidables * ячейки. Вместо этого игра является теперь ужасно медленной, поставляя только 1/10-й из ее производительности с моим выше подходов.
Профилировщик указывает, что другой метод является теперь основной горячей точкой, и время для получения соседей к объекту тривиально коротко. Тот метод не изменился до, поэтому возможно, я называю его ПУТЕМ больше, чем я привык для...
7 ответов
Он тратит 50% своего времени на эту функцию, потому что вы часто вызываете эту функцию. Оптимизация этой одной функции приведет только к постепенному повышению производительности.
Или просто вызовите функцию less!
Вы уже начали идти по этому пути, настроив схему пространственного разделения (найдите Quadtrees , чтобы увидеть более сложную форму вашей техники).
Второй подход - разбить цикл N * N на инкрементную форму и использовать бюджет ЦП .
Вы можете выделить бюджет ЦП для каждого модуля, который требует действий во время кадра (во время обновлений). Столкновение - один из этих модулей, AI может быть другим.
Допустим, вы хотите запустить игру со скоростью 60 кадров в секунду. Это означает, что у вас есть около 1/60 с = 0,0167 с процессорного времени для записи между кадрами. Нет, мы можем разделить эти 0,0167 с между нашими модулями. Дадим коллизию 30% бюджета: 0,005 с .
Теперь ваш алгоритм столкновения знает, что он может работать только 0,005 с. Так что, если время истечет, придется отложить некоторые задачи на потом - вы сделаете алгоритм инкрементальным.Код для достижения этого может быть таким простым, как:
const double CollisionBudget = 0.005;
Collision[] _allPossibleCollisions;
int _lastCheckedCollision;
void HandleCollisions() {
var startTime = HighPerformanceCounter.Now;
if (_allPossibleCollisions == null ||
_lastCheckedCollision >= _allPossibleCollisions.Length) {
// Start a new series
_allPossibleCollisions = GenerateAllPossibleCollisions();
_lastCheckedCollision = 0;
}
for (var i=_lastCheckedCollision; i<_allPossibleCollisions.Length; i++) {
// Don't go over the budget
if (HighPerformanceCount.Now - startTime > CollisionBudget) {
break;
}
_lastCheckedCollision = i;
if (CheckCollision(_allPossibleCollisions[i])) {
HandleCollision(_allPossibleCollisions[i]);
}
}
}
Итак, теперь не имеет значения, насколько быстрым является код коллизии, он будет выполнен как можно быстрее , не влияя на воспринимаемую пользователем производительность .
Преимущества включают:
- Алгоритм рассчитан на то, что время истекает, он просто возобновляется в следующем кадре, поэтому вам не нужно беспокоиться об этом конкретном граничном случае.
- Бюджетирование ЦП становится все более важным по мере увеличения количества сложных / трудоемких алгоритмов. Подумайте об ИИ. Так что внедрить такую систему на раннем этапе - хорошая идея.
- Время отклика человека меньше 30 Гц, цикл кадра работает с частотой 60 Гц. Это дает алгоритму 30 кадров для завершения своей работы, так что нормально, что он не завершает свою работу.
- Выполнение этого способа дает стабильную , независимую от данных частоту кадров.
- Он по-прежнему выигрывает от оптимизации производительности самого алгоритма коллизий.
- Алгоритмы коллизий предназначены для отслеживания «подкадра», в котором произошли коллизии. То есть вам никогда не повезет поймать столкновение только , как только это случилось - думать, что вы это делаете, - это вранье самому себе.
Похоже, что вы перебираете все игровые объекты только для того, чтобы увидеть, какие объекты содержатся в ячейке. Кажется, что лучшим подходом было бы хранить список игровых объектов, которые находятся в ячейке, для каждой ячейки. Если вы сделаете это, и каждый объект будет знать, в каких ячейках он находится, то перемещение объектов между ячейками должно быть простым. Кажется, что это даст наибольший прирост производительности.
Вот еще один совет по оптимизации для определения того, в каких ячейках находится объект: Если вы уже определили, в какой ячейке (ячейках) находится объект, и знаете, что на основании скорости объекта он не будет менять ячейки для текущего кадра, нет необходимости повторно запускать логику, определяющую, в каких ячейках находится объект. Можно выполнить быструю проверку, создав ограничивающую рамку, содержащую все ячейки, в которых находится объект. Затем можно создать ограничивающую область, размер которой равен размеру объекта + скорость объекта для текущего кадра. Если ограничивающая рамка ячейки содержит объект + ограничивающую рамку скорости, дальнейших проверок делать не нужно. Если объект не движется, все еще проще, и вы можете просто использовать границу объекта.
Дайте мне знать, если это имеет смысл, или поищите в google / bing по запросу "Quad Tree", или, если вы не против использовать открытый код, посмотрите на эту потрясающую библиотеку физики: http://www.codeplex.com/FarseerPhysics
Я могу помочь здесь; Я написал свое собственное обнаружение столкновений в качестве эксперимента.Думаю, я могу сказать вам прямо сейчас, что вы не получите нужной производительности без изменения алгоритмов. Конечно, наивный способ хорош, но он работает только для определенного количества предметов, прежде чем он рухнет. Что вам нужно, так это Очистить и обрезать . Основная идея выглядит так (из моего проекта библиотеки обнаружения столкновений):
using System.Collections.Generic;
using AtomPhysics.Interfaces;
namespace AtomPhysics.Collisions
{
public class SweepAndPruneBroadPhase : IBroadPhaseCollider
{
private INarrowPhaseCollider _narrowPhase;
private AtomPhysicsSim _sim;
private List<Extent> _xAxisExtents = new List<Extent>();
private List<Extent> _yAxisExtents = new List<Extent>();
private Extent e1;
public SweepAndPruneBroadPhase(INarrowPhaseCollider narrowPhase)
{
_narrowPhase = narrowPhase;
}
public AtomPhysicsSim Sim
{
get { return _sim; }
set { _sim = null; }
}
public INarrowPhaseCollider NarrowPhase
{
get { return _narrowPhase; }
set { _narrowPhase = value; }
}
public bool NeedsNotification { get { return true; } }
public void Add(Nucleus nucleus)
{
Extent xStartExtent = new Extent(nucleus, ExtentType.Start);
Extent xEndExtent = new Extent(nucleus, ExtentType.End);
_xAxisExtents.Add(xStartExtent);
_xAxisExtents.Add(xEndExtent);
Extent yStartExtent = new Extent(nucleus, ExtentType.Start);
Extent yEndExtent = new Extent(nucleus, ExtentType.End);
_yAxisExtents.Add(yStartExtent);
_yAxisExtents.Add(yEndExtent);
}
public void Remove(Nucleus nucleus)
{
foreach (Extent e in _xAxisExtents)
{
if (e.Nucleus == nucleus)
{
_xAxisExtents.Remove(e);
}
}
foreach (Extent e in _yAxisExtents)
{
if (e.Nucleus == nucleus)
{
_yAxisExtents.Remove(e);
}
}
}
public void Update()
{
_xAxisExtents.InsertionSort(comparisonMethodX);
_yAxisExtents.InsertionSort(comparisonMethodY);
for (int i = 0; i < _xAxisExtents.Count; i++)
{
e1 = _xAxisExtents[i];
if (e1.Type == ExtentType.Start)
{
HashSet<Extent> potentialCollisionsX = new HashSet<Extent>();
for (int j = i + 1; j < _xAxisExtents.Count && _xAxisExtents[j].Nucleus.ID != e1.Nucleus.ID; j++)
{
potentialCollisionsX.Add(_xAxisExtents[j]);
}
HashSet<Extent> potentialCollisionsY = new HashSet<Extent>();
for (int j = i + 1; j < _yAxisExtents.Count && _yAxisExtents[j].Nucleus.ID != e1.Nucleus.ID; j++)
{
potentialCollisionsY.Add(_yAxisExtents[j]);
}
List<Extent> probableCollisions = new List<Extent>();
foreach (Extent e in potentialCollisionsX)
{
if (potentialCollisionsY.Contains(e) && !probableCollisions.Contains(e) && e.Nucleus.ID != e1.Nucleus.ID)
{
probableCollisions.Add(e);
}
}
foreach (Extent e2 in probableCollisions)
{
if (e1.Nucleus.DNCList.Contains(e2.Nucleus) || e2.Nucleus.DNCList.Contains(e1.Nucleus))
continue;
NarrowPhase.DoCollision(e1.Nucleus, e2.Nucleus);
}
}
}
}
private bool comparisonMethodX(Extent e1, Extent e2)
{
float e1PositionX = e1.Nucleus.NonLinearSpace != null ? e1.Nucleus.NonLinearPosition.X : e1.Nucleus.Position.X;
float e2PositionX = e2.Nucleus.NonLinearSpace != null ? e2.Nucleus.NonLinearPosition.X : e2.Nucleus.Position.X;
e1PositionX += (e1.Type == ExtentType.Start) ? -e1.Nucleus.Radius : e1.Nucleus.Radius;
e2PositionX += (e2.Type == ExtentType.Start) ? -e2.Nucleus.Radius : e2.Nucleus.Radius;
return e1PositionX < e2PositionX;
}
private bool comparisonMethodY(Extent e1, Extent e2)
{
float e1PositionY = e1.Nucleus.NonLinearSpace != null ? e1.Nucleus.NonLinearPosition.Y : e1.Nucleus.Position.Y;
float e2PositionY = e2.Nucleus.NonLinearSpace != null ? e2.Nucleus.NonLinearPosition.Y : e2.Nucleus.Position.Y;
e1PositionY += (e1.Type == ExtentType.Start) ? -e1.Nucleus.Radius : e1.Nucleus.Radius;
e2PositionY += (e2.Type == ExtentType.Start) ? -e2.Nucleus.Radius : e2.Nucleus.Radius;
return e1PositionY < e2PositionY;
}
private enum ExtentType { Start, End }
private sealed class Extent
{
private ExtentType _type;
public ExtentType Type
{
get
{
return _type;
}
set
{
_type = value;
_hashcode = 23;
_hashcode *= 17 + Nucleus.GetHashCode();
}
}
private Nucleus _nucleus;
public Nucleus Nucleus
{
get
{
return _nucleus;
}
set
{
_nucleus = value;
_hashcode = 23;
_hashcode *= 17 + Nucleus.GetHashCode();
}
}
private int _hashcode;
public Extent(Nucleus nucleus, ExtentType type)
{
Nucleus = nucleus;
Type = type;
_hashcode = 23;
_hashcode *= 17 + Nucleus.GetHashCode();
}
public override bool Equals(object obj)
{
return Equals(obj as Extent);
}
public bool Equals(Extent extent)
{
if (this.Nucleus == extent.Nucleus)
{
return true;
}
return false;
}
public override int GetHashCode()
{
return _hashcode;
}
}
}
}
и вот код, который выполняет сортировку вставкой (более или менее прямой перевод псевдокода здесь ):
/// <summary>
/// Performs an insertion sort on the list.
/// </summary>
/// <typeparam name="T">The type of the list supplied.</typeparam>
/// <param name="list">the list to sort.</param>
/// <param name="comparison">the method for comparison of two elements.</param>
/// <returns></returns>
public static void InsertionSort<T>(this IList<T> list, Func<T, T, bool> comparison)
{
for (int i = 2; i < list.Count; i++)
{
for (int j = i; j > 1 && comparison(list[j], list[j - 1]); j--)
{
T tempItem = list[j];
list.RemoveAt(j);
list.Insert(j - 1, tempItem);
}
}
}
IIRC, мне удалось добиться чрезвычайно большого увеличения производительности, особенно при работе с большим количеством сталкивающихся тел. Вам нужно будет адаптировать его для своего кода, но это основная предпосылка очистки и удаления.
Еще я хочу напомнить вам, что вы должны использовать профилировщик, подобный тому, который сделан Red Gate . Существует бесплатная пробная версия, которой должно хватить на долгое время.
Я нахожусь в той же лодке, что и вы. Я пытаюсь создать шутер над головой, и мне нужно повысить эффективность до максимума, чтобы на экране одновременно отображались тонны пуль и врагов.
Я бы поместил все мои коллидируемые объекты в массив с пронумерованным индексом. Это дает возможность воспользоваться преимуществом наблюдения: если вы полностью перебираете список для каждого элемента, вы будете дублировать усилия. То есть (и обратите внимание, я придумываю имена переменных, чтобы было легче выдать некоторый псевдокод)
if (objs[49].Intersects(objs[51]))
эквивалентен:
if (objs[51].Intersects(objs[49]))
Таким образом, если вы используете нумерованный индекс, вы можете сэкономить время, не дублирование усилий. Вместо этого сделайте следующее:
for (int i1 = 0; i1 < collidables.Count; i1++)
{
//By setting i2 = i1 + 1 you ensure an obj isn't checking collision with itself, and that objects already checked against i1 aren't checked again. For instance, collidables[4] doesn't need to check against collidables[0] again since this was checked earlier.
for (int i2 = i1 + 1; i2 < collidables.Count; i2++)
{
//Check collisions here
}
}
Кроме того, я бы хотел, чтобы каждая ячейка имела счетчик или флаг, чтобы определить, нужно ли вам вообще проверять коллизии. Если установлен определенный флаг или если счетчик меньше 2, то нет необходимости проверять коллизии.
Есть несколько вещей, которые можно сделать, чтобы ускорить процесс ... но, насколько я могу судить, ваш метод проверки наличия простых прямоугольных столкновение в порядке.
Но я бы заменил проверку
if (obj.Position.X ....)
на
if (obj.Bounds.IntersercsWith(this.Bounds))
И я бы также заменил строку
result.Add(new List<GameObject>(cell.Containing.ToArray()));
For
result.Add(new List<GameObject>(cell.Containing));
, поскольку свойство Contain возвращает ICollection и это наследует IEnumerable , который принимается конструктором List .
А метод ToArray () просто выполняет итерацию по списку, возвращая массив, и этот процесс повторяется снова при создании нового списка.
Можно использовать ограничивающий круг. По сути, когда создается Collidable, отслеживайте его центральную точку и вычисляйте радиус / диаметр, который содержит весь объект. Затем вы можете выполнить исключение первого прохода, используя что-то вроде:
int r = C1.BoundingRadius + C2.BoundingRadius;
if( Math.Abs(C1.X - C2.X) > r && Math.Abs(C1.Y - C2.Y) > r )
/// Skip further checks...
Это снижает количество сравнений до двух для большинства объектов, но я не уверен, насколько это принесет вам пользу ... profile!
Внимание! Некоторые люди предлагают дальновидного; это отличная библиотека 2D-физики для использования с XNA. Если вы ищете движок трехмерной физики для XNA, я использовал bulletx (порт C # для bullet ) в проектах XNA, чтобы добиться большого эффекта.
Примечание: я не имею отношения к проектам bullet или bulletx.