大地图的话，提供个思路：
静态->用路点，在每个地块拐点的地方+路点，保证在地图的任何位置，都至少有一个路点和该位置是可通的，最终得到一张节点图。
这个可以用编辑器可以手工设置，也可以算法程序自己生成。比如地图编辑器会有刷MASK的功能，路点可以沿MASK块的凸点一段距离自己生成，再连成图（可以参考天龙八部的编辑器）。
剩下的工作就简单了，寻路时先找离自己最近的路点，再找离目标点最近的路点，然后沿着路点走过去就好了。
中间可以做一些优化，即：每过5s，如果当前位置可以直接看到下一个路点（结束点），就跳过当前路点，沿直线过去。

动态->对RTS那种游戏，一般来说，确实需要A*算的，如果距离太长，会把路径分割，每次只寻路一小段，让玩家先走起来，然后过一个间隔，再寻路一次，避免一次卡死太长时间。所以你可以看到，war3中单位的移动，如果你让他去A点，他会先往大概的位置上走，不停的寻路靠近中点的方向，如果被挡住了，他会回头的。因为路径太长，你寻出来也没意义，中间是会被“挡”住的。

寻路算法上面的优化，可以参考3D游戏场景管理里面用到的OCTree的方法，或者是四叉树。原理就是对相邻的可通过格子，组织成一个大的“区块”，比如16 * 16大小，每个区块，下面还是区块（4 * 4），一直到1 * 1，这样整个是一个树结构。在寻路的时候，找到终点位于哪个树节点里面，再寻路就可以了。这样可以大大减少A*递归的次数。

具体的寻路算法，可以参考http://www.ai-blog.net/archives/000091.html