Heurystyczny algorytm gwiazdotwórczy dla powierzchni kostki

Question

Buduję model snake game odtwarzany na powierzchni sześcianu. Obecnie wykorzystuje algorytm Dijkstry do odnajdywania ścieżki. Pomimo optymalizacji przy użyciu struktur danych kolejki o ustalonym i priorytetowym znaczeniu, nadal jest on zbyt wolny. Zauważysz opóźnienie, gdy wąż zje przedmiot żywnościowy i zaczyna szukać nowego.

Próbuję go użyć zamiast A *, ale nie mogę znaleźć dobrej heurystyki. Na płaskiej siatce z 4 kierunkami ruchu korzystałbym z odległości na Manhattanie. Próbowałem używać odległości 3D Manhattan abs(dx) + abs(dy) + abs(dz), która nie działała bez powodu: dla węża świat gry jest naprawdę 6 grids (corresponding to the faces of the cube) z niezwykłymi właściwościami zawijania.

W kodzie każde pole jest przechowywany w grid[15][15] 2D tablicy. Jest 6 takich tablic do przechowywania każdej twarzy. Tak więc każdy kwadrat ma potrójną wartość (arrayX, arrayY, d), aby opisać przesunięcie w tablicy 2D i określić, która tablica. Ponadto każdy kwadrat ma potrójną pozycję przestrzenną z potrójnym oznaczeniem (x, y, z).

Oto obszar kodu gry gdzie Pathfinding dzieje:

https://github.com/mhluska/Snakeception/blob/master/src/js/game.coffee#L105

Oto kod biblioteki dla A *:

https://github.com/mhluska/Stimpack/blob/master/src/js/graph.coffee#L60

Co jest odpowiednia, zwięzłe heurystyczny dla tego swiat gry?

Answer 1

Jednym ze sposobów rozwiązania tego problemu jest zamiast tego, aby wszystkie ścieżki znalazły się po pobraniu jednego produktu spożywczego, aby wąż przesunął się w stronę, która ma następny artykuł żywnościowy, a następnie, gdy jest po tej stronie , użyj podstawowego algorytmu A * siatki 2D, aby zdobyć artykuł spożywczy. Innymi słowy:

Kiedy wąż chwyta element pokarmu lub przenosi się do nowej stronie kostki, wykonaj następujące czynności:

• Jeśli pozycja jedzenie jest na bieżącej stronie kostki, znaleźć drogę do go za pomocą algorytmu a * z odległości 2D Manhattan heurystycznego
• Jeśli pozycja jedzenie jest na sąsiedniej stronie kostki, znaleźć drogę do krawędzi sześcianu graniczących bieżącej strony i strony docelowej za pomocą tego samego algorytmu pathfinding .
• Jeśli artykuł spożywczy znajduje się po przeciwnej stronie sześcianu, znajdź ścieżkę od bieżącej strony z tym samym algorytmem odnajdywania ścieżki.

Nie gwarantuje to najkrótszej ścieżki całkowitej, ale zwykle powinna znajdować się w pobliżu najkrótszej ścieżki i powinna być szybsza, ponieważ dzieli ścieżkę na wiele etapów i wykorzystuje bardziej wydajny algorytm dla każdej fazy.