Autor Wątek: Anatomia algorytmu szukania najkrótszej ściezki  (Przeczytany 3197 razy)

Offline shady

  • Użytkownik
    • Forum dla twórców gier przeglądarkowych

# Sierpień 11, 2013, 01:37:13
Hej, jestem bardzo młodym twórcą, skupiającym się w dużej mierze na web devie. Dotychczasowe aplikację pisałem przy użyciu PHP i paru języków frontendowych, gdyż tworzenie gier przeglądarkowych to rzecz, która mnie najbardziej kręci i rajcuję. Chciałbym zabrać się za projekt mapy 2D, w którym do wyliczeń użyłbym samego PHP, a animację zrobił w JavaScript i jego frameworkach. Na swoim koncie mam już kilka udanych silników opierających się na chodzeniu o 1 kratkę w wybranym kierunku (strzałkami). Przy grach MMO, ten pomysł jest jednak mało przekonujący, głównie z racji dużej ilości zapytań do bazy danych przez konieczność wykonywania każdego kroku. Doszedłem do wniosku, że dużo lepiej jest skorzystać z metody klikania w dany obszar, gdyż pozwoli to znacznie uregulować ilość zapytań. Załóżmy, że moja mapa składa się z kwadratowych elementów, a w jej wnętrzu występują znaczne kolizję, utrudniające przechodzenie między polami. Dodatkowo, skrypt ma z założenia nie obsługiwać chodzenia na ukos.


Z punktu A chciałbym się dostać do punktu B, omijając przy tym napotkane kolizję (tak, to te bordowe plamy). Jak widać, wartość krawędzi nie ma tutaj znaczenia, każde pole ma taki sam rozmiar, dlatego też algorytm odnajdywania takiej ścieżki nie powinien być mega skomplikowany, a jedynie uwzględniać główne rzeczy. Myślałem nad wprowadzeniem takich cudów jak Dijkstra, czy algo Bellmana Forda, jednakże trudno mi jest w wieku 17 lat napisać ich własne implementację do interpretowanego PHP. Czytałem kilka artykułów na temat budowy i funkcjonowania A* lub Dijkstry, a także wielu innych algorytmów, lecz z moją grafową wiedzą nie wiele rozumiem. Oczywiście, w sieci idzie znaleźć kilka przykładów z zagranicznych stron, gdzie przedstawiono implementację B. Forda i innych, ale ja bym chciał stworzyć coś zupełnie swojego. Chciałbym, abyście pomogli mi wybrać któryś z algorytmów, uwzględniając schemat mojej mapy oraz możliwości języka PHP. Czego bym jeszcze chciał? Ładnie opisanego pseudokodu, za co bym był naprawdę wdzięczny.. Nic do mnie tak nie przemawia, jak dobrze opisany pseudokod :P
« Ostatnia zmiana: Sierpień 11, 2013, 01:51:18 wysłana przez shady »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline koirat

  • Użytkownik

# Sierpień 11, 2013, 02:00:19
Obawiam się że nie dostaniesz tu innej odpowiedzi niż A*, jak nie potrafisz zrobić (choć polecam, to jest dość prosty algorytm) to ściągnij sobie gotowe rozwiązanie. Nie wierzę że nie ma takowego pod PHP.

Offline shady

  • Użytkownik
    • Forum dla twórców gier przeglądarkowych

# Sierpień 11, 2013, 02:04:50
Mam wrażenie, że nie przeczytałeś mojego postu. Nie chcę A*, nie potrzeba mi wszystkich funkcjonalności tego algorytmu, poza tym nie dla każdego jest coś łatwe, jak się nie ma pojęcia o matmie złożonej. Taki subiektywizm.. Tak, nie ma dobrej implementacji algorytmu A* do PHP, gdyż nie da się go tam całkowicie przedstawić ;) Chodzi mi o ładne opisanie procesu/schematu działania jakiegoś pasującego pod moje potrzeby algorytmu.
« Ostatnia zmiana: Sierpień 11, 2013, 02:10:48 wysłana przez shady »

Offline Xender

  • Użytkownik

# Sierpień 11, 2013, 02:30:19
Tak, nie ma dobrej implementacji algorytmu A* do PHP, gdyż nie da się go tam całkowicie przedstawić ;)
Pojęcie na dziś: Turing-complete. To taka skrajność, żeby udowodnić, że A* można zaimplementować nawet w Brainfucku. Ale PHP ma do tego środki wyrazu* porównywalne z innymi językami wysokiego poziomu, tj. nie jest specjalnie kulawy (no, może poza designem), więc da się również zrobić to efektywnie.

*(nie musisz "emulować" mnożenia iterowanym dodawaniem itp.)

I nie wykręcaj mi się tu wiekiem. Jako metryka jest po prostu bezużyteczny - zawsze znajdzie się w danym wieku, ktoś kto będzie ogarniał lepiej i nie jest to ani usprawiedliwienie, ani powód do popadania w kompleksy.

Do rzeczy: innego algorytmu raczej nie znajdziesz. Masz i czytaj: https://en.wikipedia.org/wiki/A*
Jak nie rozumiesz notacji matematycznej, to na nią nie patrz - zostaw ją dla matematyków, obok jest pseudokod i animowane ilustracje działania. Jak struktur danych, czy czegoś innego związanego z implementacją, to pisz tutaj.

//EDIT - Poprawiony link. Oj wkleiłem na żywca i przeoczyłem, że sparsowało bez '*' :P
« Ostatnia zmiana: Sierpień 11, 2013, 04:41:22 wysłana przez Xender »

Offline koirat

  • Użytkownik

# Sierpień 11, 2013, 04:02:53
Popraw linka, bo przez chwilkę myślałem że sobie jaja robisz :)

Offline shady

  • Użytkownik
    • Forum dla twórców gier przeglądarkowych

# Sierpień 11, 2013, 04:27:06
przeczytałem całą angielską wikipedie na temat litery 'A' i dalej nic nie wiem o algo najkrótszej ścieżki.




hehehe, oczywiście żart..

Offline Adam27

  • Użytkownik

# Sierpień 11, 2013, 11:36:46
A ja polecam inny algorytm, który sprawdzi się znakomicie do wyszukiwania ścieżki w dwuwymiarowej tablicy.

http://www.unit1.pl/349,txt

Offline shady

  • Użytkownik
    • Forum dla twórców gier przeglądarkowych

# Sierpień 11, 2013, 19:08:42
Adam27, dziękuje bardzo za tę odpowiedź! Strzał w 10, ktoś pomyślał o innych i nie zarzucił linka do manuala/wikipedii..

Offline Xion

  • Redaktor
    • xion.log

  • +5
# Sierpień 11, 2013, 19:32:47
@Adam27: To zwykły algorytm Dijkstry, który jest szczególnym przypadkiem A* :)

@OP: Nie pomyślał "o innych", tylko musiał specjalnie pomyśleć o tobie. "Inni" jakoś korzystają z manuali i Wikipedii bez problemów. Postaraj się, żebyś i ty też to potrafił, bo na dłuższą metę daleko tak nie zajdziesz.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 12, 2013, 00:42:22
@Adam27: To zwykły algorytm Dijkstry, który jest szczególnym przypadkiem A* :)
Poprawka: to jest zwykły BFS. Algorytm Dijkstry jest nieco bardziej skomplikowany i korzysta z kolejki priorytetowej.