HERZLICHEN GLÜCKWUNSCH an @kuroineko für den besten Beitrag und den Gewinn der 200 Bounty von @TheBestOne (exzellentes Sportsgeist!).

Schreiben Sie ein Programm, um so viele Bilder wie möglich einzufärben, bevor Oppositionsprogramme dies tun.

Regeln in Kürze

• Ihr Programm erhält ein Bild, Ihre Farbe und die Ganzzahl N.
• In jeder Runde erhalten Sie Pixel-Updates von anderen Programmen und werden nach Ihren N Updates gefragt.
• Sie können alle weißen Pixel aktualisieren, die neben einem Pixel Ihrer Farbe liegen.
• Das Programm, das die meisten Pixel hinzugefügt hat, gewinnt.

Regeln im Detail

Ihr Programm erhält einen PNG-Bilddateinamen, eine Standardfarbe und eine Nummer N. Die Nummer N gibt die maximale Anzahl von Pixeln an, die Ihr Programm in jeder Runde einfärben darf.

Beispiel: MyProg arena.png (255,0,0) 30

Das Eingabebild ist ein Rechteck mit Seiten zwischen 20 und 1000 Pixeln. Es besteht aus schwarzen, weißen und farbigen Pixeln. Ihr Programm wählt möglicherweise eine Folge von weißen Pixeln aus, die Sie selbst einfärben möchten, unter der Bedingung, dass jedes neue Pixel mindestens eines der vier Nachbarpixel Ihrer eigenen Farbe hat. Das Bild enthält zunächst mindestens ein Pixel Ihrer Farbe. Es kann auch Farbpixel enthalten, denen kein Programm zugewiesen ist. Der Alphakanal wird nicht verwendet.

Ihr Ziel ist es, Ihre Gegner zu blockieren und Ihre Farbe in so viele Pixel wie möglich zu schreiben.

In jeder Runde akzeptiert Ihr Programm 1 oder mehr Nachrichtenzeilen auf STDIN und schreibt eine Zeile mit Pixelkoordinaten auf STDOUT. Denken Sie daran, STDOUT als ungepuffert zuzuweisen, oder leeren Sie den STDOUT-Puffer in jeder Runde.

Die Reihenfolge der Spieler, die in jeder Runde aufgerufen werden, wird nach dem Zufallsprinzip festgelegt. Dies bedeutet, dass ein Gegner (oder Ihr Programm) 2 Runden hintereinander haben kann.

Ihrem Programm werden colour (N,N,N) chose X,Y X,Y ... X,YInformationsnachrichten gesendet, die die Pixel beschreiben, die von Player-Programmen ausgefüllt werden. Wenn ein Spieler keine oder keine gültigen Züge ausführt, wird keine Nachricht über die Züge dieses Spielers gesendet. Ihr Programm erhält auch eine Nachricht über Ihre eigenen akzeptierten Züge (wenn Sie mindestens einen gültigen Zug angegeben haben). Das Pixel 0,0 befindet sich in der oberen linken Ecke des Bildes.

Beim Empfang pick pixelsgibt Ihr Programm X,Y X,Y ... X,Ybis zu N Pixel aus (eine leere Zeichenfolge, die nur aus einem '\ n' besteht, ist zulässig). Die Pixel müssen in der Reihenfolge des Zeichnens sein. Wenn ein Pixel ungültig ist, wird es ignoriert und ist nicht im Bericht an die Spieler enthalten. Ihr Programm muss nach dem Start innerhalb von 2 Sekunden initialisiert werden, aber nur 0,1 Sekunden, um mit einer Antwort pro Runde zu antworten. Andernfalls wird diese Runde verpasst. Eine Pixelaktualisierung, die nach 0,1 Sekunden gesendet wird, zeichnet einen Fehler auf. Nach 5 Fehlern wird Ihr Programm angehalten und es werden keine Aktualisierungen oder pick pixelsAnfragen gesendet .

Wenn das Richterprogramm von jedem nicht gesperrten Spielerprogramm eine leere oder ungültige Pixelauswahl erhält, wird das Bild als vollständig betrachtet und Programme erhalten die Nachricht "exit". Programme müssen nach Erhalt von "exit" beendet werden.

Wertung

Der Richter erhält Punkte, wenn das Bild vollständig ist. Ihre Punktzahl ist die Anzahl der aktualisierten Pixel geteilt durch die durchschnittliche Pixelerfassung dieser Runde, ausgedrückt als Prozentsatz.

Die Anzahl der vom Player zum Bild hinzugefügten Pixel beträgt A. Die Gesamtanzahl der von allen P-Playern hinzugefügten Pixel beträgt T. avg = T/P score = 100*A/avg

Punkte veröffentlichen

Ein Referenzgegner "The Blob" wird gegeben. Benenne für jede Antwort deinen Bot mit einem Namen, einer Sprache und deiner Punktzahl (Durchschnitt von Arena 1 bis 4) gegen den Referenzgegner. Ein Bild oder eine Animation von einem Ihrer Schlachten wäre auch gut. Der Gewinner ist das Programm mit der höchsten Punktzahl gegen den Referenz-Bot.

Wenn sich der Blob als zu leicht zu besiegen erweist, füge ich möglicherweise eine zweite Runde mit einem stärkeren Referenzgegner hinzu.

Sie können auch gerne mit 4 oder mehr Player-Programmen experimentieren. Sie können Ihren Bot auch mit anderen Bots testen, die als Antworten veröffentlicht wurden.

Der Richter

Das Judge-Programm benötigt die gemeinsame Python Imaging Library (PIL) und sollte unter Linux einfach von Ihrem Betriebssystem-Paket-Manager aus zu installieren sein. Ich habe einen Bericht, dass PIL unter Windows 7 nicht mit 64-Bit-Python funktioniert. Überprüfen Sie daher, ob PIL für Sie funktioniert, bevor Sie mit dieser Herausforderung beginnen (aktualisiert am 29.01.2015).

#!/usr/bin/env python
# Judge Program for Image Battle challenge on PPCG.
# Runs on Python 2.7 on Ubuntu Linux. May need edits for other platforms.
# V1.0 First release.
# V1.1 Added Java support
# V1.2 Added Java inner class support
# usage: judge cfg.py
import sys, re, random, os, shutil, subprocess, datetime, time, signal
from PIL import Image

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def place(loc, colour):
    # if valid, place colour at loc and return True, else False
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        if any(pix[p]==colour for p in plist if 0<=p[0]<W and 0<=p[1]<H):
            pix[loc] = colour
            return True
    return False

def updateimage(image, msg, bot):
    if not re.match(r'(\s*\d+,\d+)*\s*', msg):
        return []
    plist = [tuple(int(v) for v in pr.split(',')) for pr in msg.split()]
    plist = plist[:PIXELBATCH]
    return [p for p in plist if place(p, bot.colour)]

class Bot:
    botlist = []
    def __init__(self, name, interpreter=None, colour=None):
        self.prog = name
        self.botlist.append(self)
        callarg = re.sub(r'\.class$', '', name)  # Java fix
        self.call = [interpreter, callarg] if interpreter else [callarg]
        self.colour = colour
        self.colstr = str(colour).replace(' ', '')
        self.faults = 0
        self.env = 'env%u' % self.botlist.index(self)
        try: os.mkdir(self.env)
        except: pass
        if name.endswith('.class'): # Java inner class fix
            rootname = re.sub(r'\.class$', '', name)
            for fn in os.listdir('.'):
                if fn.startswith(rootname) and fn.endswith('.class'):
                    shutil.copy(fn, self.env)
        else:
            shutil.copy(self.prog, self.env)
        shutil.copy(imagename, self.env)
        os.chdir(self.env)
        args = self.call + [imagename, self.colstr, `PIXELBATCH`]
        self.proc = subprocess.Popen(args, stdin=subprocess.PIPE, 
            stdout=subprocess.PIPE, stderr=subprocess.PIPE)
        os.chdir('..')
    def send(self, msg):
        if self.faults < FAULTLIMIT:
            self.proc.stdin.write(msg + '\n')
            self.proc.stdin.flush()
    def read(self, timelimit):
        if self.faults < FAULTLIMIT:
            start = time.time()
            inline = self.proc.stdout.readline()
            if time.time() - start > timelimit:
                self.faults += 1
                inline = ''
            return inline.strip()
    def exit(self):
        self.send('exit')

