プログラマ専用SNS ミクプラ

毎度お世話になっております、山崎です。
大阪での研究会に参加された皆さん、お疲れ様でした。
東京のほうでも同じようなイベントがあれば、参加して皆さんのお話をお伺いしたいなぁと思っております。

さて、今回の質問は矩形と円の当たり判定についてです。
こちらOSはXP,エディタはVisualStudio2008を使い始めました。

現在、X,Y,Z座標を持つアクションゲームを作っております。
キャラクターが一歩進んだ先の地形との当たり判定をする関数を作成中で、
地形となるマップは正方形として扱っており、キャラクターは円柱として扱っております。
このマップの矩形とキャラクターの足元となる円を見て、
円と接地している矩形を全て探索したいのですが
円と矩形が重なっているかどうかをどう判別すればいいのか半日考えてもわかりませんでした。

添付している画像を見ていただけるとおわかりになるかと思いますが、
矩形がマップを表しており、赤い円がキャラクターが立っている部分となります。
キャラクターが接触している矩形を水色で塗ってあります、
この水色の部分にアクセスしていき当たり判定を行っていきたいのですが、
どういう式やアルゴリズムで水色の部分を導き出せばいいのかわかりません。

キャラクターはメンバとして、現在位置X,Y,Z,円の半径Width、一歩の長さStepを持っています。
座標（X,Y)がキャラクターの足元の円の中心となっています。
マップは構造体の２次元配列で、矩形の辺は全て同じ長さです。

どのような手法で、キャラクターの立っている矩形を判別すればよいのでしょうか。

はじめまして、ベッキーと申します。
私は初心者なので、参考にならないかもしれませんが
私ならば、というものを書こうと思います。
（DXライブラリでの実装経験がないので未知ですが、素晴らしい関数が提供されているかもしれません）


私の場合、各矩形のもつ線分と円との交差を判定し、その線分をもつ矩形
ならば重なっている、と判定します。

この場合、点と線分の距離を導き、半径と比較すれば良いと思います。
おそらく線分ごとではなく、矩形単位での探索になると思います。。
しかしながら各矩形の線分について毎回比較するのはムダが多いので
４分木や８分木も取り入れたいところです。

もし、矩形に傾斜等がある場合（Z方向の移動がある場合）にはキャラクタの円柱単位ではなく
中心座標と矩形との衝突判定を行う方が無難かと思います。
その場合は矩形の辺からキャラクタ座標への外積をとり、結果の符号が一致すれば衝突、となると思います。

円を描くアルゴリズムというのはご存じですか？
内側を塗りつぶさなければいけませんが、これを使えばそのままこれではないですか？

ベッキーさん、hss12さん、ご返信ありがとうございます。

ご教授頂いたとおり、縁と線分の交差を調べることでキャラと矩形の重なりを探索することにいたしました。

円の式　(x-p)^2 + (y-q)^2 = r^2　と、２次方程式の解の公式を使って交差を調べるので
計算にかかる時間的な負担がちょっと心配ですが、とりあえずはプログラムを組み
実際の動作を見てみようと思います。

アドバイスいただき、誠にありがとうございます。

おつかれさまです。
乗算や平方根などを適用すると計算の負担が多いとおもいますが
まずは自分でわかりやすいアルゴリズムで組むほうが良いと思います。
頑張ってください。

線分と円との衝突を検出するアルゴリズムとしては
線分と円の中心との距離を出し、半径と比較する、という方法もありますので
コスト的なものは組み方にもよりますが、そういったアルゴリズムもあるということを
知っておいて損はないと思います。