37: TraceLine関数の理解

概要

前回のAimbotの実装では、敵が壁の向こう側にいても狙ってしまいます。
ゲームエンジンには、TraceLine/TraceRayという関数があり、ある座標Aから座標Bまでの線上に何も物が無いかどうかを判定できます。 つまり、TraceLine関数をAimbotのコードで呼び出すことにより、狙った敵と自分との間に物が何もない事を確認してから打つという事ができるようになります。
今回は、TraceLine関数をAssaultCubeのソースコードを見ながら理解し、リバーシングに必要な特徴を見つける事を目標にやっていきます。
チート対象のゲームは、x86でオープンソースのAssault Cube v1.2.0.2を使います。
EntityListの知識が必要なので、見ていない方は 35回 から見ていただければ。

TraceLine関数とは

TraceLineは、大体どのゲームエンジンにも備わっている関数で、ある座標fromから座標toまでの線上に何もエンティティが無いかどうかを判定し、 何かあればtrue、何もなければfalseを返す関数です。

例えばAssaultCubeにてプレイヤーが敵にエイムした時、敵の名前が左下に表示されます。 しかし、敵の方を向いていたとしても、壁が間にあると名前は表示されません。 この機能の中では、このTraceLineが使われている事が想像できます。
また、実際に弾を打った時にも使われている可能性は高いです。 弾のように小さくかつ高速で移動するオブジェクトは、衝突判定が上手く行かない事が多いです。 しかも、どうせ弾は見えないのでわざわざ弾の3Dオブジェクトを作成し、それと敵プレイヤーとの衝突判定を実装するよりかは、 弾を作らずに、「敵の方を向いていてかつ自分と相手との間に何もない時にクリックした時にダメージを入れる」とした方が軽いですし効率的です。 なので、弾を打つ関数内でも使われている事が想像できます。

TraceLineの詳細

TraceLine関数をリバーシングにて見つける際、TraceLineがそもそもどういう関数なのかという点を知っておくと便利です。
TraceLineの細かい実装はゲームエンジンによりけりかもですが、大部分は同じだと思うので、 ここではAssaultCubeのTraceLineの実装を徹底的に見ていきます。 AssaultCubeはオープンソースなので、実際にコードを見る事ができます。 AssaultCubeのTraceLineは戻り値がvoidですが、結果は引数の traceresult_s *tr に入ります。 この構造体は、tr->collided に、線の間に障害物があったかどうかの true/false を格納するのに加えて、 tr->end に、実際に衝突した線上のポイントの座標を格納します。
これ踏まえて、AssaultCubeのTraceLineのソースコードを解析し、大事なポイントをピックアップすると以下のようになります。 
void TraceLine(
    座標(from),
    座標(to),
    このTraceLineを読んでるエンティティ(自分),  // 向いてる方向の取得、自分は障害物としてカウントしない に必要
    bCheckPlayers,                         // 線上にいるプレイヤーを障害物としてカウントするか
    結果を格納する構造体(tr),                 // ゲームエンジンによっては戻り値である可能性もある
)
{
    // マップ上のオブジェクトとの衝突判定
    for(entity : マップ上のオブジェクト) {
        if(現状collided=trueな物よりもfromに近い位置にある && intersect(entity, from, to, tr->end))
            tr->collided = true
    }

    // 敵との衝突判定
    if(bCheckPlayers) {  // bCheckPlayers=false の場合、敵は障害物としてカウントしない
        for(entity : 敵達) {
            if(entity!=自分) {
                if(現状collided=trueな物よりもfromに近い位置にある && intersect(entity, from, to, tr->end)==true)
                    tr->collided = true
            }
        }
    }

    // cube? との衝突判定 （よくわからないけど上記の処理内容で十分なので多分見る必要無さげ）
}
つまるところ、単にエンティティリストをループで回し、それぞれに置いてintersect関数を用いて線と衝突があるかどうかを見ていっているだけです。 なので、コアな機能はintersectにあります。後は、trは実際に衝突した線上のポイントの座標を tr->end に格納しないといけなく、 衝突した物の中で一番fromに近い位置にある物が実際に衝突するポイントなので、その処理があります。 また、TraceLineの呼び出し元のエンティティが、自分を障害物とカウントしないようにしてたりと細かな調整があるだけで、やってる事は単純です。

