使用Java编写的B*算法 (一)

package rpg.stage.path;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

import rpg.objs.Point;

public class BFinding {
	
	
	public BFinding() {
	}
	
	protected HashSet openList = new HashSet();
	protected HashSet leftList = new HashSet();
	protected HashSet rightList = new HashSet();
	protected HashSet closeList = new HashSet();
	
	public synchronized ArrayList find(Point start,Point end,boolean canPenetrate){
		if(end == null){
			return new ArrayList();
		}
		if(start == null){
			return new ArrayList();
		}
		end.clear();
		start.clear();
		openList.clear();
		openList.add(start);
		leftList.clear();
		rightList.clear();
		closeList.clear();
		
		int count = 0;
		
		while(!openList.isEmpty() || !leftList.isEmpty() || !rightList.isEmpty()){
			count ++;
			if(count>1000)
				break;
			Iterator it = openList.iterator();
			if(it.hasNext()){
				Point p = it.next();
				it.remove();
				if(sideNext(p,end,0,canPenetrate))break;
			}
			it = leftList.iterator();
			if(it.hasNext()){
				Point p = it.next();
				it.remove();
				if(sideNext(p,end,1,canPenetrate))break;
			}
			it = rightList.iterator();
			if(it.hasNext()){
				Point p = it.next();
				it.remove();
				if(sideNext(p,end,-1,canPenetrate))break;
			}
		}
		final ArrayList list = new ArrayList();
		while(end.parent!=null){
			list.add(0,new int[]{end.x,end.y});
			end = end.parent;
		}
		return list;
	}
	
	/**
	 * 
	 * @param p
	 * @p





aram end 目标点
	 * @param side 0 direct -1 right 1 left
	 * @param canPenetrate 可否穿透
	 */
	protected boolean sideNext(Point p,Point end,int side,boolean canPenetrate){
		int dir = Point.getDirSimple(p, end);
		Point nextp = null;
		
		if(closeList.contains(p)){
			nextp = nextPassPointSide(p,end,-1,canPenetrate);
			if(nextp != null){
				if(nextp == end){
					nextp.parent = p;
					return true;
				}
				if(this.closeList.contains(nextp))
//					return sideNext(nextp, end, side, canPenetrate);
					return false;
				else if(!this.leftList.contains(nextp))
					addToSearch(p,nextp,this.rightList);
			}
			nextp = nextPassPointSide(p,end,1,canPenetrate);
			if(nextp != null){
				if(nextp == end){
					nextp.parent = p;
					return true;
				}
				if(this.closeList.contains(nextp))
//					return sideNext(nextp, end, side, canPenetrate);
					return false;
				else if(!this.rightList.contains(nextp))
					addToSearch(p,nextp,this.leftList);
			}
			return false;
		}
		this.closeList.add(p);
		if(side == 0){
			if(p.canWalkDir(dir,canPenetrate)){//下一个点可以走
				nextp = p.getPassPointByDir(dir);
				if(nextp == end){
					nextp.parent = p;
					return true;
				}
				if(!this.closeList.contains(nextp)){
					addToSearch(p,nextp,this.openList);
				}
			}
			else//不可走，就分支出两个围绕探索点
			{
				nextp = nextPassPointSide(p,end,-1,canPenetrate);
				if(nextp == end){
					nextp.parent = p;
					return true;
				}
				if(nextp != null){
					if(this.closeList.contains(nextp))
						return sideNext(nextp, end, side, canPenetrate);
//						return false;
					else if(!this.lef