Теоретически вероятный алгоритм сортировки столкновений - PullRequest
Новая
       28

Теоретически вероятный алгоритм сортировки столкновений

0 голосов
/ 06 сентября 2011

Скажем, у вас есть куча объектов для проверки на столкновение.Скажем, вы предприимчивый программист-любитель, изучающий физику столкновений.Скажем, вы слышали об этой изумительной вещи, где вы сортируете по X, Y или Z позиции и по X, Y или Z границам «наихудшего» случая, что позволяет отбрасывать целые полосы объектов, которые «не могут» сталкиваться,(Я еще не реализовал циклическое / непрерывное столкновение, поэтому кавычки).

После того, как это было реализовано на оси X, я добавил дополнительные фильтры Z и Y, сортируя оси X, Z и Yсписки по очереди и разбиваются, когда я достиг объекта, с которым невозможно столкнуться.

Это все работало довольно хорошо, хотя любое увеличение скорости от последнего фильтра было незначительным.

Тогда я подумал "Если я сортирую их по оси X, по оси Z, если эта проверка возвращает эквивалентность, то по оси Y, если эта проверка возвращает эквивалентность, я смогу отказаться от сортировки вторичных списков ».Это бы снизилось примерно на 40% от времени.

Так что я сделал это так.И это не сработало - объекты падали на землю.Другие объекты попали в землю.Выглядело так, как будто первый набор объектов провалился, а все остальные отскочили.

Итак, два вопроса - Может ли это сработать и, пожалуйста, проверьте мой код на наличие ошибок: 

        bodies.Sort(
            (a, b) =>
            {
                // Should sort the list in X, then Z, then Y order.
                int signX, signY, signZ;
                return (signX = Math.Sign((a.LocalPosition.X - a.Bounds.X) - (b.LocalPosition.X - b.Bounds.X))) == 0 ? 
                    (signZ = Math.Sign((a.LocalPosition.Z - a.Bounds.Z) - (b.LocalPosition.Z - b.Bounds.Z))) == 0 ? 
                    (signY = Math.Sign((a.LocalPosition.Y - a.Bounds.Y) - (b.LocalPosition.Y - b.Bounds.Y))) == 0 ? 
                    0 :
                    signY : signZ : signX;
            }
        );
        Contact info;
        List<BodyEnt> checkBodiesZ = new List<BodyEnt>();
        List<BodyEnt> checkBodiesY = new List<BodyEnt>();
        for (int t = 0; t < bodies.Count; ++t)
        {
            checkBodiesZ.Clear();
            for (int t2 = t + 1; t2 < bodies.Count; ++t2)
            {
                // If we've reached the last object we could collide with, exit.
                if (bodies[t].LocalPosition.X + bodies[t].Bounds.X <= bodies[t2].LocalPosition.X - bodies[t2].Bounds.X)
                    break;
                checkBodiesZ.Add(bodies[t2]);
            }
            // checkBodiesZ.Sort((a, b) => { return Math.Sign((a.LocalPosition.Z - a.Bounds.Z) - (b.LocalPosition.Z - b.Bounds.Z)); });
            checkBodiesY.Clear();
            for (int t2 = 0; t2 < checkBodiesZ.Count; ++t2)
            {
                if (bodies[t].LocalPosition.Z + bodies[t].Bounds.Z <= checkBodiesZ[t2].LocalPosition.Z - checkBodiesZ[t2].Bounds.Z)
                    break;
                checkBodiesY.Add(checkBodiesZ[t2]);
            }
            // One of the two sorts I removed in this test.
            // checkBodiesY.Sort((a, b) => { return Math.Sign((a.LocalPosition.Y - a.Bounds.Y) - (b.LocalPosition.Y - b.Bounds.Y)); });
            for (int t2 = 0; t2 < checkBodiesY.Count; ++t2)
            {
                if (bodies[t].LocalPosition.Y + bodies[t].Bounds.Y <= checkBodiesY[t2].LocalPosition.Y - checkBodiesY[t2].Bounds.Y)
                    break;
                info = bodies[t].CheckCollision(checkBodiesY[t2]);
                // .CheckCollision() returns null if no collision detected.
                if (info != null)
                    contacts.Add(info);
            }
        }

Спасибо.:)

...