Flood-itでのゲームプロセスの自動化について読むことが興味深いかどうかについて質問を投稿した後。 この記事を公開することに関連して、いくつかの肯定的なレビューが寄せられました。
はじめに
Flood-itは多色のセルを備えた14x14の競技場です。プレーヤーの仕事は、最小限の手数でフィールドを1色で塗りつぶすことです。 各動きはパレットからの色の選択を表し、パレットには合計で6色があります。 ゲームでは合計25の動きが与えられます。
図1：競技場。
塗りつぶしに最適な色を選択するアルゴリズムを実装する必要があります。 詳細は猫の下で実装を読むことができます。
アルゴリズムの最初のバージョンの説明
研究の過程で、2つのアルゴリズムが開発されました。 最初のアルゴリズムはより単純で、次の手順で構成されていました。
- 競技場の現在の状態を取得する。
- 可能な各色を塗りつぶし、注がれた細胞の数を数える試み。
- 最大の塗りつぶし領域を与える色が注ぐために選択されます
このアルゴリズムでは、100ゲームがプレイされ、そのうち28ゲームで勝ちました。得点の最大数は640（連続2勝）でした。
このアルゴリズムの問題は、1つのセルが異なる色のいくつかの隣接するセルを閉じたときの状況を追跡せず、2回の移動でさらに多くを塗りつぶせることでした。
図2：最初のアルゴリズムの問題。
図では、最初に緑で塗りつぶすと、大きなピンク色の領域にアクセスできることがわかります。 紫色でペイントすると、2つのセルの赤い領域のみを取得できます。 同様に、他の色を考えることもできます。
記載されたアルゴリズムをテストした後、この問題は数ステップ先を分析することで解決されました。
アルゴリズムの2番目のバージョンの説明
ゲームには6色があり、最初のセルの現在の色を除いて、5色のいずれかをペイントできます。 したがって、4ステップ先の単純な検索では、5 ^ 4 = 625オプションを整理する必要があります。 実際、アルゴリズムでは、1296（4度で6）の組み合わせがソートされます。 各色の組み合わせは1つの数字で表され、塗りつぶしの順序は6で割った余りによって決まります。
- 1-ピンク;
- 2-紫;
- 3-黄色;
- 4-赤;
- 5-青;
- 6-緑。
4色すべてで塗りつぶした後、最初のセルの色で塗りつぶされたセルの数がカウントされます。 これらの数値の中で、最大値が選択されています：
int[] fill_rate = new int[1296]; //
int max_color;
int max_count;
for (int i = 0; i < 1296; i++) {
FloodLevel t = new FloodLevel(colors);
t.fill(i / 1 % 6 + 1); // 1-
t.fill(i / 6 % 6 + 1); //
t.fill(i / 36 % 6 + 1); // ..
t.fill(i / 216 % 6 + 1);
fill_rate[i] = t.count(); //
}
max_color = 0;
max_count = 0;
for (int i = 0; i < 1296; i++)
if (fill_rate[i] > max_count) {
max_color = i;
max_count = fill_rate[i];
}
// - max_color % 6 + 1
FloodLevelクラスは、コピーとシェーディングを簡素化するように設計されており、次のメソッドが含まれています。
public final class FloodLevel {
public FloodLevel();
public FloodLevel(FloodLevel prototype); //
public void setColors(int[] new_colors);
public void setColor(int i, int j, int color);
public int getColor(int i, int j);
public void fill(int color); //
public int count(); //
public boolean gameCompleted(); //
}
メソッドのテキストはプロジェクトのソースコードで表示できます。コードは簡単で、イメージを埋めるための再帰的なアルゴリズムだからです。
図3：SuperPixieタイトルの達成。
100ゲームでアルゴリズムをテストすると、そのような特徴が示されました-96勝、最大19680ポイント。 テストプロセスで、SuperPixieのタイトルを受け取りました。 リファクタリングと最適化は無期限に実行できるため、このアルゴリズムを停止しました。
レベル画像の取得
レベルは、複数の色のセルで構成されるフィールドです。 各セルは単色で塗られているため、次のレベルでセルの色を簡単に取得できます。
FloodLevel colors = new FloodLevel();
for (int move = 0; move < 25; move++) {
for (int j = 0; j < 14; j++)
for (int i = 0; i < 14; i++) {
int color = robot.getPixelColor(FIELD_X_OFFSET + 24 * i, FIELD_Y_OFFSET + 24 * j).getRGB() & 0x00ffffff;
switch (color) {
case 0x00ed70a1: //
colors.setColor(i, j, 1);
break;
case 0x00605ca8: //
colors.setColor(i, j, 2);
break;
case 0x00f3f61d: //
colors.setColor(i, j, 3);
break;
case 0x00dc4a20: //
colors.setColor(i, j, 4);
break;
case 0x0046b1e2: //
colors.setColor(i, j, 5);
break;
case 0x007e9d1e: //
colors.setColor(i, j, 6);
break;
default: //
return;
}
}
画面からピクセル値を取得するには、Robotクラスを使用して実行します。次に、受信した各ピクセルがゲーム内の特定の色に準拠しているかどうかを確認します。 競技場のセルは単調であるため、リストされた色に属さない色は、競技場ではないことを意味すると主張できます。
ゲーム管理
また、単純なアルゴリズムを使用して色を選択します。これにより、色の1つに対応する位置にマウスを移動し、色をクリックします。
switch (max_color % 6 + 1) {
case 1:
robot.mouseMove(BUTTON_X_OFFSET + 45 * 0, BUTTON_Y_OFFSET + 45 * 0);
break;
case 2:
robot.mouseMove(BUTTON_X_OFFSET + 45 * 1, BUTTON_Y_OFFSET + 45 * 0);
break;
case 3:
robot.mouseMove(BUTTON_X_OFFSET + 45 * 2, BUTTON_Y_OFFSET + 45 * 0);
break;
case 4:
robot.mouseMove(BUTTON_X_OFFSET + 45 * 0, BUTTON_Y_OFFSET + 45 * 1);
break;
case 5:
robot.mouseMove(BUTTON_X_OFFSET + 45 * 1, BUTTON_Y_OFFSET + 45 * 1);
break;
case 6:
robot.mouseMove(BUTTON_X_OFFSET + 45 * 2, BUTTON_Y_OFFSET + 45 * 1);
break;
}
robot.mousePress(InputEvent.BUTTON1_MASK);
robot.mouseRelease(InputEvent.BUTTON1_MASK);
アクションを完了した後、ゲームが反応して競技場を更新するまでしばらく待つ必要があります。 これには小さな遅延が使用されます。
おわりに
図4：プログラムで獲得した最大ポイント。
プログラムは、土曜日の夕方から日曜日の朝までの1日で作成されました。 これに関連して、アンチマジック、特にマジックナンバーをおIびします。 また、プログラムはレベルを自動的に検出しません。コードには画面の隅からのオフセットが含まれています（GnomeでSeamonkeyブラウザーを使用しています）。 トピックが興味深い場合、競技場の自動検索を終了できます。
ソースコードをダウンロードできます。