ICPC 2011 FUKUOKA / Java Challenge AI

KL11.java

import java.util.LinkedList;
import jp.ac.kyushu_u.icpc2011.game.*;
import jp.ac.kyushu_u.icpc2011.game.GameInfo.Direction;
import jp.ac.kyushu_u.icpc2011.game.GameInfo.Handle;
import jp.ac.kyushu_u.icpc2011.game.GameInfo.Speed;
import jp.ac.kyushu_u.icpc2011.game.model.*;
import jp.ac.kyushu_u.icpc2011.gameAPI.*;
import jp.ac.kyushu_u.icpc2011.gameAPI.PlayerAction.*;


public class KL11 implements PlayerRoutine {
	private static int _id = 0;
	private String my_id;
	private static boolean _initialized = false;

	private static int _width, _height;
	private static int _stage[][];
	private static Direction _direction_map[][];
	private int _speed_limit;
	
	public KL11() {
		my_id = "KLab-" + _id++;
		_speed_limit= 3+_id*2;
	}

	private void dumpInfo(GameInfo info) {
		String id = my_id;
		int team = info.getOwnTeam();
		int count = info.getOwnCount();
		Direction direction = info.getOwnDirection();
		int order = info.getOwnOrder();
		int x = info.getOwnPosX();
		int y = info.getOwnPosY();
		int speed = info.getOwnSpeed();
		int distance = info.getGoalDistance(x, y, count);
		int distance0= info.getGoalDistance(x, y, 1);
		
		System.out.println(
				"id=" + id +
				" team=" + team +
				" count=" + count +
				" direc=" + direction.name() +
				" order=" + order +
				" x=" + x + " y=" + y +
				" speed=" + speed +
				" dist=" + distance +
				" dist0=" + distance0);
	}
	private void dumpAction(PlayerAction act) {
		Handle h = act.getHandle();
		Speed s = act.getSpeedChange();
		String target = act.getTarget();
		Type t = act.getType();
		System.out.println("type=" + t + " handle=" + h + " speed=" + s + " target=" + target);
	}

	// 各 cell で車がどの方角を向いていて欲しいかを表示する.
	private void dumpDirectionMap() {
		int w = _width;
		int h = _height;
		int x,y;
		// render direction map
		for (y=0; y<h; ++y) {
			for (x=0; x<w; ++x) {
				char c = ' ';
				Direction d = _direction_map[y][x];
				if (d != null) {
					switch (d) {
					case NORTH:
						c = '^'; break;
					case SOUTH:
						c = 'v'; break;
					case WEST:
						c = '<'; break;
					case EAST:
						c = '>'; break;
					}
				} else {
					if (isWall(x,y)) c = '.';
					else c = Integer.toString(_stage[y][x]).charAt(0);
				}
				System.out.print(c);
			}
			System.out.println();
		}
	}
	
	// calc stage size.
	private void _checkStageSize(GameInfo info) {
		int i=0;
		try {
			for (i = 0;; ++i) info.getGoalDistance(i, 0, 0);
		} catch (ArrayIndexOutOfBoundsException e) {
			_width = i;
		}
		try {
			for (i = 0;; ++i) info.getGoalDistance(0, i, 0);
		} catch (ArrayIndexOutOfBoundsException e) {
			_height = i;
		}
	}
	
	private final boolean isGoal(int x, int y) {
		return _stage[y][x] == 0;
	}
	private final boolean isWall(int x, int y) {
		if (x<0 || x>=_width || y<0 || y>=_height) return true;
		return _stage[y][x] == -1;
	}
	private final boolean isTight(int x, int y) {
		int wall=0;
		if (isWall(x-1, y)) wall++;
		if (isWall(x+1, y)) wall++;
		if (isWall(x, y-1)) wall++;
		if (isWall(x, y+1)) wall++;
		return wall>=2;
	}

