Stuff

// This software is released under the DBAD (Dont be a duche) license.// If you improve this code in any way, you must release your modifications publicly.#include "Map.h"#include <string>#include <vector>#include <iostream>#define DEPTH 3const char *moves[] = {	"SOUTH",	"NORTH",	"EAST",	"WEST"};bool is_blocked(int x, int y, const Map &map,	std::vector<std::vector<bool> > &blocked_grid){	return map.IsWall(x, y) || blocked_grid[x][y];}int flood_fill_grid(const Map &map,	std::vector<std::vector<bool> > &blocked_grid,	std::vector<std::vector<bool> > &grid,	int x, int y){	int count = 1;	if (is_blocked(x, y, map, blocked_grid) || grid[x][y])		return 0;	grid[x][y] = true;	count += flood_fill_grid(map, blocked_grid, grid, x, y+1);	count += flood_fill_grid(map, blocked_grid, grid, x, y-1);	count += flood_fill_grid(map, blocked_grid, grid, x+1, y);	count += flood_fill_grid(map, blocked_grid, grid, x-1, y);	return count;}std::vector<std::vector<bool> > *create_map_grid(const Map &map){	return new std::vector<std::vector<bool> >(map.Width(),		std::vector<bool>(map.Height(), false));}bool can_move_from(int x, int y, const Map &map, std::vector<std::vector<bool> > &blocked_grid){	if(!is_blocked(x, y+1, map, blocked_grid))		return true;	if(!is_blocked(x, y-1, map ,blocked_grid))		return true;	if(!is_blocked(x+1, y, map, blocked_grid))		return true;	if(!is_blocked(x-1, y, map, blocked_grid))		return true;	return false;}bool is_same_location(int x1, int y1, int x2, int y2){	return x1 == x2 && y1 == y2;}int max(std::vector<int> &vals){	unsigned int i;	int highest;	highest = vals[0];	for(i=1;i<vals.size();i++)	{		if(vals[i] > highest)			highest = vals[i];	}	return highest;}int score_my_move(const Map &map,	std::vector<std::vector<bool> > &blocked_grid,	int my_x, int my_y,	int their_x, int their_y,	int max_depth);int move_count(const Map &map,	std::vector<std::vector<bool> > &blocked_grid,	int x, int y){	int count = 0;	if(!is_blocked(x, y+1, map, blocked_grid))		count++;	if(!is_blocked(x, y-1, map, blocked_grid))		count++;	if(!is_blocked(x+1, y, map, blocked_grid))		count++;	if(!is_blocked(x-1, y, map, blocked_grid))		count++;	return count;}int abs(int val){	if(val >= 0)		return val;	return -val;}int score_their_move(const Map &map,	std::vector<std::vector<bool> > &blocked_grid,	int my_x, int my_y,	int their_x, int their_y,	int max_depth){	int my_area, their_area;	bool they_have_moves, we_have_moves;	std::vector<int> scores(4, -100);	if(is_same_location(my_x, my_y, their_x, their_y))		return 50;		they_have_moves = can_move_from(their_x, their_y, map, blocked_grid);	we_have_moves = can_move_from(my_x, my_y, map, blocked_grid);	if(!they_have_moves)	{		if(!we_have_moves)			return 50;		return -100;	}	if(!we_have_moves)		return 100;	if(max_depth > 0)	{		max_depth--;		blocked_grid[my_x][my_y] = true;		blocked_grid[their_x][their_y] = true;		if(!is_blocked(my_x, my_y+1, map, blocked_grid))			scores[0] = -score_my_move(map, blocked_grid, my_x, my_y+1, their_x, their_y, max_depth);		if(!is_blocked(my_x, my_y-1, map, blocked_grid))			scores[1] = -score_my_move(map, blocked_grid, my_x, my_y-1, their_x, their_y, max_depth);		if(!is_blocked(my_x+1, my_y, map, blocked_grid))			scores[2] = -score_my_move(map, blocked_grid, my_x+1, my_y, their_x, their_y, max_depth);		if(!is_blocked(my_x-1, my_y, map, blocked_grid))			scores[3] = -score_my_move(map, blocked_grid, my_x-1, my_y, their_x, their_y, max_depth);		blocked_grid[my_x][my_y] = false;		blocked_grid[their_x][their_y] = false;		return max(scores);	}		std::vector<std::vector<bool> > *fg = create_map_grid(map);	my_area = flood_fill_grid(map, blocked_grid, *fg, my_x, my_y);	if(!(*fg)[their_x][their_y])	{		their_area = flood_fill_grid(map, blocked_grid, *fg, their_x, their_y);		delete fg;		fg = 0;		if(their_area > my_area)			return 75;		if(their_area < my_area)			return -75;	}	if(fg)		delete fg;		float dist = abs(my_x - their_x) + abs(my_y - their_y);	return -20 + ((dist / map.Width() + map.Height())* 40.0f);}int score_my_move(const Map &map,	std::vector<std::vector<bool> > &blocked_grid,	int my_x, int my_y,	int their_x, int their_y,	int max_depth){	if(is_blocked(my_x, my_y, map, blocked_grid))	{		if(is_blocked(their_x, their_y, map, blocked_grid))			return -50;		return -100;	}	std::vector<int> scores(4, -100);#define try_move(t_x, t_y, n)\	if(!is_blocked(t_x, t_y, map, blocked_grid))\		scores[n] = -score_their_move(map, blocked_grid, my_x, my_y, t_x, t_y, max_depth);	try_move(their_x, their_y+1, 0);	try_move(their_x, their_y-1, 1);	try_move(their_x+1, their_y, 2);	try_move(their_x-1, their_y, 3);#undef try_move	return max(scores);}std::string MakeMove(const Map& map) {	int x = map.MyX();	int y = map.MyY();	int their_x = map.OpponentX();	int their_y = map.OpponentY();	int best_score = -101;	int best_move = 2;	int score;	std::vector<std::vector<bool> > *grid = create_map_grid(map);#define try_move(my_x, my_y, n)\	if (!map.IsWall(my_x, my_y)) {\		score = score_my_move(map, *grid, my_x, my_y, their_x, their_y, DEPTH);\		if(score > best_score)\		{\			best_score = score;\			best_move = n;\		}\	}\	try_move(x, y+1, 0);	try_move(x, y-1, 1);	try_move(x+1, y, 2);	try_move(x-1, y, 3);#undef try_move	return moves[best_move];}// Ignore this function. It is just handling boring stuff for you, like// communicating with the Tron tournament engine.int main() {  while (true) {    Map map;    Map::MakeMove(MakeMove(map));  }  return 0;}