I’m doing a project at my school where I make different path finding algorithms and compare them based on their solution, the time it took to get a solution, and the size of their closed sets (my way of measuring how much memory they were taking up). however I am having trouble with my path finder. it finds a path that does solve the maze but it isn’t a correct path. for instance, using the Dikista algorithm it should just go straight diagonal across an empty maze but it goes in all sorts of weird directions. I think the problem happening when the program changes the ‘cameFrom’ of a node but i can’t figure out what is causing it to mess up.
here is my path finding class. it says AStar as its name but i changed it to a dikista algorithm by just making a nodes ‘h’ function return 0. the getData function is just for ease of reading information from the class
Thank you for your help
package main;
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.awt.Point;
public class AStarPathFinder_Euclidian implements HasData {
public static final int SAVE_LOCATION = 2;
private Field field;
private double time;
private PriorityQueue<Node> openSet;
private ArrayList<Node> closedSet;
private ArrayList<Point> solution;
AStarPathFinder_Euclidian(Field f){
openSet = new PriorityQueue<Node>();
closedSet = new ArrayList<Node>();
solution = new ArrayList<Point>();
field = f;
closedSet.add(new Node(f.startPoint.x,f.startPoint.y,null));
Node currN = closedSet.get(0);
time = System.currentTimeMillis();
while(!(currN.toPoint().equals(f.endPoint))){
System.out.println("testing [" + currN.getX()+","+currN.getY()+"]");
Point[] pl = getAdjPoints(currN);
System.out.println("going thorugh points list");
for(Point n : pl){
if(n != null){
System.out.print("n NOT equal to null: ");
Node tn = new Node(n.x, n.y, currN);
//add nodes to openset that are not in openset
if(!openSet.contains(tn)){
openSet.offer(tn);
System.out.println("added to openSet");
//test to see if a node would have a smaller gScore if
//its came from was set to currN, if not then it reverts
//to its original camefrom
}else{
Node orig = null;
Node[] Narray = new Node[openSet.size()];
Narray = openSet.toArray(Narray);
for(Node e : Narray){
if(e.equals(tn)){
orig = e;
openSet.remove(e);
}
}
if(orig!=null){
tn.setCameFrom(orig.getCameFrom());
openSet.offer(tn);
System.out.println("mChange, ");
}
}
}else{
System.out.println("n was equal to null");
}
}
System.out.println();
currN = openSet.poll();
closedSet.add(currN);
}
while(currN.getCameFrom() != null){
currN = currN.getCameFrom();
solution.add(0,currN.toPoint());
}
time = System.currentTimeMillis()-time;
}
private Point[] getAdjPoints(Node o){
System.out.println("getting adjacent points");
Point tn;
Point[] rl = new Point[8];
//for(int i = 0; i<rl.length; i++){
int counter = 0;
for(int x = -1; x<2; x++){
for(int y = -1; y<2; y++){
if(!(x == 0 && y == 0)){
//System.out.println(x+","+y);
tn = new Point(o.getX()+x, o.getY()+y);
if(field.getCharAt(tn)==Field.WALL_CHARACTER || closedSet.contains(new Node(tn.x, tn.y, null))){
System.out.println("set "+counter+" equal to null");
rl[counter]=null;
// rl*=null;
}else{
System.out.println("set "+counter+" equal "+tn);
rl[counter]=tn;
//rl* = tn;
}
counter++;
}
}
//}
}
System.out.println();
return rl;
}
public Data getData() {
Point[] rSolution = new Point[1];
Point[] rClosedSet = new Point[1];
ArrayList<Point> tempArrL = new ArrayList<Point>();
for(Node n : closedSet){
tempArrL.add(n.toPoint());
}
rSolution = solution.toArray(rSolution);
rClosedSet = tempArrL.toArray(rClosedSet);
return new Data(SAVE_LOCATION, field, time,rClosedSet,rSolution);
}
private class Node implements Comparable<Node> {
public static final int DIAGONAL_DISTANCE = 14;
public static final int ADJACENT_DISTANCE = 10;
private int x;
private int y;
private double hScore; //heuristic score to goal
private double gScore; // distance travelled
private Node cameFrom;
private double fScore;
Node(int x, int y, Node cameFrom){
this.cameFrom = cameFrom;
this.x = x;
this.y = y;
gScore = calcG(cameFrom);
hScore = calcH(this);
fScore = calcF();
}
private double calcF(){
return getGScore()+getHScore();
}
private double calcG(Node o){
if(cameFrom == null){
return 0;
}else{
double g = o.getGScore();
if(isDiagonalTo(o)){
g += DIAGONAL_DISTANCE;
}else{
g += ADJACENT_DISTANCE;
}
return g;
}
}
//euclidian
private double calcH(Node o){
return 0;
//return Point.distance(o.getX(), o.getY(), field.startPoint.x, field.startPoint.y);
}
public int getX(){
return x;
}
public int getY(){
return y;
}
public double getGScore(){
return gScore;
}
public double getHScore(){
return hScore;
}
public double getFScore(){
return fScore;
}
public Node getCameFrom(){
return cameFrom;
}
public void setCameFrom(Node o){
Node tempCameFrom = cameFrom;
double tempGScore = gScore;
cameFrom = o;
gScore = calcG(o);
if(gScore>tempGScore){
gScore = tempGScore;
cameFrom = tempCameFrom;
}
}
public Point toPoint(){
return new Point(x,y);
}
/*
public boolean isNextTo(Node o){
int difX = Math.abs(x)-Math.abs(o.getX());
int difY = Math.abs(y)-Math.abs(o.getX());
if(difX >= -1 && difX <= 1 && difX != 0 &&
difY >= -1 && difY <= 1 && difY != 0){
return true;
}else{
return false;
}
}
*/
private boolean isDiagonalTo(Node o){
if(o.getX() != x && o.getY() != y){
return true;
}else{
return false;
}
}
@Override
public boolean equals(Object o){
if(o instanceof Node){
Node a = (Node)o;
if(a.toPoint().equals(toPoint())){
return true;
}else{
return false;
}
}else{
return false;
}
}
public int compareTo(Node o) {
if(fScore>o.getFScore()){
return -1;
}else if(fScore<o.getFScore()){
return 1;
}else{
return 0;
}
}
}
}
