From e8428af781f6cd8f0360aace90ba2e7eddb98033 Mon Sep 17 00:00:00 2001
From: Junjie <fallin.jie@qq.com>
Date: 星期二, 22 四月 2025 10:35:22 +0800
Subject: [PATCH] #
---
src/main/java/com/zy/common/utils/NavigateSolution.java | 122 +++++++++++++++++++---------------------
1 files changed, 58 insertions(+), 64 deletions(-)
diff --git a/src/main/java/com/zy/common/utils/NavigateSolution.java b/src/main/java/com/zy/common/utils/NavigateSolution.java
index d9887d3..1967be1 100644
--- a/src/main/java/com/zy/common/utils/NavigateSolution.java
+++ b/src/main/java/com/zy/common/utils/NavigateSolution.java
@@ -13,9 +13,7 @@
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
-import java.util.ArrayList;
-import java.util.List;
-import java.util.PriorityQueue;
+import java.util.*;
/**
* 鍥涘悜搴撴牳蹇�
@@ -45,10 +43,10 @@
public PriorityQueue<NavigateNode> Open = new PriorityQueue<NavigateNode>();
//Close琛ㄧ敤鏅�氱殑鏁扮粍
public ArrayList<NavigateNode> Close = new ArrayList<NavigateNode>();
- //Exist琛ㄧ敤鏉ュ瓨鏀惧凡缁忓嚭鐜拌繃鐨勭粨鐐广��
- public ArrayList<NavigateNode> Exist = new ArrayList<NavigateNode>();
+ //鐢ㄦ潵瀛樻斁宸茬粡鍑虹幇杩囩殑缁撶偣銆�
+ Map<String, Integer> bestGMap = new HashMap<>();
- public String astarSearch(NavigateNode start, NavigateNode end, String pythonScriptPath) {
+ public String astarSearchPython(NavigateNode start, NavigateNode end, String pythonScriptPath) {
String maps = JSON.toJSONString(map);
String startStr = start.getX() + "-" + start.getY();
String targetStr = end.getX() + "-" + end.getY();
@@ -104,44 +102,45 @@
return null;
}
-// public NavigateNode astarSearch(NavigateNode start, NavigateNode end) {
-// //鎶婄涓�涓紑濮嬬殑缁撶偣鍔犲叆鍒癘pen琛ㄤ腑
-// this.Open.add(start);
-// //鎶婂嚭鐜拌繃鐨勭粨鐐瑰姞鍏ュ埌Exist琛ㄤ腑
-// this.Exist.add(start);
-// //涓诲惊鐜�
-// while (Open.size() > 0) {
-// //鍙栦紭鍏堥槦鍒楅《閮ㄥ厓绱犲苟涓旀妸杩欎釜鍏冪礌浠嶰pen琛ㄤ腑鍒犻櫎
-// NavigateNode current_node = Open.poll();
-// //灏嗚繖涓粨鐐瑰姞鍏ュ埌Close琛ㄤ腑
-// Close.add(current_node);
-// //瀵瑰綋鍓嶇粨鐐硅繘琛屾墿灞曪紝寰楀埌涓�涓洓鍛ㄧ粨鐐圭殑鏁扮粍
-// ArrayList<NavigateNode> neighbour_node = extend_current_node(current_node);
-// //瀵硅繖涓粨鐐归亶鍘嗭紝鐪嬫槸鍚︽湁鐩爣缁撶偣鍑虹幇
-// for (NavigateNode node : neighbour_node) {
-// // G + H + E (瀵瑰惎鍙戝嚱鏁板鍔犲幓鎷愮偣鏂规calcNodeExtraCost)
-// int gCost = calcNodeCost(current_node, node) * calcNodeExtraCost(current_node, node, end);
-// if (node.getX() == end.getX() && node.getY() == end.getY()) {//鎵惧埌鐩爣缁撶偣灏辫繑鍥�
-// //init_node鎿嶄綔鎶婅繖涓偦灞呯粨鐐圭殑鐖惰妭鐐硅缃负褰撳墠缁撶偣
-// //骞朵笖璁＄畻鍑篏锛� F锛� H绛夊��
-// node.setLastDistance(gCost);
-// node.init_node(current_node, end);
-// return node;
-// }
-//
-// //杩涜璁＄畻瀵笹, F, H 绛夊��
-// node.setLastDistance(gCost);
-// node.init_node(current_node, end);
-// node.setH(calcNodeCost(node, end));
-// node.setF(node.getG() + node.getH());
-//
-// Open.add(node);
-// Exist.add(node);
-// }
-// }
-// //濡傛灉閬嶅巻瀹屾墍鏈夊嚭鐜扮殑缁撶偣閮芥病鏈夋壘鍒版渶缁堢殑缁撶偣锛岃繑鍥瀗ull
-// return null;
-// }
+ public NavigateNode astarSearchJava(NavigateNode start, NavigateNode end) {
+ //鎶婄涓�涓紑濮嬬殑缁撶偣鍔犲叆鍒癘pen琛ㄤ腑
+ this.Open.add(start);
+ //涓诲惊鐜�
+ while (Open.size() > 0) {
+ //鍙栦紭鍏堥槦鍒楅《閮ㄥ厓绱犲苟涓旀妸杩欎釜鍏冪礌浠嶰pen琛ㄤ腑鍒犻櫎
+ NavigateNode current_node = Open.poll();
+
+ if (current_node.getX() == end.getX() && current_node.getY() == end.getY()) {//鎵惧埌鐩爣缁撶偣灏辫繑鍥�
+ return current_node;
+ }
+
+ //灏嗚繖涓粨鐐瑰姞鍏ュ埌Close琛ㄤ腑
+ Close.add(current_node);
+ //瀵瑰綋鍓嶇粨鐐硅繘琛屾墿灞曪紝寰楀埌涓�涓洓鍛ㄧ粨鐐圭殑鏁扮粍
+ ArrayList<NavigateNode> neighbour_node = extend_current_node(current_node);
+ //瀵硅繖涓粨鐐归亶鍘嗭紝鐪嬫槸鍚︽湁鐩爣缁撶偣鍑虹幇
+ for (NavigateNode node : neighbour_node) {
+ // G + H + E (瀵瑰惎鍙戝嚱鏁板鍔犲幓鎷愮偣鏂规calcNodeExtraCost)
+ int gCost = calcNodeExtraCost(current_node, node, end);
+
+ //杩涜璁＄畻瀵笹, F, H 绛夊��
+ node.setG(1 + gCost);
+ node.init_node(current_node, end);
+ node.setH(calcNodeCost(node, end));
+ node.setF(node.getG() + node.getH());
+
+ String key = node.getX() + "_" + node.getY();
+ Integer recordedG = bestGMap.get(key);
+ if (recordedG == null || node.getG() <= recordedG) {
+ bestGMap.put(key, node.getG());
+
+ Open.add(node);
+ }
+ }
+ }
+ //濡傛灉閬嶅巻瀹屾墍鏈夊嚭鐜扮殑缁撶偣閮芥病鏈夋壘鍒版渶缁堢殑缁撶偣锛岃繑鍥瀗ull
+ return null;
+ }
public ArrayList<NavigateNode> extend_current_node(NavigateNode current_node) {
@@ -150,7 +149,7 @@
ConfigService configService = SpringUtils.getBean(ConfigService.class);
if (configService != null) {
Config config = configService.selectOne(new EntityWrapper<Config>()
- .eq("config", "direction_map")
+ .eq("code", "direction_map")
.eq("status", 1));
if (config != null) {
mapDirection = config.getValue();
@@ -196,11 +195,13 @@
if (is_valid(x + 1, y))
{
NavigateNode node = new NavigateNode(x + 1, y);
+ node.setNodeValue(map[x + 1][y]);
neighbour_node.add(node);
}
if (is_valid(x - 1, y))
{
- NavigateNode node = new NavigateNode(x -1, y);
+ NavigateNode node = new NavigateNode(x - 1, y);
+ node.setNodeValue(map[x - 1][y]);
neighbour_node.add(node);
}
}
@@ -210,11 +211,13 @@
if (is_valid(x, y + 1))
{
NavigateNode node = new NavigateNode(x, y + 1);
+ node.setNodeValue(map[x][y + 1]);
neighbour_node.add(node);
}
if (is_valid(x, y - 1))
{
NavigateNode node = new NavigateNode(x, y - 1);
+ node.setNodeValue(map[x][y - 1]);
neighbour_node.add(node);
}
}
@@ -224,11 +227,13 @@
if (is_valid(x, y + 1))
{
NavigateNode node = new NavigateNode(x, y + 1);
+ node.setNodeValue(map[x][y + 1]);
neighbour_node.add(node);
}
if (is_valid(x, y - 1))
{
NavigateNode node = new NavigateNode(x, y - 1);
+ node.setNodeValue(map[x][y - 1]);
neighbour_node.add(node);
}
}
@@ -238,11 +243,13 @@
if (is_valid(x + 1, y))
{
NavigateNode node = new NavigateNode(x + 1, y);
+ node.setNodeValue(map[x + 1][y]);
neighbour_node.add(node);
}
if (is_valid(x - 1, y))
{
- NavigateNode node = new NavigateNode(x -1, y);
+ NavigateNode node = new NavigateNode(x - 1, y);
+ node.setNodeValue(map[x - 1][y]);
neighbour_node.add(node);
}
}
@@ -264,22 +271,9 @@
if (map[x][y] == MapNodeType.CAR.id) {//鑺傜偣鏄皬杞�
return false;
}
- NavigateNode navigateNode = new NavigateNode(x, y);
- if (is_exist(navigateNode)) {
- return false;
- }
+
//浠ヤ笂鎯呭喌閮芥病鏈夊垯鍚堟硶
return true;
- }
-
- public boolean is_exist(NavigateNode node)
- {
- for (NavigateNode exist_node : Exist) {
- if (node.getX() == exist_node.getX() && node.getY() == exist_node.getY()) {
- return true;
- }
- }
- return false;
}
//------------------A*鍚彂鍑芥暟------------------//
@@ -294,12 +288,12 @@
// 绗竴涓偣鎴栫洿绾跨偣
if (currNode.getFather() == null || nextNode.getX() == currNode.getFather().getX()
|| nextNode.getY() == currNode.getFather().getY()) {
- return 1;
+ return 0;
}
// 鎷愬悜缁堢偣鐨勭偣
if (nextNode.getX() == endNode.getX() || nextNode.getY() == endNode.getY()) {
- return 2;
+ return 1;
}
// 鏅�氭嫄鐐�
@@ -308,7 +302,7 @@
鎷垮埌鐖惰妭鐐瑰拰涓嬩竴鑺傜偣
閫氳繃鍒ゆ柇鐖惰妭鐐瑰拰涓嬩竴鑺傜偣鐨剎鏁版嵁鍜寉鏁版嵁閮戒笉鐩稿悓鏃讹紝鍒欒〃鏄庡綋鍓嶅潗鏍囨槸涓�涓嫄鐐�
*/
- return 3;
+ return 1;
}
//------------------A*鍚彂鍑芥暟-end------------------//
--
Gitblit v1.9.1