Поиск пути апплета A * с использованием больших массивов byte [] - ошибка кучи - PullRequest
Новая
       15

Поиск пути апплета A * с использованием больших массивов byte [] - ошибка кучи

0 голосов
/ 24 марта 2010

Я написал базовый Java-апплет, который работает в качестве средства просмотра карт (например, Google Maps) для фанатов игр.

В нем я реализовал алгоритм поиска пути A * на 2D-карте с 16 различными этажами, «соединенными» в определенных точках. Этажи хранятся в PNG-изображениях, которые при необходимости загружаются и преобразуются в байтовые массивы. Стоимость узла извлекается из значений пикселей RGB и помещается в байтовые массивы.

Карта содержит около 2 миллионов плиток на 16 этажах. Изображения имеют размер 1475 x 2000 (15–140 КБ для изображений PNG), поэтому на некоторых этажах много пустых плиток.

Массивы байтов будут огромными в памяти, что приведет к ошибке «java.lang.OutOfMemoryError: Java heap space» для большинства конфигураций JVM.

Так что мои вопросы

  • Есть ли способ уменьшить размер этих байтовых массивов и при этом правильно использовать функцию поиска пути?
  • Стоит ли использовать другой подход к поиску оптимального пути, не имея тайлов в памяти?

Я думаю, что поиск пути на веб-сервере будет слишком загружен процессором.

С уважением,
A

1 Ответ

1 голос
/ 24 марта 2010

Вы только что столкнулись с самой большой проблемой с A *: его требования к памяти пропорциональны размеру пространства состояний.

У вас есть несколько вариантов здесь.

Первым было бы изменить алгоритм поиска с A * на IDA * и добавить улучшения поиска, такие как кэш памяти, чтобы запомнить как можно больше ранее найденных затрат на узел.

Другая альтернатива - сохранить A *, но перейти к иерархическому поиску. Однако это, вероятно, потребует от вас некоторой предварительной обработки файлов изображений.

Вы найдете несколько хороших ресурсов (загружаемые статьи) по этой теме здесь: http://webdocs.cs.ualberta.ca/~holte/CMPUT651/readinglist.html

...