では、コアな機能の intersect関数 を見ていきます。
intersect関数はオーバーロードされていて、マップ上のオブジェクトとの衝突判定 と 敵との衝突判定 に用いられるintersectで処理内容が違います。 マップオブジェクトとのintersect では、内部でintersectboxが呼ばれており、 敵とのintersect では、内部でintersectsphereとintersectcylinderが呼ばれています。 これは、そもそもマップ上のオブジェクトと敵のオブジェクトで、 形状の種類が違うため、衝突判定方法も異なるから処理内容が分かれていると考えられます。 マップオブジェクトの方のintersectを深堀していきます。
マップオブジェクトのintersect関数のメインの役割は、intersectboxを適切な引数を渡して呼ぶ事だけです。
その引数は、ざっくり以下のような形です。
つまり、intersectbox がコアな機能となっています。
intersectbox は、コアな衝突判定の機能なので、中身はベクトル計算がメインとなっています。
intersectboxでは、以下三つの場合に分けて考えています。 灰色の線より後か前かは、cosθが正か負かで判断しており、具体的には 内積を使って この正負を確かめています。上図の例で言えば、ベクトルv=(from,to) と ベクトルw=(from,e) の内積を取っており、 内積は、v・w = |v||w|cosθ の式で表されるため、cosθが正か負かは、内積が正か負かを見ればわかるという原理です。

各場合において、fromからtoへの線上に このオブジェクトがintersectする(交わる)ケースはこんな感じです。
  1. オブジェクトが大きく、fromの座標と重なるケース
  2. オブジェクトが大きく、toの座標と重なるケース
  3. オブジェクトの範囲内に、線上の任意の点が含まれている場合
1,2のケースは、一見 線上にオブジェクトは来ないように思えますが、以下の用にオブジェクト内にfromやtoの座標がある場合に、線上に来る可能性があります。 なので、1の場合はfromの座標が、2の場合はtoの座標が、 オブジェクトの中に含まれているか どうかでintersectしてるかどうかを判断しています。

一方、3のケースは一番衝突する可能性が高いケースで、処理内容 も少しややこしくなっています。
説明すると以下のように、オブジェクトの中心との最短距離にある座標を求め、それがオブジェクトの範囲内にあるかどうかで判断しています。 これら3パターンの内、一つでもintersectしていれば、trueが返り、intersect関数もtrue を返し、TraceLineの方で tr->collided=true になる事で、座標fromからtoの間の線上にこのエンティティがありますよという結果になります。

リバーシングでTraceLineを見つけるポイント

上述の通り、TraceLineは結構ややこしい機能であると共に、"計算"の処理 をリバーシングにて見つけるのは大変です。
なので、ここではリバーシングでこれを特定するためのポイントをいくつか書きます。

リバーシングにてある関数を見つける際、引数と戻り値 は特に良い手掛かりとなります。
TraceLineの引数と戻り値の特徴は、以下に注目すると良いと思います。 ちなみに、引数は大体どのゲームエンジンのTraceLineでも似たような物があります (Sourceエンジン, Quakeエンジン)。

引数や戻り値で怪しいと思った後、処理内容に注目すると思います。
TraceLine関数の処理内容で確認すべきポイントは以下だと思います。 ここまででも絞り切れない場合、さらにintersectと思われる関数の中身を確認しにいくのはあまりオススメしません。
ベクトル計算等に強い人ならいけるかもですが、基本的にintersectboxやintersectsphere等の関数はパッと身訳わからないので、 そこを見るよりかは、TraceLineを使っていそうな別の機能をリバーシングし、TraceLine関数だと思った関数をそこでも読んでいるかを見た方がいいかもしれないです。