Mam grę, w której musisz poruszać się po mapiezbieranie złota, a następnie przejść do wyjścia. Obecnie próbuję napisać sztuczną inteligencję, która będzie grała w tę grę, ale chcę wiedzieć, jaki algorytm powinienem użyć, aby znaleźć najbliższą instancję obiektu. Na przykład najbliższy kawałek złota lub najbliższy nieznany kwadrat mapy. Problem polega na tym, że są ściany, przez które gracz nie może się poruszać, więc zamiast znajdować najbliższy obiekt, muszę znaleźć ten, do którego jest najkrótsza droga. Czy istnieje algorytm, który może to zrobić?
Odpowiedzi:
5 dla odpowiedzi № 1Algorytm, którego szukasz, nazywa się A *Wyszukaj algorytm. Jest to najlepszy algorytm wyszukiwania, który działa od początku w punkcie początkowym i buduje serię możliwych ścieżek (z wyłączeniem przechodzenia przez przeszkody, ponieważ nie są one możliwymi ścieżkami), a następnie wyznaczenia tych ścieżek w celu znalezienia najmniejszego kosztu. W twoim przypadku musisz dostosować punktację, zmniejszając koszt w oparciu o obiekty wzdłuż ścieżki i zwiększając koszt na odległość.
Oto niektóre informacje, które mogą ci w tym pomóc:
Tutaj jest fajne interaktywne demo (kod również na githubie): http://qiao.github.io/PathFinding.js/visual/
Inne zasoby:
- https://harablog.wordpress.com/2011/09/01/rectangular-symmetry-reduction/
- https://en.wikipedia.org/wiki/A*_search_algorithm
- Jaki jest dobry algorytm wyszukiwania ścieżki oparty na siatce 2D?