Столкновения прямоугольников.

← →
IPranker © (2011-06-05 20:16) [0]

Всем привет! :)

Вот никак не могу написАть програмку столкновения 2-х прямоугольников. Т.е. передвигаем один прямоугольник, а как
столкнулись с другим (преграда), то не даем ему проехать сквозь него. Наш прямоугольник должен в него какбы упереться.

P.S. Можете "протестить" данный код, надо только положить на форму TTimer с интервалом в 1.
P.S.S. Это нужно для скромной игры.

var FR : TRect; // Местоположение преграды. FX, FY: LongWord; // Наши координаты. FW, FH: LongWord; // Наши ширина и высота. FKeys : array [0..255] of boolean; // Массив клавиш клавиатуры. function KDown(Key: byte): boolean; // Проверка нажатой клавиши. begin Result:= FKeys[Key]; end; procedure ObjectMove(OffSet: LongWord); // Передвигаемся. begin If KDown(VK_UP) then Dec(FY, OffSet) else If KDown(VK_DOWN) then Inc(FY, OffSet) else If KDown(VK_LEFT) then Dec(FX, OffSet) else If KDown(VK_RIGHT) then Inc(FX, OffSet); end; function IsCollide: boolean; // Функция проверяет пересечение с преградой. var R: TRect; begin Result:= InterSectRect(R, Rect(FX, FY, FX + FW, FY + FH), FR); end; procedure TForm1.Timer1Timer(Sender: TObject); begin ObjectMove(10); // Двигаемся со скоростью в 10 единиц. If IsCollide then // Проверяем столкновение с преградой. begin Caption:= "1"; end else Caption:= "0"; Invalidate; end; procedure TForm1.FormPaint(Sender: TObject); begin // Очищаем фон. Canvas.Brush.Color:= clWhite; Canvas.FillRect(Canvas.ClipRect); // Рисуем наш прямоугольльник. Canvas.Brush.Color:= clRed; Canvas.Rectangle(Rect(FX, FY, FX + FW, FY + FH)); // Рисуем преграду. Canvas.Brush.Color:= clBlue; Canvas.Rectangle(FR); end; procedure TForm1.FormCreate(Sender: TObject); begin // Задаём наше местоположение и размеры. FX:= ClientWidth div 2; FY:= ClientHeight div 2; FW:= 50; FH:= 50; // Задаём местоположение и размеры преграды. SetRect(FR, 100, 100, 356, 567); DoubleBuffered:= True; end; procedure TForm1.FormKeyDown(Sender: TObject; var Key: Word; Shift: TShiftState); begin FKeys[Key]:= True; end; procedure TForm1.FormKeyUp(Sender: TObject; var Key: Word; Shift: TShiftState); begin FKeys[Key]:= False; end;

← →
sniknik © (2011-06-05 21:40) [1]

> Вот никак не могу написАть програмку столкновения 2-х прямоугольников.
странные слова рядом с кодом уже написанной программки, в которой все есть (расчеты), и она работает...
откуда тогда "не могу"? или "нарыл" где то код, или на другом форуме дали, но немного не то... и хочешь чтобы его здесь "подогнали"?

> P.S.S. Это нужно для скромной игры.
скорее для сдачи зачета. т.к. писал бы для себя то хотел бы разобраться, и спрашивал по конкретно тому что не получается.

← →
IPranker © (2011-06-05 22:04) [2]

Это мой код.
Комментарии сделал специально, чтобы этот маленький код был понятен любому.
Вот так вот.

← →
sniknik © (2011-06-05 22:11) [3]

> Это мой код.
тогда как такое возможно, написав проверку, не "мочь" ее использовать? т.е. проверить светофор на "красный" и сказать "это красный" можешь, а не идти по нему через улицу нет... странно.
вот как то так.

← →
IPranker © (2011-06-06 16:44) [4]

Я сделал в коде возможность движения прямоугольника.
Проверку наличия столкновения. Т.е. все условия для тестов.
Но не смог сделать возможность "упереться" в преграду.

Как это сделать?

← →
Dimka Maslov © (2011-06-06 17:54) [5]

Рассматривай преграду как дополнительный неподвижный прямоугольник с которым надо определять столкновение.

← →
IPranker © (2011-06-06 18:04) [6]

