ColorFighter - C++ - eats a couple of swallowers for breakfast
EDIT
- cleaned up the code
- added a simple but effective optimization
- added some GIF animations
God I hate snakes (just pretend they are spiders, Indy)
Actually I love Python. I wish I were less of a lazy boy and started to learn it properly, that's all.
All this being said, I had to struggle with the 64 bits version of this snake to get the Judge working. Making PIL work with the 64 bits version of Python under Win7 requires more patience than I was ready to devote to this challenge, so in the end I switched (painfully) to the Win32 version.
Also, the Judge tends to crash badly when a bot is too slow to respond.
Being no Python savvy, I did not fix it, but it has to do with reading an empty answer after a timeout on stdin.
A minor improvement would be to put stderr output to a file for each bot. That would ease tracing for post-mortem debugging.
Except for these minor problems, I found the Judge very simple and pleasant to use.
Kudos for yet another inventive and fun challenge.
The 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();
}
Building the executable
I used LODEpng.cpp and LODEpng.h to read png images.
About the easiest way I found to teach this retarded C++ language how to read a picture without having to build half a dozen libraries.
Just compile & link LODEpng.cpp along with the main and Bob's your uncle.
I compiled with MSVC2013, but since I used only a few STL basic containers (deque and vectors), it might work with gcc (if you're lucky).
If it doesn't, I might try a MinGW build, but frankly I'm getting tired of C++ portability issues.
I did quite a lot of portable C/C++ in my days (on exotic compilers for various 8 to 32 bits processors as well as SunOS, Windows from 3.11 up to Vista and Linux from its infancy to Ubuntu cooing zebra or whatever, so I think I have a pretty good idea of what portability means), but at the time it did not require to memorize (or discover) the innumerable discrepancies between the GNU and Microsoft interpretations of the cryptic and bloated specs of the STL monster.
Results against Swallower
How it works
At the core, this is a simple brute-force floodfill pathing.
The frontier of the player's color (i.e. the pixels that have at least one white neighbour) is used as a seed to perform the classic distance-flooding algorithm.
When a point reaches the vincinity of an enemy color, a backward path is computed to produce a string of pixels moving toward the nearest enemy spot.
The process is repeated until enough points have been gathered for a response of the desired length.
This repetition is obscenely expensive, especially when fighting near the enemy.
Each time a string of pixels leading from the frontier to an enemy pixel has been found (and we need more points to complete the answer), the flood fill is redone from start, with the new path added to the frontier. It means you could have to do 5 flood fills or more to get an 10 pixels answer.
If no more enemy pixels are reachable, arbitraty neighbours of the frontier pixels are selected.
The algorithm devolves to a rather inefficient flood fill, but this only happens after the outcome of the game has been decided (i.e. there is no more neutral territory to fight for).
I did optimize it so that the Judge do not spend ages filling up the map once the competition has been dealt with. In its current state, the execution time is neglectible compared with the Judge itself.
Since enemy colors are not known at start, the initial arena image is kept in store in order to copy the enemy's starting areas when it makes its first move.
If the code plays first, it will simply flood fill a few arbitrary pixels.
This makes the algorithm capable of fighting an arbitrary number of adversaries, and even possibly new adversaries arriving at a random point in time, or colors appearing without a starting area (though this has absolutely no practical use).
Enemy handling on a color-per-color basis would also allow to have two instances of the bot cooperate (using pixel coordinates to pass a secret recognition sign).
Sounds like fun, I'll probably try that :).
Computation-heavy pathing is done as soon as new data are available (after a move notification), and some optimizations (the frontier update) are done just after a response has been given (to do as much computation as possible during the other bots turns).
Here again, there could be ways of doing more subtle things if there were more than 1 adversary (like aborting a computation if new data become available), but at any rate I fail to see where multitasking is needed, as long as the algorithm is able to work on full load.
Performance issues
All this cannot work without fast data access (and more computing power than the whole Appolo program, i.e. your average PC when used to do more than post a few tweets).
The speed is heavily compiler-dependent. Usually GNU beats Microsoft by a 30% margin (that's the magic number I noticed on 3 other pathing-related code challenges), but this mileage may vary of course.
The code in its current state barely breaks a sweat on arena 4. Windows perfmeter reports about 4 to 7 % CPU usage, so it should be able to cope with a 1000x1000 map within the 100ms response time limit.
At the heart of about every pathing algorithm lies a FIFO (possibly proritized, though not in that case), which in turn requires fast element allocation.
Since the OP obligingly set a limit to the arena size, I did some maths and saw that fixed data structures dimensioned to max (i.e. 1.000.000 pixels) would not consume more than a couple dozen megabytes, which your average PC eats for breakfast.
Indeed under Win7 and compiled with MSVC 2013, the code consumes about 14Mb on arena 4, while Swallower's two threads are using more than 20Mb.
I started with STL containers for easier prototyping, but STL made the code even less readable, since I had no desire to create a class to encapsulate each and every bit of data to hide the obfuscation away (whether that is due to my own inabilities to cope with the STL is left to the appreciation of the reader).
Regardless, the result was so atrociously slow that at first I thought I was building a debug version by mistake.
I reckon this is partly due to the incredibly poor Microsoft implementation of the STL (where, for instance, vectors and bitsets do bound checks or other crypic operations on operator[], in direct violation of the spec), and partly to the STL design itself.
I could cope with the atrocious syntax and portability (i.e. Microsoft vs GNU) issues if the performances were there, but this is certainly not the case.
For instance, deque is inherently slow, because it shuffles lots of bookkeeping data around waiting for the occasion to do its super smart resizing, about which I could not care less.
Sure I could have implemented a custom allocator and whaterver other custom template bits, but a custom allocator alone costs a few hundred lines of code and the better part of a day to test, what with the dozen of interfaces it has to implement, while a handmade equivalent structure is about zero lines of code (albeit more dangerous, but the algorithm would not have worked if I did not know - or think I knew - what I was doing anyway).
So eventually I kept the STL containers in non-critical parts of the code, and built my own brutal allocator and FIFO with two circa 1970 arrays and three unsigned shorts.
Swallowing the swallower
As its author confirmed, the erratic patterns of the Swallower are caused by lag between enemy moves notifications and updates from the pathing thread.
The system perfmeter shows clearly the pathing thread consuming 100% CPU all the time, and the jagged patterns tend to appear when the focus of the fight shifts to a new area.
This is also quite apparent with the animations.
A simple but effective optimization
After looking at the epic dogfights between Swallower and my fighter, I remembered an old saying from the game of Go: defend close up, but attack from afar.
There is wisdom in that. If you try to stick to your adversary too much, you will waste precious moves trying to block each possible path. On the contrary, if you stay just one pixel away, you will likely avoid filling small gaps that would gain very little, and use your moves to counter more important threats.
To implement this idea, I simply extended the moves of an enemy (marking the 4 neighbours of each move as an enemy pixel).
This stops the pathing algorithm one pixel away from the enemy's border, allowing my fighter to work its way around an adversary without getting caught in too many dogfights.
You can see the improvement
(though all runs are not as successful, you can notice the much smoother outlines):
