Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » A* algoritm

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

A* algoritm

Module by: Ott Vaiknemets. E-mail the author

Summary: A* algoritmi kasutamine lühima tee leidmiseks kaardil asuva kahe punkti vahel.

Algoritm "A*"

A* võib olla olla algajaile keeruline. Kuigi veebis on palju artikleid, mis selgitavad A* algoritmi, on enamus neist kirjutatud inimeste poolt kes on kursis põhialustega. Selle artikli sihtgrupp on algajad. Kuigi artikli lõpus on viited näitekoodile C++-s ja Blitz Basic-us, pole see artikkel programmeerimiskeele-spetsiifiline.

Otsingupiirkond

Oletame et keegi tahab minna punktist A punkti B ja nende kahe punkti vahel on sein. Pildil kujutab roheline punkt alguspunkti A ja punane lõpppunkti B, sinised ruudud nende vahel on sein.

Joonis 1
Joonis 1 (graphics1.jpg)

Paneme tähele, et otsingupiirkond on jaotatud ruudustikuks. Otsingupiirkonna lihtsustamine, mida me sellega tegime, on esimene samm teeleidmisel. See konkreetne võte lihtsustab meie otsipiirkonna lihtsaks kahemõõtmeliseks maatriksiks. Iga üksus selles maatriksis kujutab endast ühte ruutu ruudustikust, mis on märgitud kas "läbitavaks" või "läbimatuks". Tee leidmiseks leitakse ruudud, mis tuleb läbida jõudmaks punktist A punkti B. Tee läbimisel liigutakse ühe ruudu keskkohast järgmise ruudu keskele kuni jõutakse sihtkohta.

Neid ruute kutsutakse sõlmedeks (node). Miks mitte kutsuda neid lihtsalt ruutudeks? Sellepärast, et võid piirkonna jaotada ka ükskõik mis muudeks kujunditeks, näiteks kolmnurkadeks. Ja sõlmed ei pea asuma kujundi keskel, vaid võivad olla ka servades või ükskõik kus. Siin kasutatakse ruute, kuna see on lihtsaim.

Alustamine

Peale otsipiirkonna lihtsustamist hallatavaks arvuks sõlmedeks on järgmiseks sammuks lühima tee leidmine. Selleks me alustame punktist A naaberruutudele liikumist kuni jõuame punkti B.

See toimub järgmiste sammudega:

  1. Lisa alguspunkt A loendisse "avatud". See loendis hoiame ruute mis võivad jääda otsitavale teele ehk see on loend ruutudest, mis vajavad lähemat uurimist. Esialgu on seal vaid 1 ruut - A.
  2. Lisa ka kõik naaberruudud, mis on märgitud "läbitavaks" (ehk mis eelmisel joonisel pole sinised), "avatud" loendisse. Iga lisatud ruudu kohta märgi temale eelnevaks ruuduks ruut A. Eelnevate ruutude meeles pidamine on oluline kui tahame hiljem teed läbida. Seda vaatleme lähemalt allpool.
  3. Eemalda alguspunkt A "avatud" loendist ja lisa ta "suletud" loendisse. Selles loendis on ruudud mida praegu pole vaja rohkem uurida.

Selleks hetkeks on sul olemas info, mida illustreerib järgnev joonis. Keskmine roheline ruut on alguspunkt, heledama raamiga tähistame, et ta on kantud "suletud" loendisse. Kõik piirnevad ruudud on "avatud" loendis, seda tähistab roheline raam. Iga uurimisel ruut sisaldab viidet eelmisele ruudule, joonisel tähistab seda hall joon mis on suunatud alguspunktile (ehk ruudule, kust jõuti noolega ruudule). 

Joonis 2
Joonis 2 (graphics2.jpg)

