Допустим есть большое бильярдное поле, на нем шары. Потери при соударениях небольшие, поэтому пущеный шар вполне может расшевелить все остальные.

Задача алгоритма — расчитывать положения шаров во времени, оптимально по времени и памяти. Или, (если это поможет) только соударения с границами поля.

В голову приходит только самый очевидный и очень медленный способ просчета. А может есть и другие?

PS. Кручения можно не учитывать.

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

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

А>Задача алгоритма — расчитывать положения шаров во времени, оптимально по времени и памяти. Или, (если это поможет) только соударения с границами поля.

А>В голову приходит только самый очевидный и очень медленный способ просчета. А может есть и другие?

А>PS. Кручения можно не учитывать.


тебе надо функции x(t), y(t), x,y — координата шара, t — время ?

если да — то опередляешь границы поля, например, x E (0, w); y E (0, h); E — принадлежит, w,h — ширина, высота поля.

возмем один шар

придаем ему импульс — дальше он сам катится...

x(t), y(t) — будут циклическими функциями, наподобие синуса, но не плавно ( c переменным ускорением ), а с постоянным.

то есть, например, при скорости (поx, поy) = (3,5), и (w,h) = (10, 10) :

t 0  1  2         3           4
x 0  3  6         9           2*w-(9+3)=8
y 0  7  2*h-14=6  -1*(6-7)=1  1+7=8

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

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


p.s.
только идея, но вдруг поможет...

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

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

Да, но шаров много, они могут соударятся между собой и менять направление, некоторые недостигая борта. Как с этим?

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

А>В голову приходит только самый очевидный и очень медленный способ просчета. А может есть и другие?

Мы как-то пытались решить похожую задачу самостоятельно, но потом плюнули и стали использовать ODE.

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

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

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

А>Да, но шаров много, они могут соударятся между собой и менять направление, некоторые недостигая борта. Как с этим?

координаты шара (х, y, t) x(t) и y(t) некоторые функции.
если не учитывать потери энергии на трение и кручение, то от сооударения до соударения шары движутся по прямой в трехмерном пространстве.
соответственно можно посчитать ближайший момент соударения для каждого из шаров.
сооударений 2 типа.
1) о борт — считается вообще тривиально.
2) о другой шар — пересечение двух цилинров в пространстве. (находишь ближайшие точки 2х скрещивающихся прямых и проверяшь больше это суммы радиусов или нет, если меньше, то придется еще немного повозиться, но кажется не сложно)

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

надеюсь вы не подразумевали под самым тупым решением этот вариант.

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

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

А>Задача алгоритма — расчитывать положения шаров во времени, оптимально по времени и памяти. Или, (если это поможет) только соударения с границами поля.

А>В голову приходит только самый очевидный и очень медленный способ просчета. А может есть и другие?

А>PS. Кручения можно не учитывать.

Мне в свое время пришел в голову такой способ:
Рассчитываются все времена ближайших столкновений шаров: каждого с бортами и каждого с каждым. Из этого набора выбирается наименьшее время. В течении этого времени все шары катятся прямолинейно и равномерно. При достижении этого момента времени пересчитывается направление и скорость столкнувшихся шаров (или шара, если с бортом) и происходит пересчет всех его возможных соударений. Опять выбирается наименьшее время и т.д.
Рассчет столкновения с бортом тривиален. А вот рассчет столкновения двух шаров немного посложнее.
Пусть есть 2 шара: S1 и S2. В текущий момент времени они характеризуются положением их центров на столе S1x01, y01), S2x02, y02) и скоростями: S1Vx1, Vy1), S2Vx2, Vy2). Тогда в момент соударения расстояние между центрами шаров будет 2r, где r-радиус шара.
Положение шара в момент времени t: (x0+Vx*t, y0+Vy*t).
Получаем уравнение:
(x01+Vx1*t-x02-Vx2*t)^2 + (y01+Vy1*t-y02-Vy2*t)^2 = (2r)^2
Решая его, получаем время столкновения. Если корней нет, то и столкновения тоже не предвидится.

Разлет шаров после столкновения тоже рассчитывается несложно. В кратце: нужно получить проекции скоростей шаров на линию, соединяющую центры шаров в момент столкновения и на перпендикуляр к этой линии. В случае упругого соударения нужно просто поменять проекции скоростей на линию центров местами (с одного шара на другой). Если механизм сложнее, то нужен пересчет соответствующий.

