16
我正在研究一个简单的碰撞检测演示，其中只包含一堆在窗口中弹跳的对象。 （目标是看看游戏可以一次处理多少物体而不会丢帧）。C＃XNA：优化碰撞检测？
有重力，所以物体要么移动要么碰撞墙。
天真溶液为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我决定维持名单在最后更新时发现在单元格中的对象，并首先检查它们是否仍在单元格中。另外，我保留了CollisionCell变量的area，当单元格填满时我可以停止查找。这是我实现这一点，它要慢得多使整个演示：
// 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;
}
这只能产生边际的改善，而不是2个或3x I”寻找。
UPDATE 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 *单元格。相反，现在这款游戏的速度非常慢，只用我的上述方法提供其性能的十分之一。
探查表明不同的方法是现在的主要热点，并获得邻居的某个对象的时间是平凡短。这种方法并没有从之前的变化，所以也许我打电话比我以前WAY更多...
您是否尝试过使用XNA的farseer physcs引擎？ http://www.codeplex.com/FarseerPhysics – jjxtra 2010-02-26 20:34:41
@Rosarch：伟大的职位。很棒的更新。在下面修改我的回答，可能值得检查，我试图突出adv \ dis，更多地解释发生了什么以及为什么，并提及一些替代方案。正如杰夫约翰逊所建议的那样，也值得调查第三方图书馆。如果它有效的话，也可以为自己省去一些悲伤;） – 2010-02-27 17:36:08
我听说原来的Quake引擎通过缩小游戏世界来检查碰撞，直到玩家像素大小，并用它来检查碰撞。 – NibblyPig 2010-03-03 17:14:41