from cfg import *
for i, (prog, interp) in enumerate(botspec):
    Bot(prog, interp, colourspec[i])

image = Image.open(imagename)
pix = image.load()
W,H = image.size

time.sleep(INITTIME)
total = 0
for turn in range(1, MAXTURNS+1):
    random.shuffle(Bot.botlist)
    nullbots = 0
    for bot in Bot.botlist:
        bot.send('pick pixels')
        inmsg = bot.read(TIMELIMIT)
        newpixels = updateimage(image, inmsg, bot)
        total += len(newpixels)
        if newpixels:
            pixtext = ' '.join('%u,%u'%p for p in newpixels)
            msg = 'colour %s chose %s' % (bot.colstr, pixtext)
            for msgbot in Bot.botlist:
                msgbot.send(msg)
        else:
            nullbots += 1
    if nullbots == len(Bot.botlist):
        break
    if turn % 100 == 0: print 'Turn %s done %s pixels' % (turn, total)
for msgbot in Bot.botlist:
    msgbot.exit()

counts = dict((c,f) for f,c in image.getcolors(W*H))
avg = 1.0 * sum(counts.values()) / len(Bot.botlist)
for bot in Bot.botlist:
    score = 100 * counts[bot.colour] / avg
    print 'Bot %s with colour %s scored %s' % (bot.prog, bot.colour, score)
image.save(BATTLE+'.png')

Beispielkonfiguration - cfg.py

BATTLE = 'Green Blob vs Red Blob'
MAXTURNS = 20000
PIXELBATCH = 10
INITTIME = 2.0
TIMELIMIT = 0.1
FAULTLIMIT = 5

imagename = 'arena1.png'

colourspec = (0,255,0), (255,0,0)

botspec = [
    ('blob.py', 'python'),
    ('blob.py', 'python'),
    ]

Der Blob - der Referenzgegner

# Blob v1.0 - A reference opponent for the Image Battle challenge on PPCG.
import sys, os
from PIL import Image

image = Image.open(sys.argv[1])
pix = image.load()
W,H = image.size
mycolour = eval(sys.argv[2])
pixbatch = int(sys.argv[3])

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def canchoose(loc, colour):
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        if any(pix[p]==colour for p in plist if 0<=p[0]<W and 0<=p[1]<H):
            return True
    return False

def near(loc):
    plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
    pboard = [p for p in plist if 0<=p[0]<W and 0<=p[1]<H]
    return [p for p in pboard if pix[p] == (255,255,255)]

def updateimage(image, msg):
    ctext, colourtext, chose, points = msg.split(None, 3)
    colour = eval(colourtext)
    plist = [tuple(int(v) for v in pr.split(',')) for pr in points.split()]
    for p in plist:
        pix[p] = colour
        skin.discard(p)
        if colour == mycolour:
            for np in near(p):
                skin.add(np)

board = [(x,y) for x in range(W) for y in range(H)]
skin = set(p for p in board if canchoose(p, mycolour))

while 1:
    msg = sys.stdin.readline()
    if msg.startswith('colour'):
        updateimage(image, msg.strip())
    if msg.startswith('pick'):
        plen = min(pixbatch, len(skin))
        moves = [skin.pop() for i in range(plen)]
        movetext = ' '.join('%u,%u'%p for p in moves)
        sys.stdout.write(movetext + '\n')
        sys.stdout.flush()
    if msg.startswith('exit'):
        break

image.save('blob.png')

Arena 1

Arena 2

Arena 3

Arena 4

Ein Beispiel Battle - Blob vs Blob

Dieser Kampf hatte ein vorhersehbares Ergebnis:

Bot blob.py with colour (255, 0, 0) scored 89.2883333333
Bot blob.py with colour (0, 255, 0) scored 89.365

ColorFighter - C ++ - isst ein paar Schlucker zum Frühstück

BEARBEITEN

• den Code aufgeräumt
• fügte eine einfache aber effektive Optimierung hinzu
• einige GIF-Animationen hinzugefügt

Gott, ich hasse Schlangen (tu einfach so, als wären sie Spinnen, Indy)

Eigentlich liebe ich Python. Ich wünschte, ich wäre weniger faul und hätte angefangen, es richtig zu lernen, das ist alles.

Trotzdem musste ich mich mit der 64-Bit-Version dieser Schlange herumschlagen, um den Richter zum Laufen zu bringen. PIL mit der 64-Bit-Version von Python unter Win7 zum Laufen zu bringen, erfordert mehr Geduld, als ich bereit war, mich dieser Herausforderung zu widmen. Am Ende bin ich (schmerzhaft) auf die Win32-Version umgestiegen.

Außerdem stürzt der Richter häufig schwer ab, wenn ein Bot zu langsam ist, um zu reagieren.
Da ich kein Python-Kenner bin, habe ich es nicht behoben, aber es hat mit dem Lesen einer leeren Antwort nach einem Timeout auf stdin zu tun.

Eine kleine Verbesserung wäre, die stderr-Ausgabe für jeden Bot in eine Datei zu legen. Dies würde die Nachverfolgung für das Post-Mortem-Debugging erleichtern.

Abgesehen von diesen kleinen Problemen fand ich den Richter sehr einfach und angenehm zu bedienen.
Ein dickes Lob für eine weitere erfinderische und unterhaltsame Herausforderung.

Der Code

#define _CRT_SECURE_NO_WARNINGS // prevents Microsoft from croaking about the safety of scanf. Since every rabid Russian hacker and his dog are welcome to try and overflow my buffers, I could not care less.
#include "lodepng.h"
#include <vector>
#include <deque>
#include <iostream>
#include <sstream>
#include <cassert>   // paranoid android
#include <cstdint>   // fixed size types
#include <algorithm> // min max

using namespace std;

// ============================================================================
// The less painful way I found to teach C++ how to handle png images
// ============================================================================
typedef unsigned tRGB;
#define RGB(r,g,b) (((r) << 16) | ((g) << 8) | (b))
class tRawImage {
public:
    unsigned w, h;

    tRawImage(unsigned w=0, unsigned h=0) : w(w), h(h), data(w*h * 4, 0) {}
    void read(const char* filename) { unsigned res = lodepng::decode(data, w, h, filename); assert(!res);  }
    void write(const char * filename)
    {
        std::vector<unsigned char> png;
        unsigned res = lodepng::encode(png, data, w, h, LCT_RGBA); assert(!res);
        lodepng::save_file(png, filename);
    }
    tRGB get_pixel(int x, int y) const
    {
        size_t base = raw_index(x,y);
        return RGB(data[base], data[base + 1], data[base + 2]);
    }
    void set_pixel(int x, int y, tRGB color)
    {
        size_t base = raw_index(x, y);
        data[base+0] = (color >> 16) & 0xFF;
        data[base+1] = (color >>  8) & 0xFF;
        data[base+2] = (color >> 0) & 0xFF;
        data[base+3] = 0xFF; // alpha
    }
private:
    vector<unsigned char> data;
    void bound_check(unsigned x, unsigned y) const { assert(x < w && y < h); }
    size_t raw_index(unsigned x, unsigned y) const { bound_check(x, y); return 4 * (y * w + x); }
};

// ============================================================================
// coordinates
// ============================================================================
typedef int16_t tCoord;

struct tPoint {
    tCoord x, y;
    tPoint operator+  (const tPoint & p) const { return { x + p.x, y + p.y }; }
};

typedef deque<tPoint> tPointList;

// ============================================================================
// command line and input parsing
// (in a nice airtight bag to contain the stench of C++ string handling)
// ============================================================================
enum tCommand {
    c_quit,
    c_update,
    c_play,
};

class tParser {
public:
    tRGB color;
    tPointList points;

    tRGB read_color(const char * s)
    {
        int r, g, b;
        sscanf(s, "(%d,%d,%d)", &r, &g, &b);
        return RGB(r, g, b);
    }

    tCommand command(void)
    {
        string line;
        getline(cin, line);

        string cmd = get_token(line);
        points.clear();

        if (cmd == "exit") return c_quit;
        if (cmd == "pick") return c_play;

        // even more convoluted and ugly than the LEFT$s and RIGHT$s of Apple ][ basic...
        if (cmd != "colour")
        {
            cerr << "unknown command '" << cmd << "'\n";
            exit(0);
        }
        assert(cmd == "colour");
        color = read_color(get_token(line).c_str());
        get_token(line); // skip "chose"
        while (line != "")
        {
            string coords = get_token(line);
            int x = atoi(get_token(coords, ',').c_str());
            int y = atoi(coords.c_str());
            points.push_back({ x, y });
        }
        return c_update;
    }

private:
    // even more verbose and inefficient than setting up an ADA rendezvous...
    string get_token(string& s, char delimiter = ' ')
    {
        size_t pos = 0;
        string token;
        if ((pos = s.find(delimiter)) != string::npos)
        {
            token = s.substr(0, pos);
            s.erase(0, pos + 1);
            return token;
        }
        token = s; s.clear(); return token;
    }
};

// ============================================================================
// pathing
// ============================================================================
class tPather {

public:
    tPather(tRawImage image, tRGB own_color)
        : arena(image)
        , w(image.w)
        , h(image.h)
        , own_color(own_color)
        , enemy_threat(false)
    {
        // extract colored pixels and own color areas
        tPointList own_pixels;
        color_plane[neutral].resize(w*h, false);
        color_plane[enemies].resize(w*h, false);
        for (size_t x = 0; x != w; x++)
        for (size_t y = 0; y != h; y++)
        {
            tRGB color = image.get_pixel(x, y);
            if (color == col_white) continue;
            plane_set(neutral, x, y);
            if (color == own_color) own_pixels.push_back({ x, y }); // fill the frontier with all points of our color
        }

        // compute initial frontier
        for (tPoint pixel : own_pixels)
        for (tPoint n : neighbour)
        {
            tPoint pos = pixel + n;
            if (!in_picture(pos)) continue;
            if (image.get_pixel(pos.x, pos.y) == col_white)
            {
                frontier.push_back(pixel);
                break;
            }
        }
    }

    tPointList search(size_t pixels_required)
    {
        // flood fill the arena, starting from our current frontier
        tPointList result;
        tPlane closed;
        static tCandidate pool[max_size*max_size]; // fastest possible garbage collection
        size_t alloc;
        static tCandidate* border[max_size*max_size]; // a FIFO that beats a deque anytime
        size_t head, tail;
        static vector<tDistance>distance(w*h); // distance map to be flooded
        size_t filling_pixels = 0; // end of game  optimization

    get_more_results:

        // ready the distance map for filling
        distance.assign(w*h, distance_max);

        // seed our flood fill with the frontier
        alloc = head = tail = 0;
        for (tPoint pos : frontier)
        {
            border[tail++] = new (&pool[alloc++]) tCandidate (pos);
        }

        // set already explored points
        closed = color_plane[neutral]; // that's one huge copy

        // add current result
        for (tPoint pos : result)
        {
            border[tail++] = new (&pool[alloc++]) tCandidate(pos);
            closed[raw_index(pos)] = true;
        }

        // let's floooooood!!!!
        while (tail > head && pixels_required > filling_pixels)
        {
            tCandidate& candidate = *border[head++];
            tDistance  dist = candidate.distance;
            distance[raw_index(candidate.pos)] = dist++;
            for (tPoint n : neighbour)
            {
                tPoint pos = candidate.pos + n;
                if (!in_picture (pos)) continue;
                size_t index = raw_index(pos);
                if (closed[index]) continue;
                if (color_plane[enemies][index])
                {
                    if (dist == (distance_initial + 1)) continue; // already near an enemy pixel

                    // reached the nearest enemy pixel
                    static tPoint trail[max_size * max_size / 2]; // dimensioned as a 1 pixel wide spiral across the whole map
                    size_t trail_size = 0;

                    // walk back toward the frontier
                    tPoint walker = candidate.pos;
                    tDistance cur_d = dist;
                    while (cur_d > distance_initial)
                    {
                        trail[trail_size++] = walker;
                        tPoint next_n;
                        for (tPoint n : neighbour)
                        {
                            tPoint next = walker + n;
                            if (!in_picture(next)) continue;
                            tDistance prev_d = distance[raw_index(next)];
                            if (prev_d < cur_d)
                            {
                                cur_d = prev_d;
                                next_n = n;
                            }
                        }
                        walker = walker + next_n;
                    }

                    // collect our precious new pixels
                    if (trail_size > 0)
                    {
                        while (trail_size > 0)
                        {
                            if (pixels_required-- == 0) return result;       // ;!; <-- BRUTAL EXIT
                            tPoint pos = trail[--trail_size];
                            result.push_back (pos);
                        }
                        goto get_more_results; // I could have done a loop, but I did not bother to. Booooh!!!
                    }
                    continue;
                }

                // on to the next neighbour
                closed[index] = true;
                border[tail++] = new (&pool[alloc++]) tCandidate(pos, dist);
                if (!enemy_threat) filling_pixels++;
            }
        }

        // if all enemies have been surrounded, top up result with the first points of our flood fill
        if (enemy_threat) enemy_threat = pixels_required == 0;
        tPathIndex i = frontier.size() + result.size();
        while (pixels_required--) result.push_back(pool[i++].pos);
        return result;
    }

    // tidy up our map and frontier while other bots are thinking
    void validate(tPointList moves)
    {
        // report new points
        for (tPoint pos : moves)
        {
            frontier.push_back(pos);
            color_plane[neutral][raw_index(pos)] = true;
        }

        // remove surrounded points from frontier
        for (auto it = frontier.begin(); it != frontier.end();) 
        {
            bool in_frontier = false;
            for (tPoint n : neighbour)
            {
                tPoint pos = *it + n;
                if (!in_picture(pos)) continue;
                if (!(color_plane[neutral][raw_index(pos)] || color_plane[enemies][raw_index(pos)]))
                {
                    in_frontier = true;
                    break;
                }
            }
            if (!in_frontier) it = frontier.erase(it); else ++it; // the magic way of deleting an element without wrecking your iterator
        }       
    }

    // handle enemy move notifications
    void update(tRGB color, tPointList points)
    {
        assert(color != own_color);

        // plot enemy moves
        enemy_threat = true;
        for (tPoint p : points) plane_set(enemies, p);

        // important optimization here :
        /*
         * Stop 1 pixel away from the enemy to avoid wasting moves in dogfights.
         * Better let the enemy gain a few more pixels inside the surrounded region
         * and use our precious moves to get closer to the next threat.
         */
        for (tPoint p : points) for (tPoint n : neighbour) plane_set(enemies, p+n);

        // if a new enemy is detected, gather its initial pixels
        for (tRGB enemy : known_enemies) if (color == enemy) return;
        known_enemies.push_back(color);
        tPointList start_areas = scan_color(color);
        for (tPoint p : start_areas) plane_set(enemies, p);
    }

private:
    typedef uint16_t tPathIndex;

    typedef uint16_t tDistance;
    static const tDistance distance_max     = 0xFFFF;
    static const tDistance distance_initial = 0;

    struct tCandidate {
        tPoint pos;
        tDistance distance;
        tCandidate(){} // must avoid doing anything in this constructor, or pathing will slow to a crawl
        tCandidate(tPoint pos, tDistance distance = distance_initial) : pos(pos), distance(distance) {}
    };

    // neighbourhood of a pixel
    static const tPoint neighbour[4];

    // dimensions
    tCoord w, h; 
    static const size_t max_size = 1000;

    // colors lookup
    const tRGB col_white = RGB(0xFF, 0xFF, 0xFF);
    const tRGB col_black = RGB(0x00, 0x00, 0x00);
    tRGB own_color;
    const tRawImage arena;
    tPointList scan_color(tRGB color)
    {
        tPointList res;
        for (size_t x = 0; x != w; x++)
        for (size_t y = 0; y != h; y++)
        {
            if (arena.get_pixel(x, y) == color) res.push_back({ x, y });
        }
        return res;
    }

    // color planes
    typedef vector<bool> tPlane;
    tPlane color_plane[2];
    const size_t neutral = 0;
    const size_t enemies = 1;
    bool plane_get(size_t player, tPoint p) { return plane_get(player, p.x, p.y); }
    bool plane_get(size_t player, size_t x, size_t y) { return in_picture(x, y) ? color_plane[player][raw_index(x, y)] : false; }
    void plane_set(size_t player, tPoint p) { plane_set(player, p.x, p.y); }
    void plane_set(size_t player, size_t x, size_t y) { if (in_picture(x, y)) color_plane[player][raw_index(x, y)] = true; }
    bool in_picture(tPoint p) { return in_picture(p.x, p.y); }
    bool in_picture(int x, int y) { return x >= 0 && x < w && y >= 0 && y < h; }
    size_t raw_index(tPoint p) { return raw_index(p.x, p.y); }
    size_t raw_index(size_t x, size_t y) { return y*w + x; }

    // frontier
    tPointList frontier;

    // register enemies when they show up
    vector<tRGB>known_enemies;

    // end of game optimization
    bool enemy_threat;
};

// small neighbourhood
const tPoint tPather::neighbour[4] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

// ============================================================================
// main class
// ============================================================================
class tGame {
public:
    tGame(tRawImage image, tRGB color, size_t num_pixels)
        : own_color(color)
        , response_len(num_pixels)
        , pather(image, color)
    {}

    void main_loop(void)
    {
        // grab an initial answer in case we're playing first
        tPointList moves = pather.search(response_len);
        for (;;)
        {
            ostringstream answer;
            size_t        num_points;
            tPointList    played;

            switch (parser.command())
            {
            case c_quit: 
                return;

            case c_play:
                // play as many pixels as possible
                if (moves.size() < response_len) moves = pather.search(response_len);
                num_points = min(moves.size(), response_len);
                for (size_t i = 0; i != num_points; i++)
                {
                    answer << moves[0].x << ',' << moves[0].y;
                    if (i != num_points - 1) answer << ' '; // STL had more important things to do these last 30 years than implement an implode/explode feature, but you can write your own custom version with exception safety and in-place construction. It's a bit of work, but thanks to C++ inherent genericity you will be able to extend it to giraffes and hippos with a very manageable amount of code refactoring. It's not anyone's language, your C++, eh. Just try to implode hippos in Python. Hah!
                    played.push_back(moves[0]);
                    moves.pop_front();
                }
                cout << answer.str() << '\n';

                // now that we managed to print a list of points to stdout, we just need to cleanup the mess
                pather.validate(played);
                break;

            case c_update:
                if (parser.color == own_color) continue; // hopefully we kept track of these already
                pather.update(parser.color, parser.points);
                moves = pather.search(response_len); // get cracking
                break;
            }
        }
    }

private:
    tParser parser;
    tRGB    own_color;
    size_t  response_len;
    tPather pather;
};

void main(int argc, char * argv[])
{
    // process command line
    tRawImage raw_image; raw_image.read (argv[1]);
    tRGB my_color = tParser().read_color(argv[2]);
    int num_pixels               = atoi (argv[3]);

    // init and run
    tGame game (raw_image, my_color, num_pixels);
    game.main_loop();
}

Erstellen der ausführbaren Datei

Ich habe LODEpng.cpp und LODEpng.h zum Lesen von PNG-Bildern verwendet.
Auf die einfachste Art und Weise brachte ich dieser verzögerten C ++ - Sprache bei, wie man ein Bild liest, ohne ein halbes Dutzend Bibliotheken erstellen zu müssen.
Kompilieren und verlinken Sie einfach LODEpng.cpp zusammen mit dem Main und Bob ist Ihr Onkel.

Ich habe mit MSVC2013 kompiliert, aber da ich nur ein paar STL-Basiscontainer (Deque und Vektoren) verwendet habe, funktioniert es möglicherweise mit gcc (wenn Sie Glück haben).
Wenn nicht, probiere ich vielleicht einen MinGW-Build aus, aber ehrlich gesagt habe ich keine Lust mehr auf C ++ - Portabilitätsprobleme.

Ich habe in meinen Tagen ziemlich viel portables C / C ++ gemacht (auf exotischen Compilern für verschiedene 8- bis 32-Bit-Prozessoren sowie auf SunOS, Windows von 3.11 bis Vista und Linux von den Anfängen bis zu Ubuntu, das Zebra gurrt, oder was auch immer, denke ich Ich habe eine ziemlich gute Vorstellung davon, was Portabilität bedeutet, aber zu der Zeit mussten die unzähligen Diskrepanzen zwischen der GNU- und der Microsoft-Interpretation der kryptischen und aufgeblähten Spezifikation des STL-Monsters nicht auswendig gelernt (oder entdeckt) werden.

Ergebnisse gegen Swallower

Wie es funktioniert

Im Kern handelt es sich um ein einfaches Brute-Force-Floodfill-Pathing.

Die Grenze der Farbe des Players (dh die Pixel, die mindestens einen weißen Nachbarn haben) wird als Ausgangswert für den klassischen Entfernungsüberschwemmungsalgorithmus verwendet.

Wenn ein Punkt die Nähe einer feindlichen Farbe erreicht, wird ein Rückwärtspfad berechnet, um eine Folge von Pixeln zu erzeugen, die sich zum nächsten feindlichen Punkt bewegen.

Der Vorgang wird wiederholt, bis genügend Punkte für eine Antwort der gewünschten Länge gesammelt wurden.

Diese Wiederholung ist unglaublich teuer, besonders wenn man in der Nähe des Feindes kämpft.
Jedes Mal, wenn eine Reihe von Pixeln gefunden wurde, die von der Grenze zu einem feindlichen Pixel führen (und wir brauchen mehr Punkte, um die Antwort zu vervollständigen), wird die Überflutungsfüllung von Anfang an überarbeitet und der neue Pfad zur Grenze hinzugefügt. Dies bedeutet, dass Sie möglicherweise 5 oder mehr Überflutungen durchführen müssen, um eine 10-Pixel-Antwort zu erhalten.

Wenn keine feindlichen Pixel mehr erreichbar sind, werden arbitratische Nachbarn der Grenzpixel ausgewählt.
Der Algorithmus führt zu einer eher ineffizienten Überflutung, dies geschieht jedoch erst, nachdem der Ausgang des Spiels entschieden wurde (dh es gibt kein neutrales Gebiet mehr, für das man kämpfen kann).
Ich habe es so optimiert, dass der Richter nicht ewig die Karte auffüllt, sobald der Wettbewerb abgeschlossen ist. In seinem gegenwärtigen Zustand ist die Ausführungszeit im Vergleich zum Richter selbst vernachlässigbar.

Da die feindlichen Farben zu Beginn nicht bekannt sind, wird das ursprüngliche Bild der Arena gespeichert, um die Startbereiche des Feindes zu kopieren, wenn dieser seinen ersten Zug macht.
Wenn der Code zuerst abgespielt wird, wird er einfach ein paar beliebige Pixel füllen.

Dies macht den Algorithmus in der Lage, eine beliebige Anzahl von Gegnern und möglicherweise sogar neue Gegner, die zu einem zufälligen Zeitpunkt eintreffen, oder Farben, die ohne Startbereich erscheinen, zu bekämpfen (obwohl dies absolut keinen praktischen Nutzen hat).

Die Behandlung von Feinden auf Basis von Farbe pro Farbe würde es auch ermöglichen, dass zwei Instanzen des Bots zusammenarbeiten (unter Verwendung von Pixelkoordinaten, um ein geheimes Erkennungszeichen zu übergeben).
Hört sich nach Spaß an, das werde ich wahrscheinlich ausprobieren :).

Berechnungsintensives Pathing wird ausgeführt, sobald neue Daten verfügbar sind (nach einer Bewegungsmeldung), und einige Optimierungen (die Grenzaktualisierung) werden unmittelbar nach einer Antwort ausgeführt (um während der anderen Bots-Runden so viel wie möglich zu berechnen) ).

Auch hier könnte es Möglichkeiten geben, subtilere Dinge zu tun, wenn es mehr als einen Gegner gibt (z. B. einen Rechenvorgang abzubrechen, wenn neue Daten verfügbar werden), aber ich sehe jedenfalls nicht, wo Multitasking erforderlich ist, solange der Algorithmus vorhanden ist Volllast arbeiten können.

Performance-Probleme

All dies funktioniert nicht ohne schnellen Datenzugriff (und mehr Rechenleistung als das gesamte Appolo-Programm, dh Ihr durchschnittlicher PC, wenn Sie mehr als ein paar Tweets posten).

Die Geschwindigkeit ist stark vom Compiler abhängig. Normalerweise schlägt GNU Microsoft um 30% (das ist die magische Zahl, die ich bei drei anderen Code-Herausforderungen im Zusammenhang mit Pfaden bemerkt habe), aber dieser Kilometerstand kann natürlich variieren.

