Гедоммист (в Древнем Риме) — человек, получающий кайф от программирования.

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

Помню об этом, одолевая манящие сложностью алгоритмы.

И хочу рассказать об одной бесполезной задаче, которую я решал неделю в полном экстазе. Задача родилась благодаря 3aicheg, чей комментарий дал мне идею для игры под iOS (вижу Ваши глаза, Шо опять?). Смысл в том, чтобы сделать match game на нерегулярной сетке с гравитацией.

Кстати, если вы думаете, что рассказывая здесь о своем бесплатном приложении, можно получить мировую славу и купить яхту, то вот таблица

Рейтинг статьи	Просмотров статьи	Просмотров видео	Загрузок
+30	20 000	5 000	18
-2	2 500	2 000	14

И потому я восхищаюсь бескорыстными авторами Хабра (особенно теми, кто владеет русским слогом). Теперь к делу! А дело такое…

Задачка 1 — расстановка начальных данных

Итак, рассмотрим прямоугольник (экран нашего телефона), вершины прямоугольника перенумерованы 0, 1, 2, 3. Внутри этого прямоугольника будут твориться всякие безобразия.


Рис. 1 Прямоугольник с вершинами 0, 1, 2, 3

Бросим в данный прямоугольник случайно N точек, пронумеруем их от 4 до 4+N. Почему от 4? Потому что все места (0-3) уже заняты бегемотиками.


Рис. 2 Набор случайных точек

Случайный разброс порой опасен — некоторые точки могут упасть слишком близко друг от друга, так что игрок не сможет различать их на экране и нажать на приглянувшуюся ему точку. Зная физический размер отпечатка указательного пальца игрока, я добавляю условие, что расстояние между точками должно быть не менее 26 пикселов. Каким образом удовлетворить этому условию? Два способа 1) Двигать точки в направлении разреженного пространства и 2) бросать новую точку, пока не выполнится условие radiusMin>26. Второй способ легче, но опасней — возможно зацикливание при слишком больших значениях N. Но у меня с N все в порядке, запас свободной площади пятикратный и потому двигаемся дальше, а именно находим ближайших соседей для всех наших точек. Идем по порядку, то есть сначала ищем соседей для точки с номером, как вы понимаете, 4.

Для этого упорядочим по часовой стрелке все радиус-векторы от нашей точки до всех остальных.


Рис. 3 Упорядочим радиус-векторы [9-7-5-10-11-8-6]

На языке Swift это выглядит так:

                let x0 = pts[4].x
                let y0 = pts[4].y
                var vtx = [Point]()
                for i in 5..<pts.count {
                    let x = pts[i].x
                    let y = pts[i].y
                    let u = x-x0
                    let v = y-y0
                    let a = atan2(v, -u)
                    vtx.append(Point(x:(x+x0)/2, y:(y+y0)/2, angle:a ))
                    }
                }
                vtx = vtx.sorted(by:{ $0.angle > $1.angle })
 

Теперь в нашем массиве vtx хранятся вершины [9-7-5-10-11-8-6], пройдемся по ним и построим многоугольник, окружающий искомую точку с номером 4. Итак, изначально, нашу точку окружает прямоугольник с вершинами [0-1-2-3], как на рис. 1.

Берем первую вершину из упорядоченного списка — это точка с номером 9. Строим перпендикуляр к отрезку [4-9], делящий его пополам.


Рис. 4 Прямая, равноудаленая от точек 4 и 9

Получившаяся прямая либо пересекает многоугольник [0-1-2-3], либо нет. Глядя на рисунок 4 легко обнаружить, что пересекает. Уравнение пересечения отрезка и прямой я решил не приводить. Таким образом вместо [0-1-2-3] получился многоугольник [0-1-9-3], который мы видим на рисунке 5.


Рис. 5 Многоугольник [0-1-9-3]

Переходим к следующей точке из списка [9-7-5-10-11-8-6]. Это точка номер 7. Делаем все то же самое — строим перпендикуляр, равноудаленный от точек 4 и 7 и проверяем, пересекает он наш многоугольник [0-1-9-3].


Рис. 6 Многоугольник [0-1-9-3] не пересекается прямой [4-7]

Не пересекает, делать ничего не надо, следовательно переходим к следующей паре точек с номерами 4 и 5.


Рис. 7 Многоугольник [0-1-9-5-3]

И так далее. Метод Форчуна (так любимый на Хабре, уже 3 статьи про него листал) для ускорения нахождения соседей применять здесь не стоит, поскольку нет у нас 100 000 точек в задаче. И 1000 точек нет. А сколько? 50-70 точек — это число обусловлено физическим размером экрана телефона. Вот финальная картина для многоугольника вокруг первой вершины с номером 4


Рис. 8 Многоугольник [0-6-9-10-8-3]

Для рисования многоугольников я использую родной UIKit с заливкой текстурой ( оттуда же и рисование линий). Пример кода внутри func draw(_ rect: CGRect):

    let colors:[UIColor] = [UIColor.black,
       UIColor(patternImage: UIImage(named: "b_19.png")!),
       UIColor(patternImage: UIImage(named: "b_20.png")!),
       UIColor(patternImage: UIImage(named: "b_21.png")!),
       UIColor(patternImage: UIImage(named: "b_22.png")!),
       UIColor(patternImage: UIImage(named: "b_23.png")!),
    ]
 
    func renderSimple(_ t:Convex)
    {
        let path = UIBezierPath()
        let strokeColor = UIColor.black
        strokeColor.setStroke()
        path.lineWidth = 1.0
        let clr = t.color
        var i = 0
        for p in t.vtx {
            if i == 0 {
                i = 1
                path.move(to: p)
            } else {
                path.addLine(to: p)
            }
        }
        if clr>0 {
            let fillColor = colors[clr]
            fillColor.setFill()
            path.fill()
        }
        path.stroke()
    }
  

Ух. Устал сочинять. Разомнем пальчики сыграем пару уровней в получившейся игре Zabivaka



Идем дальше. Получилась такая случайная, но симпатичная картина.




Рис. 9 Уровень Канзас — так и хочется нажать и очистить синюю цепочку

Если у вас возникло такое желание (нажать и очистить синюю цепочку) — значит, игра не самая плохая. Как видно, нужно было придумать закон по перетеканию цветных ячеек в освобождающиеся пустые клетки. Почему они должны перетекать или сдвигаться? Потому что в игре включено поле силы тяжести. После численных экспериментов я набрел на закон Трампа-Галилея — частица перемещается в пустую соседнюю, если центр тяжести последней находится ниже центра тяжести исходной частицы. Желе вверх не течет. И второе условие — низшая точка общей границы двух частиц должна быть ниже центра тяжести исходной частицы — это значит, что желе не течет через высокий край стакана. В игровом процессе данный закон был мной незамедлительно опробован и одобрен.

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

Меню

В любой игре необходима цель — обычно ты должен пройти все уровни. Уровни изображают по всякому — например, это города на карте, которые ты должен покорить. Я решил, что триангуляция — отличный способ рисовать реальные карты (схематично, анимашно) не прикладывая никаких усилий. И действительно, я загрузил список городов мира с гео-координатами и построил на этих данных сетку по описанному выше алгоритму. И вот что получилось.




Рис. 10 Карты узнаваемых стран

Список гео-координат для, например, Италии выглядит так:

      City(name:"Rome",x:41.9000,y:12.4833,s:4),
        City(name:"Ancona",x:43.6333,y:13.5000,s:4),
        City(name:"Ascoli",x:42.8500,y:13.5667,s:4),
        City(name:"Bari",x:41.1333,y:16.8500,s:4),
        City(name:"Bologna",x:44.4833,y:11.3333,s:4),
        City(name:"Brescia",x:45.5500,y:10.2500,s:4),
        City(name:"Catania",x:37.5000,y:15.1000,s:4),
        City(name:"Cesena",x:44.1433,y:12.2497,s:4),
        City(name:"Cagliari",x:39.2167,y:9.1167,s:4),
        City(name:"Florence",x:43.7667,y:11.2500,s:4),
  

По-моему, отличный способ построения игровых карт. Разумеется, надо добавить паразитные точки, эмулирующие море или соседние страны. Я добавлял по 16 точек на каждую карту, некоторые паразитные точки приходилось редактировать ручками.

Для устрашения игрока я ввел правило — не более 15 кликов на партию. Было сложно тестировать игру в подобных условиях, я малодушно увеличил это число до 16. Кроме того, обнаружил ошибку на последнем ходе, но исправлять её не стал — эта ошибка помогает преодолеть казалось бы невозможные расклады. И придает настроения игре. Для великолепного мастерского прохождения уровня добавил бонусов — анимация грудастой девушки и пиратскую музыку. Короче, я лично доволен. Ну и вам, надеюсь, нескучно было почитать в эту ненастную пору историю про игрушку на Swifte.

Увидимся, братья…