[JAVA] I implemented the FloodFill algorithm with TRON BATTLE of CodinGame.

\ # This article is a continuation of "CodinGame may be the right way to enjoy fighting with BOT (AI program)".

I modified CodinGame's TRON BATTLE program so that the following debug output can be obtained.

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. The finished sauce

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. Finally

This may be the end of the article I write about TRON BATTLE. I posted it with the hope that it will serve as a reference for those who are challenged in C #.

\ # I want to get out of the Wood 1 League ...

Recommended Posts

I implemented the FloodFill algorithm with TRON BATTLE of CodinGame.
Visualize the behavior of the sorting algorithm with matplotlib
I read and implemented the Variants of UKR
I measured the performance of 1 million documents with mongoDB
Implemented the algorithm of "Algorithm Picture Book" in Python3 (Heapsort)
I investigated the reinforcement learning algorithm of algorithmic trading
I tried to find the entropy of the image with python
I tried to find the average of the sequence with TensorFlow
I wrote the basic grammar of Python with Jupyter Lab
Implemented the algorithm of "Algorithm Picture Book" in Python3 (Bubble Sort)
I wrote the basic operation of matplotlib with Jupyter Lab
Implemented the algorithm of "Algorithm Picture Book" in Python3 (selection sort)
I compared the speed of Hash with Topaz, Ruby and Python
I tried scraping the ranking of Qiita Advent Calendar with Python
Find the optimal value of a function with a genetic algorithm (Part 2)
I tried to automate the watering of the planter with Raspberry Pi
[Introduction to StyleGAN] I played with "The Life of a Man" ♬
I want to output the beginning of the next month with Python
Solving the Maze with Python-Supplement to Chapter 6 of the Algorithm Quick Reference-
I studied with Kaggle Start Book on the subject of kaggle [Part 1]
I wrote the basic operation of Pandas with Jupyter Lab (Part 1)
I tried to expand the size of the logical volume with LVM
I want to check the position of my face with OpenCV!
I tried running the DNN part of OpenPose with Chainer CPU
I checked the image of Science University on Twitter with Word2Vec.
I tried to improve the efficiency of daily work with Python
I wrote the basic operation of Pandas with Jupyter Lab (Part 2)
I implemented Attention Seq2Seq with PyTorch
I liked the tweet with python. ..
Implementation of Dijkstra's algorithm with python
I implemented the K-means method (clustering method)
I tried to make Othello AI with tensorflow without understanding the theory of machine learning ~ Battle Edition ~
I replaced the numerical calculation of Python with Rust and compared the speed
Calculate the shortest route of a graph with Dijkstra's algorithm and Python
I tried to get the authentication code of Qiita API with Python.
I vectorized the chord of the song with word2vec and visualized it with t-SNE
I want to express my feelings with the lyrics of Mr. Children
I tried to automatically extract the movements of PES players with software
I tried to analyze the negativeness of Nono Morikubo. [Compare with Posipa]
I made a GAN with Keras, so I made a video of the learning process.
I tried to streamline the standard role of new employees with Python
I tried to visualize the text of the novel "Weathering with You" with WordCloud
I want to stop the automatic deletion of the tmp area with RHEL7
I tried to get the movie information of TMDb API with Python
I made a mistake in fetching the hierarchy with MultiIndex of pandas
I measured the speed of list comprehension, for and while with python2.7.
I tried to predict the behavior of the new coronavirus with the SEIR model.
I checked the contents of docker volume
I tried the asynchronous server of Django 3.0
I implemented Shake-Shake Regularization (ShakeNet) with PyTorch
Compute the partition function with the sum-product algorithm
Align the size of the colorbar with matplotlib
I checked the options of copyMakeBorder of OpenCV
Algorithm Gymnastics 24 Middle of the Linked List
I summarized the folder structure of Flask
Check the existence of the file with python
Algorithm learned with Python 8th: Evaluation of algorithm
[Scikit-learn] I played with the ROC curve
Search the maze with the python A * algorithm
I didn't know the basics of Python
The third night of the loop with for