nyama++さんのプログラムソース

/*
	ハル研究所プログラミングコンテスト2009応募作品
	Author: nyama++

	【はじめに】
		今回はあまり時間がなくスコアを上げるのに必死だったので、ところどころにバグがあるのを放置していたり、
		使ってない変数が残っていたり、無駄な処理が多かったり、マジックナンバーがたくさんあったり、
		コードが汚かったりします。ごめんなさい。

	【アルゴリズムの概要】
		今回考えたアルゴリズムは大きくわけで2つの処理にわかれます。
			1. チェックポイントを作成
			2. チェックポイントを通過しながらゴールへ向かうアクションの作成

		チェックポイントの作成では、まずスタート地点、ゴール、穴の四隅などに頂点を取り、各頂点を直線で結び
		その中から穴と交差する直線を除きます。すると、グラフ構造ができるので、頂点間の距離をコストとして
		ダイクストラ法でこれを解きます。このとき求められた解の頂点がチェックポイントになります。

		次にそのチェックポイントを通過しながらゴールへ向かうアクションを作成します。単純なアルゴリズムでは
		現在位置と次のチェックポイントを結ぶ直線上を加速しながら進み、その直線の端で停止できるように速度を
		落として、端で停止したら次のチェックポイントまで同じように進む、というのを繰り返すことでゴールできます。
		この単純なアルゴリズムだけでも96万点ほど取れますが、曲がるたびに停止しているのでランキング上位に
		入るには効率が悪すぎます。

		そこで、チェックポイントごとに停止しなくても済むように、どの方向にどれだけ加速すればいいのかを推測する
		関数を導入します。ただし、これは単なる推測でしかないためこの推測に従うと穴に落ちてしまうこともありえます。
		そのため、推測に従って穴に落ちた場合やなかなかゴールできない場合は、1つ前に戻って推測された方向をちょっと
		修正(45°回転させたり、90°回転させる)して、その方向に進みます。修正したものを試しても解決しない場合には
		ブレーキをかけます。つまり、推測されたベクトル + その修正版×4方向 + ブレーキ の6つのアクションを
		選択しながら探索をします。

		どの方向にどれだけ加速すればいいのかを推測する関数は、次のチェックポイントがゴールか否かで処理を分けます。
		次がゴールの場合は単純で、ゴールのある方向へ進むようにするだけです。現在ボールの進んでいる方向がゴールとは
		全然違う方向であればブレーキをかけつつ、進む方向をゴールの方向へ修正します。
		次のチェックポイントがゴールでなければ、以下の4つから行動を選択します。
			[1]. 次の次のチェックポイント方向に曲がる
			[2]. まだ曲がり始めるには早く、曲がるために逆方向へ移動しておく必要もないので、次のチェックポイント方向へ直進
			[3]. このまま直進すると曲がりきれなくなるので、次の次のチェックポイント方向とは逆に移動しておく
			[4]. このままだと曲がりきれそうにないので、少しブレーキをかけつつ次の次のチェックポイント方向に曲がる
		以下のアスキーアートで説明すると、現在の位置○から次のチェックポイント�，鯆未蝓⊆，亮，離船Д奪�ポイント�△�
		進む場合、→に曲がって穴に落ちなければ曲がる(行動[1])、ただし↑への速度が大きいと間がりきれないのでブレーキを
		かける(行動[4])か、少し←に曲がっておきます(行動[3])。→に曲がると穴に落ちてしまう場合は、一旦←に曲がって
		スムーズに�△諒�へ曲がれるように準備する(行動[3])か、�（�向へ直進して穴に落ちずに曲がれるようになるのを
		待ちます(行動[2])。

			   ��            ��
			    ■■■■■■■
			    ■■■■■■■
			    ■■■■■■■
			    ■■■■■■■
			    ■■■穴■■■
			○  ■■■■■■■
			    ■■■■■■■
			    ■■■■■■■

		以上が今回実装したアルゴリズムの概要です。
	
	【その他、細かいポイント】
		【1. ジャンプを考慮したチェックポイントリストも作る】
			頂点を結ぶ直線と穴の矩形の交差している長さがMAX_VEL(4.0f)以下ならばジャンプできる可能性があるので
			確実にジャンプできると仮定したチェックポイントリストも作ります。あとは上で説明したのと同様に処理を
			すれば探索をする部分がうまく働いて穴に落ちないように進んでくれます。
			ただし、ジャンプ可能かどうかの判定時にボールの速度を考慮していないため、速度が足りずどうしても
			ジャンプができないことがあります。その場合でも穴を迂回してなんとかゴールに向かってくれますが、
			無駄な動きが多くなってしまいます。そのため、ジャンプありのチェックポイントリストと、ジャンプなしの
			チェックポイントリストの2つを作り、両方試して良い結果を出した方のチェックポイントリストを採用します。
		
		【2. ダイクストラでチェックポイントリストを作成する際に、曲がるコストも考える】
			ダイクストラで求めるルートは直線距離では最短でもS字カーブのようなルートを含んでいると結果的に遅くなって
			しまうことがあります。そこで、チェックポイントを結ぶエッジの接続角度を考慮してコストを計算してやると
			単純に最短なルートを選ぶのではなく、速度を落とさずに曲がりやすくそれなりに短いルートを選択してくれるように
			なります。
		
		【3. ゴール付近ではゴールの四隅と中心に頂点を取る】
			スコアには僅かな影響しかありませんが、少しスコアが上がるのでチェックポイントリストを作成する際に
			ゴールの四隅と中心の合計5箇所に頂点を取ります。

		【4. 穴と穴の交点付近にも頂点を取る】
			穴と穴の交点付近にも頂点を取ることで、交差している部分を斜めにジャンプできるルートを発見できることが
			あります。以下のアスキーアートでは�，�ら�△悗離献礇鵐廚砲覆蠅泙后�

			■■■■■■■
			■■■穴■■■��
			■■■■■■■■■■■■■
			■■■■■■■■■■■■■
			　　　　　�、�■■穴■■■
			　　　　　　■■■■■■■

		【5. ゴールを見つけてもより良い解がないか探す】
			少しでもよい解を見つけるために、解を1つ見つけたらその解に必要なターン数を上限として探索を続けます。
			調べた状態の数が一定数に達した時点で探索を終了し、それまでに見つけた最良の解を採用します。

		【6. 探索時にこれ以上探索しても無駄だとわかった場合やゴールした場合に、数ターン前に戻る】
			普通、バックトラック法などの探索では一つ前の状態に戻り探索をやり直します。
			しかし、この問題では1つ前に戻ったところで1ターン後に到達する位置は大きく変化せず、同じ位置に到達する
			ルートは1つではありません。そこで、状態を戻すときに1ターン前ではなく一気に数ターン前の状態にまで
			戻すという大雑把な探索をします。これにより探索結果の質をあまり落とすことなく、計算量を大きく削減する
			ことができます。
			このとき、何ターン前にまで戻すかというのは、ゴールに到達した回数によって増やしています。(つまり、
			ゴールに到達した回数が多いほど大雑把な探索をするようになります。)

		【7. チェックポイントのスキップ】
			チェックポイントは穴があって邪魔なときに迂回するルートを通るために用意したものなので、もし次の次の
			チェックポイントと現在のボールの位置の間に穴がなければ、もう次のチェックポイントを無視して、次の次の
			チェックポイントを目指すようにします。これにより、通らなくてもよくなったチェックポイントをわざわざ
			通過するような無駄が減ります。

		【8. 次のチェックポイントと現在のボールの位置の間にジャンプできないほどの穴があれば前の状態に戻る】
			チェックポイントの間には本来ジャンプできないほどの穴が存在することはありませんが、速度を落とさ
			ないように曲がろうとしていると変な場所に入り込んでしまい、チェックポイントと現在のボールの位置の間に
			ジャンプできない穴が存在することがあります。これを迂回しようと探索していると非常に計算コストがかかるため
			チェックポイントと現在のボールの位置の間にジャンプできない穴があった場合、そこで諦めて数ターン前の状態まで
			戻してしまいます。


*/
#include "common.hpp"
#include "answer.hpp"


//**********************************************************************************************//
//*     定数定義や簡易関数定義、グローバル変数定義など
//**********************************************************************************************//

// デバッグ用のincludeや関数定義
#ifdef DEBUG
#	include <algorithm>
#	include <limits>

bool fIsValid(const float aValue) {
	if (-std::numeric_limits<float>::max() <= aValue &&
	  aValue <= std::numeric_limits<float>::max()) {
		return true;
	} else {
		return false;
	}
}

#endif

// デバッグ用の画像のためのデータを出力するマクロ
#ifndef IMG_DATA_PRINT
#	define IMG_DATA_PRINT(...)
#endif

// タイムアウト時にエラーにさせたい場合には、このdefineを有効にする。
#define TIMEOUT_IS_ERROR

// グローバル変数
static unsigned int gameIndex_ = 0;
static unsigned int turnIndex_ = 0;

// 定数定義
#define LOOP_LIMIT 10000				// 探索の制限
#define FLOAT_MAX (1.0f/0.0000000001f)	// floatの最大値【とりあえず、大きいだけの数値で応急処置】
#define DELTA (0.01f)					// 近傍の位置を取得するための小さな値
#define MAX_NODE_COUNT  (((MAX_HOLE_COUNT * 4) + 5) * 3 )	// ダイクストラで扱うノードの最大数

// デバッグ用の画像で線を描画するのに使う色(IMG_DATA_PRINTマクロの引数で使う)
#define DEBUG_LINE_COLOR1 "44aa0000"
#define DEBUG_LINE_COLOR2 "3333ffff"
#define DEBUG_LINE_COLOR3 "0033ff55"
#define DEBUG_LINE_COLOR4 "3333ff55"

// 探索で扱うアクションの選択肢
enum ACCEL_DIRECTION{
	ACCEL_FORWARD,
	ACCEL_RIGHT45,
	ACCEL_LEFT45,
	ACCEL_RIGHT,
	ACCEL_LEFT,
	ACCEL_BRAKE,	// ブレーキ
	ACCEL_DIRECTION_MAX,
};

// ACCEL_DIRECTIONのベクトル表現（プログラムの初期化時にnormalizeされる）
static Vector2 ACCEL_VECTOR[ACCEL_DIRECTION_MAX-1] = {
	Vector2(1,  0), // ACCEL_FORWARD
	Vector2(1,  1), // ACCEL_RIGHT45
	Vector2(1, -1), // ACCEL_LEFT45
	Vector2(0,  1), // ACCEL_RIGHT
	Vector2(0, -1), // ACCEL_LEFT
	// ACCEL_BRAKE
};

// 角の種類
Rect::CornerKind CORNER_KINDS[] = {
	Rect::CornerKind_LeftUp,
	Rect::CornerKind_LeftDown,
	Rect::CornerKind_RightUp,
	Rect::CornerKind_RightDown
};

// 8方向を表す定数
enum Direction8{
	Direction8_Up,
	Direction8_RightUp,
	Direction8_Right,
	Direction8_RightDown,
	Direction8_Down,
	Direction8_LeftDown,
	Direction8_Left,
	Direction8_LeftUp,
	Direction8_MAX
};

// 8方向を表すベクトル
static Vector2 DIRECTION8_VECTOR[Direction8_MAX] = {
	Vector2( 0, -1), // Direction8_Up,
	Vector2( 1, -1), // Direction8_RightUp,
	Vector2( 1,  0), // Direction8_Right,
	Vector2( 1,  1), // Direction8_RightDown,
	Vector2( 0,  1), // Direction8_Down,
	Vector2(-1,  1), // Direction8_LeftDown,
	Vector2(-1,  0), // Direction8_Left,
	Vector2(-1, -1)  // Direction8_LeftUp,
};

// 4方向を表す定数
enum Direction4{
	Direction4_Up,
	Direction4_Right,
	Direction4_Down,
	Direction4_Left,
	Direction4_MAX
};

// 4方向を表すベクトル
static Vector2 DIRECTION4_VECTOR[Direction4_MAX] = {
	Vector2( 0, -1), // Direction8_Up,
	Vector2( 1,  0), // Direction8_Right,
	Vector2( 0,  1), // Direction8_Down,
	Vector2(-1,  0), // Direction8_Left,
};

// 簡易関数定義
#define ABS(a)   ((a < 0)? -(a): (a))
#define MAX(a, b)   ((a < b)? b: a)
#define MIN(a, b)   ((a < b)? a: b)

// floatの比較関数
bool Equal(float a, float b, float tolerance = 0.01){
	float d = ABS(a - b);
	return d < tolerance;
}

template <typename TYPE>
void swap(TYPE &a, TYPE &b){
	TYPE t = a;
	a = b;
	b = t;
}

// valueがleftとrightの間にある値かどうか判定する関数
bool Between(float left, float value, float right, bool border = true){
	if(left > right){
		swap(left, right);
	}
	if(border){
		return left <= value && value <= right;
	}
	else{
		return left < value && value < right;
	}
}

//**********************************************************************************************//
//*     ベクトル演算系の関数
//**********************************************************************************************//

//=============================================================================================//
//     ベクトルの方向が同じかどうか判定
//=============================================================================================//
bool EqualDirection(Vector2 a, Vector2 b){
	if(Equal(a.getLength(), 0.0f)){
		return Equal(b.getLength(), 0.0f);
	}
	else if(Equal(b.getLength(), 0.0f)){
		return false;
	}
	a.normalize();
	b.normalize();
	return Equal(a.x, b.x) && Equal(a.y, b.y);
}

//=============================================================================================//
//     二つのベクトルのなす角(cosθ)を求める
//=============================================================================================//
float Cos(const Vector2 &v1, const Vector2 &v2){
	HAL_ASSERT(v1.getLength() * v2.getLength() > 0);
	return v1.getDotProduct(v2) / (v1.getLength() * v2.getLength());
}

//=============================================================================================//
//     Vector2をDirection8に変換
//=============================================================================================//
Direction8 VectorToDirection8(const Vector2 &v){
	// vと一番近いDirection8のベクトルを見つけてそれを採用
	Direction8 best;
	float best_score = -1;
	for(int i=0; i<Direction8_MAX; ++i){
		float score = v.getDotProduct(DIRECTION8_VECTOR[i]) / (v.getLength() * DIRECTION8_VECTOR[i].getLength());
		if(score > best_score){
			best_score = score;
			best = (Direction8)i;
		}
	}

	return best;
}

//=============================================================================================//
//     Vector2をDirection4に変換
//=============================================================================================//
Direction4 VectorToDirection4(const Vector2 &v){
	// vと一番近いDirection4のベクトルを見つけてそれを採用
	Direction4 best;
	float best_score = -1;
	for(int i=0; i<Direction4_MAX; ++i){
		float score = v.getDotProduct(DIRECTION4_VECTOR[i]) / (v.getLength() * DIRECTION4_VECTOR[i].getLength());
		if(score > best_score){
			best_score = score;
			best = (Direction4)i;
		}
	}

	return best;
}

//=============================================================================================//
//     baseから見てvが右にあるかどうか判定
//=============================================================================================//
bool isRight(Vector2 base, Vector2 v){
	base.normalize();
	float sin = base.y, cos = base.x;
	v = Vector2(v.x * cos + v.y * sin, -v.x * sin + v.y * cos);
	return v.y > 0;
}

// std::pairの代替【作ったけど使ってない。消し忘れ。】
template<class C1, class C2>
struct pair{
	C1 first;
	C2 second;

	pair(){}
	pair(const C1 &first, const C2 &second): first(first), second(second){}
};

//**********************************************************************************************//
//*     直線や矩形の交差判定や交点を求める関数など
//**********************************************************************************************//

//=============================================================================================//
//     線分の交点を取得
//=============================================================================================//
bool CrossPoint(const Vector2 &s1, const Vector2 &e1, const Vector2 &s2, const Vector2 &e2, Vector2 *c, bool border = true){
	// 【もっとちゃんとした求め方があると思うけど、とりあえずこれで応急処置】
	Vector2 d1 = e1 - s1,
			d2 = e2 - s2;
	if(d1.y == 0 && d2.y != 0 && d1.x != 0 && d2.x == 0){
		// 直線(e1 - s1)が水平、直線(e2 - s2)が垂直な場合
		(*c).x = s2.x;
		(*c).y = s1.y;
		return Between(s1.x, (*c).x, e1.x, border) && Between(s2.y, (*c).y, e2.y, border);
	}
	else if(d1.y != 0 && d2.y == 0 && d1.x == 0 && d2.x != 0){
		// 直線(e1 - s1)が垂直、直線(e2 - s2)が水平な場合
		(*c).x = s1.x;
		(*c).y = s2.y;
		return Between(s1.y, (*c).y, e1.y, border) && Between(s2.x, (*c).x, e2.x, border);
	}
	else if(d1.y * d2.x == d2.y * d1.x){// 傾きが同じ
		return false;	// 並行
	}
	else{
		// 直線1の式： y = (d1.y / d1.x) * x + a1
		float a1 = s1.y - (d1.y / d1.x) * s1.x,
			  a2 = s2.y - (d2.y / d2.x) * s2.x;

		if(d1.x == 0){
			// 直線(e1 - s1)が垂直
			(*c).x = s1.x;
			(*c).y = (d2.y / d2.x) * (*c).x + a2;
		}
		else if(d2.x == 0){
			// 直線(e2 - s2)が垂直
			(*c).x = s2.x;
			(*c).y = (d1.y / d1.x) * (*c).x + a1;
		}
		else{
			// 交点の式： (d1.y / d1.x) * x + a1 = (d2.y / d2.x) * x + a2
			//         ： x = (a2 - a1) / ((d1.y / d1.x) - (d2.y / d2.x))
			(*c).x = (a2 - a1) / ((d1.y / d1.x) - (d2.y / d2.x));
			(*c).y = (d1.y / d1.x) * (*c).x + a1;
		}
		// 線分の範囲内かどうか判定
		return ((Equal(s1.x, e1.x) && Equal(s1.x, (*c).x)) || Between(s1.x, (*c).x, e1.x, border)) &&
			   ((Equal(s1.y, e1.y) && Equal(s1.y, (*c).y)) || Between(s1.y, (*c).y, e1.y, border)) &&
			   ((Equal(s2.x, e2.x) && Equal(s2.x, (*c).x)) || Between(s2.x, (*c).x, e2.x, border)) &&
			   ((Equal(s2.y, e2.y) && Equal(s2.y, (*c).y)) || Between(s2.y, (*c).y, e2.y, border));
	}
}

//=============================================================================================//
//     直線と矩形の交わる長さを取得
//=============================================================================================//
bool CrossLength(const Vector2 &start, const Vector2 &end, const Rect &rect, float *length){
	// 【境界で交わるとバグが出そうだけど、とりあえず放置】
	// 【矩形の中に直線が入った場合に交差したと判定されない】
	// rectの4直線と直線(end- start)の交点を求める
	Vector2 cross[2];
	int cross_count = 0;
	int size = sizeof(CORNER_KINDS)/sizeof(Rect::CornerKind);
	for(int k=0; k<size; ++k){
		if(CrossPoint(start, end, rect.getCornerPos((Rect::CornerKind)k), rect.getCornerPos((Rect::CornerKind)((k+1) % size)), &cross[cross_count])){
			++cross_count;
			if(cross_count == 2){
				break;
			}
		}
	}
	// 2箇所の交点があればその交点を結ぶ直線の長さが、直線と矩形の交わる長さ
	if(cross_count == 2){
		(*length) = (cross[0] - cross[1]).getLength();
		return true;
	}
	return false;
}

//=============================================================================================//
//     矩形同士の交点を求める
//=============================================================================================//
bool CrossPoint(const Rect &r1, const Rect &r2, Vector2 points[4], int *point_count){
	// 2つの矩形の4つの直線の全ての組で交差判定を行う
	int corner_kind_count = Rect::CornerKind_End_ - Rect::CornerKind_Begin_;
	(*point_count) = 0;
	Vector2 pos;
	for(int i=0; i<corner_kind_count; ++i){
		for(int j=0; j<corner_kind_count; ++j){
			if(CrossPoint(
				r1.getCornerPos((Rect::CornerKind)i), r1.getCornerPos((Rect::CornerKind)((i+1)%corner_kind_count)),
				r2.getCornerPos((Rect::CornerKind)j), r2.getCornerPos((Rect::CornerKind)((j+1)%corner_kind_count)),
				&pos, false
				)){
					points[(*point_count)++] = pos;
			}
		}
	}
	HAL_ASSERT((*point_count) <= 4);
	return (*point_count) != 0;
}

//=============================================================================================//
//     直線が穴と交わるか判定(ただし、jump == trueのときジャンプ可能なものは無視)
//=============================================================================================//
bool isCrossHole(const Field& aField, const Vector2 &a, const Vector2 &b, const bool jump = true, const float limit = MAX_VEL){
	// 【2つ以上の穴が関係する特殊なケースでバグがでるけど、とりあえず放置】
	float length;
	for(int i=0; i<aField.getHoleCount(); ++i){
		if(aField.getHole(i).isIntersectWithLineSegment(a, b)){
			// jumpフラグがtrueのときは、ジャンプ可能なら交差していないと判定する
			if(jump && CrossLength(a, b, aField.getHole(i), &length)){
				if(length < limit){
					continue;	// ジャンプ可能(ボールの速度などは考慮していないのでジャンプできないこともある)
				}
			}
			return true;
		}
	}
	return false;
}

//**********************************************************************************************//
//*     生成したルートに沿って走るアクションの作成
//**********************************************************************************************//

//=============================================================================================//
//     現在のstatusからtargetベクトルの方向に速度を変更するのに必要な距離を求める
//=============================================================================================//
Vector2 GetChangeVector(Status status, const Vector2 &target){
	if(Equal(status.getBallVel().getLength(), 0.0f)){
		return Vector2(0.0f, 0.0f);
	}

	Vector2 start = status.getBallPos();
	// status.getBallVel() と target の関係が、右→左 or 左→右 に変化するまで移動させてみる
	if(isRight(status.getBallVel(), target)){
		do{
			status.update(Action(Vector2(-status.getBallVel().y, status.getBallVel().x)));
		}while(isRight(status.getBallVel(), target));	// 【正確には右→左になるまでではなく一致するまでだけど、とりあえずこれで応急処置】
	}
	else{
		do{
			status.update(Action(Vector2(status.getBallVel().y, -status.getBallVel().x)));
		}while(!isRight(status.getBallVel(), target));
	}

	return status.getBallPos() - start;
}

//=============================================================================================//
//     座標から角の種類(右下、左上など)を特定
//=============================================================================================//
Rect::CornerKind GetCornerType(const Field& aField, const Vector2 &v1, const Vector2 &v2){
	Rect::CornerKind kind = Rect::CornerKind_End_;
	bool right = isRight(v1, v2);
	Direction4 d;
	switch(VectorToDirection8(v1)){
		// 上下左右はそのまま4方向の上下左右へ変換
		case Direction8_Up:			d = Direction4_Up;		break;
		case Direction8_Right:		d = Direction4_Right;	break;
		case Direction8_Down:		d = Direction4_Down;	break;
		case Direction8_Left:		d = Direction4_Left;	break;
		// 斜めの方向だった場合、v2の値から判断
		case Direction8_RightUp:
			switch(VectorToDirection8(v2)){
				case Direction8_Up:		d = Direction4_Right; break;
				case Direction4_Right:	d = Direction4_Up; break;
				default:  d = (right)? Direction4_Up: Direction4_Right; break;
			}
			break;
		case Direction8_RightDown:
			switch(VectorToDirection8(v2)){
				case Direction8_Down:	d = Direction4_Right; break;
				case Direction4_Right:	d = Direction4_Down; break;
				default:  d = (right)? Direction4_Right: Direction4_Down; break;
			}
			break;
		case Direction8_LeftDown:
			switch(VectorToDirection8(v2)){
				case Direction8_Down:	d = Direction4_Left; break;
				case Direction4_Left:	d = Direction4_Down; break;
				default:  d = (right)? Direction4_Down: Direction4_Left; break;
			}
			break;
		case Direction8_LeftUp:
			switch(VectorToDirection8(v2)){
				case Direction4_Up:		d = Direction4_Left; break;
				case Direction4_Left:	d = Direction4_Up; break;
				default:  d = (right)? Direction4_Left: Direction4_Up; break;
			}
			break;
	}
	// 移動方向dから角の種類kindへ変換
	switch(d){
		case Direction4_Down:	kind = (right)? Rect::CornerKind_RightDown:	Rect::CornerKind_LeftDown;	break;
		case Direction4_Up:		kind = (right)? Rect::CornerKind_LeftUp:	Rect::CornerKind_RightUp;	break;
		case Direction4_Left:	kind = (right)? Rect::CornerKind_LeftDown:	Rect::CornerKind_LeftUp;	break;
		case Direction4_Right:	kind = (right)? Rect::CornerKind_RightUp:	Rect::CornerKind_RightDown;	break;
	}
	return kind;
}

//=============================================================================================//
//     穴に落ちるかどうか判定（ただし、フィールド全体に収まっているかどうかは気にしない）
//=============================================================================================//
bool isInHole2(const Field &aField, const Vector2& aBallPos, const Vector2 &target, const Vector2 &corner_pos, const bool left) {
    // 全ての穴のチェック
	for (int idx = 0; idx < aField.getHoleCount(); ++idx) {
        const Rect& rect = aField.getHole(idx);
		if (rect.isInWithBorder(aBallPos)){
			Vector2 v = rect.getCenterPos() - corner_pos;
			bool f = isRight(target, v);
			if((f && !left) || (!f && left)){
				return true;
			}
		}
    }
    return false;
}

//=============================================================================================//
//     next_target方向に曲がっていいかチェックする
//=============================================================================================//
float CurveCheck(const Field &aField, Status status, const Vector2 &target, const Vector2 &corner_pos, const bool left){
	if(Equal(status.getBallVel().getLength(), 0.0f)){
		return true;
	}

	float all_length = 0.0f,	// 【未使用】
		  hole_length = 0.0f,	// このまま曲がったときにどれだけ穴の上を走ることになるのかというだいたいの距離
		  length;
	Vector2 old_pos;
	// status.getBallVel() と target の関係が、右→左 or 左→右 に変化するまで移動させる
	if(isRight(status.getBallVel(), target)){
		do{
			old_pos = status.getBallPos();
			status.update(Action(Vector2(-status.getBallVel().y, status.getBallVel().x)));
			length = (status.getBallPos() - old_pos).getLength();
			all_length += length;	// 【未使用】
			// 穴の中→穴の中への移動をしているときhole_lengthに移動距離を加算
			if(isInHole2(aField, old_pos, target, corner_pos, left) && isInHole2(aField, status.getBallPos(), target, corner_pos, left)){
				hole_length += length;
			}
			// 【デバッグ用出力】
			IMG_DATA_PRINT("%f %f %f %f %s\n", old_pos.x, old_pos.y, status.getBallPos().x, status.getBallPos().y, DEBUG_LINE_COLOR4);
		}while(isRight(status.getBallVel(), target));	// 【正確には右→左になるまでではなく一致するまでだけど、とりあえずこれで応急処置】
	}
	else{
		do{
			old_pos = status.getBallPos();
			status.update(Action(Vector2(status.getBallVel().y, -status.getBallVel().x)));
			length = (status.getBallPos() - old_pos).getLength();
			all_length += length;	// 【未使用】
			// 穴の中→穴の中への移動をしているときhole_lengthに移動距離を加算
			if(isInHole2(aField, old_pos, target, corner_pos, left) && isInHole2(aField, status.getBallPos(), target, corner_pos, left)){
				hole_length += length;
			}
			// 【デバッグ用出力】
			IMG_DATA_PRINT("%f %f %f %f %s\n", old_pos.x, old_pos.y, status.getBallPos().x, status.getBallPos().y, DEBUG_LINE_COLOR4);
		}while(!isRight(status.getBallVel(), target));
	}

	return hole_length;
}

//=============================================================================================//
//     IDをVector2に変換する(GetEstimatedBestActionVector関数でのみ使用)
//=============================================================================================//
Vector2 FToVector(
	const Field &aField, int f, const Status &status, const bool left,
	Vector2 target, const Vector2 &next_target, const Vector2 &v, Rect::CornerKind corner_kind, float curve_angle,
	const Vector2 &corner_pos
){
	Vector2 result;
	f = (f + 4*100) % 4;	// fを0〜3の範囲に収める【f<-400だとおかしくなるけどそんなことはたぶんないので、とりあえずこれで応急処置】
	if(f == 0){
		// CurveCheckの結果次第でfを修正
		float hole_length = CurveCheck(aField, status, next_target, corner_pos, left);
		if(Equal(hole_length, 0.0f)){
			f = f;
		}
		else if(hole_length < status.getBallVel().getLength() * 2){
			f = 3;
		}
		else{
			f = 2;
		}
	}
	else if(f == 3){
		// CurveCheckの結果次第でfを修正
		float hole_length = CurveCheck(aField, status, next_target, corner_pos, left);
		if(Equal(hole_length, 0.0f)){
			f = f;
		}
		else if(hole_length < status.getBallVel().getLength() * 2){
			f = 3;
		}
		else{
			f = 2;
		}
	}
	switch(f){
		case 0:
			// next_target方向へ曲がる
			result = (!left)? Vector2(-status.getBallVel().y, status.getBallVel().x): Vector2(status.getBallVel().y, -status.getBallVel().x);
			break;
		case 2:
			// next_target方向とは逆方向へ
			result = (left)? Vector2(-status.getBallVel().y, status.getBallVel().x): Vector2(status.getBallVel().y, -status.getBallVel().x);
			{
				// vが長いほどtarget方向へベクトルを修正する
				float rate = 0.0f;
				for(int i=10; i!=1; --i){
					if(v.getLength() > MAX_VEL * i){
						rate = 0.25f * (i-1);
						break;
					}
				}
				if(!Equal(result.getLength(), 0.0f)){
					result.normalize();
					result += target.normalize() * rate;
				}
			}
			// curve_angleが大きいときにもtarget方向へベクトルを修正する
			if(curve_angle > 0.0f){
				if(Equal(result.getLength(), 0.0f)){
					result = target;
				}
				else{
					float a = curve_angle;
					result = result.normalize() + target.normalize() * (6.0f * a * a * a * a);
				}
			}
			break;
		case 1:
			//*
			// 直進
			switch(corner_kind){
				case Rect::CornerKind_RightUp:		result = (left)? Vector2( 0, -1): Vector2( 1,  0); break;
				case Rect::CornerKind_RightDown:	result = (left)? Vector2( 1,  0): Vector2( 0,  1); break;
				case Rect::CornerKind_LeftDown:		result = (left)? Vector2( 0,  1): Vector2(-1,  0); break;
				case Rect::CornerKind_LeftUp:		result = (left)? Vector2(-1,  0): Vector2( 0, -1); break;
			}
			// 若干、target方向へベクトルを修正する
			result = result.normalize() * 3 + target.normalize();
			/*/
			// target方向へ真っ直ぐ + next_target方向とは逆方向へ
			result = target * 3.0f + ((left)? Vector2(-status.getBallVel().y, status.getBallVel().x): Vector2(status.getBallVel().y, -status.getBallVel().x));
			//*/
			break;
		case 3:
			// next_target方向へ曲がる + 減速 * 1.5
			result = (!left)? Vector2(-status.getBallVel().y, status.getBallVel().x): Vector2(status.getBallVel().y, -status.getBallVel().x);
			if(!Equal(result.getLength(), 0.0f)){
				result = result.normalize() * 1.5f + Vector2(-status.getBallVel().x, -status.getBallVel().y).normalize();
			}
			else{
				result = Vector2(-status.getBallVel().x, -status.getBallVel().y);
			}
			break;
	}
	return result;
}

//=============================================================================================//
//     次にすると良さそうな行動を推測
//=============================================================================================//
Vector2 GetEstimatedBestActionVector(
	const Field& aField,
	const int target_point_id,
	const Vector2 check_points[MAX_NODE_COUNT],
	const int check_point_count,
	const Status &status
){
	Vector2 result;
	if(target_point_id == check_point_count-1){// 次がゴールならば
		// velをgoalに近づける
		Vector2 vel = status.getBallVel(),
				goal = check_points[target_point_id] - status.getBallPos();
		if(Equal(vel.getLength(), 0.0f) || vel.getDotProduct(goal) / (vel.getLength()*goal.getLength()) >= 0.985f){
			result = goal;
		}
		else{
			// velから見てgoalは左右どちらにあるのか？
			if(!isRight(vel, goal)){ // 左
				result = Vector2(vel.y, -vel.x).changeLength(MAX_ACCEL);
				Vector2 new_vel = (vel + result);
				new_vel.changeLength(MAX_VEL);
				// 曲りすぎな場合に修正
				if(isRight(new_vel, goal)){
					goal.changeLength(MAX_VEL);
					result = goal - vel;
				}
			}
			else{ // 右
				result = Vector2(-vel.y, vel.x).changeLength(MAX_ACCEL);
				Vector2 new_vel = (vel + result);
				new_vel.changeLength(MAX_VEL);
				// 曲りすぎな場合に修正
				if(!isRight(new_vel, goal)){
					goal.changeLength(MAX_VEL);
					result = goal - vel;
				}
			}

			// goalと関係ない方向への勢いが強ければそれを打ち消す方向にベクトルを修正(= ちょっとブレーキをかける)
			result.normalize();
			float cos = Cos(vel, goal);
			float rate = 0.0f;
			for(int i=0; i<9; ++i){
				if(cos < -1.0f + i * 0.21f){
					rate = 2.9f - i * 0.3f;
					break;
				}
			}
			result = Vector2(-vel.x, -vel.y).normalize() * rate + result;
		}
		result.changeLength(MAX_ACCEL);
	}
	else{// 次のチェックポイントがゴールでない場合
		Vector2 target = check_points[target_point_id] - status.getBallPos(),
				next_target = check_points[target_point_id+1] - check_points[target_point_id];
		Vector2 change_vector = GetChangeVector(status, next_target);	// next_target方向に移動方向を修正するのに必要な移動距離を求める
		float curve_angle = Cos(target, next_target);

		// 【デバッグ用出力】
		Vector2 p = status.getBallPos() + change_vector;
		IMG_DATA_PRINT("%f %f %f %f %s\n", status.getBallPos().x, status.getBallPos().y, p.x, p.y, DEBUG_LINE_COLOR3);

		// change_vectorや次のチェックポイント、角の種類などの位置関係から次の行動の方針を決める
		Vector2 start = check_points[target_point_id],
				end = status.getBallPos() + change_vector,
				v = end - start;
		bool left = !isRight(target, next_target);
		int f1 = -1;
		
		if(v.x > 0){
			if(v.y < 0){
				f1 = 0;
			}
			else{
				f1 = 3;
			}
		}
		else{
			if(v.y < 0){
				f1 = 1;
			}
			else{
				f1 = 2;
			}
		}
		
		Rect::CornerKind corner_kind = GetCornerType(aField, target, next_target);
		switch(corner_kind){
			case Rect::CornerKind_RightUp:		f1 = (!left)? f1+0: 3-(f1+3); break;
			case Rect::CornerKind_RightDown:	f1 = (!left)? f1+1: 3-(f1+0); break;
			case Rect::CornerKind_LeftDown:		f1 = (!left)? f1+2: 3-(f1+1); break;
			case Rect::CornerKind_LeftUp:		f1 = (!left)? f1+3: 3-(f1+2); break;
		}

		result = FToVector(aField, f1, status, left, target, next_target, v, corner_kind, curve_angle, check_points[target_point_id]);
		
		if(Equal(result.getLength(), 0.0f)){
			result = target;
		}
		else if(status.getBallVel().getLength() < MAX_VEL){
			// 速度が十分でなければ、目的の方向(target)へベクトルを向ける
			float rate = 0.1f;
			float length = status.getBallVel().getLength();
			for(int i=1, limit=6; i<limit; ++i){
				if(length < MAX_VEL * ((i < 4)? (1.0f / (5.0f-i)): ((i-2.0f)/(i-1.0f)))){
					rate = (limit - i) * 0.5f;
					break;
				}
			}
			result = result.normalize() + target.normalize() * rate;
		}
		// vが短ければnext_target方向に曲がるベクトルを加える
		/*if(v.getLength() < status.getBallVel().getLength()){
			result = result.normalize() + FToVector(0, status, left, target, v, corner_kind, curve_angle).normalize() * (4.5f * (status.getBallVel().getLength()/MAX_VEL) * (v.getLength() / status.getBallVel().getLength()));
		}*/
		result.changeLength(MAX_ACCEL);
	}

	return result;
}

//=============================================================================================//
//     アクションの作成
//=============================================================================================//
// 【いつも再帰関数で実装すると遅いのでループで実装したが、本当に遅いかどうかは未検証】
struct Stack{
	Action action;				// 選択されたアクション
	int i;						// ループ変数
	Status status;				// 現在のボールの位置や加速度のステータス
	int target_point_id;		// 次のチェックポイントのID
	Vector2 estimated_vector;	// 次のアクションで加速すると良さそうだと推測された方向へのベクトル
	float distance_to_next;		// 次のチェックポイントまでの直線距離
	float min_distance_to_goal;	// 【未使用】
};

int MakeActions(
	const Field& aField,
	const Vector2 check_points[MAX_NODE_COUNT],
	const int check_point_count,
	const bool jump,				// ジャンプありかなしかのフラグ
	int best_score,					// これまでに見つけたゴールするまでの最短のターン数(これを超えたらそれより先は探索しない)
	Action actions[MAX_TURN_COUNT]	// 探索で見つけたベストなアクションリスト
){
	Stack stack[MAX_TURN_COUNT];
	int stack_count = 0;
	float limit_rate = best_score / 35.0f;	// デフォルトのアクションで時間のかかる問題では多く探索する

	// stackの初期化
	++stack_count;
	stack[stack_count-1].i = 0;
	stack[stack_count-1].status = Status(aField.getStartPos(), Vector2(0.0f, 0.0f));	// 初期位置
	stack[stack_count-1].target_point_id = 1;
	stack[stack_count-1].distance_to_next = (check_points[stack[stack_count-1].target_point_id] - stack[stack_count-1].status.getBallPos()).getLength();
	++stack_count;
	stack[stack_count-1].i = 0;
	stack[stack_count-1].target_point_id = stack[stack_count-2].target_point_id;
	stack[stack_count-1].status = stack[stack_count-2].status;
	stack[stack_count-1].estimated_vector = GetEstimatedBestActionVector(	// 次にすると良さそうな行動を推測
		aField, stack[stack_count-1].target_point_id, check_points, check_point_count, stack[stack_count-1].status
	);

	// 【デバッグ用】
	IMG_DATA_PRINT("%f %f %f %f %s\n", stack[stack_count-2].status.getBallPos().x, stack[stack_count-2].status.getBallPos().y, stack[stack_count-1].status.getBallPos().x, stack[stack_count-1].status.getBallPos().y, DEBUG_LINE_COLOR2);

	int find = 0;
	Vector2 v1, v2;
	int next_target_id;
	int loop;
	for(loop=0; loop<LOOP_LIMIT*limit_rate; ++loop){
		Vector2 start = stack[stack_count-1].status.getBallPos(),
				end = check_points[stack[stack_count-1].target_point_id];
		Vector2 accel = stack[stack_count-1].estimated_vector;
		accel.changeLength(MAX_ACCEL);
		Vector2 ball_vel = stack[stack_count-1].status.getBallVel();

		// アクションの決定
		float r2 = 1.0f / halSqrt(2.0f);
		if(stack[stack_count-1].i == ACCEL_BRAKE){
			// ブレーキ * 0.5 + estimated_vector
			Vector2 v = accel;
			if(!Equal(ball_vel.getLength(), 0.0f)){
				v = Vector2(-ball_vel.x, -ball_vel.y).normalize() * 0.5f + v.normalize();
			}
			v.changeLength(MAX_ACCEL);
			stack[stack_count-1].action = Action(v);
		}
		else{
			// estimated_vectorを0°、45°、90°左右に回転させたベクトルをそれぞれ試す
			float cos = ACCEL_VECTOR[stack[stack_count-1].i].x,
				  sin = ACCEL_VECTOR[stack[stack_count-1].i].y;
			stack[stack_count-1].action = Action(Vector2(accel.x * cos - accel.y * sin, accel.x * sin + accel.y * cos));
		}

		// 行動
		stack[stack_count-1].status.update(stack[stack_count-1].action);
		stack[stack_count-1].distance_to_next = (check_points[stack[stack_count-1].target_point_id] - stack[stack_count-1].status.getBallPos()).getLength();
		HAL_ASSERT(fIsValid(stack[stack_count-1].status.getBallPos().x) && fIsValid(stack[stack_count-1].status.getBallPos().y));
		HAL_ASSERT(fIsValid(stack[stack_count-1].status.getBallVel().x) && fIsValid(stack[stack_count-1].status.getBallVel().y));

		// 【デバッグ用出力】
		IMG_DATA_PRINT("%f %f %f %f %s\n", stack[stack_count-2].status.getBallPos().x, stack[stack_count-2].status.getBallPos().y, stack[stack_count-1].status.getBallPos().x, stack[stack_count-1].status.getBallPos().y, DEBUG_LINE_COLOR2);
		
		// ゴールしたか判定
		if(aField.isInGoal(stack[stack_count-2].status.getBallPos(), stack[stack_count-1].status.getBallPos())){
			// ベストスコアを更新
			best_score = stack_count-1;
			// アクションの保存
			for(int i=1; i<stack_count; ++i){
				actions[i-1] = stack[i].action;
			}
			++find;
			stack_count = MAX(stack_count - (10 + 5 * find), 3);	// これまでにゴールした回数に応じてstackをpop
			goto CANCEL;
			//return (find)? best_score: 0;	// 【デバッグ用】
		}

		// targetが変わるか判定(ベクトルv1とv2のなす角が90°以上になったらチェックポイント通過と判定する)
		next_target_id = stack[stack_count-1].target_point_id;
		do{
			v1 = check_points[next_target_id] - check_points[next_target_id-1],
			v2 = check_points[next_target_id] - stack[stack_count-1].status.getBallPos();
			if(!(v1.x * v2.x + v1.y * v2.y < 0)){
				break;
			}
			if(next_target_id+1 < check_point_count){
				++next_target_id;
			}
			else{
				goto CANCEL;
			}
		}while(1);
		// 次の次のチェックポイントとの間に穴がなければ次のチェックポイントをスキップする
		{
			int next_next_point_id = next_target_id+1;
			while(check_point_count > next_next_point_id && !isCrossHole(aField, stack[stack_count-1].status.getBallPos(), check_points[next_next_point_id], jump)){
				++next_target_id;
				++next_next_point_id;
			}
		}

		if(
				stack_count > best_score-1 ||// 時間かかりすぎ(ベストスコアを更新することがないのでこれより先は探索しない)
				isCrossHole(aField, stack[stack_count-1].status.getBallPos(), check_points[next_target_id]) ||// 次のチェックポイントまでの間に穴がある
				(
					stack_count >= 2 &&
					(stack[stack_count-2].target_point_id == next_target_id) &&
					stack[stack_count-2].distance_to_next <= stack[stack_count-1].distance_to_next
				) || // 次のチェックポイントまでの距離が減ってない
				aField.isInHole(stack[stack_count-1].status.getBallPos())	// 穴に落ちた
			){
			goto CANCEL;
		}
		else{// 次の行動へ
			// スタックを積む
			++stack_count;
			stack[stack_count-1].i = 0;
			stack[stack_count-1].target_point_id = next_target_id;
			stack[stack_count-1].status = stack[stack_count-2].status;
			
			// 次にすると良さそうな行動を推測
			stack[stack_count-1].estimated_vector = GetEstimatedBestActionVector(
				aField, stack[stack_count-1].target_point_id, check_points, check_point_count, stack[stack_count-1].status
			);
			HAL_ASSERT(fIsValid(stack[stack_count-1].estimated_vector.x) && fIsValid(stack[stack_count-1].estimated_vector.y));
		}
		continue;
CANCEL:
		// 行動をキャンセルして次へ
		while(stack[stack_count-1].i >= ACCEL_DIRECTION_MAX-1){
			// これ以上popできなければ探索終了
			if(stack_count == 2){
				stack_count = 0;	// 【←不要なコード。消し忘れ。】
				goto END;
			}
			stack_count = MAX(stack_count - (1+find*3), 2);	// これまでにゴールした回数に応じてstackをpop
		}
		stack[stack_count-1].status = stack[stack_count-2].status;
		++stack[stack_count-1].i;
	}
END:;
	return (find)? best_score: 0;
}

//**********************************************************************************************//
//*     ダイクストラによるチェックポイント作成 & デフォルトのアクション生成
//**********************************************************************************************//

//=============================================================================================//
//     ノードクラス(pos以外はデバッグ用の情報を保持するためのもの)
//=============================================================================================//
struct Node{
	Vector2 pos;
	int hole_id;	// 穴の番号【デバッグ用】
	Rect::CornerKind corner;	// 角の種類【デバッグ用】
	// ノードの種類【デバッグ用】
	enum Type{
		Type_Start,	// スタート地点のノード
		Type_Goal,	// ゴールのノード(ゴールは矩形なので、その四隅と中心の５つのノードが存在する)
		Type_Corner,// それぞれの穴の四隅のノード
		Type_Else	// 穴と穴の交点のノード
	} type;

	Node(){}
	Node(const Vector2 &pos, const Type type): pos(pos), type(type){}
	Node(const Vector2 &pos, const int hole_id, const Rect::CornerKind corner): pos(pos), hole_id(hole_id), corner(corner), type(Type_Corner){}
};

//=============================================================================================//
//     ダイクストラ クラス(普通のダイクストラと違い、曲がる角度を考慮したコストを計算している & ゴールが複数)
//=============================================================================================//
class DijkstraAlgorithm{
public:
	typedef float COST_TYPE;
	
protected:
	COST_TYPE link_[MAX_NODE_COUNT][MAX_NODE_COUNT];	// リンク情報(-1は未接続)
	Node *pos_list_;	// 曲がる角度を考慮したコストを計算するためにだけ持っている頂点座標
	float corner_rate_;	// 曲がる角度を考慮したコストのレート(これが0だと普通のダイクストラと同じ)
public:
	// コンストラクタ
	DijkstraAlgorithm(Node *pos_list, float corner_rate){
		// 初期化
		pos_list_ = pos_list;
		corner_rate_ = corner_rate;
		for(int i=0; i<MAX_NODE_COUNT; ++i){
			for(int j=0; j<MAX_NODE_COUNT; ++j){
				link_[i][j] = -1;
			}
		}
	}

	// リンクの設定
	void SetLink(const int node1, const int node2, const COST_TYPE &cost){
		link_[node1][node2] = cost;
		link_[node2][node1] = cost;
	}

	// 解く
	float Solve(const int start_node, const int end_node[5], int best_root[MAX_NODE_COUNT]){
		float min_cost[MAX_NODE_COUNT];
		int prev_node[MAX_NODE_COUNT];
		bool expanded[MAX_NODE_COUNT];
		// 初期化
		for(int i=0; i<MAX_NODE_COUNT; ++i){
			min_cost[i] = FLOAT_MAX;
			prev_node[i] = -1;
			expanded[i] = false;
			best_root[i] = -1;
		}

		min_cost[start_node] = 0;
		do{
			// 未展開のノードで、コストが最も低いノードを展開
			int best_node = -1;
			float min = FLOAT_MAX;
			for(int i=0; i<MAX_NODE_COUNT; ++i){
				if(!expanded[i] && min > min_cost[i]){
					min = min_cost[i];
					best_node = i;
				}
			}
			if(best_node == -1){
				break;
			}
			for(int i=0; i<5; ++i){
				if(best_node == end_node[i]){
					break;
				}
			}

			expanded[best_node] = true;
			Vector2 v1, v2;
			for(int i=0; i<MAX_NODE_COUNT; ++i){
				// ノードiへのリンクが存在するかチェック
				if(link_[best_node][i] >= 0){
					float cost = min_cost[best_node] + link_[best_node][i];
					// 通常のコストに曲がる角度を考慮したコストを加算
					if(best_node != start_node){
						v1 = pos_list_[best_node].pos - pos_list_[prev_node[best_node]].pos;
						v2 = pos_list_[i].pos - pos_list_[best_node].pos;
						if(v1.getLength() * v2.getLength() > 0){
							float cos = (0.001f + (-(Cos(v1, v2) - 1.0f)/2.0f)) * 0.999f;	// 【計算誤差対策にとりあえず0.001fを足して0.999fをかけておく】
							cost += corner_rate_ * MAX_VEL * cos;
						}
					}
					// コストが前よりも低ければ更新
					if(min_cost[i] > cost){
						min_cost[i] = cost;
						prev_node[i] = best_node;
					}
				}
			}
		}while(1);

		// ベストな終了ノードを取得
		float min = FLOAT_MAX, cost;
		int best_end_node = -1;
		for(int i=0; i<5; ++i){
			cost = min_cost[end_node[i]];
			if(min > cost){
				min = cost;
				best_end_node = end_node[i];
			}
		}

		// ベストなルートを取得
		int c = 0;
		for(int n=best_end_node; prev_node[n]!=-1; n=prev_node[n], ++c){}	// ルートの長さ取得
		for(int n=best_end_node, j=0; prev_node[n]!=-1; n=prev_node[n], ++j){
			best_root[c-j] = n;
		}
		best_root[0] = start_node;

		return min_cost[best_end_node];
	}
};

//=============================================================================================//
//     チェックポイントの作成
//=============================================================================================//
float MakeCheckPoints(const Field& aField, Vector2 check_points[MAX_NODE_COUNT], int *check_point_count, bool jump, float corner_rate){
	// 頂点リストの作成
	Node pos_list[MAX_NODE_COUNT];
	int pos_list_count = 0;
	Vector2 pos;
	Vector2 deltas[] = {
		Vector2(-DELTA, -DELTA),	// Rect::CornerKind_LeftUp
		Vector2(-DELTA,  DELTA),	// Rect::CornerKind_LeftDown
		Vector2( DELTA, -DELTA),	// Rect::CornerKind_RightUp
		Vector2( DELTA,  DELTA)		// Rect::CornerKind_RightDown
	};
	const int deltas_count = sizeof(deltas)/sizeof(Vector2);
	// それぞれの穴の角付近に頂点を取る
	const int corner_type_count = sizeof(CORNER_KINDS)/sizeof(Rect::CornerKind);
	for(int i=0; i<aField.getHoleCount(); ++i){
		bool flag[corner_type_count] = {};
		for(int j=0; j<deltas_count; ++j){
			for(int k=0; k<corner_type_count; ++k){
				// そのまま四隅の座標を使うと穴に落ちるのでちょっとずらす(ずらした先が別の穴という可能性もあるので4方向にずらすのを試す)
				pos = aField.getHole(i).getCornerPos(CORNER_KINDS[k])   +deltas[(j+k)%deltas_count];
				// posで穴に落ちなければリストに追加
				if(!flag[k] && !aField.isInHole(pos)){
					flag[k] = true;
					pos_list[pos_list_count++] = Node(pos, i, CORNER_KINDS[k]);
				}
			}
		}
	}
	// 穴と穴の交点付近に頂点を取る
	Vector2 point_list[4];
	int point_count;
	for(int i=0; i<aField.getHoleCount(); ++i){
		for(int j=i+1; j<aField.getHoleCount(); ++j){
			if(CrossPoint(aField.getHole(i), aField.getHole(j), point_list, &point_count)){
				bool flag[4] = {};
				for(int k=0; k<point_count; ++k){
					for(int l=0; l<deltas_count; ++l){
						pos = point_list[k] + deltas[l];
						if(!flag[k] && !aField.isInHole(pos)){
							flag[k] = true;
							pos_list[pos_list_count++] = Node(pos, Node::Type_Else);
						}
					}
				}
			}
		}
	}
	// スタートとゴール(四隅＋中心)を頂点とする
	int start_id = pos_list_count;
	pos_list[pos_list_count++] = Node(aField.getStartPos(), Node::Type_Start);
	int goal_id_list[5] = {pos_list_count};
	pos_list[pos_list_count++] = Node(aField.getGoalRect().getCenterPos(), Node::Type_Goal);
	{
		bool flag[corner_type_count] = {};
		for(int k=0; k<corner_type_count; ++k){
			pos = aField.getGoalRect().getCornerPos(CORNER_KINDS[k]) - deltas[k];
			if(!aField.isInHole(pos)){
				goal_id_list[pos_list_count-goal_id_list[0]] = pos_list_count;
				pos_list[pos_list_count++] = Node(pos, Node::Type_Goal);
			}
		}
	}

	// コスト付き無向グラフの作成
	DijkstraAlgorithm dijkstra(pos_list, corner_rate);
	float cost;
	for(int i=0; i<pos_list_count; ++i){
		for(int j=i+1; j<pos_list_count; ++j){
			// ノードを結ぶエッジが穴と交差していなければエッジを追加
			if(!isCrossHole(aField, pos_list[i].pos, pos_list[j].pos, jump)){
				// コストを計算しエッジを追加
				cost = (pos_list[i].pos - pos_list[j].pos).getLength();
				if(!Equal(cost, 0.0f)){
					dijkstra.SetLink(i, j, cost);
				}
			}
		}
	}
	
	// ダイクストラで解く
	int check_point_id_list[MAX_NODE_COUNT];
	float length = dijkstra.Solve(start_id, goal_id_list, check_point_id_list);

	// 【デバッグ用出力】
	HAL_PRINT("best root %s[", ((jump)? "(jump)": ""));
	char direction[4][5] = {
		"左上",
		"右上",
		"右下",
		"左下"
	};
	Vector2 prev;
	for(unsigned int i=0; check_point_id_list[i]!=-1; ++i){
		switch(pos_list[check_point_id_list[i]].type){
			case Node::Type_Corner:
				HAL_PRINT("%d%s(%.2f, %.2f) ",
					pos_list[check_point_id_list[i]].hole_id, direction[pos_list[check_point_id_list[i]].corner],
					pos_list[check_point_id_list[i]].pos.x,
					pos_list[check_point_id_list[i]].pos.y
				);
				break;
			case Node::Type_Start:
				HAL_PRINT("start(%.2f, %.2f) ", pos_list[check_point_id_list[i]].pos.x, pos_list[check_point_id_list[i]].pos.y);
				break;
			case Node::Type_Goal:
				HAL_PRINT("end(%.2f, %.2f)", pos_list[check_point_id_list[i]].pos.x, pos_list[check_point_id_list[i]].pos.y);
				break;
			default:
				HAL_PRINT(" (%.2f, %.2f)", pos_list[check_point_id_list[i]].pos.x, pos_list[check_point_id_list[i]].pos.y);
				break;

		}
		if(i != 0){
			IMG_DATA_PRINT("%f %f %f %f %s\n", prev.x, prev.y, pos_list[check_point_id_list[i]].pos.x, pos_list[check_point_id_list[i]].pos.y, DEBUG_LINE_COLOR1);
		}
		prev = pos_list[check_point_id_list[i]].pos;
	}
	HAL_PRINT("]\n\n");

	// チェックポイントリストの作成
	*check_point_count = 0;
	for(int i=0; check_point_id_list[i]!=-1; ++i){
		check_points[(*check_point_count)++] = pos_list[check_point_id_list[i]].pos;
	}

	return length;
}

//=============================================================================================//
//     現在の速度から止まるのに最低限必要な距離の取得
//=============================================================================================//
float StopDistance(const float vel){
	unsigned int n = (unsigned int)(vel / MAX_ACCEL);	// 商
	float a = vel - n * MAX_ACCEL;	// 剰余

	return (MAX_ACCEL * (n * (n-1))/2) + a * n;
}

//=============================================================================================//
//     デフォルトのアクションの作成
//=============================================================================================//
void MakeDefaultActions(
	const Field& aField,
	const Vector2 check_points[MAX_NODE_COUNT],
	const int check_point_count,
	Action actions[MAX_TURN_COUNT],	// 作成されたアクション
	int turns[MAX_NODE_COUNT]	// 各チェックポイントを通過するのにかかったターン数
){
	Status status(aField.getStartPos(), Vector2());
	int current_point_id = 0;
	Vector2 last_ball_pos;

	// 【実際に動かさなくてもアクションとターン数とか計算できそうだけど、とりあえずこれで応急処置】

	int action_count = 0;
	int turns_count = 0;
	int turn = 0;
	turns[current_point_id++] = turn;
	do{
		++turn;

		Vector2 start = status.getBallPos(),
			end = check_points[current_point_id];
	    Vector2 accel = end - start;

		// 加速度の決定
		float distance = accel.getLength();
		if(current_point_id == check_point_count-1){
			// 次がゴールなら常に加速
			accel.changeLength(MAX_ACCEL);
		}
		else if(Equal(distance, 0.0f)){
			// 速度が0になるように減速
			accel = status.getBallVel();
			accel = Vector2(-accel.x, -accel.y);
			turns[current_point_id++] = turn;
		}
		else if(distance <= MAX_ACCEL && distance <= status.getBallVel().getLength()){
			// 目標の位置に止まるように減速
			accel.changeLength(MAX(status.getBallVel().getLength() - distance, 0));
			accel = Vector2(-accel.x, -accel.y);
		}
		else{
			float v = MIN(status.getBallVel().getLength() + MAX_ACCEL, MAX_VEL);
			if(status.getBallVel().getLength() < MAX_VEL && distance - v >= StopDistance(v)){
				// 加速
				accel.changeLength(MAX_ACCEL);
			}
			else if(distance - status.getBallVel().getLength() >= StopDistance(status.getBallVel().getLength())){
				// 加速も減速もしない
				accel = Vector2(0, 0);
			}
			else{
				// 減速
				accel.changeLength(MAX_ACCEL);
				accel = Vector2(-accel.x, -accel.y);
			}
		}

		// 状態の更新とアクションの保存
		Action action(accel);
		last_ball_pos = status.getBallPos();
		status.update(action);
		actions[action_count++] = action;
	}while(!aField.isInGoal(last_ball_pos, status.getBallPos()));
	turns[current_point_id] = turn;
}

//**********************************************************************************************//
//*     イベント処理
//**********************************************************************************************//

//=============================================================================================//
//     プログラムの初期化
//=============================================================================================//
void onStartEvaluation() {
	for(int i=0; i<ACCEL_DIRECTION_MAX-1; ++i){
		ACCEL_VECTOR[i].normalize();
	}
}

//=============================================================================================//
//     プログラムの終了処理
//=============================================================================================//
void onEndEvaluation() {
}

//=============================================================================================//
//     ゲームの初期化(ここでアクションを最後まで決めてしまい、あとは順番にアクションを実行するだけ)
//=============================================================================================//
Action actions_[MAX_TURN_COUNT];

void onStartOneGame(const Field& aField) {
	++gameIndex_;
	turnIndex_ = 0;

	// 大まかなルートを決めるため、チェックポイントを作成(ジャンプありとジャンプなしで2パターン)
	Vector2 non_jump_check_points[MAX_NODE_COUNT], jump_check_points[MAX_NODE_COUNT];
	int non_jump_check_point_count, jump_check_point_count;
	float length1 = MakeCheckPoints(aField, non_jump_check_points, &non_jump_check_point_count, false, 6.5f);
	float length2 = MakeCheckPoints(aField, jump_check_points, &jump_check_point_count, true, 6.5f);
	// とりあえず、単純なアルゴリズムでデフォルトのアクションを作成
	//  ＋その場合のチェックポイントごとにかかったターン数を取得
	int turns[MAX_NODE_COUNT];
	MakeDefaultActions(aField, non_jump_check_points, non_jump_check_point_count, actions_, turns);

	// 【デバッグ用出力】
	HAL_PRINT("turns: [ ");
	for(int i=0; i<non_jump_check_point_count; ++i){
		HAL_PRINT("%d ", turns[i]);
	}
	HAL_PRINT("]\n\n");

	// デフォルトのアクションよりも良いアクションを探索
	if(non_jump_check_point_count > 2){
		int limit = turns[non_jump_check_point_count-1];
		int result = MakeActions(aField, jump_check_points, jump_check_point_count, true, limit, actions_);

		// non_jump_check_pointsとjump_check_pointsが違うチェックポイントリストならnon_jump_check_point_countでも探索
		if(!Equal(length1, length2)){
			limit = (result == 0)? limit: result;
			result = MakeActions(aField, non_jump_check_points, non_jump_check_point_count, false, limit, actions_);
		}
	}

	IMG_DATA_PRINT("\n");
}

//=============================================================================================//
//     ゲームの終了処理
//=============================================================================================//
void onEndOneGame() {
	HAL_PRINT("--------------------------------------------------------------------------\n");
}

//=============================================================================================//
//     アクションの実行
//=============================================================================================//
Action decideAction(const Field& aField, const Status& aStatus) {
	++turnIndex_;
	// 【デバッグ用出力】
	HAL_PRINT("-----[game %d: turn %d]---------------------------------------------------\n", gameIndex_, turnIndex_);
	HAL_PRINT("pos: (%.2f, %.2f)  vel: %.2f(%.2f, %.2f)  rest: %.2f\n",
		aStatus.getBallPos().x, aStatus.getBallPos().y,
		aStatus.getBallVel().getLength(), aStatus.getBallVel().x, aStatus.getBallVel().y,
		(aField.getGoalRect().getCenterPos() - aStatus.getBallPos()).getLength()
	);
	
	// アクションの取得
	Action action;
	action = actions_[turnIndex_-1];

	// 【デバッグ用出力】
	HAL_PRINT("action: %.2f (%.2f, %.2f)\n", action.getAccel().getLength(), action.getAccel().x, action.getAccel().y);
	HAL_PRINT("\n");

	return action;
}
【作品の著作権について】
プログラム作品の著作権は各作成者に帰属するものであり、その無断転載、無断引用を禁じます。