JavaFX：使用 Point2D 和 Line 进行寻路

Question

我需要实现某种寻路算法，上下文如下：我有一个起点 Point2D 和目标（一个圆）。我在起点和圆心之间画了一条线。我尝试计算一条不穿过任何其他圆圈的路径。（蓝色方块是我想要移动的对象（在起点）），红色圆圈是我的目标）。我首先想做的是做这样的事情：但是我的代码有时似乎有问题，我有负交叉坐标（黑点）。有没有其他方法可以解决这个问题？我是否从正确的角度看待问题？还有一个问题，因为我正在遍历圆圈以确定哪些相交或不相交，但如果线与 2 个或更多圆圈相交，它与行星相交的顺序与我在屏幕上看到的点的顺序不同。我的目标是按照正确的路径（没有交叉点）在起点和目标之间创建一个 PathTransition。我没有提到它，但容器是一个窗格。

Answer 1

这可能不是您想要的答案，但您是否考虑过对您的数学代码进行单元测试？数学代码很容易做到，然后您可以确保低级函数正常工作。

如果之后您仍然有错误，您可以编写一个单元测试以便更轻松地复制它并将其发布在这里。

主题：

您的线条算法可能会变得非常复杂，甚至找不到更多和/或重叠圆圈的解决方案。

为什么不使用标准 A* 算法，其中所有非白色像素都是障碍物。这是矫枉过正吗？

Answer 2

解决方案策略与实施

我使用以下策略构建了一个解决方案：在给定的线上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

}