java - 使用大字节 [] 数组的 Applet A* 寻路 - 堆空间错误

Question

我编写了一个基本的 Java 小程序，它可以用作游戏粉丝网站的 map 查看器(如 Google map )。

其中，我在具有 16 个不同楼层的 2D map 上实现了 A* 寻路算法，在某些点上“连接”。地板存储在 PNG 图像中，需要时下载并转换为字节数组。节点成本从像素 RGB 值中检索并放入字节数组中。

该 map 包含约 200 万 block 图 block ，分布在 16 层楼上。图像大小为 1475 x 2000(PNG 图像为 15-140 KB)，因此某些地板包含大量空瓷砖。

字节数组在内存中会很大，导致大多数 JVM 配置出现“java.lang.OutOfMemoryError: Java heap space”错误。

所以我的问题是

• 有没有办法减少这些字节数组的大小，同时仍然可以正常使用探路器功能？
• 我是否应该采取不同的方法来寻找最佳路径，而不是将图 block 保留在内存中？

我认为在 Web 服务器上查找路径会占用大量 CPU 资源。

最诚挚的问候，

Answer 1

您刚刚遇到了 A* 的最大问题:它的内存需求与状态空间的大小成正比。

这里有几个选项。

第一个是将搜索算法从 A* 更改为 IDA* ，并添加搜索增强功能，例如内存缓存，以记住尽可能多的先前搜索的节点成本。

另一种选择是保留 A* 但转向分层搜索。但是，这可能需要您对图像文件进行一些预处理。

您可以在这里找到有关此主题的一些很好的资源(可下载论文):http://webdocs.cs.ualberta.ca/~holte/CMPUT651/readinglist.html