Forum

Algorytm tworzenia tras

[+] Twoje konto

Subskrybuj kanał najnowszych wypowiedzi w tym temacie

RozwiązaneWątek zamknięty Forum > Porady > Programowanie > Algorytm tworzenia tras

Rozwiązany: Pomysł na szybkie tworzenie trasy z punktu A do B omijającego przeszkody
Idź do strony:1
Ocena: (Ocen: 0)
Wypowiedzi 1 - 12 z 12
AvatarAdministrator Dżyszla Mężczyzna Kopiuj nick (83.2.108.*) |  
Wypowiedź dodana: 19 marca 2008, 16:24:05
« Opcje

Miałby ktoś pomysł, albo potrafił wskazać na jakieś ciekawe informacje dotyczące takiego zagadnienia:

Załóżmy, że mamy mapę:

Kod:

┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼
│ │ │ │ │ X │ │ │ │ │ │ │ │ │ │ │ │
┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼
│ │ │ │ │ │ X │ │ │ X │ │ │ │ │ │ │ │
┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼
│ │ │ A │ │ X │ │ │ │ X │ │ │ │ │ │ │ │
┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼
│ │ │ │ │ │ │ X │ │ X │ │ X │ │ X │ │ │ │
┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼
│ │ X │ │ X │ │ X │ │ │ X │ │ │ X │ │ │ │ │
┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼
│ │ │ X │ X │ X │ X │ │ X │ │ X │ │ B │ │ │ │ │
┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼

Zadanie polega teraz na wyznaczeniu trasy z punktu A do B tak, aby nie wejść w sektory X. Poruszać się można oczywiście wyłącznie w kierunkach N, S, W i E o jedno pole.

I nie bardzo potrafię sobie poradzić inaczej z tym problemem, niż rekurencyjnie, ale to zdecydowanie zbyt czasochłonny sposób.


mgr inż. Dżyszla

Nie odpisuję na problemy zgłaszane na e-mail lub PW!

Także dzięki firmie Netlook.pl możesz za darmo korzystać z tej strony!

 Gość REKLAMA Kopiuj nick (*->*)
Wypowiedź dodana: 19 marca 2008, 16:24:06

AvatarZarejestrowany, zwieszony Zonewelld Mężczyzna Kopiuj nick (89.174.125.*) |  
Wypowiedź dodana: 19 marca 2008, 17:09:07
Za tą wypowiedź przyznano użytkownikowi punkt pożyteczności
« Opcje

Jeśli chodzi o trasę to coś mi świta z Dijkstrą czy jkaoś tak on miał, albo sieci neuronowe, le nie wiem czy do Twojego przypadku to się nadaje, bo nie miałem z tym za dużo do czynienia


C2D 2.2GHz| FOXCONN P35A | 4x 1024MB Patriot 1066MHz | PALIT GeForce 8600GT | Amacrox Warrior 400W | Samsung SM940nw
___
There are only 10 types of people on the world: these who unterstand binary and these who don't...

 Zarejestrowany Soul Mężczyzna Kopiuj nick (83.6.34.*) |  
Wypowiedź dodana: 19 marca 2008, 18:35:22 | Wypowiedź edytowana Ostatnio edytowana: 19 marca 2008, 18:35:46 po raz 1-wszy przez: Soul
« Opcje

Tak jak w grze w kulki? to można inaczej niz rekurencyjnie? :-) Algorytm Dijkstry wyszukuje chyba tylko najkrotszą drogę, a nie najmniej kosztowną.

Ale ja nie mialem z tym wiele do czynienia ;-)


Duszołap

 Zarejestrowany, zwieszony Stasiek-j Mężczyzna Kopiuj nick (0.0.0.*) |  
Wypowiedź dodana: 19 marca 2008, 20:17:54 | Wypowiedź edytowana Ostatnio edytowana: 19 marca 2008, 20:42:33 po raz 1-wszy przez: Stasiek-j
Za tą wypowiedź przyznano użytkownikowi punkt pożyteczności
« Opcje

Soul, a w grafie z wagami na krawędziach to czym niby się różni najkrótsza od najmniej kosztownej? :-|

Myślę, że Dijkstra by tu się nadał całkiem dobrze. Zwłaszcza, że ten graf byłby raczej rzadki, więc złożoność byłaby rzędu O(|E|log|V|) gdzie oczywiście E-zbiór krawędzi, a V- zbiór wierzchołków.

(BTW: w RPGach jakoś sobie z tym problemem radzą ;-) )

*** Dodano o 20:36:37: *** (Autoscalanie)

