ハル研プロコンの回答プログラム

hpc2014_answer.cpp

//------------------------------------------------------------------------------
/// @file
/// @brief    HPCAnswer.hpp の実装 (解答記述用ファイル)
/// @author   ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright  Copyright (c) 2014 HAL Laboratory, Inc.
/// @attention  このファイルの利用は、同梱のREADMEにある
///             利用条件に従ってください

//------------------------------------------------------------------------------

// Answer.cpp 専用のインクルードファイルです。
// 別のファイルをインクルードした場合、評価時には削除されます。
#include "HPCAnswerInclude.hpp"

namespace {
    using namespace hpc;

    /// 現在目標としている蓮の番号
    int target = 0;

    /// フィールドの流水
    Vec2 sFlow;
}

/// プロコン問題環境を表します。
namespace hpc {

    //------------------------------------------------------------------------------
    /// 目標方向への速度成分を求める
    /// 速度が小さい場合には速度は0と考える
    ///
    /// @param[in] chara      キャラクター
    ///            target_pos 目標座標
    ///
    /// @return 目標方向への速度成分
    Vec2 GetVelOfTargetComponent(const Chara& chara, const Vec2& target_pos)
    {
        const Vec2 vel = chara.vel();

        // 速度が十分に小さければ速度は0と考える
        if (vel.length() <= 0.00001f) {
            return Vec2(0.0f, 0.0f);
        }

        const Vec2 to_target = target_pos - chara.pos();
        return vel.getProjected(to_target.getNormalized());
    }

    //------------------------------------------------------------------------------
    /// 与えられた目標座標を流水に対応した座標に変更する
    ///
    /// @param[in] p      プレイヤー
    ///            target 目標座標
    ///            flow   流水の速度ベクトル
    ///
    /// @return 流水に対応した座標
    Vec2 PosThinkFlow(const Chara& p, const Vec2& target, const Vec2& flow)
    {
        const Vec2 point1(p.pos().x, target.y);
        const Vec2 point2(target.x , p.pos().y);
        const Vec2 seg = target - p.pos(); // プレイヤーと目標座標を結ぶ線分
        const Vec2 ver = point1 - p.pos(); // 進行方向の垂直方向ベクトル
        const Vec2 hor = point2 - p.pos(); // 進行方向の水平方向ベクトル

        const float sign1 = (ver.y > 0)         ? -1.0f : 1.0f;
        const float sign2 = (hor.x * ver.y > 0) ? -1.0f : 1.0f;
        const float fai = seg.angle(hor);

        // 進行方向の垂直方向ベクトルから傾ける角度
        // ave_velの値は目標までの距離にかかる時間に対する平均速度のほうがよいと思う
        const float ave_vel = 0.5f;
        const float theta = Math::ACos((sign1 * Math::Abs(seg.x) * flow.length()) / (ave_vel * seg.length())) - fai;

        return p.pos() + ver.getRotated(sign2 * theta);
    }

    //------------------------------------------------------------------------------
    /// 目標座標の計算
    /// もし流水があれば流水を考慮する
    ///
    /// @param[in] p       プレイヤー
    ///            lotuses 蓮たち
    ///            field   フィールド
    ///
    /// @return 流水を考慮した座標か蓮と線分の交点
    Vec2 CalcTarget(const Chara& p, const LotusCollection& lotuses, const Field& field)
    {
        int next_no = (p.targetLotusNo() == lotuses.count()-1) ? 0 : p.targetLotusNo()+1;
        const Vec2 p_to_curr = lotuses[p.targetLotusNo()].pos() - p.pos();
        const Vec2 p_to_next = lotuses[next_no].pos()           - p.pos();
        const Vec2 next_to_curr = lotuses[p.targetLotusNo()].pos() - lotuses[next_no].pos();

        const Vec2 norm = p_to_next.getNormalized();
        float dist = Math::Abs(norm.cross(p_to_curr));

        // 次の蓮が現在の蓮の向こうにあり、直線的に進める
        Vec2 target_pos;
        if (p_to_next.dot(p_to_curr) * p_to_next.dot(next_to_curr) <= 0 &&
            dist <= (p.region().radius() + lotuses[p.targetLotusNo()].radius())) {
                target_pos = p.pos() + p_to_curr.getProjected(norm);
        }
        else
        {
            const Vec2 curr_to_p = p.pos() - lotuses[p.targetLotusNo()].pos();
            const Vec2 curr_to_next = lotuses[next_no].pos() - lotuses[p.targetLotusNo()].pos();
            // sum_rの計算式は少しの値を引くことが必要
            // 流水の考慮が正しくないせいだと思われる
            // しかし、おそらく問題に最適化していることになる
            float sum_r = p.region().radius() + lotuses[p.targetLotusNo()].radius() - 0.4f;
            float theta = curr_to_p.rotSign(curr_to_next);
            const Vec2 t = curr_to_p.getRotated(theta/2.0f);
            target_pos = p.pos() + p_to_curr + t.getNormalized(sum_r);
        }

        if (field.flowVel().isZero()) { // 流水がない
            return target_pos;
        }

        // 流水がある
        return PosThinkFlow(p, target_pos, field.flowVel());
    }

    //------------------------------------------------------------------------------
    /// 敵が視界内に入っているか
    ///
    /// @param[in] p      プレイヤー
    ///            enemy  敵
    ///            target 目標座標
    ///
    /// @return 敵が視界内に入っているか
    bool IsInSight(const Chara &p, const Chara& enemy, const Vec2& target)
    {
        const Vec2 ed = enemy.pos() - p.pos();
        const Vec2 td = target - p.pos();

        return td.angle(ed) <= Math::DegToRad(30) && ed.length() <= 5.0f;
    }

    //------------------------------------------------------------------------------
    /// 敵がプレイヤーにとって邪魔かどうか
    ///
    /// @param[in] p      プレイヤー
    ///            enemy  敵
    ///            target 目標座標
    ///
    /// @return 敵が邪魔かどうか
    bool IsObstacle(const Chara& p, const Chara& enemy, const Vec2& target)
    {
        const Vec2 etop = p.pos() - enemy.pos(); // 敵からプレイヤーへのベクトル
        if (IsInSight(p, enemy, target)) {
            if (!enemy.vel().isZero() &&
                etop.angle(enemy.vel()) <= Math::DegToRad(90)) {
                return true;
            }
        }
        return false;
    }

    //------------------------------------------------------------------------------
    /// 衝突回避を考えた目標地点を求める
    ///
    /// @param[in] p       プレイヤー
    ///            enemies 敵たち
    ///            target  目標地点の座標
    ///
    /// @return 敵にぶつからない目標地点
    Vec2 PosAvoidCollision(const Chara& p, const EnemyAccessor& enemies, const Vec2& target)
    {
        Vec2 cand[6];
        int  n = 0;
        const Vec2 to_target = target - p.pos(); // 目標方向へのベクトル
        for (int i=0; i < enemies.count(); ++i) {
            const Chara& e = enemies[i];
            if (IsObstacle(p, e, target)) { // 敵が邪魔
                // 敵ににぶつからない目標方向を２つ求める
                const Vec2 de = e.pos() - p.pos(); // 敵への方向ベクトル
                float d = de.length();
                float theta = Math::ACos(1.0f - (2.0f / (d * d)));
                const Vec2 left  = de.getRotated(theta);
                const Vec2 right = de.getRotated(-theta);
                // 敵の速度がゼロであれば、目標方向に近いほうを候補として選択
                if (e.vel().isZero()) {
                    const float left_angle  = to_target.angle(left);
                    const float right_angle = to_target.angle(right);
                    if (left_angle > right_angle) {
                        cand[n++] = right;
                    }
                    else
                    {
                        cand[n++] = left;
                    }
                }
                else // 敵の速度がゼロでなければ、敵の進行方向と逆の方向を選択
                {
                    const float left_angle = e.vel().angle(left);
                    const float right_angle = e.vel().angle(right);
                    if (left_angle > right_angle) {
                        cand[n++] = left;
                    }
                    else
                    {
                        cand[n++] = right;
                    }
                }
            }
        }
        // 上で求めた目標方向の中で、最も外側の２方向を選択
        float l_max = -10000, r_max = -10000;
        int   l_idx = -1,     r_idx = -1;
        for (int i=0; i < n; ++i) {
            if (to_target.cross(cand[i]) > 0) { // 左側
                float angle = to_target.angle(cand[i]);
                if (angle > l_max) {
                    l_max = angle;
                    l_idx = i;
                }
            }
            else // 右側
            {
                float angle = to_target.angle(cand[i]);
                if (angle > r_max) {
                    r_max = angle;
                    r_idx = i;
                }
            }
        }
        if (l_idx == -1 && r_idx == -1) {
            return target;
        }

        if (l_idx == -1) {
            return p.pos();
        }

        if (r_idx == -1) {
            return p.pos();
        }

        // 目標方向の角度が小さい方を選択
        if (l_max > r_max) {
            return p.pos() + cand[r_idx];
        }
        else
        {
            return p.pos() + cand[l_idx];
        }
    }

