The state represented by each search node doesn’t have to be limited to a position;
on the contrary, it can include an arbitrarly complex set of values. For example,
if turning 90 degrees takes the same time as walking from one square to the next,
the state of your character can be [position, heading]. Each node now represents
not only the position of the character, but also its heading; and the new edges
of the graph (implicit or explicit) reflect that.
Going back to the original 5x5 grid, the starting position of the search now may
be [A, East]. The adjacent nodes are now [B, East] and [A, South] - if you want
to reach F, you need to correct your heading first, so the path would be
[A, East], [A, South], [F, South].
First-person shooter? At least four dimensions: [X, Y, Z, Heading]. Maybe even
[X, Y, Z, Heading, Health, Ammo].
It's even more than that. You can get great results from A* on any graph search problem where you can find a good heuristic for the distance to the goal from some node, which may not be related to position at all. For example, I once did this with nodes that represented sets of database attributes and arcs that represented table joins.
A* is not only a pathfinding algorithm, but a search algorithm. In my AI classes I used it for pathfinding, solving sudokus and other puzzles, and even to solve a job shop scheduling problem[1]. If you can translate your problem into a graph, you can use A* with it.
In these classes, we had a problem to solve, and we had to solve it using different algorithms and in the end submit a report in wich we compared the result and efficiency of each. The ones that used heuristics, we had to implement about three different heuristics, analyze each and mix them up.
My take-away, from the last part: