Дано: растровое ч/б изображение (без градаций серого, т.е.2 цвета) и объект, формами которого можно пренебречь, то бишь округлим до шарика (x,y,r). Радиус шарика больше размера пикселя.
Найти: разработать алгоритм обработки столкновения шарика и растра, чтобы это выглядяло физическим верным (тобишь шарик отскакивал в верном направлении, угол падения равно угол отражения).
Условия:Растровое изображение может быть жутко заковыристым (включая отдельно стоящие пиксели), "шариков" может быть достаточно много (штук 20 вполне реально), обрабатывать необходимо в режиме реального времени.
Существующий пример: серия Worms — поле боя — растр, граната — объект, формами которого можно пренебречь. Различие в том, что там гранату "сжимают" до точки, а необходимо до шарика.

Здравствуйте, Fitus, Вы писали:

F>Дано: растровое ч/б изображение (без градаций серого, т.е.2 цвета) и объект, формами которого можно пренебречь, то бишь округлим до шарика (x,y,r). Радиус шарика больше размера пикселя.
F>Найти: разработать алгоритм обработки столкновения шарика и растра, чтобы это выглядяло физическим верным (тобишь шарик отскакивал в верном направлении, угол падения равно угол отражения).
F>Условия:Растровое изображение может быть жутко заковыристым (включая отдельно стоящие пиксели), "шариков" может быть достаточно много (штук 20 вполне реально), обрабатывать необходимо в режиме реального времени.
F>Существующий пример: серия Worms — поле боя — растр, граната — объект, формами которого можно пренебречь. Различие в том, что там гранату "сжимают" до точки, а необходимо до шарика.

Вообще-то все зависит от соотношения масштабов шарик/растровое поле/шаг движения шарика за ед. времени (такт, кадр). Насколько меняется скорость шарика?

Банальные фантазии (если шарик движется медленно). Смотрим, попадают ли точки растра в квадрат, охватывающий шарик. Точки есть смысл искать в направлении движения шарика, т.е. со смещением dx, dy. Для тех, которые попадают в квадрат, смотрим, не пересекаются ли с шариком, вычисляя расстояние (возможно с учетом движения шарика). Дальше — сумируем их силы/моменты, т.е. как бы действуем по используемой физической модели.

Задачку можно ускорить, если для шарика тоже построить растровую маску, тогда не надо вычислять расстояния, а только смотреть пересекаются ли точки растра и маски шарика. Эту маску можно как бы "гнать" перед шариком по его движению. Это имет смысл, когда шарик за такт проходит рассояние меньше своего радиуса. Еще ускорить, если растровое поле заранее побить на квадратики со стороной в несколько пискселов и посчитать кол-во пикселов в каждом — можно игнорировать пустые.

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

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

Ну и еще. Я фантазирую, а в играх вобщем-то задача довольно хорошо объезжена,имхо. Забыл, как она там называется, что-то вроде hit test. Алгоритмы, думаю, хорошо отработаны.

Здравствуйте, goto, Вы писали:

G>Вообще-то все зависит от соотношения масштабов шарик/растровое поле/шаг движения шарика за ед. времени (такт, кадр). Насколько меняется скорость шарика?

Шарик — 5-20 пикселей диаметр, растр — минимум 1000х1000 точек, Шаг шарика может превышать размеры шарика (мин — 1 пиксель, макс — 40-50 пикселей).

G>Банальные фантазии (если шарик движется медленно). Смотрим, попадают ли точки растра в квадрат, охватывающий шарик.(...)
G>Задачку можно ускорить, если для шарика тоже построить растровую маску, тогда не надо вычислять расстояния, (...)

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

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

А это не слишком трудоемкий процесс при больших скоростях большом количестве шариков? Не уверен, что это в реальном времени работать будет...

G>Оптимизаций можно придумать много. Вообще задачка может оказаться вязкой, если все делать очень честно и не вводить насильственные правила и упрощения. Зависит от подробностей.

