Algoritm pentru evitarea obstacolelor

Algoritm pentru evitarea obstacolelor

Există următoarea sarcină - pe o hartă bidimensională cu obstacole pentru a deschide calea de la punctul A la punctul B. Harta este dată ca o matrice bidimensională cu două tipuri de celule - pasibile și impracticabile.







Să avem o secțiune a hărții prin care trebuie să trecem (figura 1).

Pentru a ocoli obstacolele utilizați bine-cunoscut de ieșire a algoritmului labirint, și anume - o mână pe perete și se deplasează de-a lungul ei, mai devreme sau mai târziu vom ajunge la ieșirea din labirint de orice subiect pe care am pornit de la intrarea sa. Dacă pentru început este luat orice perete din interiorul labirintului, atunci situația este posibilă atunci când procesul devine obsedat (de exemplu, în jurul coloanei).

Cu toate acestea, această problemă este destul de simplu - pe hartă este o zonă continuă de celule impenetrabile (care se va numi „The Wall“), care se intersectează cu linia dreaptă care unește punctul A - începutul căii și B - capăt de drum. Este necesar să ocolim acest obstacol. Trebuie remarcat faptul că, întrucât „continuitatea“ poate fi folosit condițiile cele mai riguroase de conectivitate, și anume două celule sunt considerate adiacente, dacă cel puțin o pereche corespunzătoare de coordonate diferă de 1. Aceasta este, cele două celule de pe diagonala vor fi considerate ca o singură regiune.

În primul rând, introducem câteva variabile.
· Fie P (x_p, y_p) punctul punctului imediat adiacent obstacolului. Asta este, următorul punct după ce va aparține deja obstacolului (vezi figura 1).
· Fie W (x_w, y_w) un punct al traseului imediat după punctul P, adică acesta este primul punct care aparține obstacolului și liniei traseului (vezi figura 1).

Este necesar să ajungem de la punctul P la punctul D. Trebuie remarcat faptul că punctul P este localizat unde este tras doar la începutul căii, pe măsură ce se mișcă, se va deplasa spre punctul D.

În condiția algoritmului, se spune că trebuie să ținem o mână pe perete, cu alte cuvinte, întotdeauna cu aceeași latură (!) Ar trebui să avem un perete. Cum să realizăm acest lucru într-un domeniu discret? Luați în considerare astfel de "dipoli" în figura 2.







Ca și înainte, literele P denotă celulele căii, iar litera W denotă celulele peretelui. În plus, numărul "1" denotă celulele situate în partea dreaptă a peretelui celular și numărul "2" - celulele situate în dreapta căii celulare. Cum putem vorbi despre direcții în acest caz? Direcția este dată de două puncte, care pot fi considerate ca fiind coordonatele vectorului - originea vectorului la punctul P, sfârșitul punctului W.

Deci, pentru a vă putea deplasa de-a lungul peretelui, trebuie să puteți stabili în mod unic coordonatele punctelor "1" și "2". De fapt, avem de-a face cu ocolirea obstacolului cu ajutorul mâinii stângi.

Formulele pentru coordonatele punctelor corespunzătoare sunt date mai jos.
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);

Dacă înlocuiți valori pentru aceste formule, puteți observa că acestea oferă coordonatele corecte pentru toate cazurile.

Cu toate acestea, se pune întrebarea - cum se manipulează celulele poziționate în diagonală? Două cazuri sunt posibile aici - atunci când se obțin celule în diagonală atunci când se traversează o linie de drum cu un obstacol (ca în figura 1) și când acestea apar în timpul executării algoritmului, de exemplu prin traversarea punctelor de colț. În primul caz, totul este simplu - trebuie să alegeți punctele P și W astfel încât acestea să fie 4 vecini conectați, adică să nu stea în diagonală. Cel de-al doilea caz este explicat prin algoritmul de funcționare al întregului mecanism de deplasare.

Suntem în căutarea de modalități în jurul punctului curent (unde suntem, de fapt), peretele celular, care ar „apuca“ de mână pentru mișcarea în continuare, adică, în cazul în care „2“ punctul de netrecut, atunci W = „2“ de ieșire. Dacă "2" este acceptabilă, atunci verificați punctul "1", dacă este acceptabil, atunci P = "1", ieșiți. Dacă "1" este impracticabil, atunci W = "1", P = "2", ieșire.

Cum puteți determina sfârșitul algoritmului? Totul depinde de implementarea concretă. Puteți să marcați cumva celulele hărții, traversând calea de-a lungul lor și, după ce vă împiedicați să treceți prin astfel de bypass-uri, nu mai lucrați. Este important să ne asigurăm că acesta este într-adevăr un punct D și nu un altul situat între A și P. Acest lucru se poate face numerotând toate punctele de parcurs și aruncându-le pe cele ale căror număr este mai mic decât numărul punctului de pornire P.

12/6/00
Andrei Frolov.

P.S. Algoritmul a fost obținut ca rezultat al lucrărilor asupra proiectului StarCrusade.
P.P.S. Sursa din joc, care demonstrează munca algoritmului
și descrierea acestui algoritm în formatul doc - findpath.zip.







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: