Гедоммист (в Древнем Риме) — человек, получающий кайф от программирования.
Увлечению программированием сопутствуют опасности — антисанитария, забытые дети, служебные выговоры, сбежавшее молоко или летящий в висок женский сапог.
Помню об этом, одолевая манящие сложностью алгоритмы.
И хочу рассказать об одной бесполезной задаче, которую я решал неделю в полном экстазе. Задача родилась благодаря 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.
Увидимся, братья…
