Простое обнаружение столкновений

Question

Я хочу написать платформенную игру, все, что я делал раньше, это головоломки, не требующие физики.
Все, что мне нужно, это простое обнаружение столкновений, то, что я предоставлю физическому движку, это положение всех объектов, и оно должно вывести:

1. Все объекты определенного типа объектов (маркеры), которые сталкиваются с любым объектом (и каким объектом), просто список пар.
2. Для каждого объекта определенного типа (игроки и NPC), если он находится на земле или в воздухе.

Вся симуляция движения / скорости / гравитации / ударов / отражений будет выполняться с использованием пользовательского кода, потому что я хочу реализовать мир со странной физикой.
Должен ли я катить свой собственный двигатель? я могу использовать существующие, такие как chipmunk / box2d? Если мне нужно реализовать свои собственные, как я сделаю обнаружение столкновений не дорогостоящей операцией? (как наивная реализация просто проверки всего в O(n^2).
Я могу использовать target-c или c ++, я бы предпочел c ++ (он должен иметь лучшую производительность).

Answer 1

Для такого рода проблем я бы порекомендовал вам написать собственную библиотеку.

Да, вы можете найти такую ​​функцию в существующих библиотеках, однако вы многому научитесь, написав собственную.

Я рекомендую изучить граф и древовидные структуры данных.

Answer 2

Если вы пишете свою физику, вы, вероятно, захотите включить собственное обнаружение столкновений. Есть также некоторые общедоступные бесплатные физические движки, которые вы можете попробовать как пуля. (http://www.bulletphysics.org)

Но вы можете просто выполнить поиск в Google алгоритмов обнаружения столкновений, которые могут применяться к той игре, которую вы делаете, с типами пересечений, для которых вам нужно проверить.

Вот случайная статья, которую я нашел: http://www.gamespp.com/algorithms/collisionDetection.html