	private void _adjustCost() {
		int[][] costmap = new int[_height][_width];
		final int w=_width;
		final int h=_height;
		
		LinkedList<Integer> q = new LinkedList<Integer>();
		
		for (int y=0; y<h; ++y) {
			for (int x=0; x<w; ++x) {
				if (_stage[y][x] <= 0) {
					costmap[y][x] = _stage[y][x];
					continue;
				}
				if (_stage[y][x] == 1) {
					costmap[y][x] = _stage[y][x];
					q.addLast(y*w+x);
					continue;
				}
				costmap[y][x] = Integer.MAX_VALUE; // means not calculated.
			}
		}
		
		while (!q.isEmpty()) {
			int z = q.removeFirst();
			int x=z%w;
			int y=z/w;
			
			int cost = costmap[y][x];
			final int penalty = 3;
			
			if (!isWall(x-1,y)) {
				int nc = cost+1;
				if (isTight(x-1, y)) nc+=penalty;
				if (nc < costmap[y][x-1]) {
					costmap[y][x-1] = nc;
					q.addLast(z-1);
				}
			}
			if (!isWall(x+1,y)) {
				int nc = cost+1;
				if (isTight(x+1, y)) nc+=penalty;
				if (nc < costmap[y][x+1]) {
					costmap[y][x+1] = nc;
					q.addLast(z+1);
				}
			}
			if (!isWall(x,y-1)) {
				int nc=cost+1;
				if (isTight(x, y-1)) nc+=penalty;
				if (nc < costmap[y-1][x]) {
					costmap[y-1][x] = nc;
					q.addLast(z-w);
				}
			}
			if (!isWall(x,y+1)) {
				int nc=cost+1;
				if (isTight(x, y+1)) nc+=penalty;
				if (nc < costmap[y+1][x]) {
					costmap[y+1][x] = nc;
					q.addLast(z+w);
				}
			}
		}
		_stage = costmap;
	}

	private void _init(GameInfo info) {
		if (_initialized) return;

		_checkStageSize(info);
		int x=0, y=0;
		final int w=_width;
		final int h=_height;

		// mapping goal distance.
		_stage = new int[h][w];

		// get lap count to goal.
		int lap;
		for (lap=0; lap<100; ++lap) {
			x = info.getOwnPosX();
			y = info.getOwnPosY();
			if (info.getGoalDistance(x, y, lap+1) == -1)
				break;
		}

		for (y=0; y<h; ++y) {
			for (x=0; x<w; ++x) {
				_stage[y][x] = info.getGoalDistance(x, y, lap);
				System.out.printf("%3d ", _stage[y][x]);
			}
			System.out.println();
		}
		_adjustCost();
		System.out.println("--adjust--");
		for (y=0; y<h; ++y) {
			for (x=0; x<w; ++x) {
				System.out.printf("%3d ", _stage[y][x]);
			}
			System.out.println();
		}

		// assume direction at start is same to direction at goal.
		_direction_map = new Direction[h][w];
		Direction start_direction = info.getOwnDirection();

		for (y=0; y<h; ++y) {
			for (x=0; x<w; ++x) {
				if (_stage[y][x] == 0) {
					_direction_map[y][x] = start_direction;
					continue;
				}
				if (_stage[y][x] < 0)
					continue; // wall

				Direction d = Direction.NORTH;
				int xx=x, yy=y, max_st=0, st=0;
				while (!isWall(xx,yy-1) && _stage[yy-1][xx] < _stage[y][x]) {
					yy--;
					st++;
				}
				if (st > max_st) {
					max_st = st; d = Direction.NORTH;
				}
				xx=x; yy=y; st=0;
				while (!isWall(xx,yy+1) && _stage[yy+1][xx] < _stage[y][x]) {
					yy++;
					st++;
				}
				if (st > max_st) {
					max_st = st;
					d = Direction.SOUTH;
				}
				xx=x; yy=y; st=0;
				while (!isWall(xx-1,yy) && _stage[yy][xx-1] < _stage[y][x]) {
					xx--;
					st++;
				}
				if (st > max_st) {
					max_st = st;
					d = Direction.WEST;
				}
				xx=x; yy=y; st=0;
				while (!isWall(xx+1,yy) && _stage[yy][xx+1] < _stage[y][x]) {
					xx++;
					st++;
				}
				if (st > max_st) {
					max_st = st;
					d = Direction.EAST;
				}
				_direction_map[y][x] = d;
			}
		}
		dumpDirectionMap();
		_initialized = true;
	}