Järgmiseks valime ühe ruudu "avatud" loendist ja kordme eelnevaid samme. Valiku tegemiseks leiame "avatud" loendi ruutudele "hinna", selle valem onF = G + HF tähistab hinda, G tähistab praeguseks hetkeks leitud tee pikkust alguspunktist sellesse konkreetsesse punkti, H on oletuslik teepikkus sellest punktist lõpppunkti B. Seda on tihti nimetatud heuristiliseks, mis võib olla pisut eksitav. Põhjus selle tee nimetamiseks heuristiliseks on, et me ei tea veel tegelikku teepikkust punkti B (me alles otsime seda ja pole jõudnud kõigi takistusteni). On erinevaid võimalusi H arvutamiseks, neist tuleb juttu allpool.Tee leitakse, korrates eelnavalt toodud töötlussamme, valides järgmiseseks ruuduks "avatud" loendist sellise, mille hind F on väikseim.Nagu üleval öeldud, on G teepikkus alguspunktist antud ruutu. Käesolevas näites määrame igale horisontaal- või vertikaal-suunas liikumise sammule hinnaks 10 ja diagonaal-suunas liikumise sammule 14. Hind 14 tuleneb sellest, et teepikkus ühikruudu diagonaali pidi liikumisel on ruutjuur 2-st ehk ca. 1,414 korda pikem kui horisontaalis või vertikaalis liikudes. Kümnega on need ühikud korrutatud vaid lihtsustamise huvides. (Pealegi arvutab arvuti täisarvudega kiiremini, tee leidmine võib teinekord olla väga töömahukas ettevõtmine.)Seni läbitud teepikkuse G leidmiseks tuleb eelmise ruudu G-le liita 14 või 10 vastavalt sellele, kas eelmine ruut on diagonaalsuunas või mitte. H leidmiseks on mitmeid võimalusi. Siin me kasutame Manhattani meetodit, kus me leiame sammude kogusumma vertikaalselt ja horisontaalselt liikudes, ignoreerides diagonaalset liikumist ja ignoreerides võimalikke takistusi mis võivad olla teel. Ehk H=x koordinaatide erinevuse ja y koordinaatide erinevuse summa korrutatud 10-ga (külgepidi liikumise sammu hind). Nimetus "Manhattani meetod" tulenevat sellest, et taoline loogika kehtib ka ruudustiku-kujuliste kvartalitega linnas liikudes (mil kvartalit ei saa läbida diagonaalselt).

Mida täpsemini me järelejäänud teelõigu pikkust ennustada suudame, seda kiiremini leiab ka algoritm lahenduse. Kui me ülehindame vahemaad, siis pole garanteeritud et lahenduseks on lühim tee. Sel juhul tegeleb meie algoritm "sobimatu heuristikaga" (inadmissible heuristic). Tehniliselt meie näites on Manhattani meetod sobimatu kuna ülehindab pisut järgijäänud distantsi. Kuid me kasutame seda ikkagi kuna on lihtsalt mõistetav ja kuivõrd ta põhjustab vaid väikese ülehindamise. Harvadel juhtudel, kui tulemuseks tagastatav tee ka pole lüheim võimalik, on see kindlasti üks lühemaist. Täiendavat lugemist teepikkuse ennustamiseks saab siit.

F leitakse G ja H liitmisega. Esimese sammu tulemus on näha järgneval joonisel. F, G ja H tulemused on kirjutatud igasse ruutu. Nagu on näidatud rohelisest parempoolsel ruudul, F on üleval, G all vasakul ja H all paremal.

Joonis 3
Joonis 3 (graphics3.jpg)

Tähtedega ruudul on G=10 ehk kaugus alguspunktist on 1 horisontaalsamm. Rohelisest alguspunktist diagonaalsuunda jäävatel ruutudel on G=14. H on arvutatud kui eeldatav kaugus punase punktini, kasutades Manhattani meetodit, liikudes ainult horisontaalselt ja vertikaalselt ning ignoreerides ruutude läbitavust. Seetõttu ei olegi rohelisest diagonaalsuunas asuva ruudu H võrdne 34-ga (mis oleks 1 diagonaalsamm + 2 horisontaalsammu punase punktini), vaid 40 (ehk punasesse punkti liikumiseks peaks kuluma 3 horisontaalsammu ja 1 vertikaalsamm). Ja F on lihtsalt G ja H summa.

Jätkamine