Poszukałem trochę w necie i wniski są takie:
1. Dosyć łatwo, średnio wydajnie (ale chyba wystarczająco): zastosować algorytm Dijkstry.
2. Dosyć trudno, ale najwydajniej byłoby zastosować algorytm a*
( http://www.policyalmanac.org/games/aStarTutorial.htm ), z tym, że to jest bardzo mocne narzędzie i nie wiadomo, czy warto się w to bawić dla tak prostego przypadku.
3. Niektórzy wspominają też o jakichś naiwnych prostych do napisania sposobach, które dla przypadku takiego "labiryntu" miałyby działać wystarczająco dobrze, ale szczerze w to wątpię. Zobacz: http://forum.java.sun.com/thread.jspa?threadID=466782&messageID=2148809

*** Dodano o 20:42:33: *** (Autoscalanie)

Przytoczę krótki cytat, który ładnie podsumowuje różnice między A* a Dijkstrą i pomoże Ci się zdecydować. Zdaje się to potwierdzać przypuszczenie, że dla Twojego przypadku najstosowniejszy będzie Dijkstra.

8. Dijkstra's Algorithm: While A* is generally considered to be the best pathfinding algorithm (see rant above), there is at least one other algorithm that has its uses - Dijkstra's algorithm. Dijkstra's is essentially the same as A*, except there is no heuristic (H is always 0). Because it has no heuristic, it searches by expanding out equally in every direction. As you might imagine, because of this Dijkstra's usually ends up exploring a much larger area before the target is found. This generally makes it slower than A*.


Stasiek

AvatarAdministrator Dżyszla Mężczyzna Kopiuj nick (83.2.108.*) |  
Wypowiedź dodana: 19 marca 2008, 21:30:12
« Opcje

Tak jak w grze w kulki? to można inaczej niz rekurencyjnie? :-) Algorytm Dijkstry wyszukuje chyba tylko najkrotszą drogę, a nie najmniej kosztowną.

Ale ja nie mialem z tym wiele do czynienia ;-)

Tak, dokładnie jak w kukach :-)

Dzięki wszystkim za pomoc... Być może jak znajdę czas, to go zastosuję - chwilowo jest mocno uproszczona wersja trasowania bez wykrywania kolizji...


mgr inż. Dżyszla

Nie odpisuję na problemy zgłaszane na e-mail lub PW!

Także dzięki firmie Netlook.pl możesz za darmo korzystać z tej strony!

 Zarejestrowany Soul Mężczyzna Kopiuj nick (83.6.13.*) |  
Wypowiedź dodana: 19 marca 2008, 22:42:25 | Wypowiedź edytowana Ostatnio edytowana: 19 marca 2008, 22:45:52 po raz 1-wszy przez: Soul
« Opcje

Soul, a w grafie z wagami na krawędziach to czym niby się różni najkrótsza od najmniej kosztownej? :-|

No tak, chodziło mi o najmniej kosztowny proces wyszukiwania drogi :-) O ile rozumiem, to algorytm Dijkstry wyszukuje wszystkie drogi i wybiera najkrótszą. A u Dżyszli wystarczy pierwsza, jaką znajdzie. Czyli średnio może działać nawet 2x szybciej (chyba).


Duszołap

AvatarAdministrator Dżyszla Mężczyzna Kopiuj nick (83.2.108.*) |  
Wypowiedź dodana: 20 marca 2008, 00:32:12
« Opcje

Przyznaję, że wciąż nie potrafię go rozgryźć mimo tylu rysunków :-/ Chwilowo mam bardzo oryginalną wersję swojego własnego algorytmu błądzenia, który czasami daje piękne kokardki i pętelki :-D Pewnym problemem w tym wszystkim jest fakt, że mam... nieskończoną liczbę wierzchołków... No i nawet kody gdzieś dorwałem gry kulki, ale... Dalej nie jarzę :-( Poza tym to musi być naprawdę szybkie, bo musi być wykonywane nawet po kilkadziesiąt razy w ciągu sekundy.


mgr inż. Dżyszla

Nie odpisuję na problemy zgłaszane na e-mail lub PW!

Także dzięki firmie Netlook.pl możesz za darmo korzystać z tej strony!

 Zarejestrowany, zwieszony Stasiek-j Mężczyzna Kopiuj nick (0.0.0.*) |  
Wypowiedź dodana: 20 marca 2008, 01:09:26
« Opcje

A do czego chcesz to zastosować?

No i ten problem raczej taki prosty dla kompa nie jest i trochę czasu mu zajmie. Może warto zwrócić uwagę na to, żeby zmniejszyć konieczność częstego wywoływania, oprócz optymalizować samo wyszukiwanie?

Jak to masz nieskończoną liczbę wierzchołków? chodzi, że "tablica ma wymiary nie N x M tylko alef0 x alef0 ? Bo to by nam dodatkowo komplikowało sprawę :-( chyba, że byś mógł rozważać wycinki, ale wtedy możesz zgubić jakieś drogi, wśród których mogła być ta najkrótsza)

BTW: Patrzyłeś na tego linka o algorytmie A*? Wygląda na naprawdę dobry, tylko musisz pomyśleć nad dobrą funkcją heurystyczną.


Stasiek

AvatarAdministrator Dżyszla Mężczyzna Kopiuj nick (83.2.108.*) |  
Wypowiedź dodana: 20 marca 2008, 10:53:16
« Opcje

Do trasowania połączeń pomiędzy elementami tak, aby nie przecinały istniejących elementów.

Zdecydowałem, że zastosuję jednak metodę A* - spodobała mi się :-) No myślałem o rozważaniu wycinków, ale pytanie - jak duże otoczenie dobrać pomiędzy punktem startowym a końcowym.

