sappersearch.java

这是一个基于AStar算法,用于四国军旗中的工兵搜索!(以前这一块是单独写的,后来又加到的主程序中的,但那份不知道放到哪里去了,只好从主程序中再把这部分挖出来,希望大家谅解)

private class SapperSearch{
private GridNode startNode,endNode;
private AStarSearch search;
public SapperSearch(int startI,int startJ,int endI,int endJ){
      startNode=new GridNode(startI,startJ);
      endNode=new GridNode(endI,endJ);
      search=new AStarSearch();
  }
public List findPath(){
      return search.findPath(startNode,endNode);
      
   }
   
}


private  List getStaticNodes(){
  ArrayList<ChessPoint> staticlist=new ArrayList<ChessPoint>();
      for(int i=0,m=1,u=12;i<2;i++){
        for(int j=0,n=6,v=6;j<2;j++){
        	
        	staticlist.add(point[m][n]);
        	staticlist.add(point[u][v]);
        	staticlist.add(point[n][m]);
        	staticlist.add(point[v][u]);
        	n=10;v=10;
        }
       m=5;u=15;
      }
      for(int k=6;k<=10;k +=2 )
         for(int l=6;l<=10;l +=2)
            staticlist.add( point[k][l]);
     staticlist.add(point[8][5]);
     staticlist.add(point[5][8]);
     staticlist.add(point[8][11]);
     staticlist.add(point[11][8]); 

return staticlist;
   
   
}


private class GridNode implements Comparable{
   public GridNode parentNode;
   private int costFromStart;
   private int estimatedCostToGoal;
   public int i,j;
   private static final int constant=40;
   private static final int step_length=4;
   public GridNode(int i,int j){
    this.i=i;
    this.j=j;
      
   }
   public int compareTo(Object o){
   	
   		GridNode other=(GridNode)o;
   	int otherValue=other.getCost();
   	int thisValue=this.getCost();
   	return (thisValue-otherValue);
     
                          
  }
   public int getCost(){
   	 return costFromStart+estimatedCostToGoal;
   }
   public int getCost(GridNode node){
   	  return 1;
  }
  public int getEstimatedCost(GridNode node){
  	return Math.abs(this.i-node.i)%step_length+Math.abs(this.j-node.j)%step_length;
  }
   
   public List getNeighbors(){
   	  List<GridNode> list=new ArrayList<GridNode>();
   	  //向上
   	  conditionalAdd(list,i,j,0,-1);  
   	  //向下
   	  conditionalAdd(list,i,j,0,1);
   	  //向左
   	  conditionalAdd(list,i,j,-1,0);
   	  //向右
   	  conditionalAdd(list,i,j,1,0); 
   	  
   	  return list;
   }
   private void conditionalAdd(List list,int i,int j,int di,int dj){
   	 int newI=i;
   	 int newJ=j;
         List staticList=getStaticNodes();
   	  while(!isOutOfBorder(i,j)&&!point[i][j].isPiece()){
   	  	
   	  	newI +=di;
   	  	newJ +=dj;
   	  	if(!point[newI][newJ].getScotoma())
   	  	  continue;
   	  	  
   	  	GridNode neighbor=new GridNode(newI,newJ);
   	  	if(staticList.contains(neighbor)){          //可能存在bug 比较的是不同的对象
   	  	  list.add(neighbor);
   	  	  break;
   	  	}
   	  	
   	  	}
   	   return; 
   	  
  }
   private boolean isOutOfBorder(int i,int j){
   	  if(i==1||i==5||i==11||i==15)
   	    if(j<=10&&j>=6)
   	    return true;
   	  if(i==6||i==10)
   	    if(j>=1&&j<=15)
   	    return true;
   	  if(j==1||j==5||j==11||j==15)
   	    if(i>=6&&i<=10)
   	    return true;
   	  if(j==6||j==10)
   	    if(i>=1&&i<=15)
   	    return true;
   	  
   	  if(i==8)
   	    if(j>=5&&j<=11)
   	     return true;
   	     
   	  if(j==8)
   	    if(i>=5&&i<=11)
   	    return true;
   	  
   	  return false;
   	
  }
  public boolean equals(Object o){
  	if(o instanceof GridNode){
  		GridNode node=(GridNode)o;
  		if(this.i==node.i&&this.j==node.j)
  		  return true;
  	}
  	return false;
  	
  }
  public int hashCode(){
  	return 100*this.i+1000*this.j;
  } 


}



private class AStarSearch{
  private  class PriorityList<GridNode> extends LinkedList{
  	public void add(Comparable element){
  		for(int i=0;i<size();i++){
  		if(element.compareTo(get(i))<=0){
  			add(i,element);
  			return ;
  		}
  		
  		   
  	}
  	addLast(element);
  	}
  }
  public List constructPath(GridNode node){
  	LinkedList<GridNode> path=new LinkedList<GridNode>();
  	while(node.parentNode!=null){
  		path.addFirst(node);
  		node=node.parentNode;
  	}
  	return path;
  }
  public List findPath(GridNode startNode,GridNode goalNode){
  	PriorityList<GridNode> openList=new PriorityList<GridNode>();
  	ArrayList<GridNode> closedList=new ArrayList<GridNode>();
  	
  	startNode.costFromStart=0;
  	startNode.estimatedCostToGoal=startNode.getEstimatedCost(goalNode);
  	startNode.parentNode=null;
  	openList.add(startNode);
  	
  	while(!openList.isEmpty()){
  		GridNode node=(GridNode)openList.removeFirst();
  		if(node.equals(goalNode)){
  			return constructPath(node);
  		}
  		
  		List neighbors=node.getNeighbors();
  		for(int i=0;i<neighbors.size();i++){
  			GridNode neighborNode=(GridNode)neighbors.get(i);
  			boolean isOpen=openList.contains(neighborNode);
  			boolean isClosed=closedList.contains(neighborNode);
  			int costFromStart=node.costFromStart+node.getCost(neighborNode);
  			if((!isOpen&&!isClosed)||costFromStart<node.costFromStart){
  				neighborNode.parentNode=node;
  				neighborNode.costFromStart=costFromStart;
  				neighborNode.estimatedCostToGoal=neighborNode.getEstimatedCost(goalNode);
  				if(isClosed){
  					closedList.remove(neighborNode);
  					
  				}
  				if(!isOpen){
  					openList.add(neighborNode);
  				}

  			}
  		}
  		closedList.add(node);  
  		   
  		
  	}
  	return null;
  }
}