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.
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
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
@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. –