我需要實現某種尋路算法，上下文如下：我有一個起點 Point2D 和目標（一個圓）。我在起點和圓心之間畫了一條線。我嘗試計算一條不穿過任何其他圓圈的路徑。（藍色方塊是我想要移動的對象（在起點）），紅色圓圈是我的目標）。我首先想做的是做這樣的事情：但是我的代碼有時似乎有問題，我有負交叉坐標（黑點）。有沒有其他方法可以解決這個問題？我是否從正確的角度看待問題？還有一個問題，因為我正在遍歷圓圈以確定哪些相交或不相交，但如果線與 2 個或更多圓圈相交，它與行星相交的順序與我在屏幕上看到的點的順序不同。我的目標是按照正確的路徑（沒有交叉點）在起點和目標之間創建一個 PathTransition。我沒有提到它，但容器是一個窗格。
2 回答
翻過高山走不出你
TA貢獻1875條經驗 獲得超3個贊
這可能不是您想要的答案，但您是否考慮過對您的數學代碼進行單元測試？數學代碼很容易做到，然后您可以確保低級函數正常工作。
如果之后您仍然有錯誤，您可以編寫一個單元測試以便更輕松地復制它并將其發布在這里。
主題：
您的線條算法可能會變得非常復雜，甚至找不到更多和/或重疊圓圈的解決方案。
為什么不使用標準 A* 算法，其中所有非白色像素都是障礙物。這是矯枉過正嗎？
料青山看我應如是
TA貢獻1772條經驗 獲得超8個贊
解決方案策略與實施
我使用以下策略構建了一個解決方案：在給定的線上from(X,Y)，to(X,Y)我計算與障礙物形狀之一最近的交點。根據該形狀，我將交叉點的長度作為障礙物大小的量度，并從交叉點前不久的某個點以該長度的 1/2 左右觀察點。然后使用不在障礙物內的左右點中的第一個點來細分尋找繞過障礙物的路徑的任務。
protected void computeIntersections(double fromX, double fromY, double toX, double toY) {
// recursively test for obstacles and try moving around them by
// calling this same procedure on the segments to and from
// a suitable new point away from the line
Line testLine = new Line(fromX, fromY, toX, toY);
//compute the unit direction of the line
double dX = toX-fromX, dY = toY-fromY;
double ds = Math.hypot(dX,dY);
dX /= ds; dY /= ds;
// get the length from the initial point of the minimal intersection point
// and the opposite point of the same obstacle, remember also the closest obstacle
double t1=-1, t2=-1;
Shape obst = null;
for (Shape c : lstObstacles) {
if (testLine.intersects(c.getLayoutBounds())) {
Shape s = Shape.intersect(testLine, c);
if( s.getLayoutBounds().isEmpty() ) continue;
// intersection bounds of the current shape
double s1, s2;
if(Math.abs(dX) < Math.abs(dY) ) {
s1 = ( s.getBoundsInLocal().getMinY()-fromY ) / dY;
s2 = ( s.getBoundsInLocal().getMaxY()-fromY ) / dY;
} else {
s1 = ( s.getBoundsInLocal().getMinX()-fromX ) / dX;
s2 = ( s.getBoundsInLocal().getMaxX()-fromX ) / dX;
}
// ensure s1 < s2
if ( s2 < s1 ) { double h=s2; s2=s1; s1=h; }
// remember the closest intersection
if ( ( t1 < 0 ) || ( s1 < t1 ) ) { t1 = s1; t2 = s2; obst = c; }
}
}
// at least one intersection found
if( ( obst != null ) && ( t1 > 0 ) ) {
intersectionDecorations.getChildren().add(Shape.intersect(testLine, obst));
// coordinates for the vertex point of the path
double midX, midY;
// go to slightly before the intersection set
double intersectX = fromX + 0.8*t1*dX, intersectY = fromY + 0.8*t1*dY;
// orthogonal segment of half the length of the intersection, go left and right
double perpX = 0.5*(t2-t1)*dY, perpY = 0.5*(t1-t2)*dX;
Rectangle testRect = new Rectangle( 10, 10);
// go away from the line to hopefully have less obstacle from the new point
while( true ) {
// go "left", test if free
midX = intersectX + perpX; midY = intersectY + perpY;
testRect.setX(midX-5); testRect.setY(midY-5);
if( Shape.intersect(testRect, obst).getLayoutBounds().isEmpty() ) break;
// go "right"
midX = intersectX - perpX; midY = intersectY - perpY;
testRect.setX(midX-5); testRect.setY(midY-5);
if( Shape.intersect(testRect, obst).getLayoutBounds().isEmpty() ) break;
// if obstacles left and right, try closer points next
perpX *= 0.5; perpY *= 0.5;
}
intersectionDecorations.getChildren().add(new Line(intersectX, intersectY, midX, midY));
// test the first segment for intersections with obstacles
computeIntersections(fromX, fromY, midX, midY);
// add the middle vertex to the solution path
connectingPath.getElements().add(new LineTo(midX, midY));
// test the second segment for intersections with obstacles
computeIntersections(midX, midY, toX, toY);
}
}
正如人們所看到的，第一個選擇的點可能不是最佳點，但它確實可以完成工作。為了做得更好，必須構建某種左右決策的決策樹，然后在變體中選擇最短路徑。然后應用所有常用策略，例如從目標位置開始第二棵樹、深度優先搜索等。
輔助線是使用的交點和與新中點垂直的線。
PathfinderApp.java
我使用這個問題來熟悉 FXML 的使用，因此主應用程序具有通常的樣板代碼。
package pathfinder;
import javafx.application.Application;
import javafx.fxml.FXMLLoader;
import javafx.scene.Parent;
import javafx.scene.Scene;
import javafx.stage.Stage;
public class PathfinderApp extends Application {
@Override
public void start(Stage primaryStage) throws Exception{
Parent root = FXMLLoader.load(getClass().getResource("pathfinder.fxml"));
primaryStage.setTitle("Finding a path around obstacles");
primaryStage.setScene(new Scene(root, 1600, 900));
primaryStage.show();
}
public static void main(String[] args) {
launch(args);
}
}
探路者.fxml
FXML 文件包含用戶界面的“大多數”靜態元素（在給定類型的任務中總是存在的意義上）。它們是光標矩形、目標圓和它們之間的一條線。然后將路徑構建中的障礙和“裝飾”分組，以及路徑本身。這種分離允許在沒有其他組織工作的情況下相互獨立地清除和填充這些分組。
<?xml version="1.0" encoding="UTF-8"?>
<?import javafx.scene.layout.Pane?>
<?import javafx.scene.Group?>
<?import javafx.scene.text.Text?>
<?import javafx.scene.shape.Line?>
<?import javafx.scene.shape.Path?>
<?import javafx.scene.shape.Circle?>
<?import javafx.scene.shape.Rectangle?>
<?import javafx.scene.paint.Color?>
<Pane xmlns:fx="http://javafx.com/fxml"
fx:controller="pathfinder.PathfinderController" onMouseClicked="#setCursor">
<Circle fx:id="target" centerX="800" centerY="250" radius="25" fill="red"/>
<Rectangle fx:id="cursor" x="175" y="175" width="15" height="15" fill="lightblue"/>
<Line fx:id="straightLine" startX="${cursor.X}" startY="${cursor.Y}" endX="${target.centerX}" endY="${target.centerY}"
strokeWidth="2" stroke="gray" strokeLineCap="butt" strokeDashArray="10.0, 5.0" mouseTransparent="true" />
<Group fx:id="obstacles" />
<Group fx:id="intersectionDecorations" />
<Path fx:id="connectingPath" strokeWidth="2" stroke="blue" />
</Pane>
探路者控制器.java
主要工作在控制器中完成。一些最小的初始化將目標和光標綁定到它們的連接線和鼠標事件處理程序（使用防止光標放置在某些障礙物內的代碼），然后是路徑查找程序。一個框架過程和上面的遞歸主力。
package pathfinder;
import javafx.fxml.FXML;
import javafx.geometry.Bounds;
import javafx.scene.layout.Pane;
import javafx.scene.Group;
import javafx.scene.text.Text;
import javafx.scene.text.Font;
import javafx.scene.shape.Shape;
import javafx.scene.shape.Line;
import javafx.scene.shape.Path;
import javafx.scene.shape.LineTo;
import javafx.scene.shape.MoveTo;
import javafx.scene.shape.Circle;
import javafx.scene.shape.Rectangle;
import javafx.scene.paint.Color;
import javafx.scene.input.MouseEvent;
import java.util.*;
public class PathfinderController {
@FXML
private Circle target;
@FXML
private Rectangle cursor;
@FXML
private Line straightLine;
@FXML
private Path connectingPath;
@FXML
private Group obstacles, intersectionDecorations;
private static List<Shape> lstObstacles = Arrays.asList(
new Circle( 500, 250, 125, Color.BLUE ),
new Circle( 240, 400, 75, Color.GREEN ),
new Circle( 700, 500, 150, Color.VIOLET),
new Circle(1150, 300, 115, Color.ORANGE)
);
@FXML
public void initialize() {
straightLine.startXProperty().bind(cursor.xProperty());
straightLine.startYProperty().bind(cursor.yProperty());
obstacles.getChildren().addAll(lstObstacles);
findPath();
}
@FXML
protected void setCursor(MouseEvent e) {
Shape test = new Rectangle(e.getX()-5, e.getY()-5, 10, 10);
for (Shape c : lstObstacles) {
if( !Shape.intersect(c, test).getLayoutBounds().isEmpty() ) return;
}
cursor.setX(e.getX());
cursor.setY(e.getY());
findPath();
}
protected void findPath() {
double fromX = cursor.getX();
double fromY = cursor.getY();
double toX = target.getCenterX();
double toY = target.getCenterY();
intersectionDecorations.getChildren().clear();
connectingPath.getElements().clear();
// first point of path
connectingPath.getElements().add(new MoveTo(fromX, fromY));
// check path for intersections, move around if necessary
computeIntersections(fromX, fromY, toX, toY);
// last point of the path
connectingPath.getElements().add(new LineTo(toX, toY));
}
protected void computeIntersections(double fromX, double fromY, double toX, double toY) {
...
}
// end class
}
添加回答
舉報
0/150
提交
取消