// 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 #include #include #define DEPTH 3 const char *moves[] = { "SOUTH", "NORTH", "EAST", "WEST" }; bool is_blocked(int x, int y, const Map &map, std::vector > &blocked_grid) { return map.IsWall(x, y) || blocked_grid[x][y]; } int flood_fill_grid(const Map &map, std::vector > &blocked_grid, std::vector > &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 > *create_map_grid(const Map &map) { return new std::vector >(map.Width(), std::vector(map.Height(), false)); } bool can_move_from(int x, int y, const Map &map, std::vector > &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 &vals) { unsigned int i; int highest; highest = vals[0]; for(i=1;i highest) highest = vals[i]; } return highest; } int score_my_move(const Map &map, std::vector > &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 > &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 > &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 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 > *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 > &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 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 > *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; }