После прочтения статьи про CGA от SLY_G я необычайно возбудился. Вспомнил юность, IBM PC/XT и игру frogger jr, в которой лягушка должна была пересечь дорогу, избежав колес бешено мчавшихся байков. Затем по бревнам допрыгать до тихой заводи. И так до смерти, которых выдавали 4 штуки. Фраю выдали 666, но я не Макс.
Поплакав о безвозвратно потерянных годах, я решил потерять еще пару дней и сделал ремейк игры под iPad.
Движение воды в речке решил смоделировать по-правильному, через разностную схему.
О численном алгоритме моделирования озерных волн и о том, что получилось, читайте дальше.
Да! забыл сказать.
Тем, кто может продолжить последовательность
T T F S E...читать будет не особенно интересно.
Итак, вода. Численно решать уравнения Навье-Стокса на телефонах еще рано. Поэтому я взял модель, любезно увиденную в статье уважаемого господина 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 и покажу волны на плоской картинке. Как бы вид с вертолета, зависшего над озером. Пикассо сделал бы так же. Берём текстуру, со сторонами пропорциональными нашей сетке.
Неплохо, если она будет похожа по цветоощущениям на воду в бассейне.
Пример текстуры. Пижженно у зептолабов.
Текстуру превращаем в двумерный массив 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.
Приложение Haken.
Приложение Frogger.
Всех хороших выходных и светлая память нашим предкам.
Комментарии (34)
Mrrl
08.05.2015 15:16А последовательность такая?...,T,S,N,T,T,T,T,F...?
PapaBubaDiop Автор
08.05.2015 15:26Кто б сомневался, что ты разгадаешь.
Я тут новую игру в слова придумал, сейчас тебе скриншот брошу, голову поломаешь.
PapaBubaDiop Автор
08.05.2015 15:34
Задача — восстановить стих на доске, записанный без пробелов. Слева-справа стоят буквы, которые должны быть в данной строке. Снизу — буквы, которые стояли в данном столбце.Mrrl
08.05.2015 15:4610 минут. Причём я не догадался, что под картинкой есть какая-то инструкция.
PapaBubaDiop Автор
08.05.2015 15:57Хорошо, значит хлеб делать не надо) В приложении, если решаешь правильно в финале высвечивается полный текст стиха. Мой самый любимый из 100 запрограммированных — Стоит могила Незнамо чья и все же мило — что не моя)
Mrrl
08.05.2015 16:15Да уж. После того, как отгадаешь второй столбец и 4-ю строку, всё ещё ничего не понятно, а ни одна буква (кроме первой) не открывается.
bobermaniac
08.05.2015 16:50Ну, задача проста и занимает ровно столько времени, сколько нужно, чтобы зачеркивать и вписывать буквы. И это даже несколько меньше, чем 10 минут.
gwer
09.05.2015 06:41В данном примере для решения не требуется просмотр вперед и поле небольшое. Потому и около 10 минут нужно. С увеличением поля и/или добавлением неоднозначных шагов головоломка может потребовать немало времени для ручного решения. Вот только не знаю, насколько сложно увеличивать именно неоднозначность.
Задачу упрощает само содержание исходного текста. Его можно додумать, что является большим бонусом к чисто алгоритмическому решению.Mrrl
09.05.2015 07:3910 минут нужно на то, чтобы по картинке понять задачу, разобраться, почему мягкие знаки в левом столбце не противоречат этому пониманию, и перерисовать картинку на бумажку, чтобы было где вычёркивать буквы.
PapaBubaDiop Автор
09.05.2015 11:18Именно так. Если внимательно посмотреть на скриншот, то по надписи на тулбаре можно вычислить начальное поле ребуса 5*5=25. Практически все стихи решались в лоб. 6 на 6 — другое дело, без знания русского языка не решить все подряд. А есть скороговорка, которую и на поле 5 на 5 решить невозможно.
gwer
09.05.2015 11:25Не фанат головоломок, но заинтригован. Можно скрин?
PapaBubaDiop Автор
09.05.2015 20:18Доберусь до компьютера- выложу. Сама игра генерит расклады случайно, не могу поймать нужный.
PapaBubaDiop Автор
12.05.2015 14:21+1
Подсказка: это скороговорка.gwer
12.05.2015 16:58А вот это уже весело. Однозначно определяется только две буквы, а дальше начинаются допущения с выделением наиболее вероятных последовательностей букв. Выручает отсутствие вычурных и неожиданных слов.
И, если мне не показалось, подходящий результат тут может быть не один.Mrrl
12.05.2015 17:46Действительно интересно. Верно ли, что если ответов больше одного, то для какого-нибудь из них найдётся ломаная с прямыми углами, у которой в чётных вершинах будет стоять одна буква (общая для всех вершин), а в нечётных — другая?
gwer
12.05.2015 18:17Не уверен, что правильно понял вопрос. Но, кажется, утверждение неверно. Если взять из приведенной выше задачи 3-4 строки и из них первые три буквы, получим подзадачу с полем 3 на 2. Подзадача имеет 2 решения: строки можно менять местами, не нарушая условий.
Насколько я понимаю, подразумевается ломаная, соединяющая хотя бы 4 точки. Но во взятой подзадаче можно соединить лишь по три.
Хотя я вижу в этой же задаче возможность провести такую ломаную, и в этом месте также появляется еще один ответ. Так что это условие, похоже, достаточное, но не необходимое.Mrrl
12.05.2015 18:39Да, согласен. И ломаную тоже теперь нашёл.
А вот задача, над которой на одном из форумов думали три года:
Расшифровать анаграмму: МЯЕАПНТНРАОАТГРИМЕ
(существительное в именительном падеже)gwer
12.05.2015 18:48В тред вызываются химики. Я бы еще пригласил людей из театрального искусства, ибо тут и про пантомиму что-то можно найти, но «грим» лежит настолько на поверхности, что это явно не оно. Так что здесь определенно химический термин. Вещество какое-нибудь. Всплывают, конечно, слова и из других сфер, но не особо похоже на правду.
Mrrl
12.05.2015 19:14+1Одной из гипотез было «прямометание гранат». Но здесь одно слово.
gwer
12.05.2015 19:22Будучи убежденным, что речь не про гранаты, и отбросив вариант с пентаграммой, я еще более убедился, что это какая-то химия, смирился с нулевой вероятностью решения и воспользовался интернетом. Как ни странно, решение нашлось мгновенно. Выяснилось, что это титриметрический метод количественного анализа веществ, основанный на реакциях окисления. Угадал я как сферу, так и то, что решить эту анаграмму мне было не под силу.
Mrrl
12.05.2015 19:35Ещё бы не мгновенно. Яндекс про этот форум знает. Но я сначала сконструировал слово, и только потом проверил его существование…
А вот перевёртыш в соседней ветке пока не по зубам.
guyfawkes
09.05.2015 13:25А что из себя представляет эта последовательность?
marten_de
09.05.2015 20:17как считаются высоты я понял а как картинка на основе этих высот строится нет.
«В каждой точке вычисляется смещение от начальной картинки и интерполируется на текущую» — это как?
Обожаю такие статьи, а есть может ресурсы где данные алгоритмы коллекционируются?PapaBubaDiop Автор
09.05.2015 20:22+1По листингу программы довольно просто восстановить алгоритм. Вкратце, луч света, отраженный от дна преломляется на границе сред. Смещение преломления прямо пропорционально смещению пружины в данной точке от начального положения. И все.
guyfawkes
10.05.2015 10:47Возможно, если бы переменные были названы чуть иначе, чем k1, s2, алгоритм стал бы понятнее.
kahi4
Которые стоят по 1$. Можно хотя бы видео приложить? Уж очень интересно.
PapaBubaDiop Автор
Хакен бесплатен до 12 мая (возможно тормоза русского аппстора), Фроггер с завтрашнего дня (хочу проверить число платных загрузок). Видео сейчас, сейчас… Готово.