Der Code in seinem aktuellen Zustand bringt Arena 4 kaum ins Schwitzen. Der Windows-Leistungsmesser meldet eine CPU-Auslastung von 4 bis 7%, sodass er in der Lage sein sollte, mit einer 1000x1000-Karte innerhalb der Reaktionszeit von 100 ms fertig zu werden.

Das Herzstück eines jeden Pfadalgorithmus ist ein FIFO (möglicherweise priorisiert, aber nicht in diesem Fall), für das wiederum eine schnelle Elementzuweisung erforderlich ist.

Da das OP die Größe der Arena verbindlich einschränkte, habe ich einige Berechnungen angestellt und festgestellt, dass feste Datenstrukturen mit einer maximalen Größe (dh 1.000.000 Pixel) nicht mehr als ein paar Dutzend Megabyte verbrauchen, die Ihr durchschnittlicher PC zum Frühstück zu sich nimmt.
Unter Win7 und mit MSVC 2013 kompiliert, verbraucht der Code in Arena 4 ungefähr 14 MB, während die beiden Threads von Swallower mehr als 20 MB belegen.

Ich habe mit STL - Containern begonnen, um das Prototyping zu vereinfachen, aber STL hat den Code noch weniger lesbar gemacht, da ich nicht die Absicht hatte, eine Klasse zu erstellen, die jedes einzelne Datenbit kapselt, um die Verschleierung zu verbergen (ob das nun an meinen eigenen Unfähigkeiten liegt) Die Bewältigung des STL bleibt der Wertschätzung des Lesers überlassen.
Ungeachtet dessen war das Ergebnis so schrecklich langsam, dass ich zunächst dachte, ich würde versehentlich eine Debug-Version erstellen.

Ich denke, dies liegt zum einen an der unglaublich schlechten Microsoft-Implementierung der STL (wo zum Beispiel Vektoren und Bitsätze gebundene Prüfungen oder andere kryptische Operationen auf operator [] ausführen, die direkt gegen die Spezifikation verstoßen) und zum anderen am STL-Design selbst.

Ich könnte mit den grausamen Syntax- und Portabilitätsproblemen (z. B. Microsoft vs GNU) fertig werden, wenn die Leistungen vorhanden wären, aber dies ist sicherlich nicht der Fall.

Zum Beispiel dequeist es von Natur aus langsam, weil es viele Buchhaltungsdaten durcheinanderbringt, während es darauf wartet, dass der Anlass seine superschicke Größenänderung vornimmt, die mir gleichgültig ist.
Natürlich hätte ich einen benutzerdefinierten Allokator und andere benutzerdefinierte Vorlagenbits implementieren können, aber ein benutzerdefinierter Allokator allein kostet ein paar hundert Codezeilen und den größten Teil eines Tages, um zu testen, was mit dem Dutzend von Schnittstellen zu tun ist, die er implementieren muss, während a Die handgefertigte äquivalente Struktur ist ungefähr null Codezeilen (obwohl gefährlicher, aber der Algorithmus hätte nicht funktioniert, wenn ich nicht gewusst hätte - oder geglaubt hätte - was ich sowieso tat).

Also habe ich schließlich die STL-Container in unkritischen Teilen des Codes aufbewahrt und meinen eigenen brutalen Allokator und FIFO mit zwei Arrays von ca. 1970 und drei nicht signierten Shorts erstellt.

Schlucken den Schlucker

Wie der Autor bestätigte, werden die fehlerhaften Muster des Schluckers durch Verzögerungen zwischen den Benachrichtigungen über feindliche Bewegungen und Aktualisierungen des Pfad-Threads verursacht.
Der System-Perfmeter zeigt deutlich, dass der Pfad-Thread die ganze Zeit 100% CPU verbraucht, und die gezackten Muster treten auf, wenn sich der Fokus des Kampfes auf einen neuen Bereich verlagert. Dies wird auch bei den Animationen deutlich.

Eine einfache aber effektive Optimierung

Nachdem ich mir die epischen Luftkämpfe zwischen Swallower und meinem Kämpfer angeschaut hatte, fiel mir ein altes Sprichwort aus dem Go-Spiel ein: Verteidigung aus der Nähe, aber Angriff aus der Ferne.

Darin liegt Weisheit. Wenn Sie versuchen, sich zu sehr an Ihren Gegner zu halten, verschwenden Sie wertvolle Moves, um jeden möglichen Pfad zu blockieren. Im Gegenteil, wenn Sie nur einen Pixel entfernt bleiben, vermeiden Sie wahrscheinlich, kleine Lücken zu schließen, die nur sehr wenig zunehmen würden, und setzen Sie Ihre Schritte ein, um wichtigeren Bedrohungen entgegenzuwirken.

Um diese Idee umzusetzen, habe ich einfach die Züge eines Feindes verlängert (die 4 Nachbarn jedes Zuges als feindliches Pixel markiert).
Dadurch wird der Suchalgorithmus einen Pixel von der feindlichen Grenze entfernt gestoppt, sodass sich mein Kämpfer um einen Gegner bewegen kann, ohne in zu viele Luftkämpfe verwickelt zu werden.

Sie können die Verbesserung sehen
(obwohl alle Läufe nicht so erfolgreich sind, können Sie die viel glatteren Umrisse bemerken):

Tiefen-erster Blob vs. Blob

Sprache = Python (3.2)

Score = 111.475388276 153.34210035

Update: Verwenden Sie jetzt eine benutzerdefinierte SetKlasse, um die pop()Methode zum Erzeugen einer Art Rastermuster zu erhalten, die den Bereich, der zu Beginn abgedeckt wurde, drastisch verbessert und große Teile des Bildes vom Feind abschneidet. Hinweis: Ich verwende hierfür ein 12 x 12-Raster, das aus einer zufälligen Stichprobe von Rastergrößen die besten Ergebnisse für arena3 zu liefern schien (dasjenige, das vor dem Update die schlechteste Punktzahl erzielt hat). Es ist jedoch sehr wahrscheinlich, dass es optimaler ist Für die gegebene Auswahl von Arenen existiert eine Rastergröße.

Ich habe eine einfache Änderung am Referenz-Bot vorgenommen, um die Auswahl praktikabler Punkte zu erleichtern, die von möglichst wenigen eigenfarbigen Punkten begrenzt werden. Eine Verbesserung könnte darin bestehen, dass auch mögliche Punkte ausgewählt werden, die von so vielen feindlichen Punkten wie möglich begrenzt werden.

dfblob.py:

import sys, os
from PIL import Image

class RoomyIntPairHashSet:
    def __init__(self, firstMax, secondMax):
        self.m1 = firstMax
        self.m2 = secondMax
        self.set = [set() for i in range((firstMax - 1) * (secondMax - 1) + 1)]
        self.len = 0

    def add(self, tup):
        subset = self.set[self.gettuphash(tup)]
        self.len -= len(subset)
        subset.add(tup)
        self.len += len(subset)

    def discard(self, tup):
        subset = self.set[self.gettuphash(tup)]
        self.len -= len(subset)
        subset.discard(tup)
        self.len += len(subset)

    def pop(self):
        for s in self.set:
            if len(s) > 0:
                self.len -= 1
                return s.pop()
        return self.set[0].pop()

    def gettuphash(self, tup):
        return (tup[0] % self.m1) * (tup[1] % self.m2)

    def __len__(self):
        return self.len

gridhashwidth = 12
gridhashheight = 12
image = Image.open(sys.argv[1])
pix = image.load()
W,H = image.size
mycolour = eval(sys.argv[2])
pixbatch = int(sys.argv[3])

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def canchoose(loc, virtualneighbors, colour, num_neighbors):
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        actual_num_neighbors = 0
        for p in plist:
            if 0<=p[0]<W and 0<=p[1]<H and pix[p]==colour or p in virtualneighbors:
                actual_num_neighbors += 1
        return num_neighbors == actual_num_neighbors
    return False

def near(loc, exclude):
    plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
    pboard = [p for p in plist if 0<=p[0]<W and 0<=p[1]<H]
    return [p for p in pboard if pix[p] == (255,255,255) and p not in exclude]

def updateimage(image, msg):
    ctext, colourtext, chose, points = msg.split(None, 3)
    colour = eval(colourtext)
    plist = [tuple(int(v) for v in pr.split(',')) for pr in points.split()]
    for p in plist:
        pix[p] = colour
        for i in range(len(skins)):
            skins[i].discard(p)
        if colour == mycolour:
            for np in near(p, []):
                for j in range(len(skins)):
                    skins[j].discard(np)
                    if canchoose(np, [], mycolour, j + 1):
                        skins[j].add(np)


board = [(x,y) for x in range(W) for y in range(H)]
skins = []
for i in range(1, 1 + len(ORTH)):
    skin = RoomyIntPairHashSet(gridhashwidth, gridhashheight)
    skins.append(skin)
    for p in board:
        if canchoose(p, [], mycolour, i):
            skin.add(p)

while 1:
    msg = sys.stdin.readline()
    print("got message "+ msg, file=sys.stderr)
    if msg.startswith('colour'):
        print("updating image", file=sys.stderr)
        updateimage(image, msg.strip())
        print("updated image", file=sys.stderr)
    if msg.startswith('pick'):
        moves = []
        print("picking moves", file=sys.stderr)
        virtualskins = [RoomyIntPairHashSet(gridhashwidth, gridhashheight) for i in range(len(skins))]
        for i in range(pixbatch):
            for j in range(len(skins)):
                if len(virtualskins[j]) > 0 or len(skins[j]) > 0:
                    move = None
                    if len(virtualskins[j]) > 0:
                        move = virtualskins[j].pop()
                    else:
                        move = skins[j].pop()
                    moves.append(move)
                    print("picking move (%u,%u) " % move, file=sys.stderr)
                    for p in near(move, moves):
                        for k in range(len(skins)):
                            virtualskins[k].discard(p)
                            if canchoose(p, moves, mycolour, k + 1):
                                virtualskins[k].add(p)
                    break
        movetext = ' '.join('%u,%u'%p for p in moves)
        print("picked %u moves" % (len(moves)), file=sys.stderr)
        sys.stdout.write(movetext + '\n')
        sys.stdout.flush()
    if msg.startswith('exit') or len(msg) < 1:
        break

image.save('dfblob.png')

Der ursprüngliche Richter wurde leicht modifiziert, um mit Python 3.2 zu arbeiten (und den Bots eine grobe Protokollierungsfunktion hinzuzufügen + das Bild der Arena regelmäßig zu speichern, um Animationen zu erstellen):

import sys, re, random, os, shutil, subprocess, datetime, time, signal, io
from PIL import Image

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def place(loc, colour):
    # if valid, place colour at loc and return True, else False
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        if any(pix[p]==colour for p in plist if 0<=p[0]<W and 0<=p[1]<H):
            pix[loc] = colour
            return True
    return False

def updateimage(image, msg, bot):
    if not re.match(r'(\s*\d+,\d+)*\s*', msg):
        return []
    plist = [tuple(int(v) for v in pr.split(',')) for pr in msg.split()]
    plist = plist[:PIXELBATCH]
    return [p for p in plist if place(p, bot.colour)]

class Bot:
    botlist = []
    def __init__(self, name, interpreter=None, colour=None):
        self.prog = name
        self.botlist.append(self)
        callarg = re.sub(r'\.class$', '', name)
        self.call = [interpreter, callarg] if interpreter else [callarg]
        self.colour = colour
        self.colstr = str(colour).replace(' ', '')
        self.faults = 0
        self.env = 'env%u' % self.botlist.index(self)
        try: os.mkdir(self.env)
        except: pass
        shutil.copy(self.prog, self.env)
        shutil.copy(imagename, self.env)
        os.chdir(self.env)
        args = self.call + [imagename, self.colstr, str(PIXELBATCH)]
        errorfile = 'err.log'
        with io.open(errorfile, 'wb') as errorlog:
            self.proc = subprocess.Popen(args, stdin=subprocess.PIPE, 
                stdout=subprocess.PIPE, stderr=errorlog)
        os.chdir('..')
    def send(self, msg):
        if self.faults < FAULTLIMIT:
            self.proc.stdin.write((msg+'\n').encode('utf-8'))
            self.proc.stdin.flush()
    def read(self, timelimit):
        if self.faults < FAULTLIMIT:
            start = time.time()
            inline = self.proc.stdout.readline().decode('utf-8')
            if time.time() - start > timelimit:
                self.faults += 1
                inline = ''
            return inline.strip()
    def exit(self):
        self.send('exit')

from cfg import *
for i, (prog, interp) in enumerate(botspec):
    Bot(prog, interp, colourspec[i])

image = Image.open(imagename)
pix = image.load()
W,H = image.size
os.mkdir('results')

