Гедоммист і найближчі сусіди


Гедоммист (в Древньому Римі) — людина, яка отримує кайф від програмування.
Захоплення програмуванням супроводжують небезпеки — антисанітарія, забуті діти, службові догани, втекти молоко або летить у скроню жіночий чобіт.

Пам'ятаю про це, долаючи манливі складністю алгоритми.

І хочу розповісти про одну марною задачі, яку я вирішував тиждень в повному екстазі. Завдання народилася завдяки 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 {
нехай 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.

Побачимося, брати…
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.