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

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

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

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

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

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

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

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