	private int _next_x, _next_y;
	private Direction _next_direction;
	private void predictNextPosition(int x, int y, int speed, Direction d, Handle h) {
		_next_direction = d;
		_next_x = x;
		_next_y = y;
		if (h == Handle.STRAIGHT) {
			switch (d) {
			case NORTH:
				_next_y -= speed;
				break;
			case SOUTH:
				_next_y += speed;
				break;
			case EAST:
				_next_x += speed;
				break;
			case WEST:
				_next_x -= speed;
				break;
			}
		} else {
			int ahead, side;
			ahead = speed;

			if (speed == 1) ahead = 0;
			else ahead = (speed+1)/2;
			side = speed - ahead;
			
			switch (d) {
			case NORTH:
				_next_y -= ahead;
				if (h == Handle.LEFT) {
					_next_direction = Direction.WEST;
					_next_x -= side;
				} else {
					_next_direction = Direction.EAST;
					_next_x += side;
				}
				break;
			case SOUTH:
				_next_y += ahead;
				if (h == Handle.LEFT) {
					_next_direction = Direction.EAST;
					_next_x += side;
				} else {
					_next_direction = Direction.WEST;
					_next_x -= side;
				}
				break;
			case EAST:
				_next_x += ahead;
				if (h == Handle.LEFT) {
					_next_direction = Direction.NORTH;
					_next_y -= side;
				} else {
					_next_direction = Direction.SOUTH;
					_next_y += side;
				}
				break;
			case WEST:
				_next_x -= ahead;
				if (h == Handle.LEFT) {
					_next_direction = Direction.SOUTH;
					_next_y += side;
				} else {
					_next_direction = Direction.NORTH;
					_next_y -= side;
				}
				break;
			}
		}
	}

	private void gonext(int x, int y, int speed, Direction d, Handle h) {
		if (speed>1 && h!=Handle.STRAIGHT) {
			predictNextPosition(x, y, 1, d, Handle.STRAIGHT);
			if (isWall(_next_x, _next_y)) return;
		}
		for (int sp=1; sp<=speed; ++sp) {
			predictNextPosition(x, y, sp, d, h);
			if (isWall(_next_x, _next_y)) return;
		}
	}
	
	private int _calc_cost(int x, int y, Direction d) {
		if (isWall(x,y)) return Integer.MAX_VALUE/2;
		if (_direction_map[y][x] != d) {
			return 10 + _stage[y][x];
		}
		return _stage[y][x];
	}
	
