r/AskComputerScience • u/[deleted] • Feb 05 '21
This is my current A* implementation, is this normal behaviour? (Full explanation in comments)
21
u/DrunkHacker Feb 05 '21
Since this seems like a homework problem, I'd rather ask questions than give answers.
The starting node is (6,6). Why does (5,5) ever get explored? It seems like (7,7), (8,8), and so on should always be preferable to explore as the cost-of-getting-there + heuristic should always be less than (5,5)'s value.
1
u/KronktheKronk Feb 06 '21
I would say it's feasible that a barrier could be constructed that would require the node to move to (5,5) or even further backward in order to path to the destination
0
Feb 05 '21
[deleted]
8
u/OriginalName667 Feb 05 '21
Your weight for Gcost is really high compared to Hcost, which is why it looks like it's just searching in a circle around the start. If you lower Gcost, does the algorithm behave more like A* should, i.e., tend to prefer searching squares that are closer to the end point? This is what it should look like.
3
u/DrunkHacker Feb 05 '21
Are you okay sharing code?
It's a little difficult to diagnose directly but given the behavior after it passes the wall, my hunch is there's something off with the Gcost calculation.
5
u/cheeseisakindof Feb 05 '21
This doesn't look like an A* path search to me. The node is clearly searching via a flood fill algorithm. It looks like you're still drawing the shortest path once you find it, but A* should be able to locate the destination point without needing to check all those points.
2
u/flebron Feb 05 '21
I suggest first implementing pure Dijkstra (no H at all, no "multiplier" for G, just straight up Dijkstra's algorithm). Then, once you have that working correctly, and you see it finds the shortest path, use G() + H() as a cost function, and experiment with allowable heuristics H. Adding multipliers to one or the other is just adding confusion, because it is no more powerful than the plain old G() + H(), and adds places where you can make mistakes.
2
1
u/Destroyer_The_Great Feb 06 '21
Hey mate, I'm really interested in this kind of thing. What did you use to make this? (Graphics wise)
0
Feb 07 '21
[deleted]
2
Feb 12 '21
I did something similar a while ago but used pygame. I wonder which is more efficient for performance.
1
1
0
Feb 05 '21
[deleted]
2
u/Mnaukal Feb 05 '21
How do you compute the G cost? Is it really the length of the current path? The results seem to me as if you were computing the G as the distance between the start and the current position, not taking the walls into account.
0
Feb 05 '21
[deleted]
4
u/Mnaukal Feb 05 '21
I believe so. The G cost should be the real cost to get from start to that position including all the obstacles, e.i. when you make a step from position A to B, you compute the G cost of B as the G cost of A plus the cost of the step.
The H cost on the other hand is a heuristic as we don't know yet how far the end really is (we can only approximate it by the straight line). For A*, the H should be admissible meaning that it should be lower or equal to the real cost (which is true for the straight line distance).
0
Feb 05 '21
[deleted]
0
u/Putnam3145 Feb 06 '21
This isn’t A-star. You’re doing a BFS which defeats the purpose of using the heuristic. You need to do a DFS for it to be A-star.
A* is absolutely 100% a BFS
2
u/idlesn0w Feb 06 '21
BFS is Breadth-First Search. A* is Best-First, which I suppose is neither
-1
u/Putnam3145 Feb 06 '21
A* is a breadth-first search over a weighted graph with a heuristic function--Dijkstra's algorithm is a special case of A*, which kind of inherently means A* is going to be breadth-first
24
u/gab800 Feb 05 '21
Nope, I think the initial part where "the splash is growing" should not be like that. A* should go more or less diagonally up until the wall, then kind-of flow around it in one direction only , and find the end point after reaching the edge of the wall. What I see here looks like Dijkstra.