A.I. który może poruszać się po losowo wygenerowanym mieście 2D

Question

Piszę grę na iOS (używając UIView), która ma losowo wygenerowane miasto 2D. Potrzebuję ataku A.I., który zajmie inteligentną ścieżkę, aby znaleźć gracza (bez kolizji z budynkami). Czy ktoś może wskazać mi właściwy kierunek, jakiego rodzaju algorytmów użyłbym, aby to osiągnąć?

Edytuj: Zdecydowałem się użyć A *. Utworzę siatkę na mapie, przetestuję każdy punkt przecięcia siatki, jeśli ten punkt znajduje się wewnątrz budynku, unieważnię ten punkt. Atakujący A.I. gracz przesunie się z aktualnej pozycji do poprawnego punktu siatki, który jest bliżej celu (w pewnym promieniu jego położenia).

Answer 1

Szukasz klasy algorytmów o nazwie pathfinding algorithms. Istnieje wiele podejść, z których możesz skorzystać.

Klasyczne algorytmy to: Dijkstra's algorithm i A* search, które mogą prowadzić obiekt z jednego miejsca do drugiego wzdłuż optymalnej ścieżki. Algorytmy te działają poprzez modelowanie świata 2D jako graph, a następnie znajdowanie najkrótszej ścieżki od położenia początkowego obiektu do miejsca docelowego na tym wykresie. Te dwa algorytmy są szeroko stosowane w AI i odnajdywaniu ścieżek i zdecydowanie sugerowałbym zainwestowanie czasu, aby przeczytać o nich więcej. Jeśli chcesz, możesz skorzystać z usługi solid tutorial on A* search.

Jeśli masz wiele różnych obiektów, które muszą zostać przeniesione do celu bez przeszkadzania, możesz zajrzeć do potencjalnych pól, które dają prostą i elastyczną strukturę umożliwiającą wielu obiektom zbliżenie się do celu. To podejście zostało użyte przez the Berkeley "Overmind" StarCraft AI i jest często używane w planowaniu ruchu robotów. Intuicyjnie to podejście polega na przypisaniu "potencjalnej" wartości do każdej lokalizacji, a następnie przeniesieniu obiektów z wysokiego potencjału do niskiego potencjału, dopóki nie trafią w cel. Takie podejście jest nieco trudniejsze do uzyskania, ale gdy działa, prowadzi do elastycznej, dostosowywalnej sztucznej inteligencji, która zachowuje się inteligentnie.

Mam nadzieję, że to pomoże!

Answer 2

To pytanie jest tutaj: Pacman: how do the eyes find their way back to the monster hole? to dobra ankieta dotycząca podejść do nawigacji AI losowej siatki 2D w poszukiwaniu poruszającego się gracza. Ogólny konsensus (i podejście zastosowane przez Pacmana) to nie martwić się wypalaniem inteligentnych algorytmów odnajdywania ścieżek w AI, ale zamiast tego używać samej mapy do przechowywania informacji o lokalizacji gracza. To fascynująca lektura, szczególnie druga i trzecia odpowiedź (i ich zewnętrzne linki) autorstwa ammoQ i Dana Vintona.

Ten link tutaj Pacman scent antiobject pattern opisuje tanie i skuteczne podejście.