Tôi đang làm việc trên một bản demo đơn giản để phát hiện va chạm, trong đó chỉ chứa một loạt các đối tượng nảy xung quanh trong cửa sổ. (Mục đích là để xem có bao nhiêu đối tượng mà trò chơi có thể xử lý cùng một lúc mà không làm rơi khung.)C# XNA: Tối ưu hóa việc phát hiện va chạm?
Có trọng lực, vì vậy vật thể đang di chuyển hoặc chạm vào tường.
Giải pháp ngây thơ là O (n^2):
foreach Collidable c1:
foreach Collidable c2:
checkCollision(c1, c2);
này là khá xấu. Vì vậy, tôi thiết lập các đối tượng CollisionCell, duy trì thông tin về một phần của màn hình. Ý tưởng là mỗi Collidable chỉ cần kiểm tra các đối tượng khác trong ô của nó. Với 60 px bởi 60 px tế bào, điều này mang lại gần như một cải tiến 10x, nhưng tôi muốn đẩy nó hơn nữa.
Một trình tiết lộ đã tiết lộ rằng mã dành 50% thời gian của nó trong hàm mà mỗi ô sử dụng để lấy nội dung của nó. Dưới đây là:
// 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;
}
}
Trong đó 20% thời gian của chương trình được chi tiêu trong điều kiện đó.
Đây là nơi mà các chức năng trên được gọi là:
// 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;
}
Ngay bây giờ, tôi phải lặp qua tất cả các tế bào - ngay cả những sản phẩm nào. Có lẽ điều này có thể được cải thiện bằng cách nào đó, nhưng tôi không chắc làm thế nào để xác minh rằng một tế bào là trống rỗng mà không nhìn vào nó bằng cách nào đó. (Có lẽ tôi có thể thực hiện một cái gì đó như đối tượng ngủ, trong một số động cơ vật lý, nếu một đối tượng sẽ vẫn còn trong một thời gian nó đi ngủ và không được bao gồm trong tính toán cho mỗi khung hình.)
Tôi có thể làm gì để tối ưu hóa điều này? (Ngoài ra, tôi mới sử dụng C# - có bất kỳ lỗi phong cách rõ ràng nào khác không?)
Khi trò chơi bắt đầu tụt hậu, các đối tượng có xu hướng được đóng gói khá chặt chẽ, vì vậy không có nhiều chuyển động diễn ra. Có lẽ tôi có thể tận dụng điều này bằng cách nào đó, viết một hàm để xem, cho tốc độ hiện tại của một đối tượng, nó có thể có thể để lại di động hiện tại của nó trước khi cuộc gọi bên cạnh Update()
UPDATE 1 tôi quyết định để duy trì một danh sách các các đối tượng được tìm thấy ở trong ô ở lần cập nhật cuối cùng và kiểm tra những vật thể đầu tiên để xem liệu chúng có còn trong ô hay không. Ngoài ra, tôi duy trì một số area của biến số CollisionCell, khi nào khi ô được lấp đầy, tôi có thể ngừng tìm kiếm. Dưới đây là thực hiện của tôi về điều đó, và nó làm cho toàn bộ bản demo chậm hơn nhiều:
// 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;
}
UPDATE 2 Tôi bị bỏ rơi mà tiếp cận cuối cùng. Bây giờ tôi đang cố gắng để duy trì một vũng collidables (orphans), và loại bỏ các đối tượng từ họ khi tôi tìm thấy một tế bào có chứa chúng:
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;
}
này chỉ mang lại một sự cải thiện biên, không phải là 2x hoặc 3x tôi' m tìm kiếm.
CẬP NHẬT 3 Một lần nữa tôi từ bỏ cách tiếp cận trên, và quyết định để cho mỗi đối tượng duy trì tế bào hiện nay:
private CollisionCell currCell;
internal CollisionCell CurrCell {
get {
return currCell;
}
set {
currCell = value;
}
}
Giá trị này được cập nhật:
// Run 1 cycle of this object
public virtual void Run()
{
position += velocity;
parent.CellManager.updateContainingCell(this);
}
đang 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;
}
Tôi nghĩ điều này sẽ làm cho nó tốt hơn - bây giờ tôi chỉ phải lặp qua các collidables, không phải tất cả các ô * collidables. Thay vào đó, trò chơi hiện đang rất chậm, chỉ phân phối 1/10 hiệu suất của nó với các phương pháp trên.
Trình hồ sơ chỉ ra rằng một phương pháp khác bây giờ là điểm nóng chính và thời gian để có được hàng xóm cho một đối tượng là không đáng kể. Phương pháp đó đã không thay đổi so với trước đây, vì vậy có lẽ tôi đang gọi nó nhiều hơn so với trước đây ...
Bạn đã thử sử dụng công cụ vật lý farseer cho XNA chưa? http://www.codeplex.com/FarseerPhysics – jjxtra
@Rosarch: bài đăng tuyệt vời. cập nhật tuyệt vời. sửa đổi phản ứng của tôi dưới đây, có thể đáng để kiểm tra, tôi đã cố gắng để làm nổi bật adv \ dis, giải thích thêm về những gì đã xảy ra và tại sao, và đề cập đến một số lựa chọn thay thế. cũng đáng để điều tra các thư viện của bên thứ ba, như Jeff Johnson đề xuất. –
Tôi nghe nói rằng động cơ Quake nguyên bản đã kiểm tra va chạm bằng cách thu hẹp gameworld cho đến khi người chơi có kích thước pixel, và sử dụng nó để kiểm tra va chạm. – NibblyPig