Akadályelkerülést algoritmus
Akadályelkerülést algoritmus
A következő feladat - egy kétdimenziós térképet akadály, hogy előkészítsék az utat a pont-pont B. A térkép formájában adott kétdimenziós tömb két sejttípus - Elfogadható és járhatatlan.
Tegyük fel, hogy egy területet a térképen, amelyen keresztül kell haladnia (1. ábra).
Hogy megkerülje az akadályokat használni a jól ismert kilépés a labirintusból algoritmus, azaz - az egyik kezével a falnak, és rajta közlekedő, előbb-utóbb eljön a kilépés a labirintus olyan tárgyat, amely abból indultunk ki, hogy a bejegyzést. Ha ez az érték a származási bármely falon belül a labirintus, a helyzet akkor állhat elő, ha a folyamat hurok (például, az oszlop körül).
Azonban ez a probléma meglehetősen egyszerű - a térkép egy összefüggő területen áthatolhatatlan sejtek (amely az úgynevezett „The Wall”), amely metszi az egyenes összekötő pont - az elején a pálya és a B - Az út végén. Be kell, hogy kap körül ezt az akadályt. Meg kell jegyezni, hogy a „folytonosság” lehet használni a legszigorúbb feltételek kapcsolat, mégpedig két sejt tartják szomszédos, ha van legalább egy pár a megfelelő koordináta különbözik az 1. Azaz, a két sejt az átlós kell tekinteni, mint az egyik régióban.
Kezdeni, bemutatjuk a változók száma.
· Legyen P (x_p, y_p) - így pont közvetlenül szomszédos az akadályt. Ez azt jelenti, hogy a következő pont tartoznak már az akadály (lásd. 1. ábra).
· Legyen W (x_w, y_w) - így pont fekvő pont után a P, akkor van - ez az első pont tartozó akadályt, és a pálya (lásd 1. ábra).
Meg kell eljutni a P pont-pont D. Meg kell jegyezni, hogy a P pont, ahol az elkészítésekor csak az elején, ahogy mozog akkor felé a pont D.
A feltétel az algoritmus azt mondja, hogy meg kell tartani az egyik kezével a falnak, más szóval, mindig ugyanaz (!) Side of us kell a falra. Hogyan lehet elérni ezt a diszkrét területen? Tekintsünk egy egyfajta „dipólusok” a 2. ábrán.
Mint korábban, a P betű, majd az út által jelzett sejtek, és a W betű - fali sejtekben. Ezen túlmenően, a szám „1” jelölt sejtek, állva a jogot a sejtfalak, és a „2” szám - sejtek, állva a jogot a küvettában a fényút. Hogyan beszélhetünk irányait ebben az esetben? Az irány által adott két pontot, amely lehet tekinteni, mint a koordinátákat a vektor - az elején a vektor a P pont, a végén - a ponton W.
Így annak érdekében, hogy képes legyen mozognak a falak, hogy képes legyen egyedileg meghatározni a koordinátáit pontok „1” és „2”. Ez azt jelenti, sőt, van dolgunk akadályok körül a bal kezét.
A képletek a koordinátákat a megfelelő pontokat az alábbiakban mutatjuk be.
x1 = x_w - (y_w - y_p); x2 = x_p - (y_w - y_p);
y1 = y_w - (x_p - x_w); y2 = y_p - (x_p - x_w);
Ha például helyettesíteni a képlet értéke, lehetőség van arra, hogy megbizonyosodjon arról, hogy a korrekt koordinátáit minden alkalomra.
Azonban felmerül a kérdés - hogyan kell feldolgozni a sejteket, álló átlósan? Két lehetséges esetben - ha állva átlósan sejteket kapott metszéspontja a sor egy akadály útját (mint az 1. ábrán), és ha azokat találkozott végrehajtása során az algoritmus, például, amikor áthaladó sarokpontjait. Az első esetben, minden egyszerű - meg kell választani a P pont és W, hogy ők 4 csatlakoztatott szomszédok, azaz nem állnánk az átlós. A második eset elmagyarázza az algoritmus működésének teljes elmozdulási mechanizmus.
Keresünk módját körüli aktuális pont (hol vagyunk, sőt), a sejtfal, ami „megragad” kéz további mozgását, vagyis, ha a „2” pont járhatatlan, akkor a W = „2” kimenet. Ha a „2” járható a .proveryaem pont „1”, és ha ez megfelelő, akkor P = «1» kimenet. Ha "1" járhatatlan, akkor W = «1», P = «2», hozam.
Hogyan állapítható meg, a végén az algoritmus? Minden attól függ, a konkrét megvalósítására. Akkor valahogy jelölje meg a kártya ketrecben töltenek ott egy vonal útját és fennakadt azok feltérképezése közben, hagyja abba a munkát. Fontos annak biztosítása, hogy tényleg a D pontban, és nem kakya más között helyezkedik el, az A és P. Ez megtehető számozás összes fordulópont, és dobja ki azokat, amelyek kisebb szám, mint ahány a kiindulási pont P.
12/6/00
Andrei Frolov.
Ui Az algoritmust kapunk munka eredményeként a projekt StarCrusade.
P.P.S. A forráskód a játék, ami azt mutatja, az algoritmus
és egy leírást az algoritmus a doc - findpath.zip.