Объяснение:
После долгого поиска в моем коде и сравнения его с другими вопросами, заданными на этом сайте, я все еще не мог понять, как решить эту проблему.
В настоящее время я занят реализацией алгоритма A * Pathfinding для простой игры на основе 2D-сетки.Код основан на этом псевдокоде:
// A* (star) Pathfinding
// Initialize both open and closed list
let the openList equal empty list of nodes
let the closedList equal empty list of nodes
// Add the start node
put the startNode on the openList (leave it's f at zero)
// Loop until you find the end
while the openList is not empty
// Get the current node
let the currentNode equal the node with the least f value
remove the currentNode from the openList
add the currentNode to the closedList
// Found the goal
if currentNode is the goal
Congratz! You've found the end! Backtrack to get path
// Generate children
let the children of the currentNode equal the adjacent nodes
for each child in the children
// Child is on the closedList
if child is in the closedList
continue to beginning of for loop
// Create the f, g, and h values
child.g = currentNode.g + distance between child and current
child.h = distance from child to end
child.f = child.g + child.h
// Child is already in openList
if child.position is in the openList's nodes positions
if the child.g is higher than the openList node's g
continue to beginning of for loop
// Add the child to the openList
add the child to the openList
Все затраты равны 1. Эвристика - это Манхэттенское расстояние.Начальная точка - это зеленый квадрат, а конечная точка - самый левый розовый квадрат.
Проблема:
На примере начальной точки (5,3) «Зеленый» и конечной точки (3,4) «Розовый», Pathfind отлично работает для этого, но как только зеленый квадрат переместится на один квадрат вправо, программа входит в бесконечный цикл.
Фотографии здесь:
Начало = (5,3), Конец = (3,4)
Начало = (6,3), конец = (3,4)
Пример вывода:
До:
java.awt.Point[x=200,y=120]
false
java.awt.Point[x=200,y=120]
java.awt.Point[x=160,y=160]
false
java.awt.Point[x=200,y=120]
java.awt.Point[x=160,y=160]
java.awt.Point[x=120,y=200]
false
java.awt.Point[x=200,y=120]
java.awt.Point[x=160,y=160]
java.awt.Point[x=120,y=200]
java.awt.Point[x=120,y=240]
false
java.awt.Point[x=200,y=120]
java.awt.Point[x=160,y=160]
java.awt.Point[x=120,y=200]
java.awt.Point[x=120,y=240]
java.awt.Point[x=120,y=280]
false
java.awt.Point[x=200,y=120]
java.awt.Point[x=160,y=160]
java.awt.Point[x=120,y=200]
java.awt.Point[x=120,y=240]
java.awt.Point[x=120,y=280]
java.awt.Point[x=120,y=320]
true
После:
java.awt.Point[x=240,y=120]
false
java.awt.Point[x=240,y=120]
java.awt.Point[x=200,y=160]
false
java.awt.Point[x=240,y=120]
java.awt.Point[x=200,y=160]
java.awt.Point[x=200,y=200]
false
java.awt.Point[x=240,y=120]
java.awt.Point[x=200,y=160]
java.awt.Point[x=200,y=200]
java.awt.Point[x=200,y=240]
false
java.awt.Point[x=240,y=120]
java.awt.Point[x=200,y=160]
java.awt.Point[x=200,y=200]
java.awt.Point[x=200,y=240]
java.awt.Point[x=200,y=280]
false
java.awt.Point[x=240,y=120]
java.awt.Point[x=200,y=160]
java.awt.Point[x=200,y=200]
java.awt.Point[x=200,y=240]
java.awt.Point[x=200,y=280]
java.awt.Point[x=200,y=280]
false
Выходные данные представляют собой закрытый список для каждого цикла в while.И затем проверка, чтобы видеть, является ли текущий узел конечным узлом или нет.
Так что по какой-то причине он продолжает повторять это.не доходя до конца.
Я включу свой код ниже, и любая помощь будет оценена.
A * алгоритм.
public Point[] aStar(Map map,Point start, Point end){
//Returns a list of positions from point start to end.
//Get map array
int[][] Mapp = map.getMap();
//Create astart and end nodes
Node startNode = new Node(null,start);
Node endNode = new Node(null,end);
//Initialize open and closed lists and path list
ArrayList<Node> open_list = new ArrayList<Node>();
ArrayList<Node> closed_list = new ArrayList<Node>();
ArrayList<Node> children = new ArrayList<Node>();
ArrayList<Point> path = new ArrayList<Point>();
//Add start node
open_list.add(startNode);
//Loop until you find the end
while(!open_list.isEmpty()){
//Get this current node
Node currentNode = open_list.get(0);
int current_index = 0;
int counter = 0;
for(Node node: open_list){
if(node.getTotal()<currentNode.getTotal()){
currentNode = node;
current_index = counter;
counter++;
}
}
//Pop current node off open list and add to the closed list
open_list.remove(current_index);
closed_list.add(currentNode);
System.out.println();
for (int i = 0; i <closed_list.size() ; i++) {
System.out.println(closed_list.get(i).getPosition());
}
//Goal
System.out.println(currentNode.equals(endNode));
if(currentNode.equals(endNode)){
Node current = currentNode;
while(current.getParent() != null){
path.add(current.getPosition());
current = current.getParent();
}
//Reverse path
Point[] pat = path.toArray(new Point[path.size()]);
return pat;
}
//Array of new positions
Point[] positions = {new Point(0,-40), new Point(0,40),new Point(-40,0),new Point(40,0),new Point(-40,-40), new Point(-40,40),new Point(40,-40), new Point(40,40)};
//Generate Children
childrenloop:
for(Point newPosition:positions){
//Get node position
Point node_position = new Point((int)(currentNode.getPosition().getX()+ newPosition.getX()),(int)(currentNode.getPosition().getY()+ newPosition.getY()));
//System.out.println(node_position);
//System.out.println(node_position);
//Contain in Map
if(node_position.getX()>(map.getxSize()-40)|| node_position.getX()<0 || node_position.getY()>(map.getySize()-40)|| node_position.getY() <0 ){
System.out.println("Out of Bounds");
continue;
}else
//Check Walkable Terrain
if(mapping[(int)node_position.getX()/40][(int)node_position.getY()/40] != 0){
//System.out.println("Not walkable");
continue;
}else {
//Create New Node
Node new_Node = new Node(currentNode, node_position);
//Add to children
children.add(new_Node);
}
}
//Loop through children
outerloop:
for(Node child : children){
//System.out.println(child.getPosition());
//Check if child is on closed list
for(Node closed_child : closed_list){
if (child.equals(closed_child)){
continue outerloop;
}
}
// Generate the Total, Distance and Heuristic values
child.setDistance(currentNode.getDistance()+1);
int heuristic =(int)Math.round ((Math.pow((child.getPosition().x-endNode.getPosition().x),2))+Math.pow((child.getPosition().y-endNode.getPosition().y),2));
child.setHeuristic(heuristic);
child.setTotal();
//Child already in open list
for(Node open_node:open_list){
if(child.equals(open_node)&& child.getDistance()>open_node.getDistance()){
continue outerloop;
}
}
//Add child to open list
open_list.add(child);
}
}
return null;
}
Узел:
public class Node {
//Node class for A*
Node parent;
Point position;
int distance,heuristic,total;
public Node(Node parent, Point position){
this.parent = parent;
this.position = position;
this.distance = 0;
this.heuristic = 0;
this.total = 0;
}
public boolean equals(Node other){
return this.position.equals(other.position);
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Point getPosition() {
return position;
}
public void setPosition(Point position) {
this.position = position;
}
public int getDistance() {
return distance;
}
public void setDistance(int distance) {
this.distance = distance;
}
public int getHeuristic() {
return heuristic;
}
public void setHeuristic(int heuristic) {
this.heuristic = heuristic;
}
public int getTotal() {
return total;
}
public void setTotal() {
this.total = heuristic+distance;
}
public String toString(){
return position.toString();
}
}
Карта:
public class Map {
final BizarreBazaar game;
ExploreScreen screen;
int level;
int xSize;
int ySize;
int[][] map;
ArrayList<Entity> entities = new ArrayList<Entity>();
public Map(int level,final BizarreBazaar game,ExploreScreen screen) {
this.screen = screen;
this.game = game;
this.level=level;
setMap();
}
public void setMap(){
switch(level){
case 1:
xSize = 15;
ySize = 15;
map = new int[][]{
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
};
entities.add(new Player(game,screen, 5*40, 3*40, 40, 40, 40.0f, new Texture("player.png"),"player"));
entities.add(new Entity(game,screen, 120, 320, 40, 40, 40.0f, new Texture("enemy.png"),""));
entities.add(new Entity(game,screen, 400, 400, 40, 40, 40.0f, new Texture("enemy.png"),""));
entities.add(new Entity(game,screen, 360, 120, 40, 40, 40.0f, new Texture("enemy.png"),""));
break;
public ArrayList<Entity> getEntities(){
return new ArrayList<Entity>(entities);
}
public int[][] getMap(){
return map;
}
public int getxSize() {
return xSize*40;
}
public int getySize() {
return ySize*40;
}
}