Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package ctf.agent;
- import static java.lang.System.out;
- import ctf.common.AgentAction;
- import ctf.common.AgentEnvironment;
- import java.awt.Point;
- import java.util.ArrayList;
- import java.util.LinkedList;
- import java.util.Random;
- import java.util.Collections;
- public class srs140430Agent extends Agent {
- Random rand = new Random();
- final int unvisited = 0;
- final int empty = 1;
- final int obstacle = 2;
- final int mybase = 3;
- final int theirbase = 4;
- final int bfsvisited = 5;
- final int mine = 6;
- class Board {
- int size;
- int[][] b;
- Point mybasepoint;
- Point theirbasepoint;
- Board(int size, boolean left) {
- this.size = size;
- b = new int[size][size];
- for (int i = 0; i < size; i++) {
- b[0][i] = empty;
- b[size - 1][i] = empty;
- }
- if (left) {
- b[0][(size - 1) / 2] = mybase;
- mybasepoint = new Point(0, (size - 1) / 2);
- b[size - 1][(size - 1) / 2] = theirbase;
- theirbasepoint = new Point(size - 1, (size - 1) / 2);
- } else {
- b[size - 1][(size - 1) / 2] = mybase;
- mybasepoint = new Point(size - 1, (size - 1) / 2);
- b[0][(size - 1) / 2] = theirbase;
- theirbasepoint = new Point(0, (size - 1) / 2);
- }
- }
- public boolean reachable(Point target, Point from){
- return target == from || getPath(from, target).size() != 1;
- }
- public LinkedList<Point> getPath(Point from, Point to) {
- int[][] visited = new int[size][size];
- int[][] cum_cost = new int[size][size];
- for (int i = 0; i < size; i++)
- for (int j = 0; j < size; j++) cum_cost[i][j] = Integer.MAX_VALUE / 2;
- for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) visited[i][j] = b[i][j];
- Point[][] pred = new Point[size][size];
- LinkedList<Point> Q = new LinkedList<Point>();
- visited[from.x][from.y] = bfsvisited;
- cum_cost[from.x][from.y] = 0;
- pred[from.x][from.y] = null;
- Q.add(from);
- while (!Q.isEmpty()) {
- Point min_p = Q.peek();
- int min_cost = cum_cost[min_p.x][min_p.y] + distance(min_p, to);
- for (Point p : Q) {
- int cost = cum_cost[p.x][p.y] + distance(p, to);
- if (cost < min_cost) {
- min_p = p;
- min_cost = cost;
- }
- }
- if (min_p.equals(to)) break;
- Q.remove(min_p);
- visited[min_p.x][min_p.y] = bfsvisited;
- ArrayList<Point> neighbors = neighbors(min_p);
- for (Point neighbor : neighbors) {
- if (!Q.contains(neighbor) && visited[neighbor.x][neighbor.y] == empty) Q.add(neighbor);
- int new_cost = cum_cost[min_p.x][min_p.y] + 1 + distance(min_p, to);
- int old_cost = cum_cost[neighbor.x][neighbor.y] + distance(neighbor, to);
- if (new_cost < old_cost) {
- cum_cost[neighbor.x][neighbor.y] = cum_cost[min_p.x][min_p.y] + 1;
- pred[neighbor.x][neighbor.y] = min_p;
- }
- }
- }
- LinkedList<Point> path = new LinkedList<>();
- Point p = to;
- while (p != null) {
- path.push(p);
- p = pred[p.x][p.y];
- }
- return path;
- }
- public int n_discovered(){
- int n = 0;
- for(int i = 0; i < size; i++)
- for(int j = 0 ; j < size;j++)
- if(b[i][j] != unvisited)
- n+=1;
- return n;
- }
- public int evalPoint(Point point, Point current, Point goal) {
- //TODO: avoid unvisited nodes with lots of barriers around them
- int dist_pg = distance(point, goal);
- int dist_pc = getPath(current, point).size();
- int pg_weight = Math.min(n_discovered()/size*size + 1/2, 1);
- // count number of unvisited nodes near target node;
- int unvisited_neighbors = 0;
- int obstacles_nearby = 0;
- int radius = 1;
- int radius_obstacle = 2;
- for (int i = -radius; i <= radius; i++) {
- for (int j = -radius; j <= radius; j++) {
- int neighborx = point.x + i;
- int neighbory = point.y + j;
- if (neighborx >= size || neighbory >= size) continue;
- if (neighborx < 0 || neighbory < 0) continue;
- if (b[neighborx][neighbory] == unvisited) unvisited_neighbors += 1;
- }
- }
- for (int i = -radius_obstacle; i <= radius_obstacle; i++) {
- for (int j = -radius_obstacle; j <= radius_obstacle; j++) {
- int neighborx = point.x + i;
- int neighbory = point.y + j;
- if (neighborx >= size || neighbory >= size) continue;
- if (neighborx < 0 || neighbory < 0) continue;
- if (b[neighborx][neighbory] == obstacle) obstacles_nearby += 1;
- }
- }
- return dist_pc + dist_pg/2 + obstacles_nearby;
- }
- public ArrayList<Point> getReachableUnvisited(Point from) {
- int[][] visited = new int[size][size];
- for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) visited[i][j] = b[i][j];
- LinkedList<Point> Q = new LinkedList<Point>();
- ArrayList<Point> reachable = new ArrayList<Point>();
- visited[from.x][from.y] = bfsvisited;
- Q.add(from);
- while (!Q.isEmpty()) {
- Point p = Q.pop();
- visited[p.x][p.y] = bfsvisited;
- ArrayList<Point> neighbors = neighbors(p);
- for (Point neighbor : neighbors) {
- if (visited[neighbor.x][neighbor.y] == unvisited) {
- reachable.add(neighbor);
- visited[neighbor.x][neighbor.y] = bfsvisited;
- }
- if (visited[neighbor.x][neighbor.y] == empty && !Q.contains(neighbor)) Q.add(neighbor);
- }
- }
- return reachable;
- }
- public ArrayList<Point> neighbors(Point p) {
- int x = p.x;
- int y = p.y;
- ArrayList<Point> neighborz = new ArrayList<>();
- if (x - 1 >= 0) neighborz.add(new Point(x - 1, y));
- if (x + 1 < size) neighborz.add(new Point(x + 1, y));
- if (y - 1 >= 0) neighborz.add(new Point(x, y - 1));
- if (y + 1 < size) neighborz.add(new Point(x, y + 1));
- return neighborz;
- }
- public String toString() {
- StringBuilder s = new StringBuilder();
- for (int i = size - 1; i >= 0; i--) {
- for (int j = 0; j < size; j++) {
- s.append(b[j][i]);
- s.append(' ');
- }
- s.append('\n');
- }
- return s.toString();
- }
- }
- static int distance(Point p1, Point p2) {
- return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
- }
- static int n_agents = 0;
- static Board board;
- static int size = 0;
- static boolean doneSizing = false;
- static int turn = 0;
- static srs140430Agent oddAgent;
- static srs140430Agent evenAgent;
- boolean topAgent, bottomAgent;
- boolean leftTeam, rightTeam;
- boolean determineSize = false;
- boolean newGame = true;
- int id;
- Point coord;
- Point prev;
- Point goal;
- LinkedList<Point> path;
- LinkedList<Boolean> memory = new LinkedList<>();
- public srs140430Agent() {
- n_agents += 1;
- id = n_agents;
- board = null;
- size = 2;
- doneSizing = false;
- turn = 0;
- if (id % 2 == 0) evenAgent = this;
- else oddAgent = this;
- }
- public int getMove(AgentEnvironment env) {
- if (newGame) newGameSetup(env);
- if (bottomAgent) turn += 1;
- if(memory != null){
- if (leftTeam)
- memory.add(env.isObstacleEastImmediate());
- if (rightTeam)
- memory.add(env.isObstacleWestImmediate());
- }
- if (determineSize) return investigateSize(env);
- if (coord == null) {
- out.println("COORD IS NULL");
- if (env.isBaseSouth(0, true)) coord = new Point(homeColumn(), (board.size - 1) / 2 + 1);
- else coord = new Point(homeColumn(), (board.size - 1) / 2 - 1);
- }
- if(memory != null){
- int x = coord.x;
- if(leftTeam)
- x += 1;
- else
- x -= 1;
- if(topAgent){
- for(int y = size - 1; y >= coord.y; y--){
- if(memory.poll())
- board.b[x][y] = obstacle;
- else
- board.b[x][y] = empty;
- }
- }
- else{
- for(int y = 0; y <= coord.y; y++){
- if(memory.poll())
- board.b[x][y] = obstacle;
- else
- board.b[x][y] = empty;
- }
- }
- memory = null;
- }
- out.println("*************");
- if (topAgent) {
- out.println("Top Agent's Move:");
- }
- if (bottomAgent) {
- out.println("Bottom Agent's Move:");
- }
- checkIfReset(env);
- checkForObstacles(env);
- int move = -1;
- if(!env.hasFlag() && attackFlagBearer(env) != AgentAction.DO_NOTHING){
- out.println("Attacking Flag");
- move = attackFlagBearer(env);
- prev = coord;
- coord = newCoord(move);
- return move;
- }
- if(topAgent && env.hasFlag(AgentEnvironment.ENEMY_TEAM)){
- ArrayList<Point> neighbors = board.neighbors(coord);
- int[][] eval = new int[board.size][board.size];
- for(int i =0; i < board.size; i ++){
- for(int j = 0; j < board.size; j++){
- if(i > coord.x){
- if(env.isFlagEast(AgentEnvironment.OUR_TEAM, false))
- eval[i][j] += 5;
- }
- if(i < coord.x){
- if(env.isFlagWest(AgentEnvironment.OUR_TEAM, false))
- eval[i][j] += 5;
- }
- if(j > coord.y){
- if(env.isFlagNorth(AgentEnvironment.OUR_TEAM, false))
- eval[i][j] += 5;
- }
- if(j < coord.y){
- if(env.isFlagSouth(AgentEnvironment.OUR_TEAM, false))
- eval[i][j] += 5;
- }
- if(getOtherAgent().coord.x == i && getOtherAgent().coord.y == j)
- eval[i][j] -= 500;
- }
- }
- Collections.shuffle(neighbors);
- Point best = null;
- int val = -1;
- for(Point p: neighbors){
- if(eval[p.x][p.y] > val){
- best = p;
- val = eval[p.x][p.y];
- }
- }
- move = actionFromPoints(coord, best);
- prev = coord;
- coord = newCoord(move);
- System.out.printf("PANIC, CURR = %s, TARGET = %s, %d\n", coord, best, val);
- return move;
- }
- move = computeNextMove(env);
- if (isBlocked(move, env)){
- move = rand.nextInt(4);
- if (isBlocked(move, env))
- move = rand.nextInt(4);
- }
- if (isBlocked(move, env))
- move = AgentAction.DO_NOTHING;
- prev = coord;
- coord = newCoord(move);
- return move;
- }
- int attackFlagBearer(AgentEnvironment env){
- if(!env.hasFlag(AgentEnvironment.ENEMY_TEAM)){
- return AgentAction.DO_NOTHING;
- }
- if(env.isFlagEast(AgentEnvironment.OUR_TEAM, true)){
- out.println("ENEMY FLAGBEARER IS ADJACENT!");
- return AgentAction.MOVE_EAST;
- }
- if(env.isFlagWest(AgentEnvironment.OUR_TEAM, true)){
- out.println("ENEMY FLAGBEARER IS ADJACENT!");
- return AgentAction.MOVE_WEST;
- }
- if(env.isFlagNorth(AgentEnvironment.OUR_TEAM, true)){
- out.println("ENEMY FLAGBEARER IS ADJACENT!");
- return AgentAction.MOVE_NORTH;
- }
- if(env.isFlagSouth(AgentEnvironment.OUR_TEAM, true)){
- out.println("ENEMY FLAGBEARER IS ADJACENT!");
- return AgentAction.MOVE_SOUTH;
- }
- return AgentAction.DO_NOTHING;
- }
- void setGoal(AgentEnvironment env){
- if (bottomAgent && goal == null) goal = board.theirbasepoint;
- if (topAgent && goal == null) goal = new Point(board.mybasepoint.x, board.mybasepoint.y - 1);
- if (env.hasFlag()){
- goal = board.mybasepoint;
- path = null;
- }
- if(goal == board.mybasepoint && !env.hasFlag()){
- goal = board.theirbasepoint;
- path = null;
- }
- if(topAgent && goal.equals(coord)){
- int ydiff = board.mybasepoint.y - coord.y;
- goal = new Point(board.mybasepoint.x, board.mybasepoint.y + ydiff);
- }
- }
- int computeNextMove(AgentEnvironment env) {
- setGoal(env);
- if(path != null){
- Point target = path.peekLast();
- if(board.b[target.x][target.y] != unvisited){
- out.println("TARGET IS ALREAD VISITED");
- path = null;
- }
- else if (coord.equals(path.peek())) {
- out.println("FOLLOWING PATH");
- path.pop();
- if(!path.isEmpty())
- return actionFromPoints(coord, path.peek());
- else
- path = null;
- }
- else
- path = null;
- }
- //recompute path
- if (path == null) {
- out.println("COMPUTING PATH TO NEW TARGET");
- int min_cost = Integer.MAX_VALUE;
- Point target = null;
- if(!board.reachable(goal, coord)){
- for (Point p : board.getReachableUnvisited(coord)) {
- if (board.evalPoint(p, coord, goal) < min_cost){ target = p;
- min_cost = board.evalPoint(p, coord, goal);
- }
- }
- }
- else{
- out.println("GOAL IS REACHABLE");
- if(topAgent)
- target = goal;
- else if(!env.hasFlag()){
- if(rand.nextDouble() < 0.25){
- for (Point p : board.getReachableUnvisited(coord)) {
- if (board.evalPoint(p, coord, goal) < min_cost){ target = p;
- min_cost = board.evalPoint(p, coord, goal);
- }
- }
- }else{
- target = goal;
- }
- }
- else{
- target = goal;
- }
- }
- out.printf("NEW TARGET: %s%n",target);
- path = board.getPath(coord, target);
- }
- out.printf("%s %s%n", coord, path);
- if(topAgent){
- if(env.isAgentNorth(AgentEnvironment.ENEMY_TEAM, true))
- return AgentAction.MOVE_NORTH;
- if(env.isAgentSouth(AgentEnvironment.ENEMY_TEAM, true))
- return AgentAction.MOVE_SOUTH;
- if(env.isAgentWest(AgentEnvironment.ENEMY_TEAM, true))
- return AgentAction.MOVE_WEST;
- if(env.isAgentEast(AgentEnvironment.ENEMY_TEAM, true))
- return AgentAction.MOVE_EAST;
- }
- if(path.isEmpty())
- return AgentAction.DO_NOTHING;
- if (coord.equals(path.peek())) {
- out.println("FOLLOWING PATH");
- path.pop();
- if(!path.isEmpty())
- return actionFromPoints(coord, path.peek());
- else
- path = null;
- }
- out.println("RETURNING RANDOM");
- return rand.nextInt(4);
- }
- int actionFromPoints(Point from, Point to) {
- assert from != null;
- assert to != null;
- int diffx = to.x - from.x;
- int diffy = to.y - from.y;
- switch (diffx) {
- case 1:
- return AgentAction.MOVE_EAST;
- case -1:
- return AgentAction.MOVE_WEST;
- }
- switch (diffy) {
- case 1:
- return AgentAction.MOVE_NORTH;
- case -1:
- return AgentAction.MOVE_SOUTH;
- }
- return AgentAction.DO_NOTHING;
- }
- int xOffset(int move) {
- switch (move) {
- case AgentAction.MOVE_EAST:
- return 1;
- case AgentAction.MOVE_WEST:
- return -1;
- default:
- return 0;
- }
- }
- int yOffset(int move) {
- switch (move) {
- case AgentAction.MOVE_NORTH:
- return 1;
- case AgentAction.MOVE_SOUTH:
- return -1;
- default:
- return 0;
- }
- }
- Point newCoord(int move) {
- return new Point(coord.x + xOffset(move), coord.y + yOffset(move));
- }
- boolean isBlocked(int move, AgentEnvironment env) {
- if(move == AgentAction.DO_NOTHING)
- return false;
- srs140430Agent other = getOtherAgent();
- assert other != this;
- Point temp = newCoord(move);
- if (temp.equals(other.coord)) return true;
- switch (move) {
- case AgentAction.MOVE_EAST:
- if(env.hasFlag() && env.isAgentEast(AgentEnvironment.ENEMY_TEAM, true))
- return true;
- assert (temp.equals(other.coord)) == env.isAgentEast(AgentEnvironment.OUR_TEAM, true);
- return env.isObstacleEastImmediate() || (env.isFlagEast(AgentEnvironment.OUR_TEAM, true) && !env.hasFlag());
- case AgentAction.MOVE_WEST:
- if(env.hasFlag() && env.isAgentWest(AgentEnvironment.ENEMY_TEAM, true))
- return true;
- assert (temp.equals(other.coord)) == env.isAgentWest(AgentEnvironment.OUR_TEAM, true);
- return env.isObstacleWestImmediate() || (env.isFlagWest(AgentEnvironment.OUR_TEAM, true) && !env.hasFlag());
- case AgentAction.MOVE_NORTH:
- if(env.hasFlag() && env.isAgentNorth(AgentEnvironment.ENEMY_TEAM, true))
- return true;
- assert (temp.equals(other.coord)) == env.isAgentNorth(AgentEnvironment.OUR_TEAM, true);
- return env.isObstacleNorthImmediate() || (env.isFlagNorth(AgentEnvironment.OUR_TEAM, true) && !env.hasFlag());
- case AgentAction.MOVE_SOUTH:
- if(env.hasFlag() && env.isAgentSouth(AgentEnvironment.ENEMY_TEAM, true))
- return true;
- assert (temp.equals(other.coord)) == env.isAgentSouth(AgentEnvironment.OUR_TEAM, true);
- return env.isObstacleSouthImmediate() || (env.isFlagSouth(AgentEnvironment.OUR_TEAM, true) && !env.hasFlag());
- case AgentAction.DO_NOTHING:
- return false;
- }
- assert false;
- return true;
- }
- void checkForObstacles(AgentEnvironment env) {
- if (coord.x - 1 >= 0) {
- boolean obst = env.isObstacleWestImmediate();
- int val = obst ? obstacle : empty;
- if (board.b[coord.x - 1][coord.y] == unvisited) board.b[coord.x - 1][coord.y] = val;
- }
- if (coord.x + 1 < size) {
- boolean obst = env.isObstacleEastImmediate();
- int val = obst ? obstacle : empty;
- if (board.b[coord.x + 1][coord.y] == unvisited) board.b[coord.x + 1][coord.y] = val;
- }
- if (coord.y - 1 >= 0) {
- boolean obst = env.isObstacleSouthImmediate();
- int val = obst ? obstacle : empty;
- if (board.b[coord.x][coord.y - 1] == unvisited) board.b[coord.x][coord.y - 1] = val;
- }
- if (coord.y + 1 < size) {
- boolean obst = env.isObstacleNorthImmediate();
- int val = obst ? obstacle : empty;
- if (board.b[coord.x][coord.y + 1] == unvisited) board.b[coord.x][coord.y + 1] = val;
- }
- }
- void checkIfReset(AgentEnvironment env) {
- if (onHomeColumn(env)) {
- if (topAgent && env.isObstacleNorthImmediate())
- coord = new Point(homeColumn(), board.size - 1);
- else if (bottomAgent && env.isObstacleSouthImmediate()) coord = new Point(homeColumn(), 0);
- }
- }
- void newGameSetup(AgentEnvironment env) {
- if (env.isObstacleSouthImmediate()) bottomAgent = true;
- else topAgent = true;
- leftTeam = env.isBaseEast(1, false);
- rightTeam = !leftTeam;
- newGame = false;
- determineSize = true;
- }
- int investigateSize(AgentEnvironment env) {
- if (topAgent && !env.isFlagSouth(0, true)) {
- size += 1;
- return AgentAction.MOVE_SOUTH;
- }
- if (bottomAgent && !env.isFlagNorth(0, true)) {
- size += 1;
- return AgentAction.MOVE_NORTH;
- }
- if (!doneSizing) {
- doneSizing = true;
- determineSize = false;
- return AgentAction.DO_NOTHING;
- }
- determineSize = false;
- size += 1;
- board = new Board(size, leftTeam);
- return AgentAction.DO_NOTHING;
- }
- boolean onHomeColumn(AgentEnvironment env) {
- if (leftTeam) return !env.isBaseWest(0, false);
- return !env.isBaseEast(0, false);
- }
- srs140430Agent getOtherAgent() {
- if (id % 2 == 0) return oddAgent;
- else return evenAgent;
- }
- int homeColumn() {
- return leftTeam ? 0 : board.size - 1;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement