0

私は、ゲーム ファンサイト用のマップ ビューアー (Google マップなど) として機能する基本的な Java アプレットを作成しました。

その中で、特定のポイントで「接続」された 16 の異なるフロアを持つ 2D マップに A* パスファインディング アルゴリズムを実装しました。フロアは、必要に応じてダウンロードされ、バイト配列に変換される PNG 画像に格納されます。ノード コストはピクセル RGB 値から取得され、バイト配列に格納されます。

マップには、16 フロアにまたがる約 200 万個のタイルが含まれています。画像は 1475 x 2000 (PNG 画像の場合は 15 ～ 140 KB) の大きさであるため、一部のフロアには空のタイルが多数含まれています。

バイト配列はメモリ内で巨大になり、ほとんどの JVM 構成で「java.lang.OutOfMemoryError: Java heap space」エラーが発生します。

だから私の質問は

  • これらのバイト配列のサイズを縮小し、パスファインダー機能を適切に維持する方法はありますか?
  • メモリにタイルを持たずに、最適なパスを見つけるために別のアプローチを取る必要がありますか?

Web サーバーでパスを見つけるのは、CPU の負荷が高すぎると思います。

よろしく、
A

4

1 に答える 1

1

A* の最大の問題に突き当たったところです。メモリ要件は状態空間のサイズに比例します。

ここにはいくつかのオプションがあります。

1 つ目は、検索アルゴリズムを A* からIDA*に変更し、メモリ キャッシュなどの検索拡張機能を追加して、以前に検索したノード コストをできるだけ多く記憶することです。

もう 1 つの方法は、A* を維持して階層検索に移行することです。ただし、これには、画像ファイルに対して何らかの前処理を行う必要がある可能性があります。

このテーマに関するいくつかの優れたリソース (ダウンロード可能な論文) は、http ://webdocs.cs.ualberta.ca/~holte/CMPUT651/readinglist.html にあります。

于 2010-03-24T19:37:03.070 に答える