Заводчик кардиганов
0,0
рейтинг
6 февраля 2013 в 00:25

Разработка → Жизнь на плоскости Лобачевского

Различные реализации игры «Жизнь» описывались на Хабре уже неоднократно. В этой статье, в качестве продолжения этой темы, рассматривается ещё один её вариант: в качестве игрового поля используется регулярная решётка на плоскости Лобаческого. Описываются общие методы использования плоскости Лобачевского в программах и необходимые для этого математические приёмы.
Как возникла плоскость Лобачевского, достаточно известно. В позапрошлом веке господа Гаусс, Лобачевский и Бойяи, проживавшие примерно в одно время в разных странах тогдашней Европы, задумались, что будет, если отменить пятый постулат Евклида и заменить его на противоположную аксиому. Оказалось, что не случится ничего плохого, и никаких противоречий не возникнет. Заметная часть последующего изучения неевклидовой геометрии была посвящена выяснению того, кто из них у кого украл идею этой самой геометрии.
Менее известно, что несмотря на «отрицательный» способ определения неевклидовой геометрии (вместо того, чтобы сказать, что через точку проходит ровно одна прямая, не пересекающая данную, мы говорим, что таких прямых может быть сколько угодно), мы, тем не менее, получаем систему теорем и формул, не менее стройную, чем та, что есть в евклидовой геометрии. И одновременно, у нас есть гораздо большее разнообразие геометрических фигур, в том числе, разбиений плоскости на правильные многоугольники.



Итак, теоремы. Теорема Пифагора, которая звучала, как a2+b2=c2, в геометрии Лобаческого приобретает вид ch(a) ch(b)=ch( c ), длина окружности оказывается равна , а площадь круга — . Здесь sh(x) — гиперболический синус, а ch(x) — гиперболический косинус. Чтобы можно было с такой свободой применять математические функции к расстояниям, нам потребуется некая абсолютная единица измерения, которая в геометрии Лобачевского присутствует (это расстояние, при сдвиге на которое расстояние между «сходящимися» прямыми уменьшится ровно в e раз). Наличие такой единицы расстояния сразу же приводит к тому, что у нас исчезает преобразование подобия — если мы в какой-нибудь фигуре попытаемся изменить расстояния в одинаковое число раз, то форма фигуры изменится. Например, величина угла правильного треугольника зависит от его стороны.
Зато появляется возможность построить треугольник по трём углам (это делается с помощью второй теоремы косинусов). И совсем просто оказывается найти площадь треугольника: . Видно, что сумма углов треугольника всегда меньше , причём её можно сделать сколь угодно малой (стороны треугольника при этом будут стремиться к бесконечности, зато площадь останется конечной).
Выбирая правильные треугольники с углом , мы получаем возможность строить «паркеты» из правильных треугольников, в которых в одной вершине сходится 7,8,… вплоть до бесконечности треугольников (есть даже вариант «ультрабесконечности», но о нём мы говорить не будем). В этой статье нас будет интересовать паркет {4,5}, который состоит из правильных четырехугольников с углами 72o. К сожалению, построить его мы пока не готовы.
Кроме наших привычных прямой и окружности, на плоскости Лобачевского есть ещё две линии с похожими свойствами — эквидистанта или гиперцикл (множество точек, находящихся на данном расстоянии от прямой с одной и той же стороны от неё) и предельная линия" или орицикл (линия, пересекающая пучок сходящихся прямых под прямым углом, предел окружности при радиусе, стремящемся к бесконечности). Перемещения плоскости бывают трёх видов — привычный нам поворот (задаётся точкой и углом), сдвиг вдоль прямой (задаётся прямой и смещением) и сдвиг вдоль предельной линии — очень странное перемещение, про которое нельзя сказать «на сколько мы сдвинулись» (в разных местах плоскости величина сдвига различна, и все такие сдвиги в каком-то смысле одинаковы). Здесь важно, что сдвиг вдоль прямой — это совсем не то же самое, что параллельный перенос на евклидовой плоскости: разные точки сдвигаются на разные расстояния (точки на оси сдвига — меньше всех), прямая может пересекаться со своим образом при сдвиге и т.д. Вообще, понятия «вектор» на плоскости Лобачевского нет, а с понятием «направление» есть большие сложности.
Чтобы работать с этой плоскостью, нам понадобится система координат. Ввести её, да ещё и так, чтобы было удобно работать, совсем непросто. Аналога декартовых координат (с равноправными x и y) нет вообще. Можно задать точку с помощью проекции на прямую и расстояния до неё, но это будет не очень удобно. Лучше работать в полярных координатах, или взять в качестве оси какую-нибудь предельную линию (одна координата — проекция точки на эту линию, другая — расстояние до неё). К счастью, эти системы координат позволяют построить очень удобые модели, которые изобрёл Пуанкаре.

Диск и верхняя полуплоскость. Осторожно, ТФКП!


Если мы возьмём предельную линию, через x обозначим проекцию точки на неё, а через y — экспоненту расстояния от точки до линии (с учётом знака, расстояние считается
положительным с «вогнутой» стороны этой линии), и рассмотрим точки с координатами (x,y) на евклидовой плоскости, то получим удивительный факт. Вся плоскость Лобачевского превратится в верхнюю полуплоскость (y>0), прямые превратятся либо в вертикальные прямые, либо в дуги окружностей (с центрами на прямой y=0), окружности останутся окружностями (со смещенным центром), а все эквидистанты и предельные линии тоже станут прямыми или дугами окружностей. Более того, все углы между прямыми и окружностями сохранятся.
Такая модель называется моделью «полуплоскости» Пуанкаре. Перемещения плоскости Лобачевского в этой модели будут выглядеть как преобразования, сохраняющие прямую y=0, и переводящие прямые и окружности в прямые или окружности (преобразования Мёбиуса). Если вместо точек (x,y) взять комплексные числа z=x+iy, то такие преобразования будут выглядеть как дробно-линейные функции , причём числа a,b,c,d должны быть вещественными. Что хорошо в этих преобразованиях — их композиция ведёт себя как умножение матриц . Это даёт нам первую подсказку для реализации плоскости Лобачевского: перемещения плоскости Лобачевского можно представить как матрицы 2x2 с вещественными коэффициентами, определенные с точностью до умножения на число (т.е. матрицы и считаются одинаковыми).
В дальнейшем через M(z), где — матрица 2x2, а z — комплексное число, мы будем обозначать величину .
Работа с матрицами и с верхней полуплоскостью удобна, но не очень наглядна. Для визуализации плоскости Лобаческого к этой полуплоскости обычно применяют преобразование , и получают круг радиусом 1. Прямые плоскости Лобачевского оказываются диаметрами этого круга и дугами, перпендикулярными его границе. Эта модель называется диском Пуанкаре, мы будем использовать её для вывода результатов.

Разбиение {4,5}. Осторожно, линейная алгебра!


Для реализации игры «Жизнь» был выбран паркет {4,5} (разбиение плоскости на правильные 4-угольники, в каждой вершине сходятся по 5 клеток). Это одно из двух разбиений, наиболее похожих на наше стандартное разбиение {4,4}. Искажения четырёхугольников при выводе будут не очень большими, и это позволит нам увидеть больший фрагмент плоскости одновременно. Второе из упомянутых разбиений — это {5,4} (в каждой вершине сходится 4 пятиугольника), но эксперименты показали, что для «Жизни» этот паркет подходит чуть меньше.
Чтобы построить и использовать разбиение {4,5}, нам надо научится делать несколько вещей. Во-первых, найти координаты центров и вершин четырёхугольников в нашей модели. Во-вторых, как-то занумеровать четырёхугольники, чтобы отличать один от другого, выяснять, какие являются соседними. И ещё надо будет научиться менять центр картинки, чтобы можно было изучить далекие участки плоскости, поскольку всё самое интересное происходит, обычно, там, где нас нет.
Наш привычный метод обозначения клеток парами индексов здесь не работает. Вообще. Зато мы знаем, что каждая клетка получается из центральной клетки с помощью перемещения плоскости, это перемещение описывается матрицей 2x2, а центр клетки будет образом центра центральной клетки, т.е. точки (0,1)=i при этом перемещении. Более того, клетки, соседние с нашей — это образы клеток, соседних с центральной, при этом перемещении. Так что для создания паркета нам потребуется следующее:
  • Найти матрицы перемещений, переводящих центральную клетку в соседние;
  • Построить цепочки этих перемещений, чтобы найти перемещения, создающие остальные клетки;
  • Выкидывать перменещния, приводящие к построению клетки с уже известным центром;
  • Не забывать, что площадь круга растёт очень быстро, поэтому глубину перебора нам придётся хорошо ограничить;
  • Найти координату хотя бы одной вершины центральной клетки. Остальные вершины из неё легко построим.

