Стратегия и реализация решения
Я построил решение со следующей стратегией: На данной линии от 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);
}
}
pathfinder.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>
PathfinderController.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
}