Lepší generátor map pro VCMI

VCMI – free software verze hry Heroes of Might and Magic 3 – mě zase chytilo. Tentokrát nejen svádím bitvy fantastických armád, ale začal jsem do projektu zasílat i patche, většinou pro zlepšení výkonu a odstranění tuctů malých neefektivit.

Naostro to začalo, když jsem hrál na mapě Devil is in the Detail s myriádou různých modů, a tahy sedmi počítačových oponentů na laptopu (2 Skylake jádra s HT, 3.2 GHz) trvaly dvě minuty. To bylo dost dlouho na to, abych rozjel perf, jeden tah ho nechal profilovat a v dalším místo čekání začal studovat, kde program tráví čas, kde se nacházejí úzká hrdla a co stojí za neefektivitami.

Od té doby jsem strávil vpravdě nerozumné množství času zíráním do výstupů perfu, zdrojáků VCMI a absorbování hrůz C++. Co James Mickens psal v The Night Watch není vtip, ale realita programování v C++. Tým dobrovolníků za 17 let vývoje VCMI napsal ohromné množství C++ kódu (tady máte vizualizaci hierarchie tříd, aby bylo jasno i nezasvěceným) a nezáleží jak moc je kód kvalitní, vždy v něm budou žít bizarní hrůzy tohohle odporného jazyka. Na druhou stranu dokumentace je docela dobrá. V porovnání s PHP (dalším free software projektem, v němž jsem ztratil nejeden týden života) neskonale lepší. PHP gang se podle dostupných indicií zapřisáhl slibu mlčení a snaží se odradit nadšence odhodlané přiložit ruku k dílu. V porovnání s mizérií PHP je VCMI bohatě dokumentováno, i když jde o nekonečně méně důležitý projekt. VCMI hraje pár nadšenců převážně z východní Evropy, zatímco PHP pohání půlku všech webů. Ale to odbočuji…

VCMI hraju na aktuální vývojové verzi s plejádou vlastních napůl rozpracovaných patchů. Chci si být aspoň trochu jistý, že moje změny budou fungovat nebo aspoň nebudou způsobovat pády.

Jednou ze změn – o níž jsem chtěl dnes psát, než jsem se pustil do příliš širokého úvodu a tangent o Lovecraftovských hrůzách C++ a zdi mlčení kolem PHP – je lepší generátor náhodných map.

Náhodné mapy se ve VCMI generují na základě šablon. Ty kromě obecných metadat obsahují dvě hlavní sekce: definice zón a spojů. Zóna je (až na spojové cesty) uzavřená oblast a její definice říká, co v ní má být: jaká města, jaké zdroje, jaké poklady, jaký terén a tak podobně. Vzájemné propojení zón pak udávají spoje. Má mezi dvěma zónami vést cesta? Má být úzké hrdlo střežené? Jak silnou armádou? To vše se v šabloně píše, ale nic v ní neříká, jak přesně mají být zóny umístěné na mapě – X je spojená s Y, ale ne že X je vlevo nahoře a Y vlevo dole. Generátor se snaží najít smysluplné rozmístění a propojené zóny nasázet vedle sebe, aby mezi nimi mohla vést cesta. Když se mu to ale nepodaří, musí použít teleport. A někdy není zbytí.

Pro určité šablony s velkým množstvím zón (třeba 8XM8, kdyby se někdo ptal) generuje velice špatné mapy. Nedokáže umístit skoro žádný pár propojených oblastí vedle sebe a výsledek je změť nikdy nekončících portálů. Když se z mlhy vynoří nepřátelská armáda, nemůžu na první pohled odhadnout jak daleko vlastně je. Může příští tah začít obléhat moje hlavní město nebo musí projít třemi teleportujícími branami a ke mě se dostane nejdřív za čtyři tahy. Není to na první pohled poznat. Moje magická země nemá hranice, ale působí jako porézní houba plná děr, jako escherovský rébus vymykající se běžnému vnímání prostoru. Je to matoucí a nepůsobí to příliš uspokojivě.

Generátor ale sám o sobě není špatný a někdo si s ním očividně dal práci, aby fungoval dostatečně dobře v dostatečném množství případů. Proces generování má dvě fáze. V první se snaží rychle ale rozumně umístit zóny na malou mřížku – pro 42 zón je velká 7x7. Ve druhé fázi tuhle hrubou polohu namapuje na mapu žádané velikosti (G mapa má 252x252 políček) a začne optimalizovat jejich rozložení pomocí algoritmů pro force-directed graph drawing. To podává dobré výsledky pro jebus cross, ale ne pro monstrózní mapy velikostí huge, extra huge a gigantic.

Tady do hry vstupuju já.

Po obligátním zírání do zdrojáků VCMI jsem si uvědomil, že není zóna jako zóna. Některé hrají roli centrálních uzlů propojujících tři a více jiných oblastí, další fungují jen jako propojky dvou zón a poslední jsou jen přívěšky jediné zóny. Ty uzlové jsou nejdůležitější pro dobrou finální mapu a začnu tak, že je zcela náhodně rozmístím na malé mřížce (ale ne u kraje), následně začnu přidávat propojky tak, aby byly blízko oběma svým sousedům a nakonec nasekám přívěšky do zbylých volných míst co nejblíže k jejich cílové destinaci.

Používám přitom mřížku o něco větší než v čistém VCMI. Problém s jejich přístupem spočívá v tom, že když se snažím umístit 42 zón na pole velikosti 7x7 (kapacita 49), to se rychle zaplní a situace zdegeneruje na případ, kdy de facto vyberu první volné místo, protože mi jich zbývá jen hrstka a všechny jsou stejně špatné. Když ale zvolím větší mřížku, řekněme 9x9, algoritmus má o něco volnější ruce a více příležitostí vybrat dobré místo.

Tímto okamžikem moje změny končí a generátor pokračuje v optimalizaci poloh pomocí force-directed graph drawing.

Moje heuristika není úplně špatná, generuje mapy s mnohem menším počtem teleportů, ale stále jich je víc, než by se mi líbilo. Proto jsem použil jeden rafinovaný trik: proces zopakuji 10000× a vyberu nejlepší rozmístění, kde co nejvíce sousedů jsou skutečně sousedé.

Proč 10000? Žádný zvláštní důvod. Jde o dostatečně vysoké číslo, aby se prozkoumalo hodně možných variant, ale na druhou stranu je dostatečně malé, že se generování map zpomalí o maximálně vteřinu a ta se zcela ztratí.

Výsledky? Podle mě dobré. První obrázek je mapa vytvořená klasickým generátorem, druhý mým vylepšeným. Čáry jsou cesty, křížky portály (kterým se snažím vyhnout) a kolečka označují místa, kde jedna zóna přechází do druhé (těch chci co nejvíce).

Změna je to gigantická a chtěl bych ji eventuálně dostat do VCMI. Musím jen implementovat všechny případy, které jsem zatím ignoroval, otestovat, jestli funguje s podzemními mapami, vyčistit kód a ověřit, jestli netvoří horší mapy v případech, kdy současný generátor exceloval. Jinými slovy nejspíš nikdy, ale můžeme doufat.