> Рассматривай преграду как дополнительный неподвижный прямоугольник
> с которым надо определять столкновение.

В коде так и сделано.
Преграда - неподвижный прямоугольник синего цвета.
Наш прямоугольник красный и двигается.

← →
sniknik © (2011-06-06 18:07) [7]

> Но не смог сделать возможность "упереться" в преграду.
т.е. если "столкнулись" то "вернуть координаты назад" не смог реализовать? это шутка юмора такой?

← →
IPranker © (2011-06-06 18:46) [8]

>sniknik © (06.06.11 18:07) [7]

Да я всё время не мог додумать, чего ж не хватает то.
Ведь не понятно в какую сторону вернуть координаты назад.

Ввёл новую переменную - направление.
Всё вроде работает, через преграду наш прямоугольник пройти больше не может.

Но он упирается в нескольких пикселях от преграды, а должен ПЛОТНО упираться.

Помогите додумать, помогите советом. :)

type TDir = (dirNone, dirUp, dirDown, dirLeft, dirRight); var FR : TRect; // Местоположение преграды. FR2 : TRect; // Местоположение преграды 2. FDir : TDir; // Направление движения. FX, FY: LongWord; // Наши координаты. FW, FH: LongWord; // Наши ширина и высота. FKeys : array [0..255] of boolean; // Массив клавиш клавиатуры. function KDown(Key: byte): boolean; // Проверка нажатой клавиши. begin Result:= FKeys[Key]; end; procedure ObjectMove(OffSet: LongWord); // Передвигаемся. begin If KDown(VK_UP) then FDir:= dirUp else If KDown(VK_DOWN) then FDir:= dirDown else If KDown(VK_LEFT) then FDir:= dirLeft else If KDown(VK_RIGHT) then FDir:= dirRight else FDir:= dirNone; Case FDir of dirUp : Dec(FY, OffSet); dirDown : Inc(FY, OffSet); dirLeft : Dec(FX, OffSet); dirRight: Inc(FX, OffSet); end; end; procedure BackMove(OffSet: LongWord); begin Case FDir of dirUp : Inc(FY, OffSet); dirDown : Dec(FY, OffSet); dirLeft : Inc(FX, OffSet); dirRight: Dec(FX, OffSet); end; end; function IsCollide(AR: TRect): boolean; // Функция проверяет пересечение с преградой. var R: TRect; begin Result:= InterSectRect(R, Rect(FX, FY, FX + FW, FY + FH), AR); end; procedure TForm1.Timer1Timer(Sender: TObject); begin ObjectMove(30); // Двигаемся со скоростью в 10 единиц. If IsCollide(FR) or IsCollide(FR2) then // Проверяем столкновение с преградой. begin Caption:= "1"; BackMove(30); end else Caption:= "0"; Invalidate; end; procedure TForm1.FormPaint(Sender: TObject); begin // Очищаем фон. Canvas.Brush.Color:= clWhite; Canvas.FillRect(Canvas.ClipRect); // Рисуем наш прямоугольльник. Canvas.Brush.Color:= clRed; Canvas.Rectangle(Rect(FX, FY, FX + FW, FY + FH)); // Рисуем преграду. Canvas.Brush.Color:= clBlue; Canvas.Rectangle(FR); Canvas.Rectangle(FR2); end; procedure TForm1.FormCreate(Sender: TObject); begin // Задаём наше местоположение и размеры. FX:= ClientWidth div 2; FY:= ClientHeight div 2; FW:= 50; FH:= 50; // Задаём местоположение и размеры преграды. SetRect(FR, 100, 100, 156, 367); SetRect(FR2, 500, 300, 600, 600); DoubleBuffered:= True; end; procedure TForm1.FormKeyDown(Sender: TObject; var Key: Word; Shift: TShiftState); begin FKeys[Key]:= True; end; procedure TForm1.FormKeyUp(Sender: TObject; var Key: Word; Shift: TShiftState); begin FKeys[Key]:= False; end;

← →
Dimka Maslov © (2011-06-06 18:50) [9]

согласно теории "угол падения равен углу отражения". При ударе абсолютно твёрдого тела об абсолютно твёрдое неподвижное тело это правило справедливо. Следовательно, вектор скорости прямоугольника поворачивается на 90° от препятствия.

← →
IPranker © (2011-06-06 18:56) [10]

> Dimka Maslov © (06.06.11 18:50) [9]
>
> согласно теории "угол падения равен углу отражения". При
> ударе абсолютно твёрдого тела об абсолютно твёрдое неподвижное
> тело это правило справедливо. Следовательно, вектор скорости
> прямоугольника поворачивается на 90° от препятствия.

Так и сделал.
Если ехали вверх и врезались, то отъезжаем на противоположную сторону, т.е.
вниз. Инвертировано получается.

← →
Inovet © (2011-06-06 18:57) [11]

> [9] Dimka Maslov © (06.06.11 18:50)
> вектор скорости прямоугольника поворачивается на 90° от препятствия

а как же

> [9] Dimka Maslov © (06.06.11 18:50)
> "угол падения равен углу отражения"

← →
Dimka Maslov © (2011-06-06 19:05) [12]

> Inovet © (06.06.11 18:57) [11]

Согласен, облажался, 90° тут не причём. Следует читать поворачивается от препятствия

> IPranker © (06.06.11 18:56) [10]

Дело не в направлении вектора скорости до удара. А во взаимном положении препятствия и вектора скорости.

При решении подобного рода задач надо начинать не с программирования, а с построения математической модели. И если программа, написанная с использованием математической модели работает неправильно, нужно корректировать математическую модель, а не программу.

← →
IPranker © (2011-06-06 19:09) [13]

> Dimka Maslov © (06.06.11 19:05) [12]

Прямоугольник имеет 4 степени свободы.
Может т.е. двигаться только в 4х направлениях.
Как в классических танчиках.

-----

Мой вопрос в силе, прямоугольник почему-то упирается не до конца.

← →
Inovet © (2011-06-06 19:18) [14]

> [13] IPranker © (06.06.11 19:09)
> Прямоугольник имеет 4 степени свободы.

Очень интересно в каких это 4-х направлениях. В плоскости у него 3 степени свободы.

← →
sniknik © (2011-06-06 19:29) [15]

> Ввёл новую переменную - направление.
???
какое направление, блин, вот честно, чувствуется разница исходного кода и твоих "вставок"

было
ObjectMove(10);

чтобы вернуть
ObjectMove(-10);
все что нужно. не вводя новых сущностей в лаконичный, и правильный в общем код... убрал бы там нажатия клавиш, нафига дублировать системные... переменные "россыпью" свел бы в рект, а то как то странно для одного набора он используется для другого нет, + переменные функции из глобальных сделал объектными. а так ничего нормальный код, твои вставки на порядок хуже, - не лаконичные.

← →
sniknik © (2011-06-06 19:31) [16]

> прямоугольник почему-то упирается не до конца.
ну так "упри" его... "молоточком постучи". делов то там (для писавшего код) раз плюнуть.

← →
Inovet © (2011-06-06 19:36) [17]

> [16] sniknik © (06.06.11 19:31)
> делов то там (для писавшего код) раз плюнуть

Врёт он, что писал.

← →
sniknik © (2011-06-06 19:51) [18]

> Врёт он, что писал.
в том то и дело, решивший "дифур"(ну или, тут попроще, скажем уравнение) и чтобы вдруг не мог понять как к полученному результату 2 прибавить... да ни в жисть.

и еще небось удивляется "а чего не помогают, код же привел, сделал вид что сам что-то делал"... ага, счаз.

← →
Dimka Maslov © (2011-06-06 20:03) [19]

> Очень интересно в каких это 4-х направлениях. В плоскости
> у него 3 степени свободы.

В пространстве-времени на плоскости как раз 4 степени свободы. У нас же релятивистская задача, как я понимаю.

← →
IPranker © (2011-06-06 20:05) [20]

> Очень интересно в каких это 4-х направлениях. В плоскости
> у него 3 степени свободы.

Имелось ввиду 4 направления движения.

> ObjectMove(-10);

Блин, я туплю!

> + переменные функции из глобальных сделал объектными

У меня привычка глобальные переменные объявлять как приватные поля класса. Их по префиксу Ф видно. :)

> переменные "россыпью" свел бы в рект

Ректы для статичных прямоугольников-преград.
А для своего сделал россыпью, чтобы легче манипулировать с координатами.
Хотя да, есть же функция OffsetRect...

> Врёт он, что писал.

Я писАл. Честно.
Просто туплю чё-та. Извините.

> и еще небось удивляется "а чего не помогают, код же привел,
> сделал вид что сам что-то делал"... ага, счаз.

Столкновение вроде как сделал.
Но столкновения то не плотно прилегают какбы.
Т.е. прямоугольник врезается в нескольких пикселях от преграды.

Может быть порядок действий в Таймере не правильный?

← →
IPranker © (2011-06-06 20:13) [21]

4 направления движения - вверх, вниз, влево, вправо. :)

← →
sniknik © (2011-06-06 20:15) [22]

> Может быть порядок действий в Таймере не правильный?
правильный... для той логики которая реализована, а не прилегает потому что дискретность... шаг выбран такой, что есть промежуток между двумя граничными состояниями.

или сделай шаг = 1, или меняй логику на подгонку (что тоже не составит труда писавшему код, потому как - делов то...)

← →
IPranker © (2011-06-06 20:24) [23]

> или сделай шаг = 1,

:)

> или меняй логику на подгонку (что тоже
> не составит труда писавшему код, потому как - делов то...)

Понять не могу, хоть убей. :)

Порядок действий такой:
Переместились на 10 единиц, если врезались, то обратно перемещаемся на 10 единиц. Вроде бы всё логично.
Но работает не так как надо.

← →
Inovet © (2011-06-06 20:39) [24]

> [19] Dimka Maslov © (06.06.11 20:03)
> У нас же релятивистская задача, как я понимаю.

А, так вот почему он никак не может долететь до стенки - это же не стенка, а горизонт событий чёрной дыры.

← →
Dimka Maslov © (2011-06-06 21:41) [25]

> это же не стенка, а горизонт событий чёрной дыры.

Причём сам прямоугольник находится внутри. Чтож, современная физика такое допускает.

← →
MonoLife © (2011-06-07 04:48) [26]

> Переместились на 10 единиц, если врезались, то обратно перемещаемся
> на 10 единиц. Вроде бы всё логично.

лучше, имхо, не так
если врезались, то положение красного нужно указывать относительно синего с учетом его ширины и высоты, т.е. впритык.

← →
han_malign (2011-06-07 10:03) [27]

> Переместились на 10 единиц, если врезались, то обратно перемещаемся
> на 10 единиц.

- а если пересеклись, смотрим на сколько "единиц" надо уменьшить последний шаг, перерассчитываем граничное состояние...

Для гладкости рендеринга граничные состояния надо предсказывать, то есть считать на шаг вперед...

> Case FDir of
> dirUp : Dec(FY, OffSet);
> dirDown : Inc(FY, OffSet);
> dirLeft : Dec(FX, OffSet);
> dirRight: Inc(FX, OffSet);
> end;

- вообще-то, достаточно вектора скорости (vx, vy), при "столкновении" менять знак нужной компоненты...
inc(FY, vy); inc(FX, vx);
или вульгарный OffsetRect...

IPranker, тебе вот что пытаются втолковать, если на пальцах.
Я понял! :)

Между прямоугольниками, например, 5 точек.
Пытаемся сдвинуться на 10
Видим - о, пересекаются - и отпрыгиваем назад на 10.
Но на 5 ведь можно было пододвинуться!
Но т.к. на 5 точек можно было подвинуться (т.е. есть зазор в 5 точек) - то и получается. что "не можем приблизиться вплотную". Т.к. чтобы упереться - надо на 5 точек переместиться.

> [28] KSergey © (08.06.11 12:33)
> и получается. что "не можем приблизиться вплотную"

И не надо. Есть интервал времени, есть скорость, куда тут воткнёшь полное сближение, всё равно будет усреднение. Только интервал времени уменьшить для плавности.

> KSergey © (08.06.11 12:33) [28]

Спасибо, я это уже понял. :)
Вот смотрите, передвигаемся со скоростью 4 единицы, отъезжаем с 2 к примеру.
Наш прямоугольник в таком случаем будет проходишь все равно сквозь преграду.

Просьба показать и объяснить мне на примере.

> если врезались, то положение красного нужно указывать относительно
> синего с учетом его ширины и высоты, т.е. впритык.

А если прямоугольников несколько, то как правильно проверять и относительно каких сторон. Вдруг наш прямоугольник столкнулся с неколькими преградами одновременно. Что тогда?

> Для гладкости рендеринга граничные состояния надо предсказывать,
> то есть считать на шаг вперед...

Все расчеты идут до процедуры оттображения Инвалидат.

> Спасибо, я это уже понял. :)
и как так получается "уже" понимать только после того как разжаловано...

> Вот смотрите ...
ну блин, прям теорема ферма в программировании... два прямоугольника рядом нарисовать после срабатывания какого то условия.

> Просьба показать и объяснить мне на примере.
это ты так свой код "написал" кто то "объяснил" на примере... не до конца. теперь еще "примеры" нужны т.к. сам даже элементарное как 2+2 осилить не можешь.

> А если прямоугольников несколько
по очереди.

> то как правильно проверять
правильно, будет так как будет работать.

> Вдруг наш прямоугольник столкнулся с неколькими преградами одновременно. Что тогда?
петь "алилуя" и славить господа за чудо... т.к. твой код допускает движение только в одном направлении, и значит пересекаться может только с 1 преградой за раз. 2 -чудо, 3 - двойное чудо.
как же ты этого не знаешь если "сам писал"?

> Все расчеты идут до процедуры оттображения Инвалидат.
и что? все одно рывки, дискретность... трудно представить "подъезд" к препятствию с уменьшенным интервалом чтобы он был равномерным?
хотя, имхо, лишнее, т.к. не настолько заметно визуально, при заметном усложнении логики, усилий на выполнение.

> > Вдруг наш прямоугольник столкнулся с неколькими преградами
> одновременно. Что тогда?
> петь "алилуя" и славить господа за чудо... т.к. твой код
> допускает движение только в одном направлении, и значит
> пересекаться может только с 1 преградой за раз.

Ну чисто теоретически (при дискретном движении) такое возможно по трем направлениям. Так что учесть всё-таки нужно.
Но сам топик меня весьма смешит. :)

> Ну чисто теоретически (при дискретном движении) такое возможно по трем направлениям. Так что учесть всё-таки нужно.
направление движения в коде одно, столкновение тоже будет одно, то что из-за дискретности его можно "перепрыгнуть" и "вляпаться" еще во что-то, ничего не значит, зачем их учитывать если значимо, и останавливаться нужно перед первым же?

> [30] IPranker © (11.06.11 20:08)
> Вот смотрите, передвигаемся со скоростью 4 единицы, отъезжаем с 2 к примеру.
> Наш прямоугольник в таком случаем будет проходишь все равно сквозь преграду.

Как он будет проходить, когда ты решаешь уравнение движения для t=n и t=n+d которое не имеет решений за краницей преграды.

> Но он упирается в нескольких пикселях от преграды, а должен
> ПЛОТНО упираться.

> А если прямоугольников несколько, то как правильно проверять
> и относительно каких сторон. Вдруг наш прямоугольник столкнулся
> с неколькими преградами одновременно. Что тогда?

Есть предложение решать данную задачу "в лоб":

1) Пробуем сдвинуться на 10. Если обнаружено столкновение, то оно, очевидно, происходит где-то в промежутке между сдвигом на 0 и сдвигом на 10, для краткости обозначим такой отрезок [0, 10].
2) Если имеется столкновение с любым из препятствий, откатываем координаты назад и пробуем сдвинуться на 5.
3) Если все еще имеется столкновение с любым из препятствий, значит точка пересечения находится в отрезке [0, 5]. Соответственно, пробуем 2.5 и снова сужаем отрезок вдвое. Если же при сдвиге на 5 столкновение исчезло, то новый отрезок [5, 10] и стоит пробовать сдвиг на 7.5.
4) Так и ищем точку пересечения методом деления пополам пока не достигнем требуемой точности.

Если требуется решение с целыми координатами, можно тупо перебрать все возможные сдвиги от 0 до 10 и найти на каком начинает появляться столкновение и использовать предыдущий.

Стоит отметить, что для задачи с прямоугольниками и движением вдоль осей данное решение весьма неоптимально. Однако, оно довольно наглядно и просто в реализации, а в игре такого плана производительность не играет решающей роли, если вы не планируете портировать его на айфон :).

> Servy © (15.06.11 04:22) [35]

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

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

Столкновения прямоугольников. Найти похожие ветки