空間分割の方法

Question

###前提・実現したいこと
キャラクターが動く迷路ゲームのようなものを作成しています。
また、現在AIにも興味があるので最終的には自動で動くものを作成したいと考えています。
###発生している問題・エラーメッセージ
360度どの方向にも動ける仕様で作成したいと思っています。
フィールドはこのような感じで、左下から出発し設定したゴールへ向かわせます。

上にも書いたのですが、自分でキャラクターを動かすのではなく、AIにキャラクターを動かしてもらうことが目的です。
そのためには、自分が今いる現在地などを整数で表す必要があると本で読みました。
今360度どこにもいけるプログラムを書きたいので下の図のよう360度を45度ずつ分けてエリアを分割したいと思っています。

----------------------------------------追加-------------------------------------------

このエリアの分割でキャラクターの状態を表現しようと思うと、(30.5,40.5)の時と(5.5,10.5)の時の区別がつけられないのではないかと考えました。

そのため、キャラクターの(x,y)座標とエリアの中心からの角度でキャラクターの状態付けをできないかどうかというのが悩みです。

衝突判定や空間分割などのサイトやと本で調べた結果、"四分木空間分割"が近いかと思ったのですが、私の作成したい度数で分けることには流用できないような気がしています。
わかりづらい質問で申し訳ありませんが、もし、このように度数でエリアを分割する方法をご存知の方がいらっしゃいましたら教えてくださるとうれしいです!

よろしくお願いします。

###補足情報(言語/FW/ツール等のバージョンなど)
C言語で作成中です。

Answer 1

質問内容を読んでも、Chironianさんへのコメントを読んでも、角度でエリア分けしないといけない理由がいまいちよく判りません。そもそも、エリア分けは必要でしょうか？

シンプルな衝突判定であれば、自機の座標と敵機の座標さえ判ればピタゴラスの定理で計算できます（一定の距離に近づいたら衝突したとみなす）。方向を知りたければ逆三角関数(atan2)で算出できます。
あるいは、自機の方向と移動距離が判れば三角関数で座標が算出できます。
迷路の壁との衝突判定であれば、自機の移動方向の線分と壁の線分との交点を算出すればできそうです。固定物の場合はマスクイメージを使えば簡単にできるかもしれません。

まずは、エリア分けなど考えずに作ってみてはどうでしょうか。その上で、もし処理速度に不満があるなら、自機を中心とした円形あるいは正方形の範囲で絞り込むとか、四分木空間分割などのアルゴリズムを試すなどすれば良いかと思います。

Answer 2

こんにちは。mikamikanさん自身が混乱されているような印象を受けます。

そのためには、自分が今いる現在地などを整数で表す必要があると本で読みました。

その通りですね。XY座標を使って表現することが多いと思います。

今360度どこにもいけるプログラムを書きたいので

こちらは移動方向を角度で表現したいということですね。
もし、一度に移動する量が「１コマ」であれば、移動は「上下左右と斜め4方向」の計８通りだけですね。

下の図のよう360度を45度ずつ分けてエリアを分割したいと思っています。

ここが分かりません。「エリア」ってなんでしょうか？
角度の範囲を「エリア」と表現することはあまりないと思いますので、この辺に混乱が感じられます。

現在位置が(x, y)で、x軸正の方向から反時計回りに角度θで、距離r移動したい場合、移動後の位置(x', y')は

x'=x + r・cosθ
y'=y + r・sinθ

となりますね。
この辺がヒントにならないでしょうか？

Comments

[mikamikan]

回答ありがとうございます。
ご指摘の通り、混乱中です。
説明不足で大変申し訳ありませんでした。

私は一番上の図のようなキャラクターを動かすためのフィールドを用意しました。これは0<x<250,0<y<250の範囲で設定しました。
次に障害物を設定するため、このフィールドを0から24の25個のエリアに分割しました。
初めは4方向に1マス(1エリア)ずつ動かしていたので、このエリア0から24を用いてキャラクターの現在位置を管理していました。

今、作成したいと思っているのはキャラクターの座標が (x , y) の時、 指定したangle 度の方向へ 5.5ずつ進みたい場合です。
動いた後の座標は以下の式で計算しています。
x+=cos(angle*3.1415926535/180)5.5;
y-=sin(angle*3.1415926535/180)*5.5;

この場合だと、上で設定したエリアの大きさよりも動く距離が小さいので同じエリアの中を何回も動くことになると思います。
AIに問題を解かせることを現在考えているのですが、そのとき、上のやり方と同じでエリアの番号だけでキャラクターの状態を管理していると例えば(5.5,10.5)と(30.5,40.5)の二つの座標がAIには区別できないのではないかと考えました。
そのため、キャラクターの(x,y)座標とエリアの中心からみてキャラクターがどの角度にいるのかの2つを用いて状態付けする良い方法があるかどうかというのが悩みです。

長くわかり辛い文になってしまいました、申し訳ありません><

[mikamikan]

すみません、画像が添付できなかったので質問の本文を更新します。

[Chironian]

> キャラクターの(x,y)座標とエリアの中心からの角度でキャラクターの状態付けをできないかどうかというのが悩みです。

これだけでしたら、エリアを45度単位で区切った８つのサブエリアに分割して、０~
7の番号を振り、エリア番号0～24とサブエリア番号0～7でキャラクタの状態管理はできると思います。

しかし、この管理方式はキャラクタの位置関係を表現できないので、平面上の問題を解く際にはあまり良い表現方法ではない可能性が高いです。実際にAIを使ってどんな問題を解こうとされているのか、書かれた方が良いように感じます。

もし、エリアの境界に壁を立てて「迷路」を作り、スタートからゴールへ至る道をAIに探させることを想定されているのでしたら、根本的な部分を勘違いされているかも知れません。
0.0～250.0で表現しているキャラクタの座標(x, y)を整数で表現した方が問題は解きやすい筈です。例えば、(5.5, 10.5)を丸めて(6, 11)、もしくは、10倍して(55, 105)で表現するなどです。

Answer 3

質問文、こういう解釈でよろしいでしょうかね。

• 正方形のセルで8方向に隣接関係があるマップ上でものを動かしたい。
• 移動は、隣接しているセルにだけ行うようにしたい。
• ただし、斜め方向の移動はピタゴラスの定理に準じた距離だけ移動するのを実現したい
• これを実現するためにセル内を「どちら方向へ移動中」という意味の８つのサブセルに分けることで表現しようとしているが行き詰まっている

隣接しているセルにしか、というのは質問文内にはありませんでしたが、おそらく前提条件ですよね？ 迷路ゲームということは、壁がどのくらいの厚さを持つオブジェクトになるのかわかりませんが、飛び越えてしてしまうのは避けないといけないということでしょう。だから「縦横方向には1ステップで3セル、斜め方向なら1ステップで2セル飛べる」なんていうのは解決にならないと。

まずこの理解は合っていますでしょうか。