Столкновение шар-шар:

        /// <summary>
        /// Столкновение двух шаров с потерей энергии, 
        /// но при отсутствии касательного трения. Не учитывается вращение тел.
        /// </summary>
        /// <param name="n">единичный!!! вектор направления от центра шара 1 до центра шара 2</param>
        /// <param name="v1_up">скорость 1-го шара до столкновения</param>
        /// <param name="v2_up">скорость 2-го шара до столкновения</param>
        /// <param name="m1">масса 1-го шара</param>
        /// <param name="m2">масса 2-го шара</param>
        /// <param name="v1_after">скорость 1-го шара после столкновения</param>
        /// <param name="v2_after">скорость 2-го шара после столкновения</param>
        /// <param name="e"> коэффициент восстановления. 1 - без потери энергии
        /// 0 - с полной потерей энергии.</param>
        public static void Collision2DBB(Vector2D n, Vector2D v1_up, Vector2D v2_up, float m1, float m2, out Vector2D v1_after, out Vector2D v2_after, float e)
        {
            // для решения задачи используем систему координат восстановленную
            // на векторах касания и нормали в точке столкновения.
            // n  - это заданный ед. вектор нормального направления
            // а это вектор касательной (на 90 град против часовой стрелки от n)
            Vector2D t = new Vector2D(-n.Y, n.X);

            // находим проекции векторов скорости в новой системе координат
            // до столкновения
            float v1_upn = v1_up * n;
            float v1_upt = v1_up * t;
            float v2_upn = v2_up * n;
            float v2_upt = v2_up * t;
            // находим проекции векторов скорости в новой системе координат
            // после столкновения
            float v1_aftern = (1 + e) * m2 * v2_upn + (m1 - e * m2) * v1_upn;
            v1_aftern = v1_aftern / (m1 + m2);
            float v1_aftert = v1_upt; // ввиду отсутствия трения
            float v2_aftern = (1 + e) * m1 * v1_upn + (m2 - e * m1) * v2_upn;
            v2_aftern = v2_aftern / (m1 + m2);
            float v2_aftert = v2_upt; // ввиду отсутствия трения

            // переходим к старым декартовым координатам
            v1_after = new Vector2D();
            v1_after.X = v1_aftern * n.X + v1_aftert * t.X;
            v1_after.Y = v1_aftern * n.Y + v1_aftert * t.Y;

            v2_after = new Vector2D();
            v2_after.X = v2_aftern * n.X + v2_aftert * t.X;
            v2_after.Y = v2_aftern * n.Y + v2_aftert * t.Y;

        }

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

    /// <summary>
    /// Кинетика мяча. Закон движения.
    /// </summary>
    /// <param name="elapsedTime"></param>
    /// <param name="bl"></param>
    public void MoveBallGravity(float elapsedTime, Ball bl)
    {
        //Равномерное прямолинейное движение
        //
        //bl.Position = bl.Position + bl.Speed * elapsedTime;
        Vector2D g = new Vector2D(0, -500); // ускорение свободного падения

        bl.Speed = bl.Speed  + g * elapsedTime;
        bl.Position = bl.Position + bl.Speed * elapsedTime + g * 0.5f*elapsedTime*elapsedTime;
    }

Бильярдное же поле можно рассматривать как как пары шаров (i,j) , причем (i,j)==(j,i).
Анализ столкновений — вполне решаемая (причем — бысторо) алгоритмическая задача.


Если нужно учесть момент инерции тела посмотрите, например, в книгу
Бутенин, Лунц, Меркин "Курс теоретической механики", где решается
даже более общая задача (в главе 17 — теория удара). Причем, можно даже
смещать центр инерции тела.

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

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

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

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

А>Задача алгоритма — расчитывать положения шаров во времени, оптимально по времени и памяти. Или, (если это поможет) только соударения с границами поля.

А>В голову приходит только самый очевидный и очень медленный способ просчета. А может есть и другие?

А>PS. Кручения можно не учитывать.

Следует выбрать один из двух алгоритмов, в зависимости от того, какие механические свойства системы должны быть воспроизведены.
Первый уже описали --- расчет времени очередного столкновения.
Второй --- пошаговое интегрирование уравнений движения вазимодействующих шаров. Метод интегрирования -- leap-frog или вовсе Эйлер. Шары представляются материальными точками, которые отталкиваются с силой (r/d)^(-n), если расстояние между шарами r меньше диаметра шара.

Если в этой задаче никакой физики не преследуется, то гораздо проще использовать второй метод.