全体の流れは以下のようになります。
この基本的な動作に加えて、色々と高得点へのアイデアを実装しました。そして最後にチューニングを行いました。
問題や動作の視覚化には、Gnuplotを用いています。
全ての穴に対して、穴の四頂点に点を配置します。スタートから点を線で結んでいき、最も安いコストでゴールに辿り着ける折れ線を探します。折れ線の距離が短く、折れ線の形が滑らかなほどコストが安くなるように計算します。
1で求めた折れ線に対して、折れ線の点と点の間に折れ線が滑らかになるように点を1つ増やします。この点を増やす処理を、1線分の長さが一定以下になるまで繰り返し行います。これによって、短い線分の集合によって表現された擬似的な曲線が完成します。
常に現在のターンで曲線上に乗れる最高の加速度で移動していきます。現在のターンで、どうしても曲線上に乗れなくなったり、穴に落ちたりする場合には、1ターン遡って、少し減速して曲線上での移動を再開します。それでも駄目だった場合は、さらに減速します。最大の減速をしても駄目な場合には、2ターン遡り減速を行います。それで駄目なら3ターン、4ターンと遡って減速を行い、移動を再開します。このような再帰を行い、ゴールにたどり付けるまで繰り返します。
穴をジャンプできる場合を2通り想定しています。
通常通り結果を求めたあとに、これらの穴を無視して(角同士が重なっている穴の場合は、重なっている部分のみを無視)、再度、経路探索、曲線生成、加速度計算を行います。
加速度計算の再帰処理で、穴の前での踏み切り調整なども自動的に行われます。ゴールにたどり着けた場合で、よりよい結果が得られた場合には、これを採用します。
最高速度未満の幅の穴がある場合。
角同士が微妙に重なっている穴がある場合。
穴の角を通過していくときに、穴の内側をかすめて移動できるようにします。
通常通り結果を求めたあとに、全ての穴を少し縮小して、再度、経路探索、曲線生成、加速度計算を行います。
この穴の縮小を、数段階行います(今回は5段階)。加速度計算の再帰処理で、穴の角の前での踏み切り調整なども自動的に行われます。ゴールにたどり着けた場合で、よりよい結果が得られた場合には、これを採用します。
経路探索の後に、探索結果の折れ線から曲線を生成しますが、折れ線の各頂点での向きのベクトルの計算に、前後の線分の長さの比から影響を受けるような重み付けをすることによって、曲線の膨らみ具合いを変化させて曲線を数パターン生成します(今回は4パターン)。その結果をもとに、再度、加速度計算を行います。
よりよい結果が得られた場合には、これを採用します。
経路の折れ線から生成される曲線は、必ず経路の折れ線の全ての点を含んでしまいます。折れ線の全ての点を通過してしまうことによって、「その点を無理に通らなければ、もっとなめらかに移動できたのに…」というケースが出てきます。そこで、削除したほうが都合のよいなめらかな曲線が生成される場合には、経路の折れ線からその点を削除してしまいます。
最後はチューニングでスコアを上げました。
などで調整を行いました。
概要
全体の流れは以下のようになります。
この基本的な動作に加えて、色々と高得点へのアイデアを実装しました。そして最後にチューニングを行いました。
問題や動作の視覚化には、Gnuplotを用いています。
基本動作(1)、経路探索
全ての穴に対して、穴の四頂点に点を配置します。スタートから点を線で結んでいき、最も安いコストでゴールに辿り着ける折れ線を探します。折れ線の距離が短く、折れ線の形が滑らかなほどコストが安くなるように計算します。
基本動作(2)、曲線生成
1で求めた折れ線に対して、折れ線の点と点の間に折れ線が滑らかになるように点を1つ増やします。この点を増やす処理を、1線分の長さが一定以下になるまで繰り返し行います。これによって、短い線分の集合によって表現された擬似的な曲線が完成します。
基本動作(3)、加速度計算
常に現在のターンで曲線上に乗れる最高の加速度で移動していきます。現在のターンで、どうしても曲線上に乗れなくなったり、穴に落ちたりする場合には、1ターン遡って、少し減速して曲線上での移動を再開します。それでも駄目だった場合は、さらに減速します。最大の減速をしても駄目な場合には、2ターン遡り減速を行います。それで駄目なら3ターン、4ターンと遡って減速を行い、移動を再開します。このような再帰を行い、ゴールにたどり付けるまで繰り返します。
高得点へのアイディア、穴のジャンプ
穴をジャンプできる場合を2通り想定しています。
通常通り結果を求めたあとに、これらの穴を無視して(角同士が重なっている穴の場合は、重なっている部分のみを無視)、再度、経路探索、曲線生成、加速度計算を行います。
加速度計算の再帰処理で、穴の前での踏み切り調整なども自動的に行われます。ゴールにたどり着けた場合で、よりよい結果が得られた場合には、これを採用します。
最高速度未満の幅の穴がある場合。
角同士が微妙に重なっている穴がある場合。
高得点へのアイディア、穴の角削り
穴の角を通過していくときに、穴の内側をかすめて移動できるようにします。
通常通り結果を求めたあとに、全ての穴を少し縮小して、再度、経路探索、曲線生成、加速度計算を行います。
この穴の縮小を、数段階行います(今回は5段階)。加速度計算の再帰処理で、穴の角の前での踏み切り調整なども自動的に行われます。ゴールにたどり着けた場合で、よりよい結果が得られた場合には、これを採用します。
高得点へのアイディア、曲線を数パターン生成する
経路探索の後に、探索結果の折れ線から曲線を生成しますが、折れ線の各頂点での向きのベクトルの計算に、前後の線分の長さの比から影響を受けるような重み付けをすることによって、曲線の膨らみ具合いを変化させて曲線を数パターン生成します(今回は4パターン)。その結果をもとに、再度、加速度計算を行います。
よりよい結果が得られた場合には、これを採用します。
高得点へのアイディア、経路の折れ線に存在するじゃまな頂点の削除
経路の折れ線から生成される曲線は、必ず経路の折れ線の全ての点を含んでしまいます。折れ線の全ての点を通過してしまうことによって、「その点を無理に通らなければ、もっとなめらかに移動できたのに…」というケースが出てきます。そこで、削除したほうが都合のよいなめらかな曲線が生成される場合には、経路の折れ線からその点を削除してしまいます。
最後のチューニング
最後はチューニングでスコアを上げました。
などで調整を行いました。