Начнём с того, что выберем парочку перемещений, из которых можно получить всё, что нам нужно. Одним таким перемещением будет поворот R вокруг точки i на угол (он переводит центральную клетку в себя), а вторым — симметрия T относительно середины одной из сторон центральной клетки — она переведёт эту клетку в соседнюю. Можно проверить, что матрицами этих перемещений будут и , где i*a — центр соседней клетки (считаем её расположенной прямо над нашей, поэтому a>1). Чтобы найти a, надо будет решить уравнение для какого-нибудь m (RT — поворот вокруг одной из вершин клетки, а — тождественное преобразование). Решать систему уравнений 5-й степени, да ещё аналитически (нам это понадобится в дальнейшем) мы не хотим, поэтому поступим по-другому: скажем, что собственные значения матрицы RT должны быть такими же, как у матрицы , т.е. их характеристические многочлены должны совпадать. Опуская выкладки, получаем, что , откуда

Вершину четырёхугольника мы найдём, решив уравнение RT(z)=z. Здесь нам аналитического решения не нужно, достаточно численного.
После того, как мы построили матрицы R и T, и убедились, что R4 и (RT)5 скалярны, построить решетку четырёхугольников — дело техники. Мы берём все матрицы M=RaTRbTRcT..., где a,b,c,... — числа от 1 до 3 (возможно, a=0), и отождествляем те, для которых M(i) одинаковы. Каждый класс таких матриц даёт ровно один четырёхугольник решетки. Четырёхугольники, соответствующие матрицам M1 и M2, будут соседними, если M2=M1RkTRl для некоторых k,l.
Для игры на ограниченном участке плоскости этого будет достаточно. Надо только не забывать, что ориентации соседних клеток исходно не согласованы, поэтому, если они важны, то при переходе на соседнюю клетку надо указывать, с какой стороны (в ориентации той клетки) мы пришли. Это непросто, но написать этот кусок надо один раз :).
Для визуализации построенного фрагмента плоскости нам будет нужна ещё матрица «положения камеры». В нашем случае это просто матрица 2x2, такая же, как использовались при идентификации клеток. Если матрица камеры F, мы хотим нарисовать клетку, заданную матрицей матрицей M, а координата точки в системе координат этой клетки равна s (комплексное число из модели «полуплоскости»), то чтобы определить, где находится образ точки на диске Пуанкаре, мы находим z=F*M(s), w=(z-i)/(z+i). w — искомая точка.

Замкнутые области на плоскости Лобачевского. Осторожно, конечные поля!


Как я уже говорил, площадь круга на плоскости Лобачевского растёт очень быстро. Увеличение радиуса на 1 приведёт к увеличению площади примерно втрое. Поэтому если мы зададим, например, миллион клеток, то они в лучшем случае покроют круг радиусом 13. Для игры «Жизнь» этого мало, там любят однородные области без границ. Так что перед нами стоит задача — как вырезать из нашего паркета кусок и склеить его края, чтобы в каждой вершине по-прежнему сходилось 5 четырёхугольников? Простой способ, который используется для декартовой сетки, не проходит — никаких прямоугольников у нас нет. Но он даёт намёк: там, если мы вырезаем из решётки {4,4} квадрат со стороной P, где P простое, то клетки (x1,y1) и (x2,y2) мы считаем одинаковыми, если x1=x2 (mod P) и y1=y2 (mod P). Почему бы нам не поступить так же? Каждой клетке у нас соответствует матрица , являющаяся произведением матриц R и T, взятых в каком-то количестве и порядке. Две матрицы соответствуют одной клетке, если M2=M1Rk. Всё, что нам нужно, это подобрать такое P, чтобы матрицы R и T по модулю P существовали.
С матрицей всё просто — она существует всегда. Чтобы существовала T, нужно, чтобы выражение вычислялось по модулю P (вот зачем нам понадобилось находить его в аналитической форме). Число модулей P, для которых такое выражение можно вычислить, невелико (примерно каждый 30-й). Например, P=179. По этому модулю у нас получается 1433790 клеток, что вполне нормально для игры. Всё равно за один раз мы видим только несколько тысяч из них.
После того, как мы выбрали модуль, построим все возможные произведения R и T по модулю P (с точностью до постоянного множителя) — их будет не больше P3-P. Для каждой матрицы запомним клетку, которой эта матрица соответствует (матрицы M и MR всегда соответствуют одной и той же клетке), а для каждой клетки — какую-нибудь матрицу. Потом для каждой клетки найдём номера всех её соседей — отдельно граничащих по сторонам, отдельно — по углам. И, наконец, при построении геометрической модели вместе с матрицей M, задающей клетку, будем считать её представление по модулю P, аккуратно вычисляя произведение матриц R(mod P) и T(mod P) в тех же степенях.
Всё посчитали, можно начинать работать. Заметим только, что клеток в геометрической модели нам много не надо — достаточно десятка тысяч. И чтобы через эту модель можно было посмотреть на любой участок игрового поля, поступим так.
Кроме матрицы F (положения камеры) будем хранить ещё и матрицу Q, заданную по модулю P — это будет «расположение поля под камерой». В частности, сама матрица Q будет одним из представлений той клетки, над которой находится камера. Чтобы нарисовать клетку с номером k из геометрической модели, мы возьмём матрицу Mk(mod P) из этой клетки, вычислим Ck=Q*(Mk(mod P)), и найдём клетку из нашего поля, соответствующую матрице Ck (мы её когда-то запомнили). И нарисуем всё содержимое клетки, используя матрицу FMk, как было указано в предыдущем разделе.
Если при движении камеры мы вышли за пределы центральной клетки, и теперь в центре рисуется клетка геометрической модели с номером , то проекцию поля на модель надо передвинуть. Скажем, что теперь в качестве положения камеры мы будем использовать F'=FMm, а в качестве матрицы расположения поля возьмём Q'=Q(Mm(mod P)). Если это не сработает (а должно сработать), мы увидим сразу — при движении над полем изображение не всегда будет двигаться непрерывно.

Собственно игра «Жизнь»


В общем, ничего интересного не осталось. Основной задачей была навигация в плоскости Лобачевского, а игра «Жизнь» — всего лишь самое простое её практическое применение. Но раз уж мы здесь...
Список полей у нас есть. Задать состояние (клетка жива или мертва) — не проблема. Проблема выбрать интересные правила. Конечно, Конвея с его правилами 4-го порядка, догнать нереально, но хотя бы планеры половить хочется.
Чтобы было больше свободы, было принято решение считать соседей по сторонам и по углам отдельно, и для каждого их сочетания давать свой ответ «жива или мертва». Довольно скоро стало понятно, что если клетки будут оживать при наличиии не менее 4 соседей, то планеров нам не видать, и нужно, чтобы хотя бы в ситуации «один живой сосед по стороне и два — по углам» клетка рождалась (такое правило записывается как B12). Неплохие результаты дало правило B12,4/S2,3,4 (клетка рождается в ситуации 2 по углу, один по стороне — или при 4 живых соседях в любой комбинации, а остаётся живой при 2,3,4 живых соседях — опять же, в любой комбинации). Там было много стабильных фигур, несколько интересных пульсаров, а вместо планеров периодически пролетали какие-то «ударные волны». К сожалению, при увеличении исходной плотности конфигурация становится хаотической, и её плотность держится на уровне 1/3.
Другая интересная конфигурация — B12,21/S3,4,6 (клетка рождается, если у неё ровно три живых соседа, причём должны быть живые соседи и по стороне и по углу, а выживает — если живых соседей 3, 4 или 6). Стабильных фигур и пульсаров в этом мире немного, зато много планеров. Фактически, всё поле состоит из планеров и их обломков (плотность держится на уровне 1/200), поэтому долго они не живут.

Другие выводы


Эксперименты с плоскостью Лобачевского показали, что она в самом деле очень маленькая по размеру и большая по площади. Если от чего-то отойти на несколько шагов, то его видимые размеры уменьшатся до полной неразличимости, и вернуться обратно будет очень сложно. Если пытаться обойти какое-нибудь препятствие, то даже тот факт, что вы всё время поворачиваете направо, не даёт гарантии, что ваш путь замкнётся (например, если мы будем идти по квадратам решетки {4,5} и поворачивать на 90 гр каждые два шага, то уйдём бесконечно далеко). Области, которые кажутся узкими свободными щелями между зонами, заполненными живыми клетками, в действительности могут оказаться огромным пустым пространством, а область живых клеток, если посмотреть издалека, окажется небольшим пятном на совершенно пустом горизонте…
В общем, объект интересный. И если кому-нибудь надоели плоские игровые поля, а уходить в трёхмер не хочется, можно попробовать перенести игру на решётки плоскости Лобачевского. Вдруг получится?

Пролёт планера


Прогулка по плоскости из серии «мы все умрём»


Фрагмент игры на решётке {5,4}
Андрей @Mrrl
карма
347,7
рейтинг 0,0
Заводчик кардиганов
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (62)

  • +24
    Я обычно не жалуюсь на отсутствие кармы, но в такие моменты мне действительно жаль, что её не хватает, чтобы поставить «плюс». (и нет, я её не выпрашиваю, как ты подумал, %username%)
    • +12
      Поделился. Я добрый :)
      • +5
        Ого, как-то неожиданно накинули столько кармы! Спасибо! :)
        • +5
          Иногда сделать приятно другому человеку проще, чем кажется.
  • +1
    какие жуткие необычные структуры!!! =)
  • +7
    Теперь наступила очередь Minecraft.
    • +1
      Чуть раньше Каркассон заказывали. А для Minecraft понадобится трёхмерное пространство Лобачевского, с решеткой {4,5,3} (в каждой вершине сходится 20 кубиков). Честно говоря, страшная штука.
    • +1
      У меня была фантазия о майнкрафте на торе или на бутылке клейна — уйти в одну сторону и прийти с противоположной стороны, в случае бутылки — отзеркаленным. Еще можно замкнуть верх и низ. Или, опять же, замкнуть со сменой ориентации, тогда совсем весело станет.
      • +3
        Или еще поиграть с нехаусдорфовостью. Дверь в чистом поле, заходишь — оказываешься в другом месте. Или обходить дерево и каждый раз видеть разный ландшафт.
        • +5
          Я как раз в затяжном процессе создания подобного клона на D. Из функций — пользовательские внутриигровые прозрачные безрамочные порталы произвольной формы, управляемые левитирующие замки/корабли/произвольные области пространства, честное освещение очень сильно оптимизированным path tracing, HDR, процедурные текстуры неограниченного разрешения, призмы, линзы и зеркала произвольных форм, радиусов и степеней кривизны, антисвет и октарин, и миры с альтернативными метриками.

          В частности, например, мир на внутренней поверхности цилиндра сродни «Раме» из романа Кларка, с солнцами в виде очень ярких блоков, находящихся на поверхности «земли». К сожалению, в уходу сохранению кубической сетки, пришлось сделать так, что цилиндр на самом деле формируется из свенутого пласта «плоского» пространства, таким образом, что на каждом уровне высоты количество блоков, требуемое для того, чтобы выложить «кольцо вокруг мира», одинаковое. Т.е. плотность блоков не меняется с высотой, искажается лишь их форма.
          • +1
            Не совсем это, я имел ввиду, чтобы в каждом месте мой тор был плоским. Я хочу просто взять квадрат блоков 100х100 чанков и ассоциировать противоположные стороны — «склеить» одну к другой. Игрок продолжает жить в плоском мире, но когда он уходит в одну сторону, он возвращается откуда-нибудь с другой стороны. В случае с тором — с противоположной. В случае бутылки клейна он возвращается с противоположной стороны, отраженный зеркально (с его точки зрения, он вернется в зеркально отраженный мир). Интересно само изменение метрики — оно повлияет на игровой процесс, а в случае каких-то агрессивных мультиплеерных забав добавляет тактических возможностей и уловок. Если похожим образом ассоциировать («склеить») верхнюю и нижнюю границу мира, то геймплей может поменяться гораздо сильнее.
            На самом деле, кроме плюшек к геймплею, интересно само ощущение нахождения в таком мире. Утратится ли ощущение свободы? Как изменится пространственное мышление? Что еще будет чувствовать человек в таком мире?
            • 0
              Да, и помимо этого появляется интерейснейшая задача создания генератора ландшафта на такой зацикленной области.
            • 0
              Можно попробовать, если я все правильно понимаю, то описанная Вами идея реализуется при помощи одних только Огромных Порталов От Земли До Неба (tm). С генерацией карты пока что беда.
              • 0
                Да, но в огромных порталах от земли до неба вы не отрендерите пять проходов света подряд (или отрендерите?). Здесь хорошо бы полностью перекроить механику игры, считая все координаты по модулю размеров карты.
          • +1
            А где можно последить за разработкой? Или даже потестировать? :)
            • 0
              Еще нигде, но я планирую статью на хабр с описанием, как я до такой жизни докатился, в скором времени — когда возьму отпуск на работе. Сейчас, к сожалению, разработку получается вести по несколько часов через день уже ночью, а это не способствует быстрому продвижению, к тому же помимо непосредственно игры, из-за выбора языка и особенностей архитектуры есть множество побочных задач, которые оттягивают силы от непосредственной реализации.
      • +2
        Тут вопрос — остаётся ли локальная геометрия евклидовой. Чтобы не слишком пугать пользователей, то лучше оставить, и тогда возникнет выбор: либо не вводить особых точек, и тогда выбор поля — либо тор, либо бутылка Клейна. Склеить плоскость, чтобы перепутались x и y, не получится, хотя повернуть плоскость при склейке по вертикали возможно. Жалко, что не получится склеить со сменой масштаба :(
        А если разрешить особые точки (непробиваемые колонны до неба, обход вокруг которых замыкается не за 360 гр, а когда угодно, то получаете полную свободу. Проще всего сделать многолистный мир: при обходе колонны по часовой стрелке переходите на уровень выше, а против часовой — на уровень ниже (уровни, естественно, зациклены — ведь, как известно, мы все живём на седьмом уровне сумрака :) ). Другой вариант — любой горизонтальный отрезок между колоннами является порталом в совсем другую клетку того же уровня. Например, мир состоит из 997 больших клеток, при проходе на восток или запад попадаете в клетку n+1 или n-1 соответственно, при проходе на север — в клетку 2*n, а при проходе на юг — в n/2. Это не очень хороший вариант (клетки не эквивалентны), но это первое, что пришло в голову.
    • 0
      Я сначала подумал о том, чтобы реализовать классическую «Жизнь» на редстоуне в майнкрафте. Идея то классная!
  • +1
    Интересно. А что насчет муравья Лэнгтона на такой плоскости?
    • +6
      Попробую. Придётся учитывать ориентацию при переходе… противно, но полезно.
    • +2
      Прогулка муравья. Записано 1200 шагов, после чего я долго пытался понять, чего же он наследил. Понять не удалось.
      При записи «прогулки» муравей всегда в центре картинки, но двигаться может в любую сторону — ориентацию всего поля я стараюсь не менять, ха-ха…

  • 0
    Здорово :)
  • +2
    Хорошая, годная статья. Расширяет сознание. В избранное.
  • +4
    Даешь больше годных математических статей!
  • +2
    Спасибо! Встречаясь впервые с геометрией Лобачевского, кажется, что это штука слишком абстрактна и далека от жизни. Потом оказывается, что она находит применение и в физике, и в астрономии, органично вписываясь в модели и уравнения. Далее выясняется, что ее удобно применять для создания карты интернета. И вот, уже, с помощью геометрии Лобачевского реализуется сама Жизнь. Потрясающе!
    • +1
      Если мне память не изменяет, из неевклидовых геометрий ту же геометрию Римана используют в космонавтике и навигации. Хотя, на первый взгляд, тоже весьма абстрактная штука.
      • 0
        Используют больше сферическую геометрию (тоже неевклидова), но в самом деле, куда без неё? Геодезисты вообще работают с геоидом, а там геометрия такая, что одними формулами не обойдёшься, нужны таблицы…
  • 0
    Замечательно. Еще пока учился, не всегда понимал, зачем нам вдалбливают всё вот это.
    Теперь хотя бы применение в игре. Ну, и то, что теперь это не придётся сдавать из-под палки тоже играет свою роль :)

    А откуда взялась идея? Я сомневаюсь, что человек может просто сидеть-сидеть, а потом вдруг внезапно сесть и начать писать геометрическую игру в неевклидовом пространстве…
    • 0
      Настоящая игра (головоломка) в неевклидовом 3D пространстве у меня была ещё несколько лет назад: astr73.narod.ru/M3dHT633/M3dHT633.html. А откуда взялась идея… уже не помню. Но когда мы впервые увидели лабиринтообразные игры на Ямахе (особенно Black Onyx — там был 8-этажный лабиринт с этажами в виде тора 16*16), то возник вопрос — а если вместо квадратной решётки взять что-то другое? Но в дело так и не пошло, не удалось придумать сценарий.
      С головоломками стало несколько легче, там всё понятно — как делать и к чему идти. Кстати, есть целый большой проект головоломок на неевклидовой плоскости: www.gravitation3d.com/magictile/. Там уже более 600 вариантов «кубика рубика», и какой-то энтузиаст из Германии решил больше трети из них
      • +1
        Судя по комментам возможно отсюда?
        • 0
          Действительно, было такое. Полгода назад.
  • 0
    А нельзя ли не менять положение камеры, а просто увеличивать разрешение и вырезать интересующую область на краю? То есть зафиксировать положение центральной клетки, а для того, чтобы рассмотреть, что там происходит на горизонте, просто увеличивать интересующее место.
    Мне кажется, что так было бы проще наблюдать за поведением колоний.
    • +2
      Будет только хуже. Изображение решетки на диске Пуанкаре полностью фрактально — любой фрагмент у края диска, под каким увеличением его не рассматривай, будет выглядеть, как кусочек модели верхней полуплоскости. Число различимых клеток не будет зависеть от величины зума, а большая часть полезной площади будет съедена большими клетками вдали от края. Так что выигрыша по сравнению со сдвигом камеры в сторону края диска мы не получим. Разве что можно будет использовать вытянутое по горизонтали окно… Тогда уж лучше сразу работать в модели верхней полуплоскости.
      Чтобы увидеть больше клеток, я слегка сжульничал — сжал центр диска и растянул его у краёв по формуле r1=1-(1-r)^(2/3) (r — расстояние до центра). В итоге четырёхугольники у края превратились в черточки и их хотя бы стало видно. Без этого растяжения они были бы точками.
      • 0
        Зато в таком случае можно вообще забыть про неевклидову геометрию и всю ту математику, о которой статья. Мы просто рассматриваем некоторую (статичную) нарисованную на плоскости сетку. Эта сетка состоит из разных по размеру и форме четырёхугольных ячеек, и её происхождение не имеет никакого значения для реализации игры. Точно также можно рассматривать совершенно любые другие паутины на плоскости, ведь так?
        • 0
          Проблема в навигации. Сконструировать сетку для визуализации и поле, разные места которого можно рассматривать через эту сетку (причём, корректно и без противоречий) не просто. Кроме того, может возникнуть желание, чтобы поле было однородно (в любой вершине сходится именно 5 четырёхугольников, а не 4 и не 6) — и без математики такую сетку уже не построить. А замкнуть её в поверхность без края и без особых точек ещё сложнее.
          Если вам не нужна такая однородность, то можете взять любую паутину. Там потребуется математика плоских графов, чтобы выделить на этой сетке вершины и области, и опять же, не было противоречий. В конечном итоге, всё пишется «на коленке», и если повезёт, то оно будет самосогласовано. Но это будет означать только, что часть нужной математики вы придумали заново, именно для конкретной задачи. Я сам часто так делаю.
          Кстати, неограниченного увеличения без математической модели вы не получите. А с ограниченным быстро уткнётесь в край.
  • 0
    Спасибо. Всплакнул.
  • +3
    Отличная статья. Спасибо! Хочу больше статей на математическую тему. Кстати, никто не подскажет, может существует какой-то ресурс, где собраны подобные статьи? Эдакий хабр с математическим уклоном. Все сайты, которые я до этого видел, либо похожи на сборник олимпиадных задач, либо ответы на ЕГЭ.
    • 0
      Насчёт статей не знаю, но есть какой-то форум dxdy.ru — может быть, на нём найдётся достаточно информации?
      • +1
        Ну вот опять что-то не то. Ресурс, наверно, полезный, но опять все по принципу «вопрос-ответ». Школьнику задали задачку в школе, он пришел на форум, спросил — получил ответ. А хочется, чтобы человек написал статью про какой-нибудь раздел математики да еще понятным языком. А ты прочитал, и сразу захотелось все изучить. Не хватает духа хабра :).
      • +2
        И еще, раз уж пошел такой разговор, у меня есть желание написать парочку статей на математическую тему, но у меня есть сомнения следующего рода:
        — являются ли такие статьи уместны на хабре (особенно, если это чистая математика, без какого-то практического применения)
        — востребованы ли они читателями хабра.
        • +2
          Конечно востребованы!
        • 0
          Не знаю. Я и насчёт этой сомневался, не слишком ли она абстрактна.
          • 0
            Ну вот, значит вы меня понимаете. Всегда найдется какой-нибудь умник и скажет: «Простите, все это, конечно, интересно, а какое этому может быть практическое применение?»
    • +1
      Когда-то был популярен arbuz.uz. Но с тех пор много лет прошло.
    • 0
      ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0 — читать не перечитать. Там наверно статей 500 как минимум)
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Она измеряется в абсолютных единицах. Как и длина. Кстати, для треугольника на сфере верна аналогичная формула: S=A+B+C-pi, площадь измеряется в стерадианах (и равна площади треугольника на единичной сфере). Конечно, по-хорошему, для сферы надо писать S=R^2*(A+B+C-pi), а для плоскости Лобачевского — S=(pi-A-B-C)/(-K), где K — кривизна поверхности, но проще принять абсолютнуб величину равной 1 и не вспоминать о ней, пока жизнь не заставит.
      • НЛО прилетело и опубликовало эту надпись здесь
        • +3
          Она будет в квадратных, но не метрах. А величинах, равных 1/sqrt(-K), где K — гауссова кривизна плоскости.
          Наглядно эту величину можно представить так. Возьмём прямую и точку поблизости от неё. Через эту точку можно провести бесконечно много прямых, не пересекающих нашу, но две из них будут ограничивать этот набор — они на бесконечности будут «сходиться» с нашей прямой (одна с одной стороны, другая с другой) — они так и называются «сходящимися». На картинке их видно: они образуют стороны белого треугольника в центре.

          Так вот, оказывается, что сходящиеся прямые сходятся с экспоненциальной скоростью. И величина, на которую надо сдвинуться, чтобы расстояние уменьшилось в «е» раз, и будет абсолютной единицей расстояния в данном экземпляре плоскости. Абсолютная единица площади — квадрат абсолютной единицы длины.
          В сферической геометрии роль абсолютной единицы играет радиус сферы: если выражать расстояния через него, то формулы получаются гораздо красивее.
  • +1
    Предлагаю на каждом шаге «жизни» смещать камеру в сторону максимальной концентрации живых клеток. В этом случае они будут в фокусе или где-то рядом, и будет довольно динамично.
    • +1
      В сторону ближайшей плотности изменений, вероятно. Хорошая идея, я подумаю. Правда, с понятием «в сторону» есть сложности, но что-нибудь придумаю.
  • 0
    Здорово, что такие статьи есть. Спасибо автору. Но подача хромает, на вики куда понятнее. И эти англоязычные ссылки, зачем?
    • +2
      Английская вики почти всегда гораздо информативнее, чем русская. Да и не у всех ссылок есть русский аналог. Вот я и сделал единообразно.
  • 0
    Почему в видео границы четырехугольников рисуются прямыми? Если это геодезические, в проекции на круг они должны быть дугами. С математикой-то все ясно, а вот когда вы пишете, что ничего интересного не осталось, как раз непонятно. Что такое планер? И зачем было выходить за евклидову геометрию, если остались те же четырехугольные клеточки. В чем разница, кроме того, что в углу встречаются не 4 а 5 клеточек?
    • +1
      Границы рисуются прямыми просто чтобы быстрее было их считать. Меня больше интересовало не идеальное воспроизведение, а комбинаторика. Можно было, конечно, нарисовать ломаную из 32 сегментов — никто бы не заметил разницы…
      Планер (он же глайдер) — объект из игры «жизнь» — конфигурация, которая через несколько поколений воспроизводится, но оказывается в другом месте (и в результате движется по полю, пока во что-нибудь не врежется). То, что клеточек встречается не 4, а 5, даёт другую комбинаторную конфигурацию (одно только отсутствие параллельного переноса чего стоит!), и было интересно, к чему это приведёт. Пока разобрался не до конца, объект ещё надо исследовать.
  • 0
    Я ничего не понял. Кто-нибудь в двух словах поясните, зачем это всё нужно и что там за видео про полёт планера?
  • 0
    А это нормально писать sinh как sh и cosh как ch?

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