Невозможно реализовать Звезду в Java
Я весь день пытался запустить этот алгоритм и запустить его, но я не могу жить ради себя. Я прочитал много учебников в сети и исходный код на AS3, javascript и C++; но я не могу приспособить то, что я вижу, к своему собственному коду.
Я создал класс AStar, который имеет вложенный класс с именем Node. Карта представляет собой двумерный массив с именем MAP.
Самая большая проблема, с которой я столкнулся, это получение значения F в функции поиска пути.
Я реализовал F = G + H, моя проблема - фактический алгоритм AStar. Может кто-нибудь, пожалуйста, помогите, вот как далеко я до сих пор:
import java.util.ArrayList;
public class AStar
{
int MAP[][];
Node startNode, endNode;
public AStar(int MAP[][], int startXNode, int startYNode,
int endXNode, int endYNode)
{
this.MAP = MAP;
startNode = new Node(startXNode, startYNode);
endNode = new Node(endXNode, endYNode);
}
public void pathfinder()
{
ArrayList openList = new ArrayList();
ArrayList closedList = new ArrayList();
}
public int F(Node startNode, Node endNode)
{
return (H(startNode, endNode) + G(startNode));
}
//H or Heuristic part of A* algorithm
public int H(Node startNode, Node endNode)
{
int WEIGHT = 10;
int distance = (Math.abs(startNode.getX() - endNode.getX()) + Math.abs(startNode.getY() - endNode.getY()));
return (distance * WEIGHT);
}
public int G(Node startNode)
{
if(MAP[startNode.getX() - 1][startNode.getY()] != 1)
{
return 10;
}
if(MAP[startNode.getX() + 1][startNode.getY()] != 1)
{
return 10;
}
if(MAP[startNode.getX()][startNode.getY() -1] != 1)
{
return 10;
}
if(MAP[startNode.getX()][startNode.getY() + 1] != 1)
{
return 0;
}
return 0;
}
public class Node
{
private int NodeX;
private int NodeY;
private int gScore;
private int hScore;
private int fScore;
public Node(int NodeX, int NodeY)
{
this.NodeX = NodeX;
this.NodeY = NodeY;
}
public int getX()
{
return NodeX;
}
public int getY()
{
return NodeY;
}
public int getG()
{
return gScore;
}
public void setG(int gScore)
{
this.gScore = gScore;
}
public int getH()
{
return hScore;
}
public void setH(int hScore)
{
this.hScore = hScore;
}
public int getF()
{
return fScore;
}
public void setF(int fScore)
{
this.fScore = fScore;
}
}
}
Это самое дальнее, что я могу получить с помощью функции поиска пути:
public void pathfinder()
{
LinkedList<Node> openList = new LinkedList();
LinkedList<Node> closedList = new LinkedList();
Node currentNode;
openList.add(startNode);
while(openList.size() > 0)
{
currentNode = (Node) openList.get(0);
closedList.add(currentNode);
for(int i = 0; i < openList.size(); i++)
{
int cost = F(currentNode, endNode);
}
}
}
2 ответа
Я недавно скомбинировал этот код A* для решения проблемы Project Euler. Вам нужно будет заполнить детали для матрицы Node объекты. Используйте его на свой страх и риск, однако я могу сказать, что это решило проблему:)
public class Node {
List<Node> neighbors = new ArrayList<Node>();
Node parent;
int f;
int g;
int h;
int x;
int y;
int cost;
}
public List<Node> aStar(Node start, Node goal) {
Set<Node> open = new HashSet<Node>();
Set<Node> closed = new HashSet<Node>();
start.g = 0;
start.h = estimateDistance(start, goal);
start.f = start.h;
open.add(start);
while (true) {
Node current = null;
if (open.size() == 0) {
throw new RuntimeException("no route");
}
for (Node node : open) {
if (current == null || node.f < current.f) {
current = node;
}
}
if (current == goal) {
break;
}
open.remove(current);
closed.add(current);
for (Node neighbor : current.neighbors) {
if (neighbor == null) {
continue;
}
int nextG = current.g + neighbor.cost;
if (nextG < neighbor.g) {
open.remove(neighbor);
closed.remove(neighbor);
}
if (!open.contains(neighbor) && !closed.contains(neighbor)) {
neighbor.g = nextG;
neighbor.h = estimateDistance(neighbor, goal);
neighbor.f = neighbor.g + neighbor.h;
neighbor.parent = current;
open.add(neighbor);
}
}
}
List<Node> nodes = new ArrayList<Node>();
Node current = goal;
while (current.parent != null) {
nodes.add(current);
current = current.parent;
}
nodes.add(start);
return nodes;
}
public int estimateDistance(Node node1, Node node2) {
return Math.abs(node1.x - node2.x) + Math.abs(node1.y - node2.y);
}
Я не знаю, пытаетесь ли вы использовать только простые типы или просто не думаете об этом, но вам нужно иметь PriorityQueue, чтобы ваш A* работал.
Хороший способ думать, что вы помещаете свою начальную точку в приоритетную очередь с расстоянием 0, а затем запускаете цикл, который останавливается только тогда, когда предыдущая очередь пуста.
В цикле вы извлекаете мин-узел и проверяете, не был ли он открыт раньше или нет, если вы нашли более короткий путь к нему. Если они верны, вы добавляете расстояние к новому узлу, добавляете ребро / из квадрата на карту, а затем добавляете расстояние + эвристика в очередь с приоритетами.
Я написал это для работы с сеткой логических значений и постоянным преобразованием между 1D и 2D массивами, но я надеюсь, что это читабельно:
public void AStarRoute()
{
gridDist = new double[rows][cols];
System.out.println("Start of AStarRoute");
MinPriorityQueue pq = new MinPriorityQueue(rows * cols);
edgeTo = new HashMap<Integer, Integer>();
gridDist[x1Dto2D(start)][y1Dto2D(start)] = 0;
pq.insert(start, 0);
int from;
while (!pq.isEmpty()) {
from = pq.delMin();
int x = x1Dto2D(from);
int y = y1Dto2D(from);
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
int newX = x + i;
int newY = y + j;
if (newX >= 0 && newY >= 0 && newX < cols && newY < rows && !(i == 0 && j == 0)) {
if (grid[newX][newY]) {
//System.out.println("NewDist: " + gridDist[newX][newY] + " - OldDist+dist: " + (gridDist[x][y] + ((Math.abs(i) == Math.abs(j)) ? 1.4 : 1.0)) + ":" + (int)(gridDist[x][y] + ((Math.abs(i) == Math.abs(j)) ? 1.4 : 1.0)));
if (!edgeTo.containsKey(convert2Dto1D(newX, newY)) || gridDist[newX][newY] > (gridDist[x][y] + ((Math.abs(i) == Math.abs(j)) ? 14 : 10))) {
gridDist[newX][newY] = (int)(gridDist[x][y] + ((Math.abs(i) == Math.abs(j)) ? 14 : 10));
maxDistToEnd = (int)Math.max(maxDistToEnd, gridDist[newX][newY]);
edgeTo.put(convert2Dto1D(newX, newY), convert2Dto1D(x, y));
pq.insert(convert2Dto1D(newX, newY), gridDist[newX][newY] + (int)Math.sqrt(Math.pow((newX - x1Dto2D(end))*10, 2) + Math.pow((newY - y1Dto2D(end))*10, 2)));
if(convert2Dto1D(newX, newY) == end){
System.out.println("End found at (" + newX + ", " + newY + ")");
paintGridDist = true;
route = new ArrayList<Integer>();
int n = convert2Dto1D(newX, newY);
route.add(n);
do{
n = edgeTo.get(n);
route.add(n);
}while(start != n);
repaint();
return;
}
}
}
}
}
}
}
paintGridDist = true;
repaint();
}