Applet A* pathfinding using large byte[] arrays - heap space error

Question

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

Answer 1

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