Help us understand the problem. What is going on with this article?

CodinGame の TRON BATTLE で FloodFill アルゴリズムを実装してみた

More than 1 year has passed since last update.

# この記事は、『CodinGame はBOT(AIプログラム)でバトルするのが正しい楽しみ方かもしれません』 の続きです。

以下のようなデバッグ出力ができるように CodinGame の TRON BATTLE プログラムを改造してみた。

  • P=0 という出力から、自機のプレイヤー番号は0であることが分かる。
  • Input{X0:2, Y0:2, X1:10, Y1:0} という出力からプレイヤー0のスタート位置(tail)は、(2, 2) であることと、現在位置(head)の座標が (10, 0) であることが分かる。 *自機のプレイヤー(プレイヤー0)のヘッドから見て現時点で到達可能であるマスが+記号で表示されている。ちなみにマイナス記号は何もない印である。
P=0
Input{X0:2, Y0:2, X1:10, Y1:0}
+ + + + + + + + + + 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

1. 出来たソース

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

class Player
{
    static void Main(string[] args) {
        Player control = new Player();
        string[] numbers;
        Input[] inputs;
        // game loop
        while (true) {
            numbers = Console.ReadLine().Split(' ');
            int N = int.Parse(numbers[0]);
            int P = int.Parse(numbers[1]);
            Console.Error.WriteLine("P={0}", P);
            inputs = new Input[N];
            for (int i = 0; i < N; i++) {
                numbers = Console.ReadLine().Split(' ');
                int X0 = int.Parse(numbers[0]);
                int Y0 = int.Parse(numbers[1]);
                int X1 = int.Parse(numbers[2]);
                int Y1 = int.Parse(numbers[3]);
                inputs[i] = new Input(i, X0, Y0, X1, Y1);
            }
            Input me = inputs[P];
            string dir = control.HandleInputs(me, inputs);
            control.DumpMap();
            Console.WriteLine(dir);
        }
    }
    Cell[,] map = new Cell[30, 20];
    Queue<Cell> ffQueue = new Queue<Cell>();
    private Player() {
        for(int y=0; y<20; y++) {
            for(int x=0; x<30; x++) {
                map[x, y] = new Cell(x, y, -1);
            }
        }
    }
    private string HandleInputs(Input me, Input[] inputs) {
        Console.Error.WriteLine(me);
        foreach(var input in inputs) {
            if (input.X1 < 0) DeleteIdsFromMap(input.Id);
            else AddInputToMap(input);
        }
        ExecuteFloodfill(me);
        if (CanMoveTo(me, -1, 0)) return "LEFT";
        if (CanMoveTo(me, 1, 0)) return "RIGHT";
        if (CanMoveTo(me, 0, -1)) return "UP";
        if (CanMoveTo(me, 0, 1)) return "DOWN";
        return "?";
    }
    void AddInputToMap(Input input) {
        this.map[input.X1, input.Y1].V = input.Id;
    }
    void DeleteIdsFromMap(int id) {
        for(int y=0; y<20; y++) {
            for(int x=0; x<30; x++) {
                if (map[x, y].V == id) map[x, y].V = -1;
            }
        }
    }
    bool CanMoveTo(Input me, int xOffset, int yOffset) {
        int x = me.X1+xOffset;
        int y = me.Y1+yOffset;
        if (x < 0) return false;
        if (x > 29) return false;
        if (y < 0) return false;
        if (y > 19) return false;
        return map[x, y].V == -1 || map[x, y].V == 9;
    }
    bool IsEmptyCell(Cell center, int xOffset, int yOffset) {
        int x = center.X+xOffset;
        int y = center.Y+yOffset;
        if (x < 0) return false;
        if (x > 29) return false;
        if (y < 0) return false;
        if (y > 19) return false;
        return map[x, y].V == -1;
    }
    void DumpMap() {
        for(int y=0; y<20; y++) {
            for(int x=0; x<30; x++) {
                if (map[x, y].V == -1) Console.Error.Write("-");
                else if (map[x, y].V == 9) Console.Error.Write("+");
                else Console.Error.Write(map[x, y].V);
                Console.Error.Write(" ");
            }
            Console.Error.WriteLine();
        }
    }
    void ExecuteFloodfill(Input me) {
        for(int y=0; y<20; y++) {
            for(int x=0; x<30; x++) {
                if (map[x, y].V == 9) map[x, y].V = -1;
            }
        }
        Cell c = map[me.X1, me.Y1];
        if (IsEmptyCell(c, -1, 0)) ffQueue.Enqueue(map[c.X-1, c.Y]);
        if (IsEmptyCell(c, 1, 0)) ffQueue.Enqueue(map[c.X+1, c.Y]);
        if (IsEmptyCell(c, 0, -1)) ffQueue.Enqueue(map[c.X, c.Y-1]);
        if (IsEmptyCell(c, 0, 1)) ffQueue.Enqueue(map[c.X, c.Y+1]);
        FloodfillLoop();
    }
    void FloodfillLoop() {
        while(ffQueue.Count > 0) {
            Cell c = ffQueue.Dequeue();
            if(map[c.X, c.Y].V != -1) continue;
            c.V = 9;
            if (IsEmptyCell(c, -1, 0)) ffQueue.Enqueue(map[c.X-1, c.Y]);
            if (IsEmptyCell(c, 1, 0)) ffQueue.Enqueue(map[c.X+1, c.Y]);
            if (IsEmptyCell(c, 0, -1)) ffQueue.Enqueue(map[c.X, c.Y-1]);
            if (IsEmptyCell(c, 0, 1)) ffQueue.Enqueue(map[c.X, c.Y+1]);
        }
    }
}
class Input
{
    public int Id;
    public int X0;
    public int Y0;
    public int X1;
    public int Y1;
    public Input(int id, int x0, int y0, int x1, int y1) {
        this.Id = id;
        this.X0 = x0;
        this.Y0 = y0;
        this.X1 = x1;
        this.Y1 = y1;
    }
    public override string ToString() {
        return String.Format("Input{{X0:{0}, Y0:{1}, X1:{2}, Y1:{3}}}", X0, Y0, X1, Y1);
    }
}
class Cell
{
    public int X;
    public int Y;
    public int V;
    public Cell(int x, int y, int v) {
        this.X = x;
        this.Y = y;
        this.V = v;
    }
    public override string ToString() {
        return String.Format("Cell{{X:{0}, Y:{1}, V:{2}}}", X, Y, V);
    }
}

2. 最後に

TRON BATTLE については書く記事としてはこれで終わりになるかもしれません。
C# で挑戦される方の「手始め」の参考にでもなればと思い投稿してみました。

# Wood 1 League を抜け出したいのだが…

javacommons
TOEICスコアは910点です。絵文字はいかがでしょうか?Qiitaの記事タイトルにも使えますよw 🎧😀😬😁😂😃😄😅😆😇😉😊🙂😋😌😍😘😗😙😚😜😝😛😎😏😶😐😑😒😳😞😟😠😡😔😕🙁😣😖😫😩😤😮😱😨😰😯😦😧😢😥😪😓😭😵😲😷😴💤💩😈👿👹👺💀👻
https://code.dlang.org/packages/pegged-cutter
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした