Жизнь Конвея на F# + OpenGL

Почему F#?



Просто потому что он мне нравится. Решив пару десятков задач на projecteuler я решил найти более практическое применение знаниям и написать нечто не сложное, но осязаемое.

Кому интересно — добро пожаловать под кат.

Сразу оговорюсь. Я не являюсь специалистом в области функционального программирования или OpenGL, поэтому буду рад любым осмысленным комментариям и подсказкам как сделать лучше/быстрее/красивее.

Описывать сам язык смысла не имеет. Уже есть достаточно много материала по теме.
Можно, для начала, посетить Wiki, F# Development Center, What's new in F# 3.0.

Итак, приступим


Первым делом определим типы для нашей клетки:
type Sex = |Male|Female
type Cell = { Sex: Sex; Age: int; Position: (int * int)}


Пол будем использовать при отрисовке ячеек. В дальнейшем я планирую использовать его для экспериментов с алгоритмом.
Объявим глобальные переменные игры:
//Globals
let mutable (field:Cell[]) = [||] //поле с клетками
let mutable pause = false         //Признак паузы игры
let mutable isInProc = false      //признак того, что поле рассчитывается
let mutable generation = 0        //текущий шаг
let mutable ftime = DateTime.Now  //
let mutable fps = 0.0             // будут использоваться для вычисления fps
//Матрица для отрисовки openGL
let mutable modelview = Matrix4.LookAt(Vector3.UnitZ, Vector3.Zero, Vector3.UnitY)
let mutable Size = 100            //размерность поля
let mutable CellCount = 2000      //стартовое количество клеток
let mutable LifeLength = 50      //время жизни клетки
let mutable ScreenWidth = 500     //размер окна по умолчанию


Основной класс, отвечающий за игровой процесс


Первым делом напишем методы для генерации новых ячеек:
type Life() = 
    member this.genCell (rnd:Random) = {
            Sex = match rnd.Next(2) with |0 -> Sex.Male |_ -> Sex.Female
            Age=0
            Position=(rnd.Next(Size), rnd.Next(Size))}
 
    member this.genCells = 
        let rnd = new System.Random()
        let rec lst (l:list<Cell>) = 
            match l.Length with
            |c when c = CellCount -> l
            |_ -> 
                match this.genCell rnd with
                |c when not (this.existCell (l |> List.toArray) c.Position) ->  lst (c::l)
                |_ -> lst l
	List.Empty |> lst |> List.toArray

genCell создает новую клетку используя объект Random.
genCells заполняет список новыми клетками.
Рекурсивная функция
let rec lst (l:list) создает новый список и вставляет туда новую клетку, если координаты свободны.

Вычисляем координаты соседних клеток:
member this.allNeighbourCells (position:int*int) = let nCells (point:int*int) = let x,y = point [| (x-1, y-1); (x-1, y); (x-1, y+1); (x, y-1); (x, y+1); (x+1, y-1); (x+1, y); (x+1, y+1); |] let (!) pos = let tx = match fst pos with |x when x < 0 -> Size - 1 |x when x >= Size -> 0 |_ -> fst pos let ty = match snd pos with |y when y < 0 -> Size - 1 |y when y >= Size -> 0 |_ -> snd pos (tx, ty) nCells position |> Array.map ((!))

Здесь присутствует 2 локальные функции:
nCells возвращает все соседние ячейки для point
! переопределенный операнд, который возвращает координаты, выходящие за границы игрового поля обратно, формируя «бесконечное» игровое пространство.

Определим еще несколько вспомогательных функций:
member this.existCell field c = field |> Array.exists (fun af -> c = af.Position)

Проверка на наличие клетки с указанными координатами.

member this.partitionfield field = this.allNeighbourCells >> Array.partition(fun c -> this.existCell field c)
member this.pFree field = this.partitionfield field >> snd
member this.pExist field = this.partitionfield field >> fst

Partitionfield делит все соседние клетки на занятые и свободные создавая tuple из двух массивов.
pFree, pExist соответственно получают доступ к списку свободных и занятых клеток

