Ответ 1
Ниже приведено объяснение столкновений круг/прямоугольник, но обратите внимание, что этот тип столкновения может не понадобиться для ваших нужд. Если, например, у вас была прямоугольная ограничительная рамка для вашего персонажа, алгоритм будет проще и быстрее. Даже если вы используете круг, вероятно, существует более простой подход, который достаточно хорош для ваших целей.
Я хотел бы написать код для этого, но это займет слишком много времени, поэтому вот только объяснение:
Вот пример движения вашего круга персонажей с его последними (предыдущими) и текущими позициями. Над ним отображается прямоугольник.
Вот то же самое движение, пунктирные линии представляют площадь, в которой этот круг перемещается. Область подметания имеет форму капсулы.
Было бы сложно вычислить столкновение этих двух объектов, поэтому нам нужно сделать это по-другому. Если вы посмотрите на капсулу на предыдущем изображении, вы увидите, что это просто линия движения, протянутая во всех направлениях радиусом круга. Мы можем переместить это "расширение" от линии движения к прямоугольнику стены. Таким образом, мы получаем округленный прямоугольник, как на изображении ниже.
Линия движения столкнется с этим расширенным (округленным) прямоугольником тогда и только тогда, когда капсула столкнется с прямоугольником стены, поэтому они как-то эквивалентны и взаимозаменяемы.
Поскольку этот расчет столкновений по-прежнему является нетривиальным и относительно дорогостоящим, вы можете сначала выполнить быструю проверку столкновения между расширенным прямоугольником стены (без округления в этот раз) и ограничивающим прямоугольником линии движения. Вы можете видеть эти прямоугольники на изображении ниже - они оба пунктирны. Это быстрый и простой расчет, и пока вы играете в игру, вероятно, НЕ будет перекрываться с конкретным прямоугольником стены > 99% времени, и здесь будет остановлен расчет столкновений.
Если, однако, существует перекрытие, возможно, столкновение круга символов с прямоугольником стены, но это не точно, как будет показано позже.
Теперь вам нужно рассчитать пересечение самой линии движения (а не ее ограничивающей рамки) и расширенного прямоугольника. Вероятно, вы можете найти алгоритм, как это сделать в Интернете, искать пересечение линий/прямоугольников или пересечение линий/абаб (aabb = Axis Aligned Bounding Box). Прямоугольник выравнивается по оси, что упрощает расчет. Алгоритм может дать вам точку пересечения или точки, так как возможно, что есть два - в этом случае вы выбираете ближайший к начальной точке линии. Ниже приведен пример этого пересечения/столкновения.
Когда вы получаете точку пересечения, вам должно быть легко подсчитать, на какой части расширенного прямоугольника это пересечение находится. Вы можете видеть эти части на изображении выше, разделенные красными линиями и отмеченные одной или двумя буквами (l - левая, r - правая, b - нижняя, t - верхняя, tl - верхняя и левая и т.д.).
Если пересечение находится на частях l, r, b или t (однобуквенные, посередине), тогда вы закончите. Существует определенно столкновение между кругом персонажей и прямоугольником стены, и вы знаете, с какой стороны. В приведенном выше примере он находится на нижней стороне. Вероятно, вы должны использовать 4 переменные, называемые как isLeftCollision, isRightCollision, isBottomCollsion и isTopCollision. В этом случае вы установите для параметра isBottomCollision значение true, а остальные 3 останутся на false.
Однако, если пересечение находится на углу, на двухбуквенных участках необходимы дополнительные вычисления, чтобы определить, существует ли фактическое столкновение между кругом персонажей и прямоугольником стены. На рисунке ниже показаны 3 таких пересечения по углам, но есть фактическое столкновение по прямоугольному прямоугольнику только на 2 из них.
Чтобы определить, есть ли столкновение, вам нужно найти пересечение между линией движения и окружностью, центрированной в ближайшем углу оригинального недлинного прямоугольника стены. Радиус этого круга равен радиусу круга символов. Опять же, вы можете google для алгоритма пересечения линии/круга (может быть, даже у libgdx есть один), это не сложно и не сложно найти.
Не существует пересечения линий/кругов (и не сталкивается с кругом/прямоугольником) на bl-части, и есть пересечения/столкновения на br и tr частях.
В случае br вы устанавливаете как isRightCollision, isBottomCollsion в true, так и в tr-случае вы устанавливаете как isRightCollision, так и isTopCollision значение true.
Существует также один крайный кейс, на который нужно обратить внимание, и вы можете увидеть его на изображении ниже.
Это может произойти, если движение предыдущего шага заканчивается в углу расширенного прямоугольника, но вне радиуса внутреннего прямоугольника (не было столкновения).
Чтобы определить, действительно ли это так, просто проверьте, находится ли точка обзора движения внутри расширенного прямоугольника.
Если это так, после первоначального теста на перекрытие прямоугольника (между расширенным прямоугольником и ограничивающим прямоугольником линии движения), вы должны пропустить тест пересечения линии/прямоугольника (потому что в этом случае не может быть никакого пересечения И все равно будет столкновением круг/прямоугольник), а также просто на основе точки указания движения определяют, в каком углу вы находитесь, а затем проверяете только пересечение линии/круга с этим угловым кругом. Если есть пересечение, возникает столкновение с символом круга/стены, иначе нет.
После этого код столкновения должен быть простым:
// x, y - character coordinates
// r - character circle radius
// speedX, speedY - character speed
// intersectionX, intersectionY - intersection coordinates
// left, right, bottom, top - wall rect positions
// I strongly recomment using a const "EPSILON" value
// set it to something like 1e-5 or 1e-4
// floats can be tricky and you could find yourself on the inside of the wall
// or something similar if you don't use it :)
if (isLeftCollision) {
x = intersectionX - EPSILON;
if (speedX > 0) {
speedX = 0;
}
} else if (isRightCollision) {
x = intersectionX + EPSILON;
if (speedX < 0) {
speedX = 0;
}
}
if (isBottomCollision) {
y = intersectionY - EPSILON;
if (speedY > 0) {
speedY = 0;
}
} else if (isTopCollision) {
y = intersectionY + EPSILON;
if (speedY < 0) {
speedY = 0;
}
}
[Обновление]
Вот простой и я считаю, что эффективная реализация пересечения сегментов-aabb, которая должна быть достаточно хороша для ваших целей. Это слегка измененный алгоритм Коэн-Сазерленд. Также вы можете проверить вторую часть этого ответа.
public final class SegmentAabbIntersector {
private static final int INSIDE = 0x0000;
private static final int LEFT = 0x0001;
private static final int RIGHT = 0x0010;
private static final int BOTTOM = 0x0100;
private static final int TOP = 0x1000;
// Cohen–Sutherland clipping algorithm (adjusted for our needs)
public static boolean cohenSutherlandIntersection(float x1, float y1, float x2, float y2, Rectangle r, Vector2 intersection) {
int regionCode1 = calculateRegionCode(x1, y1, r);
int regionCode2 = calculateRegionCode(x2, y2, r);
float xMin = r.x;
float xMax = r.x + r.width;
float yMin = r.y;
float yMax = r.y + r.height;
while (true) {
if (regionCode1 == INSIDE) {
intersection.x = x1;
intersection.y = y1;
return true;
} else if ((regionCode1 & regionCode2) != 0) {
return false;
} else {
float x = 0.0f;
float y = 0.0f;
if ((regionCode1 & TOP) != 0) {
x = x1 + (x2 - x1) / (y2 - y1) * (yMax - y1);
y = yMax;
} else if ((regionCode1 & BOTTOM) != 0) {
x = x1 + (x2 - x1) / (y2 - y1) * (yMin - y1);
y = yMin;
} else if ((regionCode1 & RIGHT) != 0) {
y = y1 + (y2 - y1) / (x2 - x1) * (xMax - x1);
x = xMax;
} else if ((regionCode1 & LEFT) != 0) {
y = y1 + (y2 - y1) / (x2 - x1) * (xMin - x1);
x = xMin;
}
x1 = x;
y1 = y;
regionCode1 = calculateRegionCode(x1, y1, r);
}
}
}
private static int calculateRegionCode(double x, double y, Rectangle r) {
int code = INSIDE;
if (x < r.x) {
code |= LEFT;
} else if (x > r.x + r.width) {
code |= RIGHT;
}
if (y < r.y) {
code |= BOTTOM;
} else if (y > r.y + r.height) {
code |= TOP;
}
return code;
}
}
Вот пример использования кода:
public final class Program {
public static void main(String[] args) {
float radius = 5.0f;
float x1 = -10.0f;
float y1 = -10.0f;
float x2 = 31.0f;
float y2 = 13.0f;
Rectangle r = new Rectangle(3.0f, 3.0f, 20.0f, 10.0f);
Rectangle expandedR = new Rectangle(r.x - radius, r.y - radius, r.width + 2.0f * radius, r.height + 2.0f * radius);
Vector2 intersection = new Vector2();
boolean isIntersection = SegmentAabbIntersector.cohenSutherlandIntersection(x1, y1, x2, y2, expandedR, intersection);
if (isIntersection) {
boolean isLeft = intersection.x < r.x;
boolean isRight = intersection.x > r.x + r.width;
boolean isBottom = intersection.y < r.y;
boolean isTop = intersection.y > r.y + r.height;
String message = String.format("Intersection point: %s; isLeft: %b; isRight: %b; isBottom: %b, isTop: %b",
intersection, isLeft, isRight, isBottom, isTop);
System.out.println(message);
}
long startTime = System.nanoTime();
int numCalls = 10000000;
for (int i = 0; i < numCalls; i++) {
SegmentAabbIntersector.cohenSutherlandIntersection(x1, y1, x2, y2, expandedR, intersection);
}
long endTime = System.nanoTime();
double durationMs = (endTime - startTime) / 1e6;
System.out.println(String.format("Duration of %d calls: %f ms", numCalls, durationMs));
}
}
Это результат, который я получаю от выполнения этого:
Intersection point: [4.26087:-2.0]; isLeft: false; isRight: false; isBottom: true, isTop: false
Duration of 10000000 calls: 279,932343 ms
Обратите внимание, что это производительность настольных ПК на процессоре i5-2400. Это, вероятно, будет намного медленнее на устройствах Android, но я считаю, что их больше, чем достаточно.
Я только тестировал это поверхностно, поэтому, если вы обнаружите какие-либо ошибки, сообщите мне.
Если вы используете этот алгоритм, я считаю, что вам не нужна специальная обработка для этого случая, когда начальная точка находится в углу расширенного прямоугольника стены, так как в этом случае вы получите точку пересечения при запуске линии, а процедура обнаружения столкновений будет продолжаться до следующего шага (столкновение по кругу).