BFS.java

import java.util.Random; // for test code

final class BFS {
	/* finds nearest ant to a destination in a maze.
	You give it a (partial) map and it plots a route using naive BFS.
	As you discover more obstacles you can call addWater() for them.
	It makes extensive use of pre-allocated data for intermediate results,
	so you must extract the path for each call to findNearestAnt() or you
	lose it. */
	
	public int path[]; /* starting at the nearest ant, steps back to start-pos */

	public BFS(String map,int cols) {
		this.rows = map.length()/cols;
		this.cols = cols;
		stack = new int[rows*cols];
		assert(stack.length == map.length());
		path = new int[rows*cols];
		data = new byte[rows*cols];
		for(int i=0; i<data.length; i++)
			data[i] = (byte)(map.charAt(i) == '%'? 0: 1);  // 0 == water, 1 otherwise
		idx = 1; // will be skipped
	}
	
	public final int rows, cols;

	private int stack[], /* the cells due to be visited */
		head, tail;
	private byte data[], idx; /* the data array combines two functions:
		1) if a cell is 0 then it water
		2) if the cell has a value==idx then it has been visited this turn
		By not using a boolean array to determine what's been visited,
		we can re-use it between calls without clearing it */
		
	public void addWater(int row,int col) {
		data[encodeCoordinate(row,col)] = 0;
	}

	public int findNearestAnt(int row,int col,boolean ant[]) {
		assert(row>=0 && row<rows);
		assert(col>=0 && col<cols);
		if(++idx == 0) { // every 255 times we have to clean the data array
			for(int i=0; i<data.length; i++)
				data[i] = (byte)(data[i] == 0? 0: 1);
			idx=2; // skip over 1
		}
		if(ant[encodeCoordinate(row,col)]) return 0;
		data[encodeCoordinate(row,col)] = idx;
		head = 0;
		tail = 1;
		visit(row,col);
		stack[head++] = 0xffff0000|(row<<8)|col; // high bits are special marker
		while(head < tail) {
			row = (stack[head]>>8)&0xff;
			col = stack[head]&0xff;
			if(ant[encodeCoordinate(row,col)]) {
				int depth = 0;
				do {
					row = (stack[head]>>8)&0xff;
					col = stack[head]&0xff;
					path[depth++] = encodeCoordinate(row,col);
					head = stack[head]>>16;
				} while(head >= 0);
				return depth;
			}
			visit(row,col);
			head++;
		}
		throw new Error("what, no ants?");
	}
	
	private void visit(int row,int col) {
		pushBack(row-1,col);
		pushBack(row+1,col);
		pushBack(row,col-1);
		pushBack(row,col+1);
	}

	private void pushBack(int row,int col) {
		row = clamp(row,rows);
		col = clamp(col,cols);
		int coordinate = encodeCoordinate(row,col);
		if((data[coordinate] != idx) && (data[coordinate]!=0)) {
			data[coordinate] = idx;
			stack[tail++] = (head<<16)|(row<<8)|col; // head encodes the stack to go back to work out the route
		}
	}

	private int clamp(int i,int max) {
		if(i<0) i+= max;
		else if(i>=max) i-=max;
		assert(i>=0 && i<max);
		return i;
	}
	
	public int encodeCoordinate(int row,int col) {
		return row*cols+col;
	}
	
	public int decodeRow(int coordinate) {
		return coordinate/cols;
	}
	
	public int decodeCol(int coordinate) {
		return coordinate%cols;
	}
	
	// test code returns a random non-blocked cell
	public int randomCoordinate() {
		int coordinate;
		do {
			coordinate = random.nextInt(rows*cols);
		} while(0 == data[coordinate]);
		return coordinate;
	}
	private Random random = new Random();

	public static void main(String[] args) {
		boolean debug = false; //### enable to get a nice debug output of the path
		String map = 
			" %%%     %%%% % "+
			" % %   % %%   % "+
			" %     % %    % "+
			" %%%   % %%%    "+
			" %%    %   %  % "+
			"  %%%%%%      % ";
		BFS bfs = new BFS(map,16);
		boolean ant[] = new boolean[map.length()];
		int testSets = 500;
		for(int i=0; i<testSets; i++) {
			long totalTime = 0, testCycles = 100;
			for(int j=0; j<testCycles; j++) {
				int start = bfs.randomCoordinate(), stop = bfs.randomCoordinate();
				ant[stop] = true;
				long startTime = System.nanoTime();
				int depth = bfs.findNearestAnt(bfs.decodeRow(start),bfs.decodeCol(start),ant);
				long elapsedTime = System.nanoTime() - startTime;
				totalTime += elapsedTime;
				ant[stop] = false;
				if(start == stop) {
					if(debug)
						System.out.println("run "+i+" not asked to go anywhere, took "+elapsedTime+"ns");
					assert(depth==0);
					continue;
				}
				assert(depth > 0);
				assert(bfs.path[0] == stop);
				assert(bfs.path[depth-1] == start);
				if(false) { 
					char result[] = map.toCharArray();
					for(int d=0; d<depth; d++) {
						int coordinate = bfs.path[d];
						result[coordinate] = '*';
					}
					result[start] = 'X';
					result[stop] = 'A';
					System.out.println("run "+i+","+j+" = "+depth+", took "+elapsedTime+"ns");
					for(int r=0; r<bfs.rows; r++)
						System.out.println("|"+new String(result,r*bfs.cols,bfs.cols)+"|");
				}
			}
			System.out.println(""+testCycles+" test calls took an average of "+((double)totalTime/(double)testCycles)+"ns");
		}
	}
	
}