Introduction to A*
redblobgames.com
redblobgames.com
Important side note: A* or other "best path" algorithms are not always preferable - there are some situations where it makes sense to use even less ideal paths in exchange for greater speed and less memory usage - even ones that are faster than greedy-best-first search with A* shown here.
If you use recursive backtracking with a decent set of heuristics (i.e. choose the node with the closest distance to the goal, "as the crow flies"), it can be be fast and ideal in many situations (it will always give an ideal path when there are few hook or concave shapes to deal with, which in many games or applications is often the case). It can be done in linear time and memory - it is important to note the cost of adding and searching nodes in the algorithm as well. It will never "fail" but it will produce very bad paths sometimes in complex situations, although even then it occasionally produces ideal paths. In many situations where having an ideal path is not critical (say, townspeople just walking about doing their business) this can work well. Of course, you can use multiple algorithms or even mix them depending on what you are trying to achieve. RBT can be a good starting point just because it is so easy (maybe the easiest fail-safe algorithm outside of brute force?).
Secondary note: it is also good to subdivide your space - it does not need to be something complex like a sparse octree (in fact, that will make it harder to write and get good performance with in many situations). Rather consider something like two levels of nodes. On a 2D map, say you were to divide it into subsets of NxN grids of nodes. Each one of these node grids attaches to its neighbor based on whether or not it is traversable in that direction (i.e. no matter where you enter the node grid, there is a path out in that direction). This allows you to easily find a "high level" path which can be rapidly changed or discarded based on changing circumstances.
Another example is when you are dealing with large crowds. Vector fields tend to shine there. A simple example is using a vector field when dealing with a large swarm with one goal:
http://gamedevelopment.tutsplus.com/tutorials/understanding-...
Something more slightly more advanced yet incredibly powerful would be "continuum crowds", where the agents in the swarm are also obstacles for each other, affecting the vector field:
https://www.youtube.com/watch?v=lGOvYyJ6r1c
http://grail.cs.washington.edu/projects/crowd-flows/
The intriguing part here is that these potential field can have any source - so it's relatively easy to get complex behaviour, such as pedestrians avoiding cars, or prey/predator behaviour.
Again, these are more relavant with large crowds, so as stated before: the best approach all depends on the particular use-case.
The crowd flow research is neat. The videos are especially fun to watch. http://gamma.cs.unc.edu/research/crowds/ is another nice set of papers.
I think I basically tried almost every A* trick available (rectangular symmetry reduction, HPA*, points of visibility, jump point search, etc) but ultimately I couldn't make it run fast enough on iOS for our max level size which was about 100x100. It also couldn't be multi-threaded because it needed to work with online code (synchronous tick engine)...
What ended up happening was I found a full C implementation of Jump Point Search, and it was incredibly fast! I had already moved several parts of my code to C in order to speed it up, but I guess using a higher level language like Objective-C is just way too slow to have instantaneous path-finding on a 100x100 grid. I think this was the code I found https://github.com/Bio2hazard/cJumpPointSearch
It started out completely broken, storing waypoints in Core Data and was taking upwards of four minutes to calculate a path. Switching to prefetching Core Data paths brought it down to about 90 seconds, but that's as far as it could go with so many Core Data faults firing.
What made it really fly was the change the underlying data to direct bitmap access on maps prepared from the source maps (shopping centre levels actually) and applying simple filters to generate monochrome maps where one color was walkable and another not. Then source and destination locations were obtained through the original Core Data coordinates and a quick search algorithm found the closest walkable point to both. The A* calculation took perhaps a second or two.
Not content with that we went further and drew more complicated maps with what amounted to train tracks, a network of walkable paths one pixel wide connecting every store to every store to narrow down the solution space. The result was instant A* pathfinding and it was a very neat feature in the app.
You can definitely do A* in Objective C - just get to know Instruments inside out and keep tuning. On a 5S I expect you could get away with a lot of inefficiency.
100x100? That sounds trivial to make fast enough. What was the programming language used?
"A* is a good choice for most pathfinding needs."
I teach A* in my game AI class, and after having examined dozens of real-world game implementations of pathfinding, this is exactly right. While it's true that you shouldn't ALWAYS use A* , most games use A* in most situations, because actually greedy approaches like you are discussing do poorly surprisingly often. My recommendation is to start with A* and only use simpler methods if it isn't giving you the performance you need.
For your subdivision comment, the general approach is generally called hierarchical pathfinding. There are lots of ways you can do this, but I like HPA* : http://aigamedev.com/open/review/near-optimal-hierarchical-p... Your comment about two levels is good, because while hierarchical pathfinding can use any number of levels, I've never seen more than two in practice in games.
I had some fun earlier this year implementing A* in 6502 assembler, starting with Python and working my way down through Objective-C and C before finally hand-optimizing the critical paths in asm. Articles are here for those who enjoy that kind of thing:
http://magervalp.github.io/2014/05/02/priority-queue-in-asm.... http://magervalp.github.io/2014/05/07/astar-in-asm.html
The code is available on github too: https://github.com/MagerValp/AsmAstar
Oh, that's a really great idea. I'm going to do that with a few interesting algorithms now, starting with Python and working down via Rust and maybe C to assembly.
I'm actually doing a take on that with several network clients (Stomp and mqtt) at the present, starting with Python and then moving to Rust.
But I'm really interested now in embedded programming so I should pick a challenging algo and work all the way down to assembly to run on bare metal. Algorithms are nice for this type of exercise since they typically have limited IO.
Great idea, thanks!
When I first read about A* a long time ago I remember, for example, reading about how static summaries of chess board positions may be useful heuristics. Developing pieces towards the center of the board is often better, for example. To me, seeing this was an "ah ha" moment for heuristics: use them if they are cheap and (sometimes) informative, relative to the search cost.
An easy heuristic that vastly improves the search: the sum of the manhattan distances of the pieces' current locations to their final positions.
So, as you said, rather than thinking about distance only in a Euclidean space, A* heuristics are much more general -- any metric that measures "done-ness".
Otherwise, the article is first-rate :-)
I threw together an implentation of A* as a library in Go [1] for a game I've been doing, it has automated tests which mock up a game world and check the length of paths with visual output.
http://theory.stanford.edu/~amitp/GameProgramming/AStarCompa...
Per https://en.wikipedia.org/wiki/Admissible_heuristic, "In computer science, specifically in algorithms related to pathfinding, a heuristic function is said to be admissible if it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the lowest possible cost from the current point in the path.[1] An admissible heuristic is also known as an optimistic heuristic."
I guess the implementation effort greatly varies depending on the programming language and the libraries at one's disposal. However, I believe that even for someone not too versed into data structures, the priority queue should be relatively easy to implement.
Well done!