Упрощения вводить можно сколько угодно, главное условие — чтобы глаз не цеплялся за кривую физику отскока. Абсолютно точных результатов не надо.

G>Ну и еще. Я фантазирую, а в играх вобщем-то задача довольно хорошо объезжена,имхо. Забыл, как она там называется, что-то вроде hit test. Алгоритмы, думаю, хорошо отработаны.

Обшарил инет где мог и где знал, ниодного подобного алгоритма не нашел если кто найдет — киньте ссылочку.

Немного подумав пришел к мысли разработать алгоритм, когда шарик "сжимаем" в точку (как в worms'ах, тобишь диаметр к одному пикселю сводим). Здесь есть только одна загвоздка — узнать угол отражения (но как ее решать я тоже не в курсе . А после этого натыкать на шарик штук 8 контрольных точек, каждую из которых обрабатывать отдельно, но совместно... однако возникает проблемма маленьких растров, которые могут случайно пройти насквозь шарика, не попав на эти контрольные точки.

Забыл залогинится, прошлое сообщение от меня

Здравствуйте, Аноним, Вы писали:


А>Шарик — 5-20 пикселей диаметр, растр — минимум 1000х1000 точек, Шаг шарика может превышать размеры шарика (мин — 1 пиксель, макс — 40-50 пикселей).

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

G>>Банальные фантазии (если шарик движется медленно). Смотрим, попадают ли точки растра в квадрат, охватывающий шарик.(...)
G>>Задачку можно ускорить, если для шарика тоже построить растровую маску, тогда не надо вычислять расстояния, (...)

А>Данное вроде не подходит, так как шаг может быть достаточно крупным. Покрайней мере я не знаю как это прикрутить...

Надо дробить таректорию, просчитывать подробно между кадрами, чтобы было физично и чтобы не проскакивать свозь стены. Для каждого шарика можно участок траектории между кадрами разбить так, чтобы за такт счета он проходил расстояние меньше своего радиуса. В каждом такте есть вектор скорости dx, dy. При возможном отскоке он поменяется, ну и считаем дальше все промежуточные такты до конца кадра. В конце кадра рисуем.

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

А>А это не слишком трудоемкий процесс при больших скоростях большом количестве шариков? Не уверен, что это в реальном времени работать будет...


То, что я предлагал как вариант. Создать приближенную карту, разбив поле точек на квадраты, сравнимые с размером шарика. В каждом квадрате подсчитать число пикселов (эта приближенная карта легко модифицирруется на лету при изменениях в поле точек). В каждой позиции шарика смотреть, какие квадраты он пересекает. Если в этом квадрате нет пикселов — игнорируем. Считаться будет быстро, нам ведь не надо просматривать всю карту при движении шарика, а только область вокруг самого шарика + подробно считать квадраты только с пикселами, т.е. где может быть столкновение. Общий размер карты на самом деле не имеет значения, т.к. каждый раз просматриваются только окрестности шарика.

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


...

А>Немного подумав пришел к мысли разработать алгоритм, когда шарик "сжимаем" в точку (как в worms'ах, тобишь диаметр к одному пикселю сводим). Здесь есть только одна загвоздка — узнать угол отражения (но как ее решать я тоже не в курсе . А после этого натыкать на шарик штук 8 контрольных точек, каждую из которых обрабатывать отдельно, но совместно... однако возникает проблемма маленьких растров, которые могут случайно пройти насквозь шарика, не попав на эти контрольные точки.

Как должна точка отскакивать от точки науке не известно. Лучше оставить шарик, имхо. Тогда проводится радиус из центра шарика к точке соударения, а вектор скорости зеркалится относительно него. Это в идеале. На практике может иногда выглядеть криво и придется что-то придумывать. К тому же шарик часто будет касаться сразу несколькизх точек одновременно (может тогда их позиции можно просуммировать и осреднить).