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.
"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.
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.