熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Java編程 >> Java核心技術 >> 正文

使用Java編寫的B*算法

2013-11-23 19:28:35  來源: Java核心技術 

  使用Java編寫的B*算法

  package rpgstagepath;

  import javautilArrayList;

  import javautilHashSet;

  import javautilIterator;

  import rpgobjsPoint;

  public class BFinding {

  public BFinding() {

  }

  protected HashSet<Point> openList = new HashSet<Point>();

  protected HashSet<Point> leftList = new HashSet<Point>();

  protected HashSet<Point> rightList = new HashSet<Point>();

  protected HashSet<Point> closeList = new HashSet<Point>();

  public synchronized ArrayList<int[]> find(Point startPoint endboolean canPenetrate){

  if(end == null){

  return new ArrayList<int[]>();

  }

  if(start == null){

  return new ArrayList<int[]>();

  }

  endclear();

  startclear();

  openListclear();

  openListadd(start);

  leftListclear();

  rightListclear();

  closeListclear();

  int count = ;

  while(!openListisEmpty() || !leftListisEmpty() || !rightListisEmpty()){

  count ++;

  if(count>)

  break;

  Iterator<Point> it = erator();

  if(ithasNext()){

  Point p = itnext();

  itremove();

  if(sideNext(pendcanPenetrate))break;

  }

  it = erator();

  if(ithasNext()){

  Point p = itnext();

  itremove();

  if(sideNext(pendcanPenetrate))break;

  }

  it = erator();

  if(ithasNext()){

  Point p = itnext();

  itremove();

  if(sideNext(pendcanPenetrate))break;

  }

  }

  final ArrayList<int[]> list = new ArrayList<int[]>();

  while(endparent!=null){

  listadd(new int[]{endxendy});

  end = endparent;

  }

  return list;

  }

  /**

  *

  * @param p

  * @param end 目標點

  * @param side direct right left

  * @param canPenetrate 可否穿透

  */

  protected boolean sideNext(Point pPoint endint sideboolean canPenetrate){

  int dir = PointgetDirSimple(p end);

  Point nextp = null;

  if(ntains(p)){

  nextp = nextPassPointSide(pendcanPenetrate);

  if(nextp != null){

  if(nextp == end){

  nextpparent = p;

  return true;

  }

  if(ntains(nextp))

  //                  return sideNext(nextp end side canPenetrate);

  return false;

  else if(!ntains(nextp))

  addToSearch(pnextpthisrightList);

  }

  nextp = nextPassPointSide(pendcanPenetrate);

  if(nextp != null){

  if(nextp == end){

  nextpparent = p;

  return true;

  }

  if(ntains(nextp))

  //                  return sideNext(nextp end side canPenetrate);

  return false;

  else if(!ntains(nextp))

  addToSearch(pnextpthisleftList);

  }

  return false;

  }

  thiscloseListadd(p);

  if(side == ){

  if(pcanWalkDir(dircanPenetrate)){//下一個點可以走

  nextp = pgetPassPointByDir(dir);

  if(nextp == end){

  nextpparent = p;

  return true;

  }

  if(!ntains(nextp)){

  addToSearch(pnextpthisopenList);

  }

  }

  else//不可走就分支出兩個圍繞探索點

  {

  nextp = nextPassPointSide(pendcanPenetrate);

  if(nextp == end){

  nextpparent = p;

  return true;

  }

  if(nextp != null){

  if(ntains(nextp))

  return sideNext(nextp end side canPenetrate);

  //                      return false;

  else if(!ntains(nextp))

  addToSearch(pnextpthisrightList);

  }

  nextp = nextPassPointSide(pendcanPenetrate);

  if(nextp == end){

  nextpparent = p;

  return true;

  }

  if(nextp != null){

  if(ntains(nextp))

  return sideNext(nextp end side canPenetrate);

  //                      return false;

  else if(!ntains(nextp))

  addToSearch(pnextpthisleftList);

  }

  }

  }

  else if(side>){

  nextp = pgetPassPointByDir(dir);

  if(nextp == end){

  nextpparent = p;

  return true;

  }

  if(nextp != null && !ntains(nextp)){

  addToSearch(pnextpthisopenList);

  }

  else

  {

  nextp = nextPassPointSide(pendcanPenetrate);

  if(nextp == end){

  nextpparent = p;

  return true;

  }

  if(nextp != null && !ntains(nextp) && !ntains(nextp)){

  addToSearch(pnextpthisleftList);

  }

  }

  }

  else if(side<){

  nextp = pgetPassPointByDir(dir);

  if(nextp == end){

  nextpparent = p;

  return true;

  }

  if(nextp != null && !ntains(nextp)){

  addToSearch(pnextpthisopenList);

  }

  else

  {

  nextp = nextPassPointSide(pendcanPenetrate);

  if(nextp == end){

  nextpparent = p;

  return true;

  }

  if(nextp != null && !ntains(nextp) && !ntains(nextp)){

  addToSearch(pnextpthisrightList);

  }

  }

  }

  return false;

  }

  protected void addToSearch(Point parentPoint nextHashSet<Point> list){

  nextclear();

  nextparent = parent;

  listadd(next);

  }

  /**

  *

  * @param p

  * @param side > 或者 <

  * @param canPenetrate

  * @return

  */

  protected Point nextPassPointSide(Point pPoint endint sideboolean canPenetrate){

  int dir = PointgetDirSimple(p end);

  Point nextp = null;

  if(side<){

  while(side>=){

  dir = Pointrightdir(dir);

  if(pcanWalkDir(dircanPenetrate)){

  nextp = pgetPassPointByDir(dir);

  if(!ntains(nextp)){

  break;

  }

  }

  side;

  }

  }

  else

  {

  while(side<=){

  dir = Pointleftdir(dir);

  if(pcanWalkDir(dircanPenetrate)){

  nextp = pgetPassPointByDir(dir);

  if(!ntains(nextp)){

  break;

  }

  }

  side++;

  }

  }

  return nextp;

  }

  }


From:http://tw.wingwit.com/Article/program/Java/hx/201311/26927.html
  • 上一篇文章:

  • 下一篇文章:
  • 推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.