Z rzeczywistego punktu widzenia: jeśli zmierzałeś z A do B i znalazłeś na drodze zamknięte drzwi D, zdasz sobie sprawę, że musisz znaleźć klucz D. Więc jeśli twoja AI jest tak nieświadoma, jak typowy człowiek , wymagałoby to poszukiwania klucza, który sam w sobie jest zestawem małych kroków w poszukiwaniu ścieżki. Z drugiej strony możesz chcieć, aby twoja sztuczna inteligencja wiedziała, zanim nawet spróbuje podążać ścieżką, że na tej trasie są zamknięte drzwi, i w takim przypadku prawdopodobnie będzie wiedział, gdzie znaleźć klucz.
Tak czy inaczej, problemem jest łączność na dwóch poziomach. Na poziomie „na ziemi” wiesz, że zawsze możesz bezpiecznie poruszać się w obrębie jednej niepodzielnej strefy ... to znaczy niepodzielnej przez zamknięte drzwi. Tutaj możesz swobodnie korzystać z bieżącej implementacji odnajdywania ścieżek A *. (W uproszczonym przykładzie możesz zobaczyć strefę jako pojedynczy pokój. Nie możesz dostać się do żadnego innego pokoju bez odblokowania drzwi. W rzeczywistości może to być cały region twojego lochu.) To podstawa twojego ruch bytu, ale to trochę jak chodzenie ze spuszczonymi oczami, zamiast najpierw badać obszar wokół ciebie - prawdopodobnie wejdziesz do latarni. Lub w tym przypadku zamknięte drzwi. Tak więc twoje mapy naziemne, na których działa Twój A *, muszą ograniczać ruch gracza tylko w obrębie bieżącej strefy.
Następnie znajduje się mapa wyższego poziomu, która jest bardziej topologiczna niż z natury topograficzna. Tak naprawdę nie zależy mu na szczegółach naziemnych przeszkód itp., Zależy tylko na łączności między strefami. Ta mapa topologiczna zawiera połączenia między nawet strefami, które obecnie mają między sobą zamknięte drzwi, ponieważ pokazuje idealną łączność wszystkich stref w lochu. Na krawędziach - każda reprezentuje drzwi między strefami - przechowuje klucz, który jest jeszcze potrzebny, jeśli taki istnieje, aby otworzyć te drzwi, w przeciwnym razie jest uważany za otwarty. Przeszukując ten wykres w poszukiwaniu najkrótszej ścieżki, należy ograniczyć tę znalezioną ścieżkę tylko do tras, które są już otwarte , sprawdzając dane na krawędziach podczas wyszukiwania. Łączność tutaj nie oznacza otwartości, a raczej potencjalnej otwartości.
Kiedy chcesz przejść do punktu znajdującego się w oddzielnej strefie, najpierw przeszukaj mapę wyższego poziomu, aby znaleźć ścieżkę. (Na tym poziomie można użyć A * lub dowolnego innego algorytmu najkrótszej ścieżki.) Po znalezieniu ścieżki ta mapa wyższego poziomu powinna również zawierać informacje na temat drzwi, których należy użyć, aby przejść z bieżącej strefy do drugiej strefy. Teraz w strefie lokalnej możesz wykonać sztuczną inteligencję na poziomie gruntu, aby przejść do tych drzwi. Po osiągnięciu drzwi twoja postać może przejść przez te drzwi / portal. Znajduje się teraz w strefie B. Jeśli jest to strefa docelowa, może użyć nawigacji na poziomie gruntu, aby przejść do klawisza. Jeśli tak nie jest, musisz powtórzyć krok pierwszy, aż dotrzesz do strefy docelowej.
Istnieje możliwość, że klucz jest poszukiwany za zamkniętymi drzwiami ... i że klucz do tych drzwi jest podobnie ... i tak dalej w ad nauseum. Jest to zasadniczo problem rozwiązywania zależności i istnieje kilka sposobów rozwiązania tego problemu, jednym z nich jest sieć Petriego. Zobacz ten znakomity papier.
PS. Jeśli tworzysz lochy w sposób proceduralny, możesz w ten sposób przechowywać informacje o porządkowaniu zależności, pod warunkiem, że znasz już pozycję początkową gracza.