I've tried looking this up for any suggestions or help but haven't really come across anything.
I'm writing an A* search for searching an image for a path from a start coordinate to an end coordinate.
For this example, the start coordinate is at somewhere in the upper-left corner of the image and the goal coordinate is in the bottom-left corner. However, in the image, there are black bars across the screen at different levels, with only only hole in them. So you start at the top, navigate towards the right side of the screen, go down through the hole, navigate back left because the hold is over there now, and you keep going until you get to the bottom of the image and the goal coordinate.
Here is my implementation currently (hybrid of java/python, but actually written in java):
void run(start, end):
openList = new HashSet<Node>()
closedList = new HashSet<Node>()
openList.add(start)
while (true):
Node current = grabBest(openList)
openList.remove(current)
closedList.add(current)
if (current == end/goal):
return genPath(current)
Node[] neighbors = genNeighbors(current)
for (Neighbor neighbor : neighbors) {
if neighbor == null || closedList.contains(neighbor):
continue;
if neighbor in openList:
// Check if current + cost to go to neighbor < gValue already at neighbor
// update neighbor if our current path costs less than the already found path
else:
neighbor.setG(current.gValue + neighbor.costToWalk)
neighbor.setParent(current)
openList.add(neighbor)
}
void grabBest -> returns the node in openList that has the lowest fValue
void genNeighbors(current) -> generates an array of 4 neighbors, x + 1, x - 1, y + 1, y - 1
// Here, the g value is set to 0 (zero) for testing now
// heuristic is the euclidean distance from the current pixel coordinate to the goal pixel coordinate
// f value is the combination of those two
However, when I run this, it takes forever to run and I eventually just stop it. It seems to be searching all pixels above each level before eventually finding the path down to the next level, where it does the same thing. The paths where I stop it I have drawing out to see it's current path: it goes straight down from the start, hits the wall, and then goes left, and then back up to the very top of the image, and just does crazy stuff like that.
I'm wondering if anyone can see where in my pseudo-code I'm going wrong... I've been trying to step through/debug my code for the past 2 hours and cannot figure out what is going on.
EDIT: Image here (This is a run where the path starts in the upper top right corner of the image and tries to go straight down but hits the black bar):