Собственно главный метод, пересчитывающий игровое поле весьма лаконичен:
    member this.Iterate (field:Cell[]) =
        //Список свободных соседних ячеек
        let freeNeighb = field 	|> PSeq.collect (fun c -> this.pFree field c.Position) 
				|> Seq.distinct 
        let born = freeNeighb 
                    |> Seq.filter (fun c -> this.pExist field c |> Array.length = 3)
                    |> Seq.map(fun c ->
                                let rnd = new System.Random()
                                {this.genCell(rnd) with Position = c})
        let alive = field   |> PSeq.filter(fun c -> let neighb = this.pExist field c.Position |> Array.length
                                                    neighb <= 3 && neighb >= 2)
                            |> PSeq.map (fun c -> {c with Age = (c.Age + 1)})
        let res = alive |> Seq.append born |> Seq.toArray
        res

Что здесь происходит:
  1. Получаем список всех свободных ячеек, которые являются соседями клеток (freeNeighb)
  2. Фильтруем их и создаем новые клетки для тех ячеек, для которых выполняется условие (кол-во соседей = 3) (born)
  3. Для существующих клеток фильтруем тех, кто выжил
  4. Объединяем 2 списка в один и возвращаем результат работы


Код, связанный с OpenGL я в тексте статьи опущу, т.к. он достаточно простой.
Остановлюсь только на 2х методах:
doNextStep

Асинхронно вычисляет следующее поколение и заполняет список клеток, когда вычисление окончено:
        member this.doNextStep =
            async{
                let res = (this.life.Iterate field)
                field <- res |> Array.filter(fun c -> c.Age < LifeLength)
                isInProc <- false
                generation <- generation + 1
                let delta = DateTime.Now - ftime
                ftime <- DateTime.Now 
                fps <- Math.Round ((fps + 1000.0 / delta.TotalMilliseconds) / 2.0, 1)
            }

OnRenderFrame

Функция OpenGL, отрисовывающая кадр:
        override o.OnRenderFrame(e) =
            base.OnRenderFrame e
            match (pause, isInProc) with
                | (false, false) -> isInProc <- true; Async.Start(o.doNextStep)
                | _ -> ()
                    
            GL.Clear(ClearBufferMask.ColorBufferBit ||| ClearBufferMask.DepthBufferBit)
            GL.MatrixMode(MatrixMode.Modelview)
            GL.LoadMatrix(&modelview)
            field |> Seq.iter (fun c -> o.DrawCell c)
            if not pause then
                base.Title <- String.Format("F# Life cell count: {0} Generation: {1} FPS: {2}", (field |> Seq.length), generation, fps)
            else
                base.Title <- String.Format("F# Life cell count: {0} Generation: {1} Paused", (field |> Seq.length), generation)
            base.SwapBuffers()


Я провел небольшой эксперимент, добавив время жизни для клетки и удаляя те, которые старше LifeLength:
member this.doNextStep =
....
               field <- res |> Array.filter(fun c -> c.Age < LifeLength
...


При отрисовке каждой ячейки я проставляю прозрачность в зависимости от возраста клетки. Чем старше, тем прозрачней:
        member this.DrawCell (cell:Cell) = 
            let cellWidth = float32(this.ClientSize.Width) / float32 Size
            let alpha = match (1.f - float32 cell.Age / float32 LifeLength) with 
                        |c when c < 0.f -> 0.f 
                        | c -> c
            let color = match cell.Sex with 
                        |Male -> [|0.5f; 0.f; 0.f; alpha|] 
                        |Female -> [|0.7f; 0.f; 0.f; alpha|]
            let pos = (float32 (fst cell.Position) * cellWidth, float32 (snd cell.Position) * cellWidth)
            GL.Begin(BeginMode.Triangles)
            GL.Color4 (color)
            GL.Vertex3(fst pos + 0.5f, snd pos + 0.5f, 1.f)
            GL.Vertex3(fst pos + 0.5f, cellWidth + snd pos - 0.5f, 1.f)
            GL.Vertex3(cellWidth + fst pos - 0.5f, cellWidth + snd pos - 0.5f, 1.f)
            GL.Vertex3(cellWidth + fst pos - 0.5f, snd pos + 0.5f, 1.f)
            GL.Vertex3(fst pos + 0.5f, snd pos + 0.5f, 1.f)
            GL.Vertex3(cellWidth + fst pos - 0.5f, cellWidth + snd pos - 0.5f, 1.f)
            GL.End()


Скриншоты работы:
image
Самая стабильная фигура при включенном времени жизни - мерцающий квадрат:


Что надо доделать

Есть что оптимизировать.
Код не стал сильно рефакторить что бы получить более полезные комментарии :)
Не хватает "рисования" с помощью мыши, загрузки/сохранения данных в файл

Исходники можно скачать по адресу bitbucket
С нетерпением жду отзывов!.

