Frogger HD и численное моделирование волн в пруду

    image

    После прочтения статьи про CGA от SLY_G я необычайно возбудился. Вспомнил юность, IBM PC/XT и игру frogger jr, в которой лягушка должна была пересечь дорогу, избежав колес бешено мчавшихся байков. Затем по бревнам допрыгать до тихой заводи. И так до смерти, которых выдавали 4 штуки. Фраю выдали 666, но я не Макс.
    Поплакав о безвозвратно потерянных годах, я решил потерять еще пару дней и сделал ремейк игры под iPad.

    Движение воды в речке решил смоделировать по-правильному, через разностную схему.
    О численном алгоритме моделирования озерных волн и о том, что получилось, читайте дальше.
    Да! забыл сказать.
    Тем, кто может продолжить последовательность
    T T F S E...
    читать будет не особенно интересно.


    image

    Итак, вода. Численно решать уравнения Навье-Стокса на телефонах еще рано. Поэтому я взял модель, любезно увиденную в статье уважаемого господина blind_designer. В работе слепого Пью описан одномерный алгоритм. Я его расширил до двухмерного.

    Модель поверхности воды.


    Представим прямоугольную сетку размером M*N. Сетка лежит на земле, из каждого узла торчит по пружине начальной длиной Lx0[i,j]. Упругость пружины определяется её коэффициентом kx[i,j].

    Набросим легкое покрывало на пружинки — это покрывало и будет моделировать зеркало водоема.

    Под действием внешних сил (камень упал), длины пружинок Lx[i,j] могут измениться. Как мы помним из жизни, волны от брошенного камня рано или поздно успокаиваются.

    Поэтому, заведем еще один массив вязкости пружины mx[i,j]. Если вязкость пружины положить равной 0, то волны никогда не остановятся и будут бесконечно долго отражаться от берегов.

    Численное уравнение для пружинок совсем простое (закон Гука с диссипацией)

       for (int i=0; i<n; i++) {
            float x = Lx[i] - Lx0[i];
            float acceleration = -kx[i] * x - mx[i]*Wx[i];
            Lx[i] += Wx[i]*dt;
            Wx[i] += acceleration*dt;
        } 
    


    Здесь массив Wx[i,j] — вертикальная скорость каждой пружинки. Все просто — ускорение пружины равно коэффициенту упругости умноженному на смещение. А скорость — интеграл от ускорения. А смещение — интеграл от скорости. Шаг по времени dt=1, введен для строгости.

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

    Следите за циклом

        float spread  = 0.025;
        
        // do some passes where springs pull on their neighbours
        for (int iki = 0; iki < 4; iki++) {      // 4 соседа в каждую сторону должны почувствовать градиент
            
       // размазываем по оси х
             for (int j = 0; j < ny; j++) {
                for (int k = 1; k < nx-1; k++) {
                    int i = k + j*nx;
                    lp[i] = spread * (Lx[i] - Lx[i-1]);
                    Wx[i - 1] += lp[i];
                    rp[i] = spread * (Lx[i] - Lx[i + 1]);
                    Wx[i + 1] += rp[i];
                }
            }
            for (int j = 0; j < ny; j++) {
                for (int k = 1; k < nx-1; k++) {
                    int i = k + j*nx;
                    Lx[i - 1] += lp[i];
                    Lx[i + 1] += rp[i];
                }
            }
            
            
        // размазываем по оси y
           for (int j = 1; j < ny-1; j++) {
                for (int k = 0; k < nx; k++) {
                    int i = k + j*nx;
                    lp[i] = spread * (Lx[i] - Lx[i-nx]);
                    Wx[i - nx] += lp[i];
                    rp[i] = spread * (Lx[i] - Lx[i + nx]);
                    Wx[i + nx] += rp[i];
                }
            }
            for (int j = 1; j < ny-1; j++) {
                for (int k = 0; k < nx; k++) {
                    int i = k + j*nx;
                    Lx[i - nx] += lp[i];
                    Lx[i + nx] += rp[i];
                }
            }
        }
    
    


    Массивы lp[] и rp[] — временные, алгоритм сами оптимизируете под свои способности.
    nx — число узлов вдоль оси x, ny — число узлов вдоль оси y.

    Все ясно? По-моему, вполне, идем дальше, к визуализации.

    Визуализация



    Вы можете нарисовать трехмерную поверхность. А я давно ушел от реализма OpenGL и покажу волны на плоской картинке. Как бы вид с вертолета, зависшего над озером. Пикассо сделал бы так же. Берём текстуру, со сторонами пропорциональными нашей сетке.
    Неплохо, если она будет похожа по цветоощущениям на воду в бассейне.

    image

    Пример текстуры. Пижженно у зептолабов.

    Текстуру превращаем в двумерный массив rawData пикселов, каждый пиксел — 4 байта или RGBA компонентами.
        myUIImage = [UIImage imageNamed:@"ground_2"];
        n = nx*ny;
        CGImageRef image = [myUIImage CGImage];
        NSUInteger width2 = CGImageGetWidth(image);
        NSUInteger height2 = CGImageGetHeight(image);
        CGColorSpaceRef colorSpace = CGColorSpaceCreateDeviceRGB();
        bytesPerPixel2 = 4;
        bytesPerRow2 = bytesPerPixel2 * width2;
        NSUInteger bitsPerComponent = 8;
        rawData = malloc(height2 * width2 * 4);
        CGContextRef context = CGBitmapContextCreate(rawData, width2, height2, bitsPerComponent, bytesPerRow2, colorSpace, kCGImageAlphaPremultipliedLast | kCGBitmapByteOrder32Big);
        CGColorSpaceRelease(colorSpace);
        CGContextDrawImage(context, CGRectMake(0, 0, width2, height2), image);
        CGContextRelease(context);
    


    У нас все готово для моделирования.
    Есть начальная картинка — rawData[i,j].
    Есть текущая высота поверхности воды в каждой точке — Lx[i,j].
    Есть вертикальная скорость поверхности воды в каждой точке — Wx[i,j].

    Остается нарисовать возмущенную скоростями текстуру. Формировать новую картинку будем в массив pixel[].

    -(void) renderWater
    {
        size_t width = nx*2;
        size_t height = ny*2;
        
        size_t bytesPerRow = 4*width;
        memset(pixel, 0, bytesPerRow*height);
        float zz = -1.9;
        for (int j=0;j<height;j++) {
            for (int k=0;k<width;k++) {
                int i2 = (int) (k*4 + j*bytesPerRow);
                int k4 = k/2;
                int j4 = j/2;
                int s1 = k%2;
                int s2 = 2-s1;
                int s3 = j%2;
                int s4 = 2-s3;
                int i4 = k4 + nx * j4;
                float h2 = Lx[i4] - Lx0[i4];
                h2 = (Wx[i4]*s2*s4 + Wx[i4+1]*s1*s4 + Wx[i4+nx+1]*s1*s3 + Wx[i4+nx]*s2*s3) / 4.0;
                int a = 255.0*h2*h2*0.15;
                
                if (a>255) a = 255;
                
                float x2 = (k4>0 && k4<nx-1) ? Lx[i4-1] - Lx[i4+1] : 0;
                float y2 = (j4>0 && j4<ny-1) ? Lx[i4-nx] - Lx[i4+nx] : 0;
                
                int k2 = k+zz*x2;
                int j2 = j+zz*y2;
                
                if (k2<1) k2 = 0;
                if (k2>width-1) k2 = (int) width-1;
                
                if (j2<1) j2 = 0;
                if (j2>height-1) j2 = (int) height-1;
                
                int byteIndex = (int) ((bytesPerRow2 * j2) + k2 * bytesPerPixel2);
                
                int red = rawData[byteIndex];
                int green = rawData[byteIndex+1];
                int blue =  rawData[byteIndex+2];
       
                pixel[i2+0] = red;
                pixel[i2+1] = green;
                pixel[i2+2] = blue;
                pixel[i2+3] = 255-a;
            }
        }
        
        
        
        CGColorSpaceRef colorSpace=CGColorSpaceCreateDeviceRGB();
        CGContextRef context=CGBitmapContextCreate(pixel, width, height, 8, bytesPerRow, colorSpace,
                                                   kCGBitmapByteOrder32Big |kCGImageAlphaPremultipliedLast);
        
        CGImageRef image=CGBitmapContextCreateImage(context);
        CGContextRelease(context);
        CGColorSpaceRelease(colorSpace);
        UIImage *resultUIImage=[UIImage imageWithCGImage:image];
        CGImageRelease(image);
        water.image = resultUIImage;
        
    }
    
    


    В каждой точке вычисляется смещение от начальной картинки и интерполируется на текущую. Интерполяция нужна для того, чтобы программа работала и на iPhone 4S. Для этого я в два раза уменьшил размер текстуры по каждому направлению и в 4 раза повысил скорость алгоритма. На шестом айфоне этого делать не надо, он справляется с сеткой 160 на 284.

    Плюс, в зависимости от скорости воды в данной точке я меняю прозрачность текстуры от 0 до 255.

    Все. Этот цикл неплохо работает даже на старом iPhone 4S с частотой 20 кадров в секунду.

    Заключение



    Вождение вилами по воде



    Результат моделирования также можно увидеть в двух приложениях под iPad и еще в двух под iPhone.

    image
    Приложение Haken.

    image
    Приложение Frogger.

    Всех хороших выходных и светлая память нашим предкам.
    Papa Buba Diop
    66,00
    Компания
    Поделиться публикацией

    Похожие публикации

    Комментарии 35

      +5
      Результат моделирования можно увидеть в двух приложениях под iPad и еще в двух под iPhone.

      Которые стоят по 1$. Можно хотя бы видео приложить? Уж очень интересно.
        +2
        Хакен бесплатен до 12 мая (возможно тормоза русского аппстора), Фроггер с завтрашнего дня (хочу проверить число платных загрузок). Видео сейчас, сейчас… Готово.
        0
        А последовательность такая?
        ...,T,S,N,T,T,T,T,F...?
          0
          Кто б сомневался, что ты разгадаешь.
          Я тут новую игру в слова придумал, сейчас тебе скриншот брошу, голову поломаешь.
            0
            image

            Задача — восстановить стих на доске, записанный без пробелов. Слева-справа стоят буквы, которые должны быть в данной строке. Снизу — буквы, которые стояли в данном столбце.
              0
              10 минут. Причём я не догадался, что под картинкой есть какая-то инструкция.
                0
                Хорошо, значит хлеб делать не надо) В приложении, если решаешь правильно в финале высвечивается полный текст стиха. Мой самый любимый из 100 запрограммированных — Стоит могила Незнамо чья и все же мило — что не моя)
                  0
                  Да уж. После того, как отгадаешь второй столбец и 4-ю строку, всё ещё ничего не понятно, а ни одна буква (кроме первой) не открывается.
                  0
                  Ну, задача проста и занимает ровно столько времени, сколько нужно, чтобы зачеркивать и вписывать буквы. И это даже несколько меньше, чем 10 минут.
                  0
                  В данном примере для решения не требуется просмотр вперед и поле небольшое. Потому и около 10 минут нужно. С увеличением поля и/или добавлением неоднозначных шагов головоломка может потребовать немало времени для ручного решения. Вот только не знаю, насколько сложно увеличивать именно неоднозначность.

                  Задачу упрощает само содержание исходного текста. Его можно додумать, что является большим бонусом к чисто алгоритмическому решению.
                    0
                    10 минут нужно на то, чтобы по картинке понять задачу, разобраться, почему мягкие знаки в левом столбце не противоречат этому пониманию, и перерисовать картинку на бумажку, чтобы было где вычёркивать буквы.
                      0
                      Именно так. Если внимательно посмотреть на скриншот, то по надписи на тулбаре можно вычислить начальное поле ребуса 5*5=25. Практически все стихи решались в лоб. 6 на 6 — другое дело, без знания русского языка не решить все подряд. А есть скороговорка, которую и на поле 5 на 5 решить невозможно.
                        0
                        Не фанат головоломок, но заинтригован. Можно скрин?
                          0
                          Доберусь до компьютера- выложу. Сама игра генерит расклады случайно, не могу поймать нужный.
                            +1
                            image

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

                                И, если мне не показалось, подходящий результат тут может быть не один.
                                  0
                                  Действительно интересно. Верно ли, что если ответов больше одного, то для какого-нибудь из них найдётся ломаная с прямыми углами, у которой в чётных вершинах будет стоять одна буква (общая для всех вершин), а в нечётных — другая?
                                    0
                                    Не уверен, что правильно понял вопрос. Но, кажется, утверждение неверно. Если взять из приведенной выше задачи 3-4 строки и из них первые три буквы, получим подзадачу с полем 3 на 2. Подзадача имеет 2 решения: строки можно менять местами, не нарушая условий.

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

                                    Хотя я вижу в этой же задаче возможность провести такую ломаную, и в этом месте также появляется еще один ответ. Так что это условие, похоже, достаточное, но не необходимое.
                                      0
                                      Да, согласен. И ломаную тоже теперь нашёл.

                                      А вот задача, над которой на одном из форумов думали три года:

                                      Расшифровать анаграмму: МЯЕАПНТНРАОАТГРИМЕ
                                      (существительное в именительном падеже)
                                        0
                                        В тред вызываются химики. Я бы еще пригласил людей из театрального искусства, ибо тут и про пантомиму что-то можно найти, но «грим» лежит настолько на поверхности, что это явно не оно. Так что здесь определенно химический термин. Вещество какое-нибудь. Всплывают, конечно, слова и из других сфер, но не особо похоже на правду.
                                          +1
                                          Одной из гипотез было «прямометание гранат». Но здесь одно слово.
                                            0
                                            Будучи убежденным, что речь не про гранаты, и отбросив вариант с пентаграммой, я еще более убедился, что это какая-то химия, смирился с нулевой вероятностью решения и воспользовался интернетом. Как ни странно, решение нашлось мгновенно. Выяснилось, что это титриметрический метод количественного анализа веществ, основанный на реакциях окисления. Угадал я как сферу, так и то, что решить эту анаграмму мне было не под силу.
                                              0
                                              Ещё бы не мгновенно. Яндекс про этот форум знает. Но я сначала сконструировал слово, и только потом проверил его существование…
                                              А вот перевёртыш в соседней ветке пока не по зубам.
                                                0
                                                Я и не заметил, что на том форуме есть ответ. Воспользовался первым сервисом, который гугл дал по запросу «анаграмма».
                                                  +1
                                                  Сволочи. Игрушку испортили. А их так мало осталось.
                        0
                        А что из себя представляет эта последовательность?
                          0
                          2 3 5 7 11…
                            +1
                            Или 10 12 14 16 18… Тогда дальше в ней будет 10 букв T подряд :)
                          0
                          TDDVVTTC. ¡Viva la patria!
                          0
                          как считаются высоты я понял а как картинка на основе этих высот строится нет.
                          «В каждой точке вычисляется смещение от начальной картинки и интерполируется на текущую» — это как?

                          Обожаю такие статьи, а есть может ресурсы где данные алгоритмы коллекционируются?
                            +1
                            По листингу программы довольно просто восстановить алгоритм. Вкратце, луч света, отраженный от дна преломляется на границе сред. Смещение преломления прямо пропорционально смещению пружины в данной точке от начального положения. И все.
                              0
                              Возможно, если бы переменные были названы чуть иначе, чем k1, s2, алгоритм стал бы понятнее.
                            +1
                            У вас прям код как половина функций в Вангерах (хотя проще, как минимум там всегда while и смещение указателей). :) Ну собственно там то же игрались с похожими эффектами.
                              +2
                              Настоящий программист способен написать программу на фортране на любом языке :)

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

                            Самое читаемое