六角マップ上の移動アルゴリズム

Question

私はこのサイトで問題が発生しました：http://www.dark-project.cz/wesnoth/map-view/1（ユニットをクリック）。私のJavascriptソースhttp://www.dark-project.cz/wesnoth/js/map/base.js（最後の$('div.unitImg').click(function()の機能）では、ユニットが行けないすべての六角形をマークしたいと思います。

私は動きが1のときにはかなり複雑なアルゴリズムを持っていますが、それが高い場合には動きません（動き2を試してください）。

正しいヘックスを見つけるアルゴリズムについて考えていますか？ここで

座標ナンバリングの例である：http://www.dark-project.cz/wesnoth/coor.png

は、すべての返信をありがとうございました。

Answer 1

まず、座標を再設計することをお勧めします。良い例はthis questionです。

しかし、座標系に関係なく、将来はフィールドにいくつかの障害物（岩や竜など）があると思われますので、そのために用意された一般的なアルゴリズムを設計する必要があります。 BFSを調べることをお勧めしますが、グラフを明示的に作成する必要はありません。エッジが必要な場合は、フィールド上の隣接する六角形（奥行き1、動作しているもの）を確認して横断します。それは一般的なアプローチです。 DFSもありますが、隣接する辺の数がかなり限られていると、BFSは到達可能性の問題に対してより効率的であると考えられることがよくあります。