    //------------------------------------------------------------------------------
    /// キャラクターの数ターン後の位置を求める
    /// 速度がなくなっても加速はしないことを仮定
    /// 流水は考慮しない
    ///
    ///
    Vec2 PosAfterMove(const Chara& chara, int turn)
    {
        // 現在のキャラクターの位置
        const Vec2 pos = chara.pos();

        // 速度
        Vec2 vel = chara.vel();

        if (turn <= 0) {
            return pos;
        }

        Vec2 x = vel; // 変位
        for (int t=1; t < turn; ++t) {
            float next_vel_length = vel.length() - 0.0625f;
            if (next_vel_length <= 0.0f) {
                break;
            }
            vel.normalize(next_vel_length);
            x += vel;
        }

        return pos + x;
    }

    //------------------------------------------------------------------------------
    /// キャラクターの数ターン後の位置を求める
    /// 速度がなくなったら加速することを仮定
    /// 流水は考慮しない
    ///
    Vec2 PosAfterMoveAccelIfPossible(const Chara& chara, const Vec2 target_pos, int turn)
    {
        // 現在のキャラクターの位置
        const Vec2 pos = chara.pos();

        // 速度
        Vec2 vel = chara.vel();

        if (turn <= 0) {
            return pos;
        }

        Vec2 x = vel; // 変位
        for (int t=1; t < turn; ++t) {
            float next_vel_length = vel.length() - 0.0625f;
            if (next_vel_length <= 0.0f) {
                next_vel_length = 0.875f;
                const Vec2 to_target = target_pos - pos;
                vel = to_target.getNormalized(next_vel_length);
            }
            vel.normalize(next_vel_length);
            x += vel;
        }

        return pos + x;
    }

    //------------------------------------------------------------------------------
    /// 数ターン以内に衝突するかどうか
    ///
    /// @param[in] p       プレイヤー
    ///            enemies 敵たち
    ///            turn    ぶつかるターン数
    /// @return turn後にプレイヤーが敵とぶつかる場合は @c true
    ///         そうでなければ @c false
    bool IsCollide(const Chara& p, const EnemyAccessor& enemies, const LotusCollection& lotuses, int turn = 1)
    {
        for (int i=0; i < enemies.count(); ++i) {

            // 現在衝突しているか
            if (Collision::IsHit(p.region(), enemies[i].region())) {
                return true;
            }

            // tターン後に衝突するか
            for (int t=1; t <= turn; ++t) {
                const Vec2 p_pos = PosAfterMove(p, t); // tターン後のプレイヤーの位置
                const Vec2 e_pos = PosAfterMoveAccelIfPossible(enemies[i], lotuses[enemies[i].targetLotusNo()].pos(), t); // tターン後の敵の位置

                // プレイヤーの半径と敵の半径の和の２乗
                const float square_radius =
                    (p.region().radius() + enemies[i].region().radius()) * (p.region().radius() + enemies[i].region().radius());

                if (p_pos.squareDist(e_pos) <= square_radius) {
                    return true;
                }
            }
        }
        return false;
    }

    //------------------------------------------------------------------------------
    /// 目標から離れているか
    bool IsFarAway(const Chara& p, const Vec2& target)
    {
        if (p.vel().isZero())
            return true;

        const Vec2 to_target = target - p.pos(); // 目標への方向ベクトル
        return to_target.dot(p.vel()) < 0;
    }

    //------------------------------------------------------------------------------
    /// 3ターン以内に目標の蓮に衝突するかどうか
    ///
    /// @param[in] p            プレイヤー
    ///            target_lotus 目標の蓮
    ///
    /// @return 3ターン以内に目標の蓮に衝突するなら @c true
    ///         そうでなければ @c false
    bool IsCollideLotus(const Chara& p, const Lotus& target_lotus)
    {
        // 次のターンに蓮に衝突する
        if (Collision::IsHit(target_lotus.region(), p.region(), p.pos() + p.vel())) {
            return true;
        }

        const Vec2 pos = p.pos() + p.vel(); // 1ターン後の位置
        const Vec2 vel = p.vel();
        // 速度が0.0635f以下なら次のターンで止まる
        if (vel.length() <= 0.0625f) {
            return false;
        }

        // 2ターン後の速度
        const Vec2 vel2 = vel.getNormalized(vel.length() - 0.0625f);

        // 2ターン後に蓮に衝突する
        if (Collision::IsHit(target_lotus.region(), p.region(), pos + vel2))
        {
            return true;
        }

        // 速度が0.0635f以下なら次のターンで止まる
        if (vel2.length() <= 0.0625f) {
            return false;
        }

        // 2ターン後の位置
        const Vec2 pos2 = pos + vel2;
        // 3ターン後の速度
        const Vec2 vel3 = vel2.getNormalized(vel2.length() - 0.0625f);
        if (Collision::IsHit(target_lotus.region(), p.region(), pos2 + vel3))
        {
            return true;
        }

        return false;
    }


    //------------------------------------------------------------------------------
    /// 各ステージ開始時に呼び出されます。
    ///
    /// この関数を実装することで、各ステージに対して初期処理を行うことができます。
    ///
    /// @param[in] aStageAccessor 現在のステージ。
    void Answer::Init(const StageAccessor& aStageAccessor)
    {
        target = 0;
        sFlow  = aStageAccessor.field().flowVel();
    }

    //------------------------------------------------------------------------------
    /// 各ターンでの動作を返します。
    ///
    /// @param[in] aStageAccessor 現在ステージの情報。
    ///
    /// @return これから行う動作を表す Action クラス。
    Action Answer::GetNextAction(const StageAccessor& aStageAccessor)
    {
        const Chara& player            = aStageAccessor.player();
        const EnemyAccessor& enemies   = aStageAccessor.enemies();
        const LotusCollection& lotuses = aStageAccessor.lotuses();
        const Field& field             = aStageAccessor.field();

        // 基準となる目標座標
        // 基本的にはこの座標を目指す
        const Vec2 target_pos = CalcTarget(player, lotuses, field);

        // プレイヤーから基準となる目標方向へのベクトル
        const Vec2 to_target = target_pos - player.pos();

        // 速度の目標方向への成分
        const Vec2 vel_to_target = GetVelOfTargetComponent(player, target_pos);


        // 加速回数が0のときは待つのみ
        if (player.accelCount() == 0) {
            return Action::Wait();
        }

        // プレイヤーはtargetに到着した
        if (target != player.targetLotusNo()) {
            target = player.targetLotusNo();    // targetの更新

            // 進行方向を変えなくてよさそうであれば、待つ
            if (to_target.dot(vel_to_target) > 0.0f && vel_to_target.length() >= 0.3f) {
                return Action::Wait();
            }
            if (IsCollide(player, enemies, lotuses, 5)) {
                return Action::Accel(PosAvoidCollision(player, enemies, target_pos));
            }
            return Action::Accel(target_pos);
        }

        // プレイヤーの速度が0であれば、加速
        if (vel_to_target.length() <= 0.001f) {
            if (IsCollide(player, enemies, lotuses)) {
                return Action::Accel(PosAvoidCollision(player, enemies, target_pos));
            }
            return Action::Accel(target_pos);
        }

        // 目標から遠ざかっている
        if (IsFarAway(player, target_pos)) {
            if (IsCollide(player, enemies, lotuses, 5)) {
                return Action::Accel(PosAvoidCollision(player, enemies, target_pos));
            }
            return Action::Accel(target_pos);
        }

        // ラストスパートをかける
        // 最終周かつあと蓮があと一つ
        if (player.roundCount() == 2 && player.targetLotusNo() == lotuses.count()-1) {
            if (player.vel().length() <= 0.8f) {
                return Action::Accel(target_pos);
            }
        }

        if (player.accelCount() <= 2 && player.vel().length() > 0.07f) {
            return Action::Wait();
        }

        // 目標方向への速度成分
        if (vel_to_target.length() < 0.2f) {

            // あと3ターン待てば蓮に到達するのであれば待つ
            if (IsCollideLotus(player, lotuses[player.targetLotusNo()])) {
                return Action::Wait();
            }
            if (IsCollide(player, enemies, lotuses, 5)) {
                return Action::Accel(PosAvoidCollision(player, enemies, target_pos));
            }
            return Action::Accel(target_pos);
        }
        return Action::Wait();
    }
}

//------------------------------------------------------------------------------
// EOF