Jak radzić sobie z obiektami o różnych rozmiarach w sytuacji odnajdywania ścieżki (A *, gwiazda A)

Question

Pracuję nad grą, która wykorzystuje gwiazdę A (A *) do wyszukiwania ścieżek, ale doszedłem do punktu, w którym przez niektóre obiekty, które są większe niż pojedynczy kwadrat siatki.

Mam na siatce 16 * 16 pikseli. segmenty ścian mają 16 * 16, a więc sprawiają, że pojedynczy kwadrat jest nieprzejezdny. Niektóre z moich złych są 32 * 32, więc muszą sprawdzić, czy luka ma co najmniej 2 siatki szerokości, aby móc ją przejść.

Nie mogę po prostu zrobić siatki 32 * 32, ponieważ projekt wymaga cienkich ścian (przy 16px) i jest kilka mniejszych złych, które zajmują tylko jeden 16 * 16 kwadrat.

Jak mogę wdrożyć to środowisko o wielu rozdzielczościach? Czy A-star jest wciąż właściwym narzędziem do użycia?

Answer 1

http://aigamedev.com/open/article/clearance-based-pathfinding/

Answer 2

Przez stosunkowo proste rozwiązanie, chciałbym trzymać się tego samego algorytmu A * co do wielkości 16x16 obiektów, ale z nieco innym sposobem oceny, czy kwadrat jest chodzenie czy nie.

• Obiekt o wymiarach 16x16 może chodzić po placu, jeśli ten kwadrat można chodzić.
• Obiekt o wymiarach 32x32 może chodzić po placu, jeśli ten kwadrat i jego "sąsiedzi" są dostępne do przechodzenia.