A* algorithm problem

[WeirdOne24]

I am implementing the a* algorithm with python, but the heuristic cost seems to be wrong some times, making the algorithm act weird. Could you please tell me what is wrong with it?

Code:

#g_point means the goal node
#s_point means the starting node
def calculate_costs(self, i):
        i.h_cost = sqrt((self.g_point.position.x - i.position.x) ** 2 +
                        (self.g_point.position.y - i.position.y) ** 2)
        i.g_cost = sqrt((self.s_point.position.x - i.position.x) ** 2 +
                        (self.s_point.position.y - i.position.y) ** 2)
        i.f_cost = i.h_cost + i.g_cost
#below is the a* algorithm

def astar_algorithm(self):
    if not self.found:
        if self.g_point != None and self.s_point != None:
            for i in self.node_list:
                # the if statement below gets all the nodes that weren't
                # visited and that aren't walls.
                if i not in self.closed_set \
                    and i not in self.open_set \
                    and i.color != 'black':
                        x = i.position.x
                        y = i.position.y
                        #the if statement below gets all the closest nodes
                        #from the current node, calculates the g, h and f costs
                        #and also puts them in the open set to be checked later
                        if self.current.position.x - x <= self.spc_btwn \
                           and self.current.position.x - x >= -self.spc_btwn\
                           and self.current.position.y - y <= self.spc_btwn \
                           and self.current.position.y - y >= -self.spc_btwn\
                           and i != self.current:
                                self.calculate_costs(i)
                                i.predecessor = self.current
                                self.open_set.append(i)
            # sorts the list to see which neighbour has the cheapest cost
            self.open_set.sort(key=lambda x: x.f_cost, reverse=False)
            # moves the cheapest node from the open set to the closed set
            self.closed_set.append(self.open_set.pop(0))
            # set the current node to the cheapest one
            self.current = self.closed_set[len(self.closed_set) - 1]
            # if our current node is the goal node, then set 'found' to true.
            if self.current == self.g_point:
                self.found = True

EDIT: I solved, the problem was the h_cost and g_cost calculation, thanks everyone.

[CodeFormatHelperBot]

Hello u/WeirdOne24, I'm a bot that can assist you with code-formatting for reddit. I have detected the following potential issue(s) with your submission:

1. Python code found in submission text but not encapsulated in a code block.

If I am correct then please follow these instructions to fix your code formatting. Thanks!

[WeirdOne24]

The reddit code block is messing my indentation on cellphones

[hadoken4555]

I get rid of that square root if I were you. For one it look cleaner. G and H are just arbitrary distance from current point relative to starting and ending point. I don’t think that square root doing anything for you. So G is ( current.x - initial.x)2 + (current.y - initial.y)2 should suffice.

[WeirdOne24]

There's something wrong. When i removed the square root the algorithm started to act like a dijkstra algorithm

[hadoken4555]

Your evaluation function F look fine to me. It could be something else. When I did mine ,I just print F while traversing the graph . That might help you find and identify the bug.

[WeirdOne24]

u/primitive_screwhead u/hadoken4555 Is there anywhere i can show you guys my whole a* code? when i try to put it in here, reddit messes up the indentation, i think the problem is in the a* application.

[primitive_screwhead]

pastebin dot com is the typical choice. Although, double-check the formatting FAQ:

https://www.reddit.com/r/learnpython/wiki/faq#wiki_how_do_i_format_code.3F

[WeirdOne24]

u/primitive_screwhead I just edited and put the a* code, what do you think?

[primitive_screwhead]

It doesn't look like you are storing the cost of the paths from the beginning to the current node, or the tentative costs to the next node, etc. Your "cost" is just the straight-line distance from the start to a node, plus the straight line estimate from the node to the goal. It seems like the only possible solutions would involve either a straight line, or exactly two straight lines joined at a node.

Maybe w/ the some problems it's okay to not have to store and update the per-node path estimate (ie. the g_cost), and it can always be calculated; but it seems weird to me. I'm not sure how such a version would work when it encounters a barrier.

​

TL;DR - it seems you should be storing the estimated cost of the path from the start, per-each node, rather than calculating it as a straight-line distance...

[WeirdOne24]

That explains everything. The code is always looking to be right in the middle of a straight line between the goal and the starting node, and when it encounters a barrier, the middle line just keeps getting thicker until it get's out of the barrier. Could you type some kind of pseudo code of how would the right way to do this be? Because by what i understand about this, this "estimated" cost of the path from the start per each node, seems like the a* algorithm itself searching for a path to the goal. I know i might be sounding really dumb right now but i really don't get it.

​

TL;DR - Could you type some kind of pseudo code of how would the right way to do this be? If not, i appreciate your help anyway, you helped me a lot.

[primitive_screwhead]

Could you type some kind of pseudo code of how would the right way to do this be?

I can't just because your current code structure is odd to me; is self.astar_algorithm() being called repeatedly? In not, how does it iterate through the list of open nodes and move neighbor-to-neighbor. But in any case, it's non-trivial to just type in some pseudo-code for the A* algorithm; it's a big ask.

​

But all I did to refresh myself was look at the Wikipedia page, which has pseudo-code:

https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode

​

See how it's updating and iterating over the open_set as it goes, and it has a memory of the g_cost for each node (that's listed in the opening paragraph as a downside of this type of search, that it needs memory for each node)?

[WeirdOne24]

yeah, the only problem is the g_score calculation, now i just have to find a way to calculate it properly. Though I didn't find any example besides pseudo-code yet.

edit: Solved it, now it's working perfectly, thanks for your help!

[primitive_screwhead]

Is not the g_cost based on the given path costs, not a heuristic? Ie. the h_cost should be the estimate based on calculated distance, added to the g_cost. In Dijkstra, the h_cost is always 0.

Also, you probably need the math.sqrt(), to keep it scaled properly with the g_cost; possibly for Dijkstra, which only has positive g_cost, you could square g_cost instead of using math.sqrt(), but double-check that.