Järgmise sammuga me lihtsalt valime väikseima F-ga ruudu "avatud" loendist, ning:

  1. Eemaldame ta loendist "avatud" ja lisame loendisse "suletud".
  2. Kõik selle ruudu naaberruudud, mis pole loendites "avatud" ega "suletud" ning pole märgitud mitteläbitavaiks, lisada loendisse "avatud", märkides ühtlasi igaühele eelmiseks ruuduks selle ruudu, millelt siia jõuti (ja mis eelmises sammus tõsteti "suletud" loendisse).
  3. Kui mõni naaberruutudest on juba loendis "avatud", siis kontrolli, kas käesoleva ruudu kaudu sinna minnes oleks tee lühem kui see teepikkus, mis on praegu märgitud sellele ruudule (G). Teisisõnu kontrolli, kas selle naaberruudu G on suurem kui käesoleva ruudu G+sammu pikkus sellele naaberruudule- sel juhul muudame ka naaberruudu ruudu G-d, määrates selleks käesoleva ruudu G+sammu pikkus (mis meie näites saab olla 10 või 14) ja märgime muudetud ruudu eellaseks käesoleva ruudu. Samuti arvutame uuesti muudetud naaberruudu F.

Vaatame lähemalt, kuidas see toimib. Meie senivaadeldud üheksast ruudust on meil 8 "avatud" loendis ja algusruut tõstetud "suletud" loendisse. Neist väikseima F-iga on parempoolne keskmine, mille F=40. Seega valime me selle ruudu järgmiseks sammuks. See on märgistatud helesinise raamiga alljägneval illustratsioonil:

Joonis 4
Joonis 4 (graphics4.jpg)
Esiteks me tõstame selle ruudu "suletud" loendisse (joonisel on kõik helesinise raamiga ruudud vaadeldud loendis). Seejärel vaatleme naaberruute. Kõik parempoolsed kujutavad kaardil müüri ehk pole läbitavad ja seetõttu ignoreerime neid. Vasakul keskel on algusruut, mis on tõstetud "vaadeldud" loendisse, seega ignoreerime ka seda. Ülejäänud neli naabreruutu on juba "vaatlemisel" loendis, seega peame vaid üle vaatama nende teepikkused, et kas mõnda neist on käesoleva ruudu kaudu minnes lühem tee. Ülemise ruudu G=14. Käesoleva ruudu kaudu liikudes oleks see 20 (käesoleva ruudu G + sammu pikkus = 10 + 10). Seega ei leidnud lühemat teed. Kordame seda seda protsessi ka ülejäänud 3 naabri korral ja näeme, et ühelgi korral ei ole läbi käesoleva ruudu minnes lühem tee, seega ei muuda me midagi. Võime võtta järgmise väikseima F-iga ruudu avatud loendis. Nüüd on meil vaatlemisel loendis 7 ruutu, milledest kahel F=54. Võime neist võtta suvalise, kuid kiiruse huvides võib olla kasulikum valida ruut mis lisati viimati "vaatlemisel" loendisse. See põhineb eeldusel, et liikudes algusruudust lõppruudu poole on hiljem vaatlusesse lisatud ruudud suurema tõenäosusega otsitaval teel kui varemlisatud. Kuid ei pruugi olla- näiteks meie kasutatava kaardi korral pole. (Erinevused samahindeliste alade valimisel ongi põhjuseks, miks erinevad A* realisatsioonid saavad leida erinevaid teid.) Valime siis alumise ruudu nagu on näidatud joonisel:
Joonis 5
Joonis 5 (graphics5.jpg)
Seekord on 2 naabrit seinad, milliseid ignoreerime. Samuti ignoreerimine ruutu mis on otse müüri all. Miks? Sellepärast, et sellel ruudule ei saa diagonaalis liikuda ilma lõikamata kõrvalolevat "müüri". Kõigepealt tuleb liikuda alla ja siis saab liikude sellele ruudule, liikudes ümber seina. (Märkus: see reegel pole kohustuslik. See sõltub eelkõige sellest, kuidas sõlmed on paigutatud.). 2 naaberruutu pole loendisse lisatud, seega lisame nad, määrates jooksva ruudu nende eellaseks. Ülejäänud 3-st ruudust 2 on juba "suletud" loendis, seega neid ei vaatle üldse, 1 on "avatud" loendis, selle korral veendume, et sealne G on väiksem kui jooksva ruudu kaudu minnes oleks. Sellega on selle ruudu töötlemine lõppenud ja saame valida järgmise väikseima F-ga ruudu "avatud" loendist.Kordame seda protsessi kuni oleme lisanud "suletud" listi sihtmärgiks oleva ruudu:
Joonis 6
Joonis 6 (graphics6.jpg)
Pane tähele, et algusruudust kaks ruutu allpool oleva ruudu eellane on muutunud võrreldes eelmise joonisega. Enne oli ta G=28, nüüd 20. See juhtus siis kui töödeldi ruutu tema kohal (misjärel läks see ruut "suletud" loendisse). Meie näite korral ei oma see suuremat mõju, kuid mõne teistsuguse kaardi korral võib sellisest ümberarvutavusest hargneda uus tee.

