codingame.com tron bot

tron_bot.cpp

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <array>
#include <algorithm>
#include <cmath>

using namespace std;

#define null (-1)

#define RIGHT (0)
#define UP (1)
#define LEFT (2)
#define DOWN (3)

#define WIDTH (30)
#define HEIGHT (20)

#define DEPTH 2

typedef struct {
    short x, y;
} Point;

typedef struct {
    Point p;
    short owner;
} VP; // Voronoi point

typedef struct {
    Point p;
    short dir;
} Player;

Point operator+(const Point a, const Point b) {
    return {a.x + b.x, a.y + b.y};
}
Point operator-(const Point a, const Point b) {
    return {a.x - b.x, a.y - b.y};
}
bool operator==(const Point a, const Point b) {
    return a.x == b.x and a.y == b.y;
}

ostream& operator<<(ostream& o, const Point p) {
    return o << "p{ " << p.x << ", " << p.y << " }";
}
template <typename T>
ostream& operator<<(ostream& o, const vector<T> v) {
    o << "v{ ";
    for (T elem : v)
        o << elem << ' ';
    o << '}';
    return o;
}

const array<Point, 4> dirs = {{
    {+1, 0}, // R
    {0, -1}, // U
    {-1, 0}, // L
    {0, +1}, // D
}};

const array<string, 4> str_dirs = {{ "RIGHT", "UP", "LEFT", "DOWN" }};

static int P; // your player number (0 to 3).
static int N; // total number of players (2 to 4).
static vector<Player> players;
static vector<vector<short>> grid;
static deque<short> moves;

void show_grid() {  // DEBUG
    for (auto elem : grid)
        cerr << elem << endl;
    cerr << endl;
}
void show_vnoi(const vector<vector<short>>& vnoi) {  // DEBUG
    for (auto elem : vnoi)
        cerr << elem << endl;
    cerr << endl;
}

inline int dist(const Point a, const Point b) // manhattan
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}

array<short, 3> genPossibleDirs(const vector<Player>& _players) 
{
    return array<short, 3> {{
        (_players[P].dir - 1) % dirs.size(), 
        _players[P].dir,
        (_players[P].dir + 1) % dirs.size(),
    }};
}

// Returns area of self player
int flood_fill(vector<vector<short>>& vnoi, const vector<Player>& _players) 
{
    int area = 0;
    deque<VP> q;
    
    for (int i = 0; i < N; i++) {
        if (players[i].p == (Point){-1, -1}) continue;
        q.push_back({_players[i].p, i});
    }
    
    while (not q.empty()) {
        VP cp = q.front(); q.pop_front();
        
        if (vnoi[cp.p.y][cp.p.x] != null) continue;
        
        vnoi[cp.p.y][cp.p.x] = cp.owner;
        
        if (cp.owner == P) area++;
        
        for (int i = 0; i < dirs.size(); i++) {
            Point np = cp.p + dirs[i];
            
            if (np.x < 0 or np.y < 0 or np.x >= WIDTH or np.y >= HEIGHT or grid[np.y][np.x] != null)
                continue;
                
            q.push_back({np, cp.owner});
        }
    }
    
    return area;
}

int gen_voronoi(const vector<Player>& _players, int depth) 
{
    vector<vector<short>> vnoi = vector<vector<short>>(HEIGHT, vector<short>(WIDTH, null));
    int area = flood_fill(vnoi, _players);
    
    if (depth > 1) {
        array<short, 3> possibleDirs = genPossibleDirs(_players);
        
        for (int i = 0; i < possibleDirs.size(); i++) {
            vector<Player> __players__ = _players;
            __players__[P].p = __players__[P].p + dirs[possibleDirs[i]];
            Point p = __players__[P].p;
            
            if (p.x < 0 or p.y < 0 or p.x >= WIDTH or p.y >= HEIGHT or grid[p.y][p.x] != null)
                continue;
    
            area += gen_voronoi(__players__, depth - 1);
        }
    }
    
    return area;
}

int choice_dir() 
{
    int area = 0;
    int bestDirIndex = null;

    array<short, 3> possibleDirs = genPossibleDirs(players);
    
    for (int i = 0; i < possibleDirs.size(); i++) {
        vector<Player> _players = players;
        
        _players[P].p = _players[P].p + dirs[possibleDirs[i]];
        Point p = _players[P].p;
        
        if (p.x < 0 or p.y < 0 or p.x >= WIDTH or p.y >= HEIGHT or grid[p.y][p.x] != null)
            continue;

        int newArea = gen_voronoi(_players, DEPTH);
        
        if (bestDirIndex == null or newArea > area) {
            area = newArea;
            bestDirIndex = possibleDirs[i];
        }
    }
    return bestDirIndex;
}

int main()
{
    // cerr << showpos; // Show + sign, just for alignment with negative
    grid = vector<vector<short>>(HEIGHT, vector<short>(WIDTH, null));
    moves = deque<short>();
    
    
    while (1) {
        cin >> N >> P; cin.ignore();
        
        if (players.size() < N)
            players = vector<Player>(N, {{null, null}, null});
            
        cerr << "N: " << N << endl;
        
        for (int i = 0; i < N; i++) {
            Point oldPos = players[i].p;
            int x0; // starting X coordinate of lightcycle (or -1)
            int y0; // starting Y coordinate of lightcycle (or -1)
            cin >> x0 >> y0 >> players[i].p.x >> players[i].p.y; cin.ignore();
            
            if (i == P) {
                cerr << "ME: " << P << " " << players[i].p << endl;
            }
            
            if (players[i].p == (Point){-1, -1}) continue; // Player died

            grid[players[i].p.y][players[i].p.x] = i;
            if (oldPos.x != null) {
                cerr << players[i].p - oldPos << endl;
                players[i].dir = find(dirs.begin(), dirs.end(), players[i].p - oldPos) - dirs.begin(); 
            }
            
            cerr << i << " " << players[i].p << " " 
                << players[i].dir << " " 
                << (players[i].dir != -1 ? str_dirs[players[i].dir] : "") << endl;
        }

        if (moves.empty())
            moves.push_back(choice_dir());
        
        cerr << "DIR: " << moves.front() << endl;
        
        if (moves.front() == -1) return 0; // Can't move
        
        players[P].dir = moves.front();
        cout << str_dirs[moves.front()] << endl; // A single line with UP, DOWN, LEFT or RIGHT
        moves.pop_front();
    }
}

It's not finished, currently it has some bugs, but it's starting to work.