使用Java编写的B*算法
2023-09-27 14:23:51 时间
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<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 start,Point end,boolean canPenetrate){ if(end == null){ return new ArrayList<int[]>(); } if(start == null){ return new ArrayList<int[]>(); } 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<Point> 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<int[]> list = new ArrayList<int[]>(); while(end.parent!=null){ list.add(0,new int[]{end.x,end.y}); end = end.parent; } return list; } /** * * @param p * @param 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.leftList.contains(nextp)) addToSearch(p,nextp,this.rightList); } 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.rightList.contains(nextp)) addToSearch(p,nextp,this.leftList); } } } else if(side>0){ nextp = p.getPassPointByDir(dir); if(nextp == end){ nextp.parent = p; return true; } if(nextp != null && !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 && !this.closeList.contains(nextp) && !this.rightList.contains(nextp)){ addToSearch(p,nextp,this.leftList); } } } else if(side<0){ nextp = p.getPassPointByDir(dir); if(nextp == end){ nextp.parent = p; return true; } if(nextp != null && !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 && !this.closeList.contains(nextp) && !this.leftList.contains(nextp)){ addToSearch(p,nextp,this.rightList); } } } return false; } protected void addToSearch(Point parent,Point next,HashSet<Point> list){ next.clear(); next.parent = parent; list.add(next); } /** * * @param p * @param side >0 或者 <0 * @param canPenetrate * @return */ protected Point nextPassPointSide(Point p,Point end,int side,boolean canPenetrate){ int dir = Point.getDirSimple(p, end); Point nextp = null; if(side<0){ while(side>=-7){ dir = Point.rightdir(dir); if(p.canWalkDir(dir,canPenetrate)){ nextp = p.getPassPointByDir(dir); if(!this.closeList.contains(nextp)){ break; } } side--; } } else { while(side<=7){ dir = Point.leftdir(dir); if(p.canWalkDir(dir,canPenetrate)){ nextp = p.getPassPointByDir(dir); if(!this.closeList.contains(nextp)){ break; } } side++; } } return nextp; } }
相关文章
- Java算法面试题(史上最强、持续更新、吐血推荐)
- 使用jvisualvm.exe工具查看java项目内存溢出(堆溢出)--制造内存溢出
- 在使用java -jar命令启动jenkins时,如何指定http端口号
- 怎么在java 8的map中使用stream
- hive启动时 Terminal initialization failed; falling back to unsupported java.lang.IncompatibleClassChangeError: Found class jline.Terminal, but interface was expected
- c#代码 天气接口 一分钟搞懂你的博客为什么没人看 看完python这段爬虫代码,java流泪了c#沉默了 图片二进制转换与存入数据库相关 C#7.0--引用返回值和引用局部变量 JS直接调用C#后台方法(ajax调用) Linq To Json SqlServer 递归查询
- 【LeetCode-面试算法经典-Java实现】【129-Sum Root to Leaf Numbers(全部根到叶子结点组组成的数字相加)】
- Word处理控件Aspose.Words功能演示:使用 Java 在 MS Word 文档中进行邮件合并
- 采用Java 8中Lambda表达式和默认方法的模板方法模式
- 安卓开发基础(Java)——TextView的使用
- Java面向对象中的异常
- 基于Java实现生产者与消费者算法模拟【100010232】
- Java final类
- java解析复杂json:JSONObject 和 JSONArray的使用
- java学习-sha1散列算法
- 图数据库 Neo4j Java Api 的使用
- java 线程
- Java实现各种加密验证算法(MD5、SHA256、base64、pdkdf2、pdkdf2_sha256)
- 华为OD机试 -数字涂色(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -求解连续数列(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -出租车计费(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 比赛评分(Java) | 机试题+算法思路+考点+代码解析 【2023】
- Java数据结构与算法 day11 多路查找树
- Java数据结构与算法 day10 树结构实际应用(三)
- Java小白入门200例53之冒泡排序