time.sleep(INITTIME)
total = 0
for turn in range(1, MAXTURNS+1):
    random.shuffle(Bot.botlist)
    nullbots = 0
    for bot in Bot.botlist:
        bot.send('pick pixels')
        inmsg = bot.read(TIMELIMIT)
        newpixels = updateimage(image, inmsg, bot)
        total += len(newpixels)
        if newpixels:
            pixtext = ' '.join('%u,%u'%p for p in newpixels)
            msg = 'colour %s chose %s' % (bot.colstr, pixtext)
            for msgbot in Bot.botlist:
                msgbot.send(msg)
        else:
            nullbots += 1
    if nullbots == len(Bot.botlist):
        break
    if turn % 100 == 0:
        print('Turn %s done %s pixels' % (turn, total))
        image.save("results/"+BATTLE+str(turn//100).zfill(3)+'.png')
for msgbot in Bot.botlist:
    msgbot.exit()

counts = dict((c,f) for f,c in image.getcolors(W*H))
avg = 1.0 * sum(counts.values()) / len(Bot.botlist)
for bot in Bot.botlist:
    score = 100 * counts[bot.colour] / avg
    print('Bot %s with colour %s scored %s' % (bot.prog, bot.colour, score))
image.save(BATTLE+'.png')

Die Arenaergebnisse folgen. Der dfblob bot erhielt für alle Arenen die rote Farbe.

Arena 1:

Bot dfblob.py with colour (255, 0, 0) scored 163.75666666666666
Bot blob.py with colour (0, 255, 0) scored 14.896666666666667

Arena 2:

Bot blob.py with colour (0, 255, 0) scored 17.65563547726219
Bot dfblob.py with colour (255, 0, 0) scored 149.57006774236964

Arena 3:

Bot blob.py with colour (0, 255, 0) scored 21.09758208782965
Bot dfblob.py with colour (255, 0, 0) scored 142.9732433108277

Arena 4:

Bot blob.py with colour (0, 255, 0) scored 34.443810082244205
Bot dfblob.py with colour (255, 0, 0) scored 157.0684236785121

Schlucker

Sprache = Java

Ergebnis = 162.3289512601408075 169.4020975612382575

Sucht nach Feinden und umgibt sie. Möglicherweise müssen Sie eine längere Frist festlegen. Könnte einiges verbessert werden. Druckt manchmal ungültige Pixel.

Update: Surrounds viel schneller. Verwendet einen anderen Thread zum Aktualisieren der Prioritäten. Gibt immer innerhalb von 0,1 Sekunden zurück. Die Punktzahl sollte nicht zu übertreffen sein, ohne zuzunehmen MAX_TURNS.

import javax.imageio.ImageIO;
import java.awt.*;
import java.awt.image.BufferedImage;
import java.io.BufferedReader;
import java.io.File;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.List;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.stream.Collectors;

public class Swallower {

    static final byte MY_TYPE = 1;
    static final byte BLANK_TYPE = 0;
    static final byte NEUTRAL_TYPE = 2;
    static final byte ENEMY_TYPE = 3;
    private static final int WHITE = Color.WHITE.getRGB();
    private static final int MAX_TIME = 50;
    private final int color;
    private final int N;
    private final int width;
    private final int height;
    private final BufferedReader in;
    Lock borderLock;
    private final PriorityBlockingQueue<Pixel> border;
    private final Set<Pixel> borderSet;
    private final Thread updater;

    Lock imageLock;
    volatile byte[][] image;
    Lock priorityLock;
    volatile int[][] priority;
    volatile boolean updating;
    volatile private boolean exit;

    class Pixel implements Comparable<Pixel> {

        int x;
        int y;

        public Pixel(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Pixel o) {
            return priority() - o.priority();
        }

        private int priority() {
            priorityLock.lock();
            int p = priority[x][y];
            priorityLock.unlock();
            return p;
        }

        public byte type() {
            imageLock.lock();
            byte i = image[x][y];
            imageLock.unlock();
            return i;
        }

        public boolean isBorder() {
            if (type() != BLANK_TYPE){
                return false;
            }
            for (Pixel p : pixelsAround()){
                if (p.type() == MY_TYPE){
                    return true;
                }
            }
            return false;
        }

        public void setType(byte newType) {
            imageLock.lock();
            image[x][y] = newType;
            imageLock.unlock();
        }

        public void setPriority(int newPriority) {
            borderLock.lock();
            boolean contains = borderSet.remove(this);
            if (contains){
                border.remove(this);
            }
            priorityLock.lock();
            priority[x][y] = newPriority;
            priorityLock.unlock();
            if (contains){
                border.add(this);
                borderSet.add(this);
            }
            borderLock.unlock();
        }

        public List<Pixel> pixelsAround() {
            List<Pixel> pixels = new ArrayList<>(4);
            if (x > 0){
                pixels.add(new Pixel(x - 1, y));
            }
            if (x < width - 1){
                pixels.add(new Pixel(x + 1, y));
            }
            if (y > 0){
                pixels.add(new Pixel(x, y - 1));
            }
            if (y < height - 1){
                pixels.add(new Pixel(x, y + 1));
            }
            return pixels;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pixel pixel = (Pixel) o;

            return x == pixel.x && y == pixel.y;

        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedImage image = ImageIO.read(new File(args[0]));
        int color = parseColorString(args[1]);
        int N = Integer.parseInt(args[2]);
        new Swallower(image, color, N).start();
    }

    private void start() throws IOException {
        updater.start();
        try {
            while (true) {
                String input = in.readLine();
                if (input.equals("exit")) {
                    exit = true;
                    if (!updating) {
                        updater.interrupt();
                    }
                    return;
                } else if (input.startsWith("colour")) {
                    updateImage(input);
                } else if (input.equals("pick pixels")) {
                    if (updating) {
                        try {
                            synchronized (Thread.currentThread()){
                                Thread.currentThread().wait(MAX_TIME);
                            }
                        } catch (InterruptedException ignored) {
                        }
                    }
                    for (int i = 0; i < N && !border.isEmpty(); i++) {
                        borderLock.lock();
                        Pixel p = border.poll();
                        borderSet.remove(p);
                        borderLock.unlock();
                        if (!p.isBorder()){
                            i--;
                            continue;
                        }
                        updateImage(MY_TYPE, p);
                        System.out.print(p.x + "," + p.y + " ");
                    }
                    System.out.println();
                }
            }
        } catch (Throwable e){
            exit = true;
            if (!updating){
                updater.interrupt();
            }
            throw e;
        }
    }

    private void updateImage(byte type, Pixel... pixels) {
        for (Pixel pixel : pixels){
            pixel.setType(type);
            if (type == MY_TYPE){
                pixel.setPriority(Integer.MAX_VALUE);
            } else {
                pixel.setPriority(0);
            }
        }
        for (Pixel pixel : pixels){
            for (Pixel p : pixel.pixelsAround()){
                if (p.type() == BLANK_TYPE){
                    addPixelToUpdate(p);
                }
                if (type == MY_TYPE && p.isBorder()){
                    borderLock.lock();
                    if (borderSet.add(p)){
                        border.add(p);
                    }
                    borderLock.unlock();
                }
            }
        }
    }

    private synchronized void addPixelToUpdate(Pixel p) {
        if (pixelsToUpdateSet.add(p)) {
            pixelsToUpdate.add(p);
            if (!updating){
                updater.interrupt();
            }
        }
    }

    Queue<Pixel> pixelsToUpdate;
    Set<Pixel> pixelsToUpdateSet;

    private void update(){
        while (true){
            if (exit){
                return;
            }
            if (pixelsToUpdate.isEmpty()){
                try {
                    updating = false;
                    while (!exit) {
                        synchronized (Thread.currentThread()) {
                            Thread.currentThread().wait();
                        }
                    }
                } catch (InterruptedException ignored){}
                continue;
            }
            updating = true;
            Pixel pixel = pixelsToUpdate.poll();
            if (pixel.type() != BLANK_TYPE){
                continue;
            }
            pixelsToUpdateSet.remove(pixel);
            updatePixel(pixel);
        }
    }

    private void updatePixel(Pixel pixel) {
        int originalPriority = pixel.priority();
        int minPriority = Integer.MAX_VALUE;
        List<Pixel> pixelsAround = pixel.pixelsAround();
        for (Pixel p : pixelsAround){
            int priority = p.priority();
            if (priority < minPriority){
                minPriority = priority;
            }
        }
        if (minPriority >= originalPriority){
            pixel.setPriority(Integer.MAX_VALUE);
            pixelsToUpdate.addAll(pixelsAround.stream().filter(p -> p.type() == 0 && p.priority() != Integer.MAX_VALUE).filter(pixelsToUpdateSet::add).collect(Collectors.toList()));
        } else {
            pixel.setPriority(minPriority + 1);
            for (Pixel p : pixelsAround){
                if (p.type() == 0 && p.priority() > minPriority + 2){
                    if (pixelsToUpdateSet.add(p)){
                        pixelsToUpdate.add(p);
                    }
                }
            }
        }

    }

    private void updateImage(String input) {
        String[] inputs = input.split("\\s");
        int color = parseColorString(inputs[1]);
        byte type;
        if (color == this.color){
            return;
        } else {
            type = ENEMY_TYPE;
        }
        Pixel[] pixels = new Pixel[inputs.length - 3];
        for (int i = 0; i < inputs.length - 3; i++){
            String[] coords = inputs[i + 3].split(",");
            pixels[i] = new Pixel(Integer.parseInt(coords[0]), Integer.parseInt(coords[1]));
        }
        updateImage(type, pixels);
    }

    private static int parseColorString(String input) {
        String[] colorString = input.split("[\\(\\),]");
        return new Color(Integer.parseInt(colorString[1]), Integer.parseInt(colorString[2]), Integer.parseInt(colorString[3])).getRGB();
    }

    private Swallower(BufferedImage image, int color, int N){
        this.color = color;
        this.N = N;
        this.width = image.getWidth();
        this.height = image.getHeight();
        this.image = new byte[width][height];
        this.priority = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                int pixelColor = image.getRGB(x,y);
                priority[x][y] = Integer.MAX_VALUE;
                if (pixelColor == WHITE){
                    this.image[x][y] = BLANK_TYPE;
                } else if (pixelColor == this.color){
                    this.image[x][y] = MY_TYPE;
                } else {
                    this.image[x][y] = NEUTRAL_TYPE;
                }
            }
        }
        border = new PriorityBlockingQueue<>();
        borderSet = Collections.synchronizedSet(new HashSet<>());
        borderLock = new ReentrantLock();
        priorityLock = new ReentrantLock();
        imageLock = new ReentrantLock();
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                Pixel pixel = new Pixel(x,y);
                if (pixel.type() == BLANK_TYPE){
                    if (pixel.isBorder()){
                        if (borderSet.add(pixel)){
                            border.add(pixel);
                        }
                    }
                }
            }
        }
        in = new BufferedReader(new InputStreamReader(System.in));
        updating = false;
        updater = new Thread(this::update);
        pixelsToUpdate = new ConcurrentLinkedQueue<>();
        pixelsToUpdateSet = Collections.synchronizedSet(new HashSet<>());
        exit = false;
    }

}

Wie es funktioniert:

Dieser Bot verwaltet eine Prioritätswarteschlange mit Pixeln, die er hinzufügen kann. Die Priorität eines feindlichen Pixels ist 0. Die Priorität eines leeren Pixels ist 1 höher als die niedrigste Priorität, die es umgibt. Alle anderen Pixel haben die Priorität Integer.MAX_VALUE. Der Updater-Thread aktualisiert ständig die Prioritäten der Pixel. In jeder Runde werden die niedrigsten N Pixel aus der Prioritätswarteschlange entfernt.

Grüner Klecks gegen roten Schlucker

Blobs Score = 1.680553372583887225

Swallower's Score = 169.4020975612382575

Arena 1:

