スタッフBLOG

経路探索2015年09月29日

チューターの田村です。

先日、javaを勉強し始めたと言ったのに何もその話をしていなかったので、ちょっとだけ。

今、僕が作ろうとしているのはSRPGという、マス目上のキャラクターを動かして戦うゲームなんですが(説明が下手ですみません)

キャラクターを動かせる範囲をどうコンピューターに計算させるかという話です。

 

簡単に話を進めるために、5×5の正方形のマス目があって真ん中にキャラクターがいるとし、キャラクターは一回の行動で2マス進めるとします。

正方形のマス目のどこでも進めるなら、進めたいマスの座標(x,y)とキャラクターのいるマス(3,3)との差を計算すれば、|x-3|+|y-3|≦2なら進めるし、それ以外なら進めないという風に計算できます。

 

では、マス目に、水たまりなど、そこは通れないというマスを追加してみましょう。

もちろん、水たまりのマスには進めませんので、そこも進めないと設定すればいいと思うかもしれませんが、それ以外にも影響が出てきます。

例えば今のままだと、キャラクターの真上のマスが水たまりだった場合、2個上のマスには|x-3|+|y-3|≦2であって水たまりのマスでもないから進めると計算されてしまいますが、実際は水たまりを飛び越えないといけません。(今回は水たまりを飛び越えることはできないとします)

どうしたらいいのでしょうか。