mainshortestpath.java

一个Java的塔防小游戏

package gameoflife;

import java.util.Stack;

class PCell {
	
	int cost;
	PCell to;
	int x, y;
	
	public PCell(int xx, int yy) {
		x = xx;  y = yy;
	}
	
	public String toString() {
		return "" + cost;
	}
}

public class MainShortestPath {

	PCell  getUp(PCell [][] cost, PCell c) {
		int w = cost[0].length;
		int h = cost.length;
		int x = c.x, y = c.y;
		if(y > 0 && cost[y-1][x].cost >= 0)	return cost[y-1][x];
		return null;
	}
	PCell  getDown(PCell [][] cost, PCell c) {
		int w = cost[0].length;
		int h = cost.length;
		int x = c.x, y = c.y;
		if(y < h - 1 && cost[y+1][x].cost >= 0)	return cost[y+1][x];
		return null;
	}
	PCell  getLeft(PCell [][] cost, PCell c) {
		int w = cost[0].length;
		int h = cost.length;
		int x = c.x, y = c.y;
		if(x > 0 && cost[y][x-1].cost >= 0)	return cost[y][x-1];
		return null;
	}
	PCell  getRight(PCell [][] cost, PCell c) {
		int w = cost[0].length;
		int h = cost.length;
		int x = c.x, y = c.y;
		if(x < w - 1 && cost[y][x+1].cost >= 0)	return cost[y][x+1];
		return null;
	}
	void  pushUnVisited(PCell [][] cost, PCell c, Stack stk) {
		int x = c.x, y = c.y;
		PCell tc = getUp(cost,c);
		if(tc != null && tc.cost == Integer.MAX_VALUE && ! stk.contains(tc)) {
			stk.push(tc);
		}
		tc = getDown(cost,c);
		if(tc != null && tc.cost == Integer.MAX_VALUE && ! stk.contains(tc)) {
			stk.push(tc);
		}
		tc = getLeft(cost,c);
		if(tc != null && tc.cost == Integer.MAX_VALUE && ! stk.contains(tc)) {
			stk.push(tc);
		}
		tc = getRight(cost,c);
		if(tc != null && tc.cost == Integer.MAX_VALUE && ! stk.contains(tc)) {
			stk.push(tc);
		}
	}
	void  setMin(PCell [][] cost, PCell c) {
		int x = c.x, y = c.y;
		PCell tc = getUp(cost,c);
		if(tc != null && tc.cost < c.cost) {
			c.cost = tc.cost + 1;
			c.to = tc;
		}
		tc = getDown(cost,c);
		if(tc != null && tc.cost < c.cost) {
			c.cost = tc.cost + 1;
			c.to = tc;
		}
		tc = getLeft(cost,c);
		if(tc != null && tc.cost < c.cost) {
			c.cost = tc.cost + 1;
			c.to = tc;
		}
		tc = getRight(cost,c);
		if(tc != null && tc.cost < c.cost) {
			c.cost = tc.cost + 1;
			c.to = tc;
		}
	}
	
	void  calAllCost(PCell [][] cost) {
		Stack<PCell>  stk = new Stack();
		for(int j = 0; j < cost.length; j++) {
			for(int i = 0; i < cost[0].length; i++) {
				if(cost[j][i].cost == 0) {
					stk.push(cost[j][i]);
					break;
				}
			}
		}
		while( ! stk.empty() ) {
			PCell c = stk.pop();
			setMin(cost, c);
			pushUnVisited(cost, c, stk);
		}
		boolean change = true; 
		while( change ) {
			change = false;
			for(int j = 0; j < cost.length; j++) {
				for(int i = 0; i < cost[0].length; i++) {
					PCell c = getUp(cost, cost[j][i]);
					if(c != null && cost[j][i].cost > c.cost + 1) {
						cost[j][i].cost = c.cost + 1;
						cost[j][i].to   = c;
						change = true;
					}
					c = getDown(cost, cost[j][i]);
					if(c != null && cost[j][i].cost > c.cost + 1) {
						cost[j][i].cost = c.cost + 1;
						cost[j][i].to   = c;
						change = true;
					}
					c = getLeft(cost, cost[j][i]);
					if(c != null && cost[j][i].cost > c.cost + 1) {
						cost[j][i].cost = c.cost + 1;
						cost[j][i].to   = c;
						change = true;
					}
					c = getRight(cost, cost[j][i]);
					if(c != null && cost[j][i].cost > c.cost + 1) {
						cost[j][i].cost = c.cost + 1;
						cost[j][i].to   = c;
						change = true;
					}
				}
			}
		}
		for(int j = 0; j < cost.length; j++) {
			for(int i = 0; i < cost[0].length; i++) {
				System.out.printf("%3d", cost[j][i].cost);
			}
			System.out.println();
		}
	}
	
	PCell[][]  shortestPath(int dx, int dy, int [][] map) {
		PCell cost [][] = new PCell[map.length][map[0].length];
		for(int j = 0; j < map.length; j++) {
			for(int i = 0; i < map[0].length; i++) {
				cost[j][i] = new PCell(i, j);
				if(map[j][i] == 0) {
					cost[j][i].cost = Integer.MAX_VALUE;
				} else {
					cost[j][i].cost = -1;
				}
			}
		}
		cost[dy][dx].cost = 0;
		calAllCost(cost);
		return cost;
	}
	
	void  doSearch() {
		int map [][] = new int[][] {
		{0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0},
		{0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0},
		{0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,1,0},
		{0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,0},
		{0,1,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0},
		{0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0}
		};
		int sx = 0, sy = 0;
		int dx = 17, dy = 5;
		
		//Stack solv = new Stack();
		shortestPath(dx, dy, map);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new MainShortestPath().doSearch();
	}

}