Metody globalne-opracowanie

Metody globalne to:
Propagacja fali
Diagramów Woronoia
Grafu widoczności
Metody biologiczne
Metoda propagacji fali- działadnie tej metody na podzieleniu przestrzeni 2D na komórki elementarne, zazwyczaj jest to jednorodna siatka. W danym obszarze przestrzeni konfiguracyjnej Pierwsza faza generuje falę rozchodzącą się w przestrzeni konfiguracyjnej a jej algorytm wygląda następująco Krok 1 zadanej komórce początkowej nadać wagę 0 i ustalić wartość poszukiwanej wagi i=0 Krok 2 przeglądając jednokrotnie wszystkie komórki przestrzeni konfiguracyjnej wykryć te o wadze równej i Krok 3 jeśli nie znaleziono komórek o takiej wadze wykonuje się kolejny krok Krok 4 każdemu z sąsiadów znalezionej komórki którego waga nie została uprzednio zdeterminowana przez nadanie statusu zajętej lub przypisanie wagi nieujemnej, nadaje się wagę i + 1 Krok 5 gdy przeglądnięto wszystkie komórki o wadze i o 1, kontynuować od kroku 2 ... zobacz całą notatkę