улучшение обнаружения столкновений
У меня есть две функции, которые я буду использовать для проверки столкновений между объектами на экране, так как эти функции — вещи, которые будут выполняться много, я хотел бы убедиться, что они работают с максимальной эффективностью, и потому что в настоящее время они кажутся довольно грязными, я Мне было интересно, могу ли я получить вашу помощь.
Мои функции следующие:
Это функция, которая фактически будет вызываться для объекта:
bool ScreenObject::intersects(ScreenObject & a,ScreenObject & b) {
if(inter(a,b))
return true;
else
return inter(b,a);
}
и это интер:
bool inter(ScreenObject & a,ScreenObject & b) {
if(a->getsx()>b->getsx()) {
if(a->getsx()<b->getSxmax()) {
if(a->getsy()>b->getsy())) {
if(a->getsy<b->getSymax()) {
return true;
}
} else {
if(b->getsy()>a->getsy())) {
if(b->getsy<a->getSymax()) {
return true;
}
}
}
}
}
return false;
}
getsx / getsy возвращает минимальное значение x / y (т.е. левый нижний угол объекта), тогда как getSxmax / getSymax возвращает максимум. Мой вопрос заключается в том, есть ли способ сделать этот код лучше, так как в настоящее время он выглядит довольно плохо выполненным.
Решение
Вы правы. Это довольно грязно. Вы хотите отслеживать прямоугольный экстент каждого объекта:
typedef struct range { int min, max; } RANGE;
typedef struct bb { RANGE x, y; } BOUNDING_BOX;
Ключевой операцией является обнаружение того, что есть нет перекрываются в одном измерении, определяя, что объект A должен лежать по обе стороны от B. Это дизъюнктность:
bool disjoint(RANGE *a, RANGE *b) { return b->max < a->min || b->min > a->max; }
Теперь мы можем использовать это дважды, чтобы обнаружить, что в 2d нет перекрытия:
bool disjoint(BOUNDING_BOX *a, BOUNDING_BOX *b) {
return disjoint(&a->x, &b->x) || disjoint(&a->y, &b->y);
}
Конечно, столкновение является логическим дополнением непересекающихся, по крайней мере, для прямоугольных объектов.
Для других фигур вы все еще можете использовать прямоугольные экстенты, чтобы исключить большую часть затрат на испытания на столкновение. Если экстенты не пересекаются, вы уверены, что столкновения нет. Если они не пересекаются, вы должны выполнить более дорогие тесты на столкновение общих многоугольников. Есть некоторая основная информация Вот. Но есть несколько больших книг на эту тему.
Для @DanielKO, которому не нравятся соглашения C, даже если они выражают вычисления более кратко, чем OO для этого вопроса; Также опуская конструктор и другой шаблон:
class Extent {
public:
bool isDisjointWithRespectTo(Extent &other) {
return max < other.min || other.min > max;
}
private:
int min, max;
}
class BoundingBox {
public:
bool isDisjointWithRespectTo(BoundingBox &other) {
return x.isDisjointWithRespectTo(other.x) || y.isDisjointWithRespectTo(other.y);
}
bool intersectsWith(BoundingBox &other) { return !isDisjointWithRespectTo(other); }
private:
Extent x, y;
}
Конструкторы должны убедиться, min а также max правильно заказаны в обеих версиях.
Другие решения
Других решений пока нет …
detector