Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
// 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 1
const 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 area = my_area;
return -20 + (area / (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))
return -100;
std::vector<int> scores(4, -100);
if(!is_blocked(their_x, their_y+1, map, blocked_grid))
scores[0] = -score_their_move(map, blocked_grid, my_x, my_y, their_x, their_y+1, max_depth);
if(!is_blocked(their_x, their_y-1, map, blocked_grid))
scores[1] = -score_their_move(map, blocked_grid, my_x, my_y, their_x, their_y-1, max_depth);
if(!is_blocked(their_x+1, their_y, map, blocked_grid))
scores[2] = -score_their_move(map, blocked_grid, my_x, my_y, their_x+1, their_y, max_depth);
if(!is_blocked(their_x-1, their_y, map, blocked_grid))
scores[3] = -score_their_move(map, blocked_grid, my_x, my_y, their_x-1, their_y, max_depth);
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 = 0;
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.