Heurystyka w A* będzie prosta, bo poruszanie się jest możliwe wyłacznie po kątach prostych. Poza tym nic się nie stanie, jeśli by nie była najkrótszą trasą.


mgr inż. Dżyszla

Nie odpisuję na problemy zgłaszane na e-mail lub PW!

Także dzięki firmie Netlook.pl możesz za darmo korzystać z tej strony!

AvatarAdministrator Dżyszla Mężczyzna Kopiuj nick (83.2.108.*) |  
Wypowiedź dodana: 20 marca 2008, 23:35:53 | Wypowiedź edytowana Ostatnio edytowana: 20 marca 2008, 23:36:32 po raz 1-wszy przez: Dżyszla
« Opcje

Udało mi się z powodzeniem zaimplementować Algorytm A* i działa mądrzej niż sądziłem :-) To jest genialne wręcz!

Tylko jeden problem mnie jeszcze nurtuje - dostania się do niedostępnego obszaru (czy też wydostania z zamkniętego) - nie bardzo mam pomysł, jak wykrywać takie sytuacje... Może ktoś ma pomysł?

A korzystałem z tego - genialny opis :-)

Że też mnie na studiach nie uczyli takich algorytmów właśnie :-|


mgr inż. Dżyszla

Nie odpisuję na problemy zgłaszane na e-mail lub PW!

Także dzięki firmie Netlook.pl możesz za darmo korzystać z tej strony!

 Zarejestrowany, zwieszony Stasiek-j Mężczyzna Kopiuj nick (83.26.74.*) |  
Wypowiedź dodana: 21 marca 2008, 01:35:25
« Opcje

Super :-)
A ten link co podałeś to kopia Google tego, który podałem wcześniej w TEJ wypowiedzi.

A co do tych obszarów, to mógłbyś analizować graf pod względem spójności (zakładając, że pola z X nie łączą się z żadnym polem, a każde inne pole łączy się ze czterema wokół (lub mniej, jeśli to X-y)
Algorytm sprawdzania spójności działa w czasie liniowym, więc ze złożonością nie ma problemu.
Przydatny link: http://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/Przeszukiwanie_graf%C3%B3w


Stasiek

AvatarAdministrator Dżyszla Mężczyzna Kopiuj nick (83.2.108.*) |  
Wypowiedź dodana: 21 marca 2008, 10:13:01
« Opcje

Stasiek - ja wiem, ale dałem po PL, bo nie działało bezpośrednio.

Co do wyjścia z zamkniętego nie ma problemu - po prostu kończą się elementy na OL. Ale wejście w zamknięty już jest, bo plansza jest nieskończona...

Myślałem nad zlimitowanie wartości F, ale tym samym ograniczę długości ścieżek :-/


mgr inż. Dżyszla

Nie odpisuję na problemy zgłaszane na e-mail lub PW!

Także dzięki firmie Netlook.pl możesz za darmo korzystać z tej strony!

 
Idź do strony:1

[+] Pokaż/odśwież listę czytających i monitorujących ten wątek

Podobne tematy:
Tytuł wątkuDziałWypowiedziWyświetleńOcenaOstatnia wypowiedź
Wątek zamkniętyalgorytm - działania na liczbach wielobajtowych
Mnożennie i dzielenie dużych liczb w asemblerze
Porady / Programowanie21 398 22.04.2006 07:33:23
Wątek[MySQL] Pomysł na szybsze znajdowanie różnicy
Wyświetlanie danych będących w jednej tabeli, a nie będących w drugiej
Porady / Internet2169 18.01.2014 11:29:41
WątekProblem z trzymaniem baterii telefonu
Szybkie rozładowywanie się baterii telefonu komórkowego
Pogaduchy19306 11.09.2009 17:30:18
WątekPomysł na zamianę rekurencji na iterację lub ochrona przed przepełnieniem stosu
Problem z rekurencją i przepełnieniem stosu
Porady / Programowanie1312 16.04.2008 21:01:46
Wątek zamkniętyPorada żywcem skopiowana do swojej strony internetowej
Skopiowana porada dotycząca menu w systemie DOS stała się częścią strony, która dokumentowała pracę dyplomową dotyczącą tworzenia stron internetowych.
Plagiaty6553 21.07.2010 18:12:24

Wątek zamknięty - nie można już do niego dodawać nowych wypowiedzi

Subskrybuj kanał najnowszych wypowiedzi w tym temacie


Chcesz mieć też takie forum na swojej stronie? Napisz!

Strona istnieje od 25.01.2001
Ta strona używa plików Cookie
 
archive To tylko kopia strony wykonana przez robota internetowego! Aby wyświetlić aktualną zawartość przejdź do strony.
Ładowanie...

Optymalizowane dla przeglądarki Firefox
© Copyright 2001-2017 Dawid Najgiebauer. Wszelkie prawa zastrzeżone.
Ostatnia aktualizacja podstrony: 22.09.2014 12:12
Wszystkie czasy dla strefy czasowej: Europe/Warsaw