Lõpetamine

Niisiis, kuidas määrata tee? Lihtne, alusta punasest lõppruudust ja liigu eelmise ruudu viiteid pidi tagasi alguspunkti. Läbitud ruudud ongi tee (vastupidises järjekorras), vt järgmist joonist. Liikudes algusruudust A sihtruutu B on lihtsalt liikumine iga ruudu (sõlme) keskpunktist järgmise ruudu (sõlme) keskpunkti kuni jõuame sihtmärgini.

Joonis 7
Joonis 7 (graphics7.jpg)

Kokkuvõte

Nüüd uuesti A* algoritm võimalikult lakooniliselt:

  1. Lisa algussõlm "avatud" loendisse.
  2. Korda järgnevaid samme:
    • Otsi väikseima F-ga sõlm "avatud" loendist. Viitame sellele kui jooksvale ruudule.
    • Tõsta see "suletud" loendisse.
    • Iga jooksva ruudu naabri kohta...
      • Kui see sõlm pole läbitav või on "suletud" loendis siis ignoreeri seda.Vastasel juhul tee alljärgnevat:
      • Kui see pole "avatud" loendis, lisa see sinna. Jooksev ruut märgi selle eellaseks. Arvuta F, G ja H.
      • Kui see on juba "avatud" loendis, siis kontrolli, kas tee jooksva ruudu kaudu oleks lühem kui praegune tee selle ruuduni. Selleks tuleb vaadata, kas G tuleks jooksva ruudu kaudu minnes väiksem kui on praegune. Kui jah, siis määrata selle sõlme eellaseks jooksev sõlm ja arvutada uuesti G ja F. Juhul, kui hoiad "avatud" listi sorteerituna F-i järgi (kiirendamaks väikseima F-iga ruudu leidmist), sorteeri uuesti.
    • Lõpeta kui sa:
      • Lisad sihtmärgi "suletud" loendisse, sel hetkel on tee leitud (vt märkust allpool), või
      • "Avatud" loend on tühi ja sihtmärki pole jõudnud. Sellele juhul teed ei eksisteeri.
  3. Salvesta tee. Tee on ruudud, mis läbitakse sihtsülmest algsõlme liikumisel viidete "eelmine ruut" kaudu liikudes.

Märkus: Lõpetades töötlemise hetkel, kui sihtmärk on lisatud "avatud" loendisse on pisut kiirem ja annab peaaegu alati sama tulemuse kui lõpetamisel "suletud" loendisse sattumisel, kuid mitte alati. Tulemus võib sõltuvalt kaardist erineda oluliselt (nt "jõe" korral, kui hakkatakse valet kallast pidi lähenema). Erinevates foorumites toimuvates arutelused A* meetodi kohta võib kohata viiteid programmikoodile mis tegelikult pole A*. A* kindlateks komponentideks on "avatud" ja "suletud" loend ning hinnete F, G ja H kasutamine. On ka palju muid teeleidmise algoritme, kuid üldiselt on A* tunnustatud parimaks. Bryan Stout on arutlenud sel teemal artiklis mis on toodud lõpus, tuues välja nii eelised kui ka puudused. Mõned alternatiivid on paremad teatud situatsioonides, kuid sel juhul peab eelnema kaardile vastav analüüs.

Lisakommentaarid

Alljärgnevalt on juttu asjaoludest, millised tuleks rakendust kirjutades läbi mõelda.

1. Liikuvad objektid (kollisioonidest hoidumine)