Bot Blob.py with colour (0, 255, 0) scored 1.2183333333333333
Bot Swallower.class with colour (255, 0, 0) scored 177.435

Arena 2:

Bot Swallower.class with colour (255, 0, 0) scored 149.57829253338517
Bot Blob.py with colour (0, 255, 0) scored 0.5159187091564356

Arena 3:

Bot Blob.py with colour (0, 255, 0) scored 0.727104853136361
Bot Swallower.class with colour (255, 0, 0) scored 163.343720545521

Arena 4:

Bot Swallower.class with colour (255, 0, 0) scored 187.25137716604686
Bot Blob.py with colour (0, 255, 0) scored 4.260856594709419

Grüner Schlucker gegen roter Klecks

Blobs Score = 1.6852943642218457375

Swallower's Score = 169.3923095387498625

Arena 1:

Bot Blob.py with colour (255, 0, 0) scored 1.3166666666666667
Bot Swallower.class with colour (0, 255, 0) scored 177.33666666666667

Arena 2:

Bot Swallower.class with colour (0, 255, 0) scored 149.57829253338517
Bot Blob.py with colour (255, 0, 0) scored 0.49573058575466195

Arena 3:

Bot Swallower.class with colour (0, 255, 0) scored 163.14367053301788
Bot Blob.py with colour (255, 0, 0) scored 0.9271548656394868

Arena 4:

Bot Swallower.class with colour (0, 255, 0) scored 187.51060842192973
Bot Blob.py with colour (255, 0, 0) scored 4.0016253388265675

Red Swallower gegen Green Depth First Blob

Swallower's Score = 157.0749775233111925

Punktzahl des ersten Blobs der Tiefe = 18.192783547939744

Arena 1:

Bot Swallower.class with colour (255, 0, 0) scored 173.52166666666668
Bot dfblob.py with colour (0, 255, 0) scored 5.131666666666667

Arena 2:

Bot dfblob.py with colour (0, 255, 0) scored 17.25635925887156
Bot Swallower.class with colour (255, 0, 0) scored 149.57829253338517

Arena 3:

Bot Swallower.class with colour (255, 0, 0) scored 153.59801488833747
Bot dfblob.py with colour (0, 255, 0) scored 10.472810510319889

Arena 4:

Bot dfblob.py with colour (0, 255, 0) scored 39.91029775590086
Bot Swallower.class with colour (255, 0, 0) scored 151.60193600485545

Grüner Schlucker gegen roten Tiefen-ersten Klecks

Swallower's Score = 154.3368355651281075

Punktzahl des ersten Blobs der Tiefe = 18.84463249420435425

Arena 1:

Bot Swallower.class with colour (0, 255, 0) scored 165.295
Bot dfblob.py with colour (255, 0, 0) scored 13.358333333333333

Arena 2:

Bot dfblob.py with colour (255, 0, 0) scored 8.91118721119768
Bot Swallower.class with colour (0, 255, 0) scored 149.57829253338517

Arena 3:

Bot Swallower.class with colour (0, 255, 0) scored 157.01136822667206
Bot dfblob.py with colour (255, 0, 0) scored 7.059457171985304

Arena 4:

Bot dfblob.py with colour (255, 0, 0) scored 46.0495522603011
Bot Swallower.class with colour (0, 255, 0) scored 145.4626815004552

Green Blob gegen Red Depth First Blob gegen Blue Swallower:

Blobs Score = 6.347962032393275525

Punktzahl des ersten Blobs der Tiefe = 27.34842554331698275

Swallower's Score = 227.720728953415375

Arena 1:

Bot Swallower.class with colour (0, 0, 255) scored 242.54
Bot Blob.py with colour (0, 255, 0) scored 1.21
Bot dfblob.py with colour (255, 0, 0) scored 24.3525

Arena 2:

Bot dfblob.py with colour (255, 0, 0) scored 17.828356088588478
Bot Blob.py with colour (0, 255, 0) scored 0.9252889892479551
Bot Swallower.class with colour (0, 0, 255) scored 224.36743880007776

Arena 3:

Bot dfblob.py with colour (255, 0, 0) scored 7.105141670032893
Bot Swallower.class with colour (0, 0, 255) scored 226.52057245080502
Bot Blob.py with colour (0, 255, 0) scored 12.621905476369092

Arena 4:

Bot dfblob.py with colour (255, 0, 0) scored 60.10770441464656
Bot Blob.py with colour (0, 255, 0) scored 10.634653663956055
Bot Swallower.class with colour (0, 0, 255) scored 217.45490456277872

Hier ist Sam Yonnous Richter mit ein paar Änderungen, so dass Sie die Dateien und den Befehl separat angeben:

import sys, re, random, os, shutil, subprocess, datetime, time, signal, io
from PIL import Image

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def place(loc, colour):
    # if valid, place colour at loc and return True, else False
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        if any(pix[p]==colour for p in plist if 0<=p[0]<W and 0<=p[1]<H):
            pix[loc] = colour
            return True
    return False

def updateimage(image, msg, bot):
    if not re.match(r'(\s*\d+,\d+)*\s*', msg):
        return []
    plist = [tuple(int(v) for v in pr.split(',')) for pr in msg.split()]
    plist = plist[:PIXELBATCH]
    return [p for p in plist if place(p, bot.colour)]

class Bot:
    botlist = []
    def __init__(self, progs, command=None, colour=None):
        self.prog = progs[0]
        self.botlist.append(self)
        self.colour = colour
        self.colstr = str(colour).replace(' ', '')
        self.faults = 0
        self.env = 'env%u' % self.botlist.index(self)
        try: os.mkdir(self.env)
        except: pass
        for prog in progs:
            shutil.copy(prog, self.env)
        shutil.copy(imagename, self.env)
        os.chdir(self.env)
        args = command + [imagename, self.colstr, str(PIXELBATCH)]
        errorfile = 'err.log'
        with io.open(errorfile, 'wb') as errorlog:
            self.proc = subprocess.Popen(args, stdin=subprocess.PIPE, 
                stdout=subprocess.PIPE, stderr=errorlog)
        os.chdir('..')
    def send(self, msg):
        if self.faults < FAULTLIMIT:
            self.proc.stdin.write((msg+'\n').encode('utf-8'))
            self.proc.stdin.flush()
    def read(self, timelimit):
        if self.faults < FAULTLIMIT:
            start = time.time()
            inline = self.proc.stdout.readline().decode('utf-8')
            if time.time() - start > timelimit:
                self.faults += 1
                inline = ''
            return inline.strip()
    def exit(self):
        self.send('exit')

from cfg import *
for i, (progs, command) in enumerate(botspec):
    Bot(progs, command, colourspec[i])

image = Image.open(imagename)
pix = image.load()
W,H = image.size
resultdirectory = 'results of ' + BATTLE
os.mkdir(resultdirectory)

time.sleep(INITTIME)
total = 0
image.save(resultdirectory+'/'+'result000.png')
for turn in range(1, MAXTURNS+1):
    random.shuffle(Bot.botlist)
    nullbots = 0
    for bot in Bot.botlist:
        bot.send('pick pixels')
        inmsg = bot.read(TIMELIMIT)
        newpixels = updateimage(image, inmsg, bot)
        total += len(newpixels)
        if newpixels:
            pixtext = ' '.join('%u,%u'%p for p in newpixels)
            msg = 'colour %s chose %s' % (bot.colstr, pixtext)
            for msgbot in Bot.botlist:
                msgbot.send(msg)
        else:
            nullbots += 1
    if nullbots == len(Bot.botlist):
        break
    if turn % 100 == 0:
        print('Turn %s done %s pixels' % (turn, total))
        image.save(resultdirectory+'/result'+str(turn//100).zfill(3)+'.png')
image.save(resultdirectory+'/result999.png')
for msgbot in Bot.botlist:
    msgbot.exit()

resultfile = io.open(resultdirectory+'/result.txt','w')
counts = dict((c,f) for f,c in image.getcolors(W*H))
avg = 1.0 * sum(counts.values()) / len(Bot.botlist)
for bot in Bot.botlist:
    score = 100 * counts[bot.colour] / avg
    print('Bot %s with colour %s scored %s' % (bot.prog, bot.colour, score))
    print('Bot %s with colour %s scored %s' % (bot.prog, bot.colour, score), file=resultfile)
image.save(BATTLE+'.png')