2013-06-15 12 views
12

Obecnie piszę grę 2D w JavaScript przy użyciu elementu HTML5 <canvas>. Nadchodzi bardzo ładnie, ale mam problem.Co to jest dobry algorytm wyszukiwania dwuwymiarowego oparty na siatce?

Konstrukcja poziomu mojej gry to siatka (więc koszt ruchu z jednej komórki do komórki północ/południe/wschód/zachód wynosi 1) z różnymi przeszkodami zajmującymi różne miejsca w siatce – bardzo podobny do labiryntu, ale z dużo większym pokojem. Każdy indywidualny poziom jest rzędu 400 × 200 komórek.

Próbuję zaimplementować wroga, który będzie szukał gracza bez względu na to, gdzie się znajduje, ale mam problem z przetłumaczyć jeden z różnych algorytmów wyszukiwania ścieżek, aby dopasować się do mojej sytuacji. Większość z tych, które spotkałem (jak A * i Dijkstra) wydaje się najlepiej pasować do 3D lub znacznie bardziej skomplikowanych sytuacji 2D. Zastanawiałem się, czy możliwe jest radykalne uproszczenie tych algorytmów, aby lepiej pasowały do ​​moich celów, lub gdyby coś takiego jak pierwsze wyszukiwanie było bardziej wydajną alternatywą, biorąc pod uwagę rozmiar poziomu.

+0

Nie zrobisz tego lepiej niż A *, nie dając mu jakiejś wstępnej wiedzy o możliwych ścieżkach (jak dzielenie mapy na segmenty o znanej łączności). Głębokość najpierw byłaby dużo (dużo dużo) wolniejsza niż szerokość. – Dave

+0

To nie jest tak naprawdę to, o czym mówi Stackoverflow/Stack Exchange; zadaj pytanie z konkretną odpowiedzią, a nie pytanie o zakupy. Za wszelką cenę używaj tego, co ludzie sugerują, ale wróć, kiedy uderzysz w przeszkodę z problemem programowania. – Amelia

+0

@Dave: Cóż, możesz łatwo [znaleźć lepszy niż zwykły "A \ *] (http://programmers.stackexchange.com/questions/197894), gdy jest ograniczony do siatki; ale JPS + A \ * jest bardziej skomplikowany niż tylko A \ * i zazwyczaj nie jest potrzebny. –

Odpowiedz

14

A * jest bardzo powszechnym algorytmem śledzenia 2D. Może zająć trochę czasu, aby owinąć głowę tym, co się dzieje, jeśli odnajdywanie drogi jest nieznane, ale nie jest to zbyt skomplikowane. Być może po prostu patrzysz na przykładowy kod kogoś innego, który został opracowany dla bardziej złożonej aplikacji, niż zamierzałeś. Jest a good tutorial for understanding the algorithm here.

+0

Dziękuję, przyjrzę się temu. – creXALBO

+5

Link wydaje się być martwy. –

+0

Jeśli link wydaje się być martwy, spróbuj wysłać wiadomość e-mail: patrick (at) policyalmanac (dot) org – Skrivener

2

EasyStar.js to ładnie wyglądająca biblioteka, która wydaje się robić to, co chcesz. Nie używałem go sam, ale dokumentacja na stronie github projektu wygląda całkiem nieźle i prawdopodobnie to właśnie bym wybrał na waszej pozycji.

Powiązane problemy