Juhul, kui tee leidmisega kaasneb kellegi/millegi liigutamine mööda seda teed, võib olla oluline ka arvestada teiste kaardil toimetavate üksustega. Lisatud näidiskood ignoreerib täielikult muid objekte kaardil. Sisuliselt tähendab see eeldust, et nende olemasolu korral saab teed otsiv üksus ja muud objektid üksteist läbistada / asuda samas ruudus. Sõltuvalt mängust võib see olla aktsepteeritav või mitte. Kui te tahate arvestada teisi objekte teeleidmise algoritmis ja need on liikuvad, siis soovitan arvestada ainult objektidega mis on seiskunud või teed otsiva objekti kõrval sel hetkel kui teed otsitakse (sel juhul tuleks sõlm lugeda läbimatuks kui seal paikneb teine objekt). Liikuvate ja naabruses asuvate objektide korral saate kokkupõrget ära hoida mitte töödeldes ruute mis asuvad nende (eeldataval) teel. (Lähemalt kirjeldatud osas #2.)Kui otsustate arvestade teiste objektidega mis liiguvad ega asu teed otsiva (ehk teie juhitava) objekt naabruses, siis peate välja töötama meetodi ennustamaks, kus nad võivad paikneda mingil ajahetkel. Vastasel juhul tekib tulemuseks veider sik-sakiline tee mis arvestab objektide asukohtadega kus neid tegelikult enam pole. Samuti on vajalik välja arendada kokkupõrke tuvastus, vähemalt juhul kui teiste objektide liikumine pole 100% kindel. Kui toimub kokkupõrge tuleb tee uuesti leida või liikuva objekti korral oodata, kuni ta on liikunud mujale.Need näpunäited on piisavad alusamiseks. Täiendava informatsiooni jaoks võib abi olla alljärgnevatest materjalidest:

2. Maastiku arvestamine

Käesolevas juhendis kaardil on kasutusel vaid kahte liiki maastikku: läbitav ja läbimatu. Kuid kuidas käituda siis, kui ruut on läbitav, kuid pikema aja jooksul? Sood, mäed, trpid koobastikes jne- näited maastikest, mis on läbitavad, kuid nõuavad seejuures rohkem energiat ja aega kui tasane maastik. Läbimise kulu võib ka väiksem olla- nt kui tee läheb allamäge. See probleem on kergelt lahendatav muutes hinna G arvutamise algoritmi, et ta arvestakse konkreetse sõlme maastikuga ning liidaks või korrutaks G vastava maastiku koefitsiendiga. A* algoritm ei leia tegelikult mitte niivõrd kõige lühemat, kuivõrd kõige "odavamat" teed (lihtsalt tavaliselt on lühim ka "odavaim").Sarnast lähenemist kasutab "mõju kaardistamine" (influence mapping) käigus luuakse täiendav punktisüsteem mida kasutatakse hindamisel. Oletame et meil on kaart koos hulga üksustega mis takistavad mingit teelõiku. Iga kord kui meie juhitav üksus üritab seda läbida, nabitakse ta kinni. Mõju kaardistamisel märgitakse ruudud, kus juhitavaid üksusi kinni on nabitud, täiendava koefitsiendiga. Iga kord kui programm saadab kellegi teele ja ta kinni nabitakse, tõstetakse vastavale ruudu koefitsienti ja muudetakse seekaudu kasutatavat teed.Kolmas võimalus on tõsta nende sõlmede koefitsienti mis on vaenulike üksuste läheduses. Üks A* nõrkusi on, et kui grupp üksusi püüab leida teed sihtpunkti, siis suur hulk üksusi (või suisa kõik, sõltub algpositsioonidest) valib sama tee. Lisades trahviühikuid sõlmedele teiste grupikaaslaste juba valitud sõlmedele hajutab gruppi ja vähendab kokkupõrkeohtu. Tuleb aga jälgida, et suure grupi korral ei läheks trahvikoefitsient liiga suureks (nt kõrgemaks kui nt vaenlase lisatav koefitsient). Samuti tuleks koefitsienti tõsta vaid neil sõlmedel, mis on teed otsiva üksuse lähedal, vältimaks hajutamist grupiliikmetest mis on nagunii eemal. Samuti on mõtet seda "trahvikoefitsienti" arvestade vaid läbimata tee kohta.

3. Avastamata ala

Mõnes arvutimängus võib täheldada, et arvuti juhitav vastane teab alati milline tee valida, kuigi kaart on veel uurimata. Sõltuvalt mängust võib selline teeleidmine paista ebarealistlik. Õnneks pole see kuigi keeruline probleem. Lahenduseks on "teadaolev läbitavuse" massiiv iga mängija ja arvuti kohta (ehk mitte üksikute objektide jaoks, vaid iga mängijate kõigi üksuste jaoks). Iga massiiv sisaldab informatsiooni mängija poolt avastatud pindade kohta, eeldades, et avastamata piirkond on läbitav seni, kuni pole kogetud vastupidist. Selle lähenemise korral üksused uitavad tupikutesse kuni plats on õpitud. Teised üksused enam järgmiste vigu ei korda.

4. Ühtlasemad teed

Kuigi A* tagastab lühima ehk odavaima tee, et tagasta ta ühtlaseimat teed. Vaadake teed meie näite lõpptulemusel:

Joonis 8
Joonis 8 (graphics8.jpg)
Sellel teel esimene samm on alla paremale. Kas poleks tee tee ühtlasem kui esimene samm oleks otse alla? On mitmeid teid selle probleemi menetlemiseks. Arvutades teed võite lisakoefintsiendi lisada teedele mille tulemusena tuleks suunda muuta, lisades selle nende G-skoorile. Või uurida teed peale selle leidmist, leidmaks kohti kus naabersõlme valimisel paistaks tee parem. Lähemalt saab sel teemal lugeda Toward More Realistic Pathfinding, Marco Pinter'i arikkel Gamasutra.com-is (lugemiseks vajalik registreerumine).

5. Mitte-ruudukujulised sõlmed

Eelnavalt on kasutatud lihtsat 2-mõõtmelist ruudustikku, kuid selle asemel võib kasutada ka muid kujundeid. On olemas lauamäng "Risk", mille kaart kujutab endast tavalist poliitilist maakaarti. Sel juhul saab luua tabeli riikide naabruste salvestamiseks ja G leidmiseks liikumisel ühest riigist teise. Samuti on vajalik leida algritm H leidmiseks. Kõik edasine toimuks sarnaselt eelkirjeldatule, lihtsalt naaberruutude asemel tuleks käsitleda naaberriike. Ehk maatriksi asemel kasutatakse graafi ja seetõttu on naabersõlmede arv, millised iga sõlme töödeldes vaja üle vaadata, erinev. Naabriteks (kellede hulgast lisatakse sõlmi avatud loendisse) on kõik sõlmed, kelledega on otseühendus (ehk siis naabreid võib olla suvaline hulk, mitte vaid 8 nagu ruudustiku korral).

Sarnaselt saab luua "peatuspunktide" süsteemi teadaolevate teede jaoks kaardil. Nn "peatuspunktid" on üldiselt teede ristumiskohad, hargnemised, aga ka nt ümberpõike kurvid- ehk kohad, kus saab või on ratsionaalne teha valikuid, mis suunas edasi liikuda. Nt tunneli algus- tunneli keskel suunda muuta pole mõttekas, ainult ümber pöörata, mis on selgelt ebaratsionaalne ja aja raiskamine. Mängu disainides on tavaliselt kasulik sellised punktid eelnevalt defineerida arvuti juhitava mängija jaoks. Kaks peatuspunkti loetakse naabriteks kui nende vahel saab liikuda sirgjooneliselt (ehk nende vahel pole takistusi). Eelnavalt toodud maakaardi näites tuleks salvestada informatsioon naabruse kohta, seda kasutatakse G ja H arvutamiseks (liites lõikude hindasi/pikkusi peatuspunktide ehk sõlmede vahel). Ehk luuakse graaf, kus sõlmedeks on peatuspunktid, kaarte hinnad on teada (=kaarte pikkused) ning tee leidmisel leitakse tee graafi kahest sõlme vahel, milledest esimene on üksuse lähedal ja teine eesmärgi lähedal.

Amit Patel on kirjutanud ülevaatliku artikli mõnedest alternatiividest.Üht võimalikku viisi isomeetrilise RPG kaardi kasutamisest mitte-ruudustikulisel kaardil on kirjeldatud artiklis kahekihilisest teeleidmisest.

6. Optimeerimine

Arendades oma A* programmi või kohandades mõnda teist, leiate lõpuks et teeleidmine võib kasutada palju protsessori ressurssi, sõltuvalt teed otsivate üksuste arvust ja kaardi suurusest. Mõned ideed kuidas töötlust optimeerida:

  • Vähenda kaardi suurust või üksuste arvu.
  • Teeotsimist rakenda korraga (ühel sammul) vaid väheste üksuste jaoks. Kasuta ootejärjekorda.
  • Kasuta suuremaid (seega ka vähem) sõlmi. Veel parem, kasuta kahte kaarti- suuresõlmelist pikemate distantside jaoks ja väiksesõlmelist väiksemates piirkondades või sihtmärgi lähedal tegutsedes. Lähemalt saab sellest tehnikast lugeda siit:Two-Tiered A* Pathfinding.
  • Pikemate vahemaade korral võib kasutada eelarvutatud teid ja sõltuvalt sihtmärgi kaugusest neid kasutada.
  • Leia eelnevalt kaardi piirkonnad, kuhu ei saa minna, nn "saared". Üks A* nõrkusi on, et kui sihtmärk juhtub olema kohal, kuhu ei saa liikuda, siis töödeldakse läbi kogu kaardi pindala selle tulemuse leidmiseks. Tuleks tähistada mingi samasamasuguse tunnusega sõlmed, millede vahel on liikumine võimalik ja A* otsingut täiendada seda arvestavaks.
  • Labürindi-taolises keskkonnas kaalu tupikteede märgistamist. Need võivad olla eelnevalt tähistatud kaardi looja poolt või paremal juhul olla tuvastatud kaardi eeltöötluse käigus. Kõik tupikud tuleks tähistada unikaalse numbriga, töötluse käigus tuleks ignoreerida kõiki tupikuid, välja arvatud juhul kui sihtmärk paikneb sama identifikaatoriga tupikus.

7. Avatud loendi haldamine

See on üks ajakulukamaid osi A* algoritmis. Iga kord, kui pöördute loendi poole, on vaja leida sõlm väikseima F-iga. On mitmeid teid selle tegemiseks. Võib salvestada sõlmed loendisse nendele sattumise järjekorras ja iga pöördumise ajal vaadata kõik sõlmed üle. See on lihtne, kuid väga aeglane suuremate kaartide korral. Võib ka hoida loendit F järgi järjestatuna ja valida töötlemiseks esimene sõlm loendist.Tõsised A* programmeerijad kasutavad nn "kahendkuhja" (binary heap). Seda on kasutatud ka lisatud näites. See on keskmiselt ca 2-3 korda tavalistes situatsioonides ja üle 10 korra kiirem suurte kaartide korral. Lähemalt on kahendkuhja kirjeldatud artiklis Using Binary Heaps in A* Pathfinding.Teine võimalik pudelikael on andmestruktuuride haldamine ja uuestiarvutamine teeleidmise vahepeal. Massiivide kasutamine on reeglina märksa kiirem kui dünaamiliste struktuuride. Jõudlusprobleemide korral tuleks hoiduda objekt-orienteeritud lahendustest. Üks võimalus massiivide kasutamiseks: Kahemõõtmeline massiiv Loend(x,y), mis määrab iga sõlme avatud või suletud loendis olevaks. Peale teeledimisprotsessi lõppu pole vaja aega raisata massiivi nullimiseks, vaid piisab kasutatavate väärtuste ümberdefineerimisest, näiteks suurendades avatud loendis olemise või suletud loendis olemise koodi +5 võrra. Hindade F, G ja H väärtusi pole vaja siis samuti nullida, need lihtsalt kirjutatakse töötluse käigus üle ja vanade väärtuste kasutamise välistab loendis olemise tunnuse uue väärtuse kasutamine. Ainus miinus massiivide kasutamisel on suurema hulga mälu kasutamine.

8. Dijkstra algoritm

Tee leidmise jaoks on kasutusel veel ka Dijkstra algoritm. See sarnab A*-le, kuid erinevuse seisneb heuristika puudumisest- ehk väärtust H ei leita. Seega laieneb otsimine võrdse kiirusega igasse suunda, muutes otsiala märksa suuremaks kui tee leidmiseks vaja ning seetõttu on ka reegline aeglasem A*-st. See algoritm osutub kasulikuks siis, kui me ei tea, kus sihtmärk asub. Kui eesmärgiks on mitme sihtmärgi seast lähimani jõudmine, siis osutub Dijkstra algoritm paremaks. A* korral tuleks korrata tee otsimist iga sihtmärgi jaoks ja valida tulemustest lühim, Dijkstra algoritmi kasutades saab lähimani esimese korraga.

Täiendavat kirjandust

Blitz Basicu demo on kättesaadav Blitz Basic-u veebilehelt.

Veebisaidid, kus veel mitmesuguseid asjassepuutuvaid materjale saadaval:

Content actions

Download module as:

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks