tsukammoの収穫記

上下左右の更地にアルゴリズムを

codingame:Spring Challenge 2020 ルール要約&マップ生成ロジック説明

これはなに？

お題のゲームを解くプログラムを各自が作成、サイト上に提出して順位を競い合うゲームAIコンテストCodinGame「Spring Challenge 2020」について、ルール要約とマップ生成ロジックを説明します。 ※記載内容の保証はし兼ねるので、自己責任で読んでください。
コンテストページ：https://www.codingame.com/contests/spring-challenge-2020/
コンテスト期間：5月8日～5月18日

f:id:tsukammo:20200508062252p:plain

(本ゲームは、コンピュータゲーム「パックマン」がモチーフです。)
相手よりも多くのペレットを食べ、マップ上の過半数のポイントを取るか、200ターン経過した場合にポイントの多ければ勝ちです。
※パックマンの残数は影響しません。

ルール説明

ゲーム開始時に与えらる壁と床で構成されるグリッド上で、各プレイヤーはグリッドに沿って移動できるパックマンを操作します。 マップはランダムに生成され、幅と高さも変化します。マップの各セルは次のいずれかです。

  • 壁 ("#"で表される)
  • 床 (" "(スペース文字)で表される )

マップは常に中心の縦軸を挟んで対称的に配置されます。 多くのマップでは左右端を壁で区切っていない箇所(トンネル)があり、パックマンがトンネルを通るとマップ反対側に移動できます。

ゲーム開始時、マップはペレット or スーパーペレットで埋め尽くされます。 同じセルにパックマンが移動するとすると取得することができ、ペレットは1ポイント。スーパーペレットは10ポイントのスコアを得て、ペレットは取り除かれます。

f:id:tsukammo:20200508062537p:plain
ペレットとスーパーペレット

各プレイヤーは最大5つのパックマンを同数コントロールします。各ターン毎に、あなたのパックマンとスーパーペレットの位置に加え、視界内にあるパックマンとペレットに関する情報が与えられます。 視界は、あなたのパックマンを起点とし、上下左右の直線上に壁に遮られるまで続きます。
※初期のwood2リーグでは、最大1つのパックマンを操作し、全ての視界を持っています。

f:id:tsukammo:20200508062639p:plain
視界と壁

パックマンはじゃんけんと同様の3つのタイプを持ちます。 各タイプは移動とパックマン同士の対決に影響します。

f:id:tsukammo:20200508062706p:plain
タイプ(ROCK・PAPER・SCISSORS)

パックマンは2つのスキル(SWITCHとSPEED)を使用でき、共通のクールダウンは10ターンです。スキルはゲーム開始時から使用可能です。

アクション

あなたのパックマンに対し、ターン毎に以下の操作のいずれか1つの操作をすることができます。

MOVE

パックマンに目標の位置を与えると、その位置までの最短ルートを見つけて最初のステップを移動します。 パックマンはルートを選ぶときにペレットや他のパックマンの存在を考慮せず、後述する衝突処理が発生することがあります。

SWITCH

パックマンのタイプを指定したタイプに変更することができます。

SPEED

次の5ターンの間スピードが上がり、MOVE時に2step移動します。つまり２倍の距離を移動できることを意味します。

衝突

他のパックマンと移動が交差したり同じセルに移動した場合、「衝突」が起こります。衝突発生時の解決順序は下記の通りです。

  1. 移動しているすべてのパックマンはSPEEDに関係なく 1 ステップ移動します。
  2. 同じタイプのパックマンや同じプレイヤーのパックマンがいる場合、各パックマンの移動はキャンセルされ元のセルに戻ります。 異なるプレイヤーかつ異なるタイプのパックマンの場合、同じセルに移動可能ですが、じゃんけん関係において自身より強いパックマンを横切る場合、同様に移動がキャンセルされます。
  3. 2.によって新たな衝突が発生する可能性があります。このため、新しい衝突が発生しなくなるまで前のステップが繰り返されます。
  4. 同じセルにいるパックマンのうち、じゃんけん関係において弱いパックマンはゲームから除外されます。
    ※ROCKはSCISSORSを、SCISSORSはPAPERを、PAPERはROCKに対して強いです。
  5. SPEED能力が発動しているパックマンは、もういちど1.から処理されます。

リーグ毎の開放

  • silver：自他共に(視界外でも)倒されたパックマンが入力で与えられる
  • bronze：スキル(SWITCH・SPEED)、視界の制約
  • wood1：一度に複数のパックマンを操作

※simulator上、4人同時対戦も想定されています。

マップ生成と初期位置

マップ

幅：28～3329～35、高：10～1517の範囲(ルール変更が入った模様)で一様ランダムで決定します。 2人対戦の場合は、横方向に折りたたむ線対称となり、4人対戦の場合は縦横4つ折りの線対称となります。 マップ左上から順に、下記の決められた通路の形状からランダムに選択し、当てはめていきます。 最後に、生成したマップの外周を壁で多います。その際、マップ端の床の上下が壁の場合、トンネルとして床を残します。

f:id:tsukammo:20200508063000p:plain
通路形状(■が床)※上限左右反転したものも対象

初期配置

各プレイヤーの操作するパックマンの数を2～5の範囲で一様ランダムに決定します。 生成したマップの床をランダムに選択し、線対称にパックマンを配置します。 さらに床をランダムに選択し、線対称にスーパーペレットを合計4つ配置します。