使用大字节 [] 数组的 Applet A* 寻路 - 堆空间错误
我编写了一个基本的 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 资源。
谨致问候，
一个
I've written a basic Java applet which works as a map viewer (like Google Maps) for a game fansite.
In it, I've implemented an A* pathfinding algorithm on a 2D map with 16 different floors, "connected" on certain points. The floors are stored in PNG images which are downloaded when needed and converted to byte arrays. The node cost is retrieved from the pixel RGB values and put in the byte arrays.
The map contains about 2 million tiles, spread over 16 floors. The images are 1475 x 2000 (15-140 KB for the PNG images) big, so some of the floors contain a lot of empty tiles .
The byte arrays will be huge in memory, resulting in a “java.lang.OutOfMemoryError: Java heap space” error for most JVM configurations.
So my questions are
- Is there anyway to reduce the size of these byte arrays and still have the pathfinder function properly?
- Should I take a different approach to finding the optimal path, not having the tiles in memory?
I would think finding a path on the web server would be too CPU intensive.
Best regards,
A
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您刚刚遇到了 A* 的最大问题：它的内存需求与状态空间的大小成正比。
您在这里有几个选择。
第一种是将搜索算法从 A* 更改为 IDA*，然后添加搜索增强功能，例如内存缓存，可以记住尽可能多的先前搜索的节点成本。
另一种选择是保留 A* 但转向分层搜索。但是，这可能需要您对图像文件进行一些预处理。
您可以在这里找到有关此主题的一些好资源（可下载论文）：http ://webdocs.cs.ualberta.ca/~holte/CMPUT651/readinglist.html
You've just run into the biggest problem with A*: its memory requirement is proportional to the size of the state space.
You have a few options here.
The first would be to change your search algorithm from A* to IDA*, and add in search enhancements like a memory cache to remember as many previously-searched node costs as possible.
Another alternative is to keep A* but move to hierarchical search. This will likely require you to do some preprocessing on your image files, however.
You'll find several good resources (downloadable papers) on this subject here: http://webdocs.cs.ualberta.ca/~holte/CMPUT651/readinglist.html