Labirynt i przeskakiwanie ścian

[joda17]

Witam, potrzebuję algorytm, który bardzo przypomina te z micromouse. A konkretnie na pustej planszy są rozstawione przeszkody, które mogę przeskoczyć, ale maksymalnie jedną (), algorytm ma znaleźć drogę, która wymaga jak najmniejszej ilości przeskoków, aby przemieścić się z punktu a do punktu b. p.s. całą planszę znam. Ma ktoś pomysł jak to rozwiązać, z góry mówię że metoda sprawdzenia wszystkich możliwości jest zbyt wolna. Od razu bardzo dziękuje za pomoc (;

[Braders94]

A to ma być robot czy program na komputer?

Pisze z telefonu.

[joda17]

Algorytm będzie uruchamiany na komputerze, który po wykonaniu algorytmu będzie sterował zdalne robotem.

[BlackJack]

Nie wiem czy przypadkiem, w książce, "Algorytmy i struktury danych", nie był poruszony temat labiryntu, i algorytmów wychodzenia z niego. Aczkolwiek twój przypadek jest specyficzny bo możesz przeszkodę przeskoczyć.

choć w sumie to prosty problem jak sietak zastanowić ?

Najkrótszą droga z punktu A do B to linia prosta. Wyznacz wszystkie kwadraty na planszy, które sa na tej linii. Potem tylko sprawdzasz czy po drodze jest przeszkoda, jeżeli da sie ją przeskoczyć po tej prostej, idziesz dalej, jeżeli nie, zatrzymujesz się, i szukasz drogi obejścia, np, w polu 5x5 wokół siebie. skaczesz na te pole, i to jest nowy punkt A', z którego musisz wyznaczyć prosta do punktu B i isc dalej.

Reasumując, cały algorytm to, algorytm rysowania linii prostej, z punktu A do B, z uwzględnieniem przeszkód po dordze.

Poszukaj sobie algorytmu na rysowani lini, ale zoptymalizowane, pod katem obliczeń stałoprzecinkowych. Taki jest najszybszy.

[joda17]

Twój pomysł zakłada najkrótszą drogę, podczas gdy ja potrzebuję na najmniejszą ilość przeskoków, ale dzięki za staranie.

[BlackJack]

Ale to jedno z drugim, nie koniecznie się wyklucza. Im krótsza droga, tym mniej kwadratów, pul do pokonania, a tym samym, mniejsze ryzyko przeszkód na niej. Musiałbyś zrobić sobie najpierw symulację takiej metody.

Druga metoda to logika odwrócona, szukać w swoim pobliżu przeszkód których nie da się przeskoczyć, i traktować jako punkty pośrednie w drodze do celu.

Obszar skanowania w kroku nie musi być duży, wystarczy 5x5 pul, przy skoku o 1 pole.

[Marooned]

Spróbuj A*, gdzie przeskok będzie miał (znacznie) wyższą wagę. Dzięki temu algorytm będzie omijał przeskoki, gdyż będzie poszukiwał ścieżki z najmniejszą wagą.

[marek1707]

A co rozumiesz przez pojęcie "metoda sprawdzenia wszystkich możliwości"?

Jeżeli masz już zaimplementowany jakiś myszowaty algorytm znajdowania najkrótszej drogi w statycznym labiryncie (rozlewanie wody, A* czy może jeszcze coś innego) to teraz uzupełnij go o usuwanie pojedyńczej ściany i sprawdzanie, czy znaleziona droga jest krótsza/lepsza od dotychczasowej najlepszej. Przy założeniu, że na całą drogę możesz przeskoczyć/usunąć tylko jedną ścianę, będzie to kosztowało tyle wywołań algorytmu poszukiwania drogi ile masz ścianek. Metoda jest prosta, do zrobienia w godzinę, ale wszystko zależy od wielkości labiryntu i liczby ścianek. Jeżeli jest to problem teoretyczny i labirynt może być ogromny (np. 1000x1000) to takie "siłowe" poszukiwanie rozwiązania może być zbyt kosztowne. W przypadku labiryntów spotykanych w "życiu rzeczywistym", może się sprawdzić nawet na małym kontrolerze a prostota jest tutaj wielką zaletą. Nie pożera też pamięci - i tak musisz mieć cały labirynt a tu dodatkowo trzeba tylko trzymać dotychczasową najlepszą drogę (np. jej długość i usuniętą przy tym ścianę).

Dalej można to rozbudować o bardziej przemyślane usuwanie ścianek. Być może są obszary w których usunięcie jednej ściany nic nie da, a są też takie, w których otwiera to nową, fajną drogę na skróty. Funkcja oceniająca "wartość" usuwanej ściany mogłaby na szybko szacować zysk i po spełnieniu jakiegoś warunku pozwalać zapuszczać cały algorytm poszukiwania drogi lub pomijać tę scianę jako "nie wartą" pełnej analizy i przechodzić do następnej.

[Braders94]

Jeśli liczy się czas obliczeń to najlepiej będzie wyznaczyć drogę najbliżej punktu docelowego i dalej szukać ścianki skierowanej w stronę punktu docelowego i obliczać dalej z punktu za tą ścianką.

Ale to nie jest najlepsze rozwiązanie.

Jeśli obliczenia nie grają roli to, najpierw zbadać czy niema drogi bez przeskakiwania jeśli jest to jesteśmy w domu jeśli nie to sprawdzamy przeskakując każdą ściankę po kolei.

Np. przeskakujemy pierwszą ściankę i badamy czy jest droga do celu jeśli nie to się cofamy do poprzedniej pozycji i badamy inną ściankę i tak w kółko.

[BlackJack]

Nie wiem czy to istotne, ale dużo zależy też od tego jak zapiszemy sobie samą mapę ? Czy jest to porostu 1-bitowa tablica dwuwymiarowa X,Y, czy tablica 1 bajtowa (char) ?

Jeżeli jest to drugi przypadek elementy tablicy mogą już same w sobie zawierać informacje o polu, oraz jego otoczeniu, czyli zawierać wskazówki co jest krok dalej w lewo, prawo górę, dół, czy po skosach.

Tak naprawdę algorytm będzie zależał od przyjętych założeń, wstępnych i rozwiązań.