I saw a few (closed) questions here and thought I could shed some light on this. I’m not an engineer but I studied computer science theory (20+ years ago). A few basic concepts stuck with me after all these years so I might be in a unique position to explain parts of A* to other non-engineers.
A* is an optimized version of Djikstra’s algorithm that uses heuristics (H) to guide the search. I find that it’s easier to understand A* if you first understand Djikstra’s algorithm and why it benefits from a heuristic.
[Note: A-star and A* are interchangeable. I switched to A-star to avoid problems with the bold formatting. They are the same thing.]
What’s Djikstra’s algorithm?
It’s a simple path finding algorithm that finds the cost of going from one point to any other point. Djikstra’s algorithm is simple (just check everything!) but that also makes it slow. If you know the cost of getting from one place to anywhere else you effectively can find the shortest path once you have that data.
What’s a heuristic? Why is it relevant here?
A heuristic is a calculation that allows you to short cut or simplify the problem in some way. You probably use heuristics in every day life. e.g. when you are shopping you probably don’t check every store or brand for every possible purchasing decision – you might have a heuristic that says only check these three stores or these two brands. Or maybe it’s only check this store for this type of product.
For our purposes, A-star improves upon Djikstra’s algorithm by offering a heuristic which reduces the search space.
Ok I understand now why we don’t want to search every path. But how does the heuristic for A-star work?"
First of all, you have to define an appropriate heuristic. The distance as the crow flies can often work because you’ll never be able to do better than that in most cases. If you know a little bit of something about how your actors move or what the terrain looks like you can apply increasingly smarter heuristics.
A-star works by putting an emphasis on paths with a low heuristic cost. This effectively reduces your need to trace every path like Djikstra’s. There are a few great animations on wikipedia for how this works if you search for A-star. I recommend you take a look!
Is it possible that no heuristic might exist for my situation?*
Yes. Imagine a fictional world with worm holes that can magically zap you to your final destination. The “as the crow files heuristic” is thus useless here. Also A-star wouldn’t be helpful in an RPG like dungeon or maze because only one path exists. There other algorithms for mazes. Use A* when there are many many possible paths but you don’t want to check them all.
What happens to my A-star algorithm if my heuristic is bad?
So long as you didn’t create any coding bugs, A-star over time should search every node. It will just be slow and perform closer to Djikstra’s algorithm.
OK so is this why Hugo said to find an A-star algorithm on the asset store?
Well I can’t read minds but most likely yes! A good A-star algorithm not only has lots of good heuristics for many different map and actor types but uses very efficient coding techniques that further reduces computation.