0

我编写了一个基本的 Java 小程序，可用作游戏爱好者网站的地图查看器（如 Google 地图）。

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

该地图包含大约 200 万块瓷砖，分布在 16 个楼层。图像大小为 1475 x 2000（PNG 图像为 15-140 KB），因此某些楼层包含很多空瓷砖。

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

所以我的问题是

  • 有没有办法减少这些字节数组的大小并且仍然有正确的探路者功能？
  • 我是否应该采取不同的方法来找到最佳路径，而不是在内存中保存图块？

我认为在 Web 服务器上查找路径会占用过多的 CPU。


最好的问候，

4

1 回答 1

1

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

您在这里有几个选择。

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

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

你可以在这里找到关于这个主题的几个很好的资源（可下载的论文）：http ://webdocs.cs.ualberta.ca/~holte/CMPUT651/readinglist.html

于 2010-03-24T19:37:03.070 回答