r/AskComputerScience • • Feb 05 '21

This is my current A* implementation, is this normal behaviour? (Full explanation in comments)

83 Upvotes

21 comments sorted by

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.

0

u/[deleted] Feb 05 '21

[deleted]

5

u/gab800 Feb 05 '21

Hmm, I haven't pulled up Dijkstra or A*, and relying on my memory, but shouldn't it be Dijkstra if we make H Cost a constant?

Also, G Cost is a bit strange for me, as it should not be estimated, it is an exact value for each visited node, because we already know the path from current to start.

For me: Dijkstra is finding the best route, in a brute force but reliable way. A* is saving a shitton of calculations by adding common sense (heuristic), and by removing the requirement of the absolute best route, which will work in real world applications. A maze is a special scenario where A* will behave Dijkstra-like.

2

u/lxpnh98_2 Feb 05 '21 edited Feb 06 '21

A* should still find the optimal path, if you choose a heuristic function that is 'admissible', that is, it always gives a lower bound on the length of the remaining nodes needed in the path.

Here, with a square grid and the heuristic function being the Euclidean distance between the current and end nodes, this applies. The reason it works is because once you get to the last step of considering the end node itself, where G Cost + H Cost will give you the actual cost of the path (H Cost = 0), that node will only be explored if there is no other node that could possibly have a lower cost (for every other node to be explored, G Cost + H Cost is greater), just like in Dijkstra.

1

u/gab800 Feb 05 '21

I think I get what you mean, but it still should propagate faster towards the wall, it keeps checking nodes that are clearly further away from the goal. The scene is quite simple, it should aim for the wall straight away at the first phase.

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

u/[deleted] 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

u/otaekek Feb 05 '21

Did you try going depth first ?

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

u/[deleted] Feb 07 '21

[deleted]

2

u/[deleted] Feb 12 '21

I did something similar a while ago but used pygame. I wonder which is more efficient for performance.

1

u/Destroyer_The_Great Feb 07 '21

Ah thanks mate! Appreciate it, I'll have a look thanks

1

u/josh2751 Feb 05 '21

That's not exactly A*, you've added something to it.

0

u/[deleted] 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

u/[deleted] 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

u/[deleted] 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