Upd: Попросили добавить ссылки на описание игры. Как оказалось не все в курсе что это :)
Раз
Два
Поделиться публикацией

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

    +1
    Может хватит уже использовать статический конвеер? Этот метод рендеринга устарел уже лет как 10. За это время способы рендеринга уже пару раз менялись: glBegin/glEnd+FFP — VAO+FFP — VBO+shaders. Может хотя бы в 2013 будем использовать VBO?
      +2
      Если вы внимательно прочитаете начиная с фразы «Сразу оговорюсь...» то поймете что я делал OpenGL часть по туториалам.
      Дайте пример правильного кода. Буду благодарен.
        +3
        Читал я внимательно. Мой комментарий стоило рассматривать как совет. Посмотрите в интернете примеры реализации рендеринга с помощью VBO, там все просто.
        P.S. Минусы аргументируйте пожалуйста.
        +1
        Тогда уже все на GPU считать.
        jbryan.github.com/webgl-experiments/life.html
          0
          О, спасибо. Интересно.
          Про GPU я начал думать, но пока не придумал как переделать код под него.
            +1
            Ну там относительно просто все. Нужно читать из текстуры предыдущее состояние, сам шаг для клетки считать в шейдере, и результат писать в текстуру. По ссылке есть весь код для WebGL, на десктопе оно не сильно отличается.
        0
        Спасибо за интересную статью!
        Единственное возможно стоит картинки перенести в хабрасторадж — а то уже не открываются.

        > Код, связанный с OpenGL я в тексте статьи опущу, т.к. он достаточно простой.

        Возможно не стоило опускать а добавить спойлером — это тоже интересно — залез в исходники ради них :).
          0
          Хабрастор не загружает картинки. Похоже локальные политики безопасности на работе. Как получится — перенесу обязательно.
          +3
          Очень много mutable. Это не принято в функциональных языках. А в многих местах оно вообще не несёт смысла — почему mutable объявлен Size? Он меняется во время работы программы?

          Position: (int * int) — а зачем? Чтобы держать в голове, что первый элемент это X, а второй — Y-координата? Или читабельности добавляют конструкции вида fst cell.Position?

          Объекты Random создаются алгоритмом самостоятельно, это нехорошо. Желательно пользоваться всегда одним и тем же объектом, который передаётся ему «снаружи» — это сделает результат повторяемым.
            0
            В принципе согласен. Есть что дорабатывать.
            0
            Реализация логики игры на том же F# в 127 символов trelford.com/blog/post/140.aspx
              0
              Не меняя саму логику вычислений уложился в 991 символ. Но это уже не читабельно :)
              let anc p = 
                  let nc (x,y) = [|(x-1,y-1);(x-1,y);(x-1,y+1);(x,y-1);(x,y+1);(x+1,y-1);(x+1,y);(x+1,y+1);|]
                  nc p |> Array.map (fun p -> (match p with|(x,_) when x<0->Size-1|(x,_) when x>=Size->0|(x,_)->x),(match p with|(_,y) when y<0->Size-1|(_,y)when y>=Size->0|(_,y)->y))
              let ec f c = f |> Array.exists (fun af -> c = af)
              let pf f = anc >> Array.partition(fun c -> ec field c)
              let pFr f = pf f >> snd
              let pEx f = pf f >> fst
              let rnd = new System.Random() 
              let gc=(rnd.Next(Size), rnd.Next(Size)) 
              let gcs = let rec lst (l:list<int*int>)=match l.Length with|c when c=CC->l|_->match gc with|c when not(ec(l|>List.toArray)c)->lst(c::l)|_->lst l
                        List.Empty |> lst |> List.toArray 
              let i f =
                  let fn=f|>PSeq.collect(fun c->pFr f c)|>Seq.distinct 
                  let b=fn|>Seq.filter (fun c ->pEx f c|>Array.length=3)|>Seq.map(fun c->gc)
                  let a=f|> PSeq.filter(fun c -> match pEx f c|>Array.length with |n when n<=3&&n>=2->true|_->false)
                  a|>Seq.append b|>Seq.toArray
              
              0
              Не совсем в тему — а вам действительно комфортно видеть красное на синем?
              Не знаю, может это у меня цветовосприятие такое, но аж плохо становится при виде такого сочетания.
                0
                Честно говоря комфортно, но допускаю что может зависеть от настроек монитора.
                  0
                  Может он конь? :)

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