	private Handle _best_handle;
	private Speed _best_speed;
	private int _find_best(int l, int x, int y, int speed, Direction d) {
		if (isWall(x,y)) return Integer.MAX_VALUE/2;
		final int cur_cost = _calc_cost(x, y, d);
		if (l==0) return cur_cost;
		l--;

		int best_cost = Integer.MAX_VALUE/2;
		Handle best_h = Handle.STRAIGHT;
		Speed best_s = Speed.STAY;

		int next_cost;
		int lap = 0;
		int sp = speed;
		//System.out.println("l=" + l + " x=" + x + " y=" + y + " speed=" + speed + " d=" + d);

		// straight / stay
		gonext(x, y, sp, d, Handle.STRAIGHT);
		next_cost = _calc_cost(_next_x, _next_y, _next_direction);
		if (next_cost > cur_cost+100) lap=-1;
		else if (next_cost+100 < cur_cost) lap=1;
		else lap=0;
		//System.out.println("cur="+cur_cost+ " next="+next_cost+ " lap="+lap);
		next_cost = _find_best(l, _next_x, _next_y, sp, _next_direction) + lap*1000;
		if (next_cost < best_cost) {
			best_cost = next_cost;
			best_h = Handle.STRAIGHT;
			best_s = Speed.STAY;
		}
		// left / stay
		gonext(x, y, sp, d, Handle.LEFT);
		next_cost = _calc_cost(_next_x, _next_y, _next_direction);
		if (next_cost > cur_cost+100) lap=-1;
		else if (next_cost+100 < cur_cost) lap=1;
		else lap=0;
		next_cost = _find_best(l, _next_x, _next_y, sp, _next_direction) + lap*1000;
		if (next_cost < best_cost) {
			best_cost = next_cost;
			best_h = Handle.LEFT;
			best_s = Speed.STAY;
		}
		// right / stay
		gonext(x, y, sp, d, Handle.RIGHT);
		next_cost = _calc_cost(_next_x, _next_y, _next_direction);
		if (next_cost > cur_cost+100) lap=-1;
		else if (next_cost+100 < cur_cost) lap=1;
		else lap=0;
		next_cost = _find_best(l, _next_x, _next_y, sp, _next_direction) + lap*1000;
		if (next_cost < best_cost) {
			best_cost = next_cost;
			best_h = Handle.RIGHT;
			best_s = Speed.STAY;
		}

		sp = speed+1;
		if (sp <= _speed_limit) {
		// straight / acc
		gonext(x, y, sp, d, Handle.STRAIGHT);
		next_cost = _calc_cost(_next_x, _next_y, _next_direction);
		if (next_cost > cur_cost+100) lap=-1;
		else if (next_cost+100 < cur_cost) lap=1;
		else lap=0;
		next_cost = _find_best(l, _next_x, _next_y, sp, _next_direction) + lap*1000;
		if (next_cost < best_cost) {
			best_cost = next_cost;
			best_h = Handle.STRAIGHT;
			best_s = Speed.UP;
		}
		// left / acc
		predictNextPosition(x, y, sp, d, Handle.LEFT);
		next_cost = _calc_cost(_next_x, _next_y, _next_direction);
		if (next_cost > cur_cost+100) lap=-1;
		else if (next_cost+100 < cur_cost) lap=1;
		else lap=0;
		next_cost = _find_best(l, _next_x, _next_y, sp, _next_direction) + lap*1000;
		if (next_cost < best_cost) {
			best_cost = next_cost;
			best_h = Handle.LEFT;
			best_s = Speed.UP;
		}
		// right / acc
		gonext(x, y, sp, d, Handle.RIGHT);
		next_cost = _calc_cost(_next_x, _next_y, _next_direction);
		if (next_cost > cur_cost+100) lap=-1;
		else if (next_cost+100 < cur_cost) lap=1;
		else lap=0;
		next_cost = _find_best(l, _next_x, _next_y, sp, _next_direction) + lap*1000;
		if (next_cost < best_cost) {
			best_cost = next_cost;
			best_h = Handle.RIGHT;
			best_s = Speed.UP;
		}
		}

		sp = speed-1;
		if (sp>0) {
		// straight / brk
			gonext(x, y, sp, d, Handle.STRAIGHT);
		next_cost = _calc_cost(_next_x, _next_y, _next_direction);
		if (next_cost > cur_cost+100) lap=-1;
		else if (next_cost+100 < cur_cost) lap=1;
		else lap=0;
		next_cost = _find_best(l, _next_x, _next_y, sp, _next_direction) + lap*1000;
		if (next_cost < best_cost) {
			best_cost = next_cost;
			best_h = Handle.STRAIGHT;
			best_s = Speed.DOWN;
		}
		// left / brk
		gonext(x, y, sp, d, Handle.LEFT);
		next_cost = _calc_cost(_next_x, _next_y, _next_direction);
		if (next_cost > cur_cost+100) lap=-1;
		else if (next_cost+100 < cur_cost) lap=1;
		else lap=0;
		next_cost = _find_best(l, _next_x, _next_y, sp, _next_direction) + lap*1000;
		if (next_cost < best_cost) {
			best_cost = next_cost;
			best_h = Handle.LEFT;
			best_s = Speed.DOWN;
		}
		// right / brk
		gonext(x, y, sp, d, Handle.RIGHT);
		next_cost = _calc_cost(_next_x, _next_y, _next_direction);
		if (next_cost > cur_cost+100) lap=-1;
		else if (next_cost+100 < cur_cost) lap=1;
		else lap=0;
		next_cost = _find_best(l, _next_x, _next_y, sp, _next_direction) + lap*1000;
		if (next_cost < best_cost) {
			best_cost = next_cost;
			best_h = Handle.RIGHT;
			best_s = Speed.DOWN;
		}
		}

		//System.out.println("l=" + l + " x=" + x + " y=" + y + " d=" + d);
		//System.out.println("  cost=" + best_cost + " handle=" + best_h + " speed=" + best_s);

		_best_speed = best_s;
		_best_handle = best_h;
		if (best_cost > 100000)
			_best_speed = Speed.DOWN;
		return best_cost;
	}

	@Override
	public PlayerAction getNextAction(GameInfo info) {
		_init(info);
		
		int x = info.getOwnPosX();
		int y = info.getOwnPosY();
		int speed = info.getOwnSpeed();
		Direction direction = info.getOwnDirection();

//		System.out.println();
//		dumpInfo(info);

		_find_best(7, x, y, speed, direction);
		if (speed >= _speed_limit && _best_speed == Speed.UP) {
			_best_speed = Speed.STAY;
		}
		Type type = Type.MOVE;
		String target = null;
		
		if (_best_speed == Speed.STAY && _best_handle == Handle.STRAIGHT && info.getNearEnemy(true)!=null) {
			type = Type.HATTACK;
			target = info.getNearEnemy(true);
		}
		else if (_best_speed == Speed.STAY && info.getFarEnemy(false)!=null) {
			type = Type.ATTACK;
			target = info.getFarEnemy(false);
		}

		PlayerAction act = new PlayerAction(_best_speed, _best_handle, type, target);
		//dumpAction(act);
		return act;
	}
}