Budu se snažit vysvětlit použité algoritmy co nejnázorněji a pomocí obrázků. Předem bych rád upozornil, že rozměry na obrázcích nejsou zcela přesné, je docela těžké přesněji vystihnout "hloubku" obrázku, když to samotný editor moc nepodporuje.
1. Vmapy
Nejdříve ale musím trochu nastínit, jak to celé funguje, protože to bude důležité pro pochopení (snad jediného) bugu tohoto systému. Vmapy jsou "vertikální mapy", které obsahují jen objekty a jejich pozice v dané (normální) mapě. Představte si třeba Crossroads v Barrens - bez vmap je to z pohledu serveru jen kus mírně vlnité země. Vmapy přidávají obrysy budov, plot, věž, ale asi nic víc. Objekty a npc nejsou na vmapách (protože se dají přidávat/mazat za běhu, vmapy jsou jen statická, neměnná data). Důležité je zmínit, že vmapy jsou jen pomocné obrazce pro výpočty na straně serveru (aby nemohl pyroblast proletět zdí), samotné budovy ve hře budou i bez nich.
Jelikož vmapy jsou jen objekty, určení výšky kdekoli na mapě jen podle nich není možné. Tam, kde nejsou, se prostě použije výška terénu. V tom spočívá ten bug - vmapy nejsou vždy přesné, existují místa, kde je terén rovný (kde by viditelně vmapa neměla být) a lze po něm projít, ale přesto tam nějaká anomálie je, nějaký špičatý kopec ve vmapě, který naprosto zkreslí výpočet výšky na daném bodě. Přes takový "kopec" pak nejde přeskočit, přestože hráč vidí jen rovnou zem, po které může chodit.
Našel jsem taková místa i v BG (ve WSG poblíž hordské základny, v EOS na 2 místech - u jednoho z konců obou postranních mostů), ale v 99% případů na ně snad nenarazíte.
S vmapami přichází na scénu další problém - jeden bod na rovině x,y může mít více bodů v rozměru Z (vizte přiložený obrázek). Algoritmus pro hledání výšky tedy napřed hledá dolů, a jen pokud nenajde zemi, hledá směrem nahoru. Více možných Z pozic mě vlastně donutilo přepsat výpočet bodů na přímce mezi hráčem a cílem z 2D do 3D (více v bodu 3).
http://i.imgur.com/rVAWH.png
2. Cíl skoku - rovnost terénu kolem pozice
Aby se nedalo skákat na zdi, bylo nutné vyřešit nějak výpočet "rovnosti" cílového "zaměřovače" skoku. Z několika vhodných algoritmů to nakonec vyhrál výpočet pomocí oktagonu:
Vrcholy oktagonu (osmiúhelníku) vepsaného kružnici s poloměrem 0.5yd tvoří 8 bodů, u kterých se kontroluje výška a zjišťuje maximum a minimum. Pokud je výškový rozdíl maxima a minima víc, jak 0.9yd (což s poloměrem 0.5yd dává myslím úhel kolem 53 stupňů), je povrch vyhodnocen jako nerovný.
http://i.imgur.com/LXPbb.png
Tento algoritmus funguje relativně dobře pro naprostou většinu případů, brání proti skoku na zeď (první obrázek), protože oktagon je tvořen jen pomocí X,Y souřadnic (je vždy vodorovně položený) a tím pádem minimálně jeden bod "zaměřovače" v prvním obrázku bude úplně nahoře na budově a minimálně jeden další dole. Jejich rozdíl je roven přibližně výšce budovy, což je určitě víc, jak 0.9yd.
Na druhém obrázku jsem zachytil trasu za alianční WSG základnou, kde je asi největší uznatelný sklon zaměřovače, na obrázku to není moc dobře zachyceno, ale výškový rozdíl mezi fialovým a žlutým bodem je okolo 0.84yd, což je méně, než 0.9yd a tudíž je terén uznán jako "rovný". Červených teček si zatím nevšímejte.
http://i.imgur.com/YHyEU.pnghttp://i.imgur.com/XzBgE.png
Teoreticky vzato ale může nastat případ, kdy se někdo pokusí skočit na objekt tak tenký, že všechny body oktagonu budou pod ním, jen střed kružnice bude na daném místě. V případě starého známého mailboxu to nevadí, na ten vyskočí skoro každý (první obrázek), ale ... mějme objekt, který vypadá jako ... spousta mailboxů na sobě - pak už je výškový rozdíl značný.
http://i.imgur.com/iLRkF.pnghttp://i.imgur.com/AcXMG.png
K vyřešení problému je tedy potřeba započítat střed - nakonec jsem použil algoritmus zprůměrování výšek všech vrcholů oktagonu - pokud je rozdíl výšky středu od tohoto průměru větší, než je velikost poloměru (0.5yd), terén není uznán jako rovný.
3. Trasa - rovnost terénu podél přímky
Naprosto nesouvisejíc s cílem skoku bylo potřeba vyřešit samotný skok. Současné řešení v podobě možné výšky skoku v závislosti na délce je dosti omezující. Inspiroval jsem se z osmiúhelníku a vytvořil několik bodů na přímce od hráče až k cíli (přímka černě, body zeleně). Body jsou od sebe vzdáleny přibližně 0.5-1yd - pokud je hráč od cíle vzdálen necelý 1yd, jsou vytvořeny jen dva body (hráč, cíl), pokud je vzdálenost 1-1.99yd, je přidán třetí bod doprostřed, atp. Tedy s rostoucí vzdáleností se "skoky" velikosti vzdálenosti mezi body zmenšují, jinak řečeno vzdálenost mezi body konverguje k 1yd s rostoucí celkovou vzdáleností hráče od cíle.
Pro každý bod je poté zjištěna jeho výška (červeně). Pokud je tato výška větší, než vzdálenost mezi body (na rovině x,y), je terén uznán jako moc strmě stoupající a tím pádem nerovný. Maximální úhel tohoto převýšení lze snadno spočítat jako arctan(rozdíl_výšek/vzdálenost), tedy 45 stupňů, což je přibližně krajní hranice toho, co hráč může vyjít "po svých" (první obrázek - skok povolen).
Na druhém obrázku je pěkně vidět výškový rozdíl posledního bodu (druhý obrázek - skok zakázán).
http://i.imgur.com/qhRvR.pnghttp://i.imgur.com/oMXmF.png
4. Detekce údolí
Napřed (před nápadem s body na trase) jsem chtěl vyřešit problém skoku warriorů mezi budovami a začal jsem pro to psát algoritmus na "detekci údolí", který by skok zakázal, ale povolil všude jinde. Z toho nakonec nic nebylo, jen jeden algoritmus (v příloze označen jako 4), který měl navíc nevýhodu v rovném, ale hodně "hrbatém" terénu (durotar). Nicméně jsem se přesto k detekci údolí vrátil v trochu jiném duchu.
Představte si rovný terén, který obsahuje hluboké úzké díry. Díry úzké natolik, že je lze přeskočit normálním skokem postavy. Při použití přímky s body by tak mohl nějaký z bodů spadnout do propasti a skok by se nepovedl.
http://i.imgur.com/HqlXa.png
Bylo tedy potřeba vymyslet nějaký způsob, jak tohle detekovat. Ten způsob je označen v příloze jako "5" - pro každý bod na přímce mezi hráčem a cílem kontrolujeme výšku, pokud je výška bodu N+1 vůči bodu N o hodně nižší (přesáhne nějakou pomyslnou hranici), je box N označen jako "fatální". Poté se kontroluje každý další bod, zda je (výškově) alespoň řekněme 2yd pod fatálním bodem, zvýšeným o 0.5yd (aby druhý okraj propasti mohl být i o trošku výše). Pokud je takový bod nalezen, vypočte se jeho x,y vzdálenost (pomocí pythagorovy věty) od fatálního bodu - pokud je větší, než 5yd (približná délka normálního skoku postavy), trasa není uznána jako rovná a v hledání dalšího fatálního bodu se nepokračuje. Tento algoritmus taky vyřešil pěkně maximální možné převýšení při seskoku dolů - pokud není nalezena druhá strana propasti (hráč skáče leapem dolů), je skok zamítnut (např. dlouhá "propast" mezi budovami).
Jak to ale v životě bývá, někdy se člověk nadře zbytečně. Po napsání a vylazení tohoto algoritmu jsem se ujal testování. Skákal jsem (leapem) jak magor všude možně - BG, durotar, outland, ..., až mi z toho hrabalo na mozku. Při tom všem skákání jsem přišel na to, že situace s "propastí" v reálném světě praticky neexistuje, zato omezení skoku dolů značně snižuje požitek ze skákání. Takže nastalo jedno kruté rozhodnutí a to předělat veškerou moji současnou práci na tomto algoritmu (asi 50 řádků kódu) do 3 řádků, které vypadají nějak takto:
Code: Select all
for (i = 1; i < numpoints; i++)
if (pointZ[i] - pointZ[i-1] > pointdist)
return false;
To by tak asi bylo všechno. Omlouvám se za případné překlepy / češtinářské nedostatky, ale je 5 hodin ráno, já jsem už docela ospalý a opravdu se mi to nechce celý tento text precizně kontrolovat.
Jo a taky jsem znemožnil leap warriora, pokud hráč padá (ale povolil ho, pokud je ve skoku a ještě "nezačal padat").
Příloha
V průběhu tvorby tohoto "systému" jsem zkoušel několik možností / algoritmů, které byly poté nahrazeny / zrušeny. Jejich stručný popis ale zůstal v komentáři v kódu, takže to zde mohu přiložit - pro rýpaly, kteří by měli nějaké připomínky o tom, že mi trvalo napsat 3 řádky tolik dní. Je to nicméně v angličtině, jako celý můj kód.
Code: Select all
/* excluded algorithms:
*
* --- height difference ---
* 1: find minimum and maximum and compare them against algo 2
* 2: use height difference (calculated from an angle, say, 45 degrees)
* between source and destination
* 3: if the height diff between any two points on the path is larger than
* the x,y distance between those points (eg. if the angle between
* point N and point N+1 is 45 (or more) degrees up/down), remember that
* - if it happens again, the path is not really flat
*
* --- valley detection ---
* 4: remember the amount of increased/decreased height between points
* and if both (and only both) of those totals are above 1/5 of the total
* distance between start/end, then there's a valley on the path
* 5: look for a point A with a negative fatal (>4yd) height difference against
* a previous one - if such point is found, remember it and look for
* another point B, which is at most 3yd below A (and still below A+0.5)
* - if point B is found, compare it's distance to point A with a regular
* player jump distance (around 5yd)
* - if within that range, look for another fatal point,
* - else ... well, the valley is just too wide
*/