* If you assign terrain costs to tiles rather than borders (= paths) between tiles, that creates a user-visible asymmetry! ... unless the cost is always max() of the two tile costs or something.
* The direction in which you run the algorithm matters, especially if you're doing one-to-many or partial paths. That said, it is possible to do any-to-goal directly, by adding an extra field to your datum.
* A* fails pretty badly on C-shaped obstacles
* You need to have an admissible heuristic. This means no negative (usually stricter, in fact: not less than 1) weights (usually reasonable, but can cause complications if you want to funnel traffic onto "highways" even if that's slightly longer), and makes teleporters complicated:
\* if a teleporter connects to all other teleporters, the new heuristic is `min(old heuristic, heuristic to the nearest teleporter, heuristic from the teleporter to the goal)
\* if sets of teleporters are unrelated, you probably want to preprocess paths between every pair of teleporters. Doing this without unnecessary work is left as an exercise for the reader.
* If you have a convex walkable area, you know that the shortest path between any two points within it is a straight line, and this can significantly shorten A*. Note that a given tile will almost always be part of more than one such useful area (you certainly don't want to consider all valid areas), and this should not be limited to rectangular areas (in particular, don't let diagonal corridors be a worst case). It's okay to exclude "pocket" tiles near the wall; they'll still exist as individual tiles for pathfinding purposes if you really need to go there.
* Optimization gets harder if your map has multiple movement types (e.g. walk, swim, fly) and individual entities can exercise more than one of those.
* When pathfinding across multiple maps (hierarchial pathfinding is important), the shortest connectivity is not necessarily the shortest path. Sometimes cutting through a building is faster than going around it. If your transitions are not point-like, even recording shortest paths between all such transitions isn't enough. (imagine citygate| .house. |citygate, where the house transitions are small enough to not be part of the shortest paths from the extremity of one gate to the other, but are optimal if you start at the center of the gate)
\* speaking of non-point-like transitions, *please* preserve relative position at least somewhat. Instead of "entering this transition line teleports you to this point on the other map", use "entering this transition line teleports you to the equivalent (with scaling if needed) position along this other transition line". It's not hard when I say it like that, right? (even if you want one-way transitions, you should model them as a transition that is currently disabled, so your target is homogeneous)
* Even if you do run a full A*, you don't have to store every node, only nodes where you turn (this usually beats storing immediate direction for every node, except for extreme mazes of twisty little passages). Rounded convex obstacles (thus concave open spaces) are your enemy unless you also add wall-sliding logic here.
* If you assign terrain costs to tiles rather than borders (= paths) between tiles, that creates a user-visible asymmetry! ... unless the cost is always max() of the two tile costs or something.
* The direction in which you run the algorithm matters, especially if you're doing one-to-many or partial paths. That said, it is possible to do any-to-goal directly, by adding an extra field to your datum.
* A* fails pretty badly on C-shaped obstacles
* You need to have an admissible heuristic. This means no negative (usually stricter, in fact: not less than 1) weights (usually reasonable, but can cause complications if you want to funnel traffic onto "highways" even if that's slightly longer), and makes teleporters complicated:
* If you have a convex walkable area, you know that the shortest path between any two points within it is a straight line, and this can significantly shorten A*. Note that a given tile will almost always be part of more than one such useful area (you certainly don't want to consider all valid areas), and this should not be limited to rectangular areas (in particular, don't let diagonal corridors be a worst case). It's okay to exclude "pocket" tiles near the wall; they'll still exist as individual tiles for pathfinding purposes if you really need to go there.* Optimization gets harder if your map has multiple movement types (e.g. walk, swim, fly) and individual entities can exercise more than one of those.
* When pathfinding across multiple maps (hierarchial pathfinding is important), the shortest connectivity is not necessarily the shortest path. Sometimes cutting through a building is faster than going around it. If your transitions are not point-like, even recording shortest paths between all such transitions isn't enough. (imagine citygate| .house. |citygate, where the house transitions are small enough to not be part of the shortest paths from the extremity of one gate to the other, but are optimal if you start at the center of the gate)
* Even if you do run a full A*, you don't have to store every node, only nodes where you turn (this usually beats storing immediate direction for every node, except for extreme mazes of twisty little passages). Rounded convex obstacles (thus concave open spaces) are your enemy unless you also add wall-sliding logic here.