Оптимизация кода столкновения объектов

[Asker13]

Всем привет.
Помогите разобраться, как лучше организовать обработку столкновений, как можно оптимизировать код.
Итак, в общем есть проект, карта генерируется рандомно, объекты создаются рандомно. Есть модель "игрок", есть модель "блок". Игрок может взаимодействовать с блоком, при этом скорость игрока передаётся блоку, пока без учёта массы блока, но с учётом трения (блок останавливается). При этом блок может взаимодействовать с другими блоками. При этом если блок заходит за экран, то он меняет своё направление на противоположное и опят проверяется столкновение с другими объектами. У меня в проекте всё это проверяется рекурсивно. Так вот какие проблемы возникают:
- Блоки могут немного "наползать" друг на друга;
- Игрок иногда может "проскочить" сквозь блок;
Я не собираюсь создавать физ. движок, помогите разобраться только с этими недочётами.
Проект во вложении. Код обработки столкновений в модуле MPhysics.pas в папке Modules. Код прокомментирован.
Спасибо за внимание.

[Beermonza]

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

[Asker13]

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

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

массив в массиве

Мощно. Можно попробовать. А массив, который в массиве, должен унаследовать позиции всех остальных объектов при их перемещении, я так понимаю? Не совсем ясно, можно чуть подробней?

[Beermonza]

В момент проверки, суть, все объекты статичны, известно их местоположение со всеми смещениями и габаритами. Внешний цикл берет каждый проверяемый объект, внутренний цикл перебирает еще раз все объекты, кроме текущего по первому циклу. У тебя что-то похожее, но какие-то флаги Checked, ...процедуры UncheckBlocks, Collision, Colis, ...если словесно опишешь работу, постараюсь помочь.

...я извиняюсь, напечатал:

массив в массиве

...правильно будет: цикл в цикле, ...это у меня свои проблемы с массивами, я и сюда по ошибке напечатал мысли по ходу дела.

[Asker13]

Честно говоря, я сам запутался...
Сейчас новый код написал обработки столкновений, более ясный, понятный, но ... не работает. В общем, сейчас проверка столкновений идёт следующим образом:
1) Проверяется пересечения всех объектов с игроком. Если проверка прошла, то присваиваем блоку(объекту) ускорение игрока по X и по Y;
2) После проверки, начинается проверка пересечения каждого блока с другими блоками, пока пересечения не прекращаться. Вот такой вот код (который и не работает...)

procedure BlocksCollision();
var
  i, j: byte;
begin
  CollisionFlag := true;
  while CollisionFlag do begin
    CollisionFlag := false;
    for i := 0 to High(Blocks) do
      for j := i+1 to High(Blocks) do
        if Collision(
           Round(Blocks[i].PosX),
           Round(Blocks[j].PosX + Blocks[j].SizeX),
           Round(Blocks[i].PosX + Blocks[i].SizeX),
           Round(Blocks[j].PosX),

           Round(Blocks[i].PosY),
           Round(Blocks[j].PosY + Blocks[j].SizeY),
           Round(Blocks[i].PosY + Blocks[i].SizeY),
           Round(Blocks[j].PosY)) then begin
            CollisionFlag := true;
            Blocks[j].PosX := Round(Blocks[j].PosX + Blocks[i].AccX*1.3)+3;
            Blocks[j].PosY := Round(Blocks[j].PosY + Blocks[i].AccY*1.3)+3;
            break;
        end;
  end;
end;

P.S. Проверки выхода за пределы экрана пока убраны.
P.S. +3 стоит затем, что некоторые блоки после рандомного расставления пересекаются и не имеют начального ускорения.

[Beermonza]

Тебя запутала функция вот эта:

function Collision(X1, X2, X3, X4, Y1, Y2, Y3, Y4: smallint): boolean;
begin
  Result := false;
  if (X1 <= X2) and (X3 <= X4) and (Y1 <= Y2) and (Y3 <= Y4) then Result := true;
end;

Давай подумаем. Может ли быть одна и та же помеха сразу с четырех сторон? ...не может. А если сравнение иное, то оно учитывает только одну из сторон для двух объектов, смотря как поместить в функцию аргументы. Условий ведь не видно сразу и легко напутать. Задача - схватить один объект и проверить все остальные по очереди на предмет столкновения с одной из сторон. Смотрим:

  // i - проверяемый объект
  // j - возможная помеха его движению

  // если помеха слева
  if (Blocks[j].PosX + Blocks[j].SizeX >= Blocks[i].PosX)
      // ИЛИ! помеха справа  
      Or (Blocks[i].PosX + Blocks[i].SizeX >= Blocks[j].PosX)
      // или помеха сверху      
      Or (Blocks[j].PosY + Blocks[j].SizeY >= Blocks[i].PosY)
      // или помеха снизу
      Or (Blocks[i].PosY + Blocks[i].SizeY >= Blocks[j].PosY) then Result := true;

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

[Asker13]

Твой код не будет работать корректно, потому что если даже допустить, что по X объекты пересеклись, то по Y они могут быть на приличном расстоянии друг от друга.
Функция Collision вообще корректно работает: когда я проверял её на одном объекте, всё было успешно (да и на нескольких объектах она тоже работает).
Сегодня уже не буду возвращаться к проекту... завтра продолжу разбираться. Если будут какие-то сдвиги, обязательно напишу.

[Beermonza]

Не нашел еще проблемы? Вот посмотри рабочую функцию определения столкновений:

// =============================================================================
// Обработка столкновений
// =============================================================================
function Collision(Px, Py, Pw, Ph, Bx, By, Bw, Bh: Word): Boolean;
begin
  Result := False;
  //    [        помеха слева              ]  или  [     помеха справа              ]
  If (((Bx < Px) And (Bx + Bw >= Px)) Or ((Bx > Px) And (Bx <= Px + Pw)))
      //     [        помеха сверху             ]  или  [     помеха снизу               ]
      And (((By < Py) And (By + Bh >= Py)) Or ((By > Py) And (By <= Py + Ph))) then Result := True;
end;

Думаю, все понятно по входящим параметрам, ...это по четыре значения для проверяемого объекта и возможного объекта препятствия: X (координата), Y (координата), W (ширина), H (высота).

[Asker13]

Beermonza, спасибо за код, но повторюсь, что та функция рабочая. Не работало, потому, что я запутался в параметрах и передавал их не в том порядке. Но всё равно проблема такая, что блоки могут как резко "перепрыгивать" друг через друга, так и нормально сталкиваться. Часто случается зацикливание, а почему - я не могу понять. Думаю, что одна из причин - это вхождение одного блока в другой и при том блок вошедший не обладает ускорением, а потому не может "выйти" из другого блока. Происходит зацикливание, потому что именно эти два блока постоянно пересекаются.
...
Нужно вот такое: игрок толкает блок, блок обретает ускорение и при столкновении с другим блоком передаёт ему ускорение, а сам располагается ровно по контуру другого блока, то есть не заходит за его границы... как-то так. Было бы проще всё это реализовать, двигаясь игрок только вверх, вниз, влево, вправо, а так он может поворачиваться на все 360 градусов, и не могу никак додумать, как же "выровнять блок по контуру другого блока"... ну может я немного коряво объяснил, с детства отличаюсь костноязычностью. =)

Картиночка:

[Beermonza]

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