游戏寻路算法A*的实现

    游戏寻路算法A*的实现
    [测试平台] Celeron 2.4GHZ + 1G内存
    [演示]
    （1）    地图大小（size），假设地图都是正方形size <= 1000
    （2）    障碍百分比（rate）：用于设置障碍点数，障碍数=size*size*rate/100
    （3）    测试软件的目标是用A*算法在地图中找到最短路径
    （4）    图示中size = 1000的地图用了624ms，这是比较好的情况，如果在比较差的情况下size=1000时可能需要3s的时间；当一般情况size=300时，一般需要100ms左右的时间，应该还是属于高效的。
    （5）    起点坐标（0，0），终点坐标（size-1,size-1）
    （6）    地图文件map.in，寻路输出文件map.out，最好用写字版打开。
    （7）    本文的目标在于介绍A*的具体实现方法，不打算介绍A*的原理，也不会对h（n）进行过多的探讨，h（n）使用最简单的dx+dy形式。从算法效率角度来说针对总体效率的把握，而没有对程序本身进行过多无谓的优化，否则如果用汇编实现一些关键运算的话效率就可以提高N多。
    [寻路结果示例] size=30,rate = 60,‘。’表示可以通行，‘*’表示障碍
    →↘ . * . . . * * * . * * * * * . . . . * . . * . . . * . *
    . *↘ . * . . * * * . . * * * . . . . * . * . . . . . * * *
    . * *↓ * * * . * . . . . * * . * . * * * . * . . . * . * .
    * * .↓ . * . * . * . * * * . . . * . . . * . . * . . * . *
    . . .↘ * * * * . * . * . . . * * . * . . . * . . . . * * .
    . . . *↘ * . . . . * * . * . * * . * * * . . * . . . * . .
    . . . . .→→→↘ * . . * * . * * . . . * * . . * . * . . *
    * * . . * . . * .↘ . * . . * * * * . . * * * . . * * . * *
    . . * . * . * . * *↓ . * . * * * * * . * . . . . . * * . .
    . . . * . * . . * *↘ * * . * . . * * . * . . * . * . . * *
    . * * * * . . . * * .↘ * * . . . . . * * * . * . . . . . .
    . * * * * * . . . . * *↓ * * * * . . * * * * . . * . . * .
    * . . . * . . * . * * *↘ . . * * * * . . . * . * . . . * .
    . . * . . . * * * . * . *↙ * * * * * . . . * . . * . . * .
    . * * * * * . . . . * *↘ * * * . * * . . . * . . * . . * .
    * * . * . * * * . * * . .→→↘ * . * * . * . * * * . * . .
    . . . . * * . . . * * * . * * *→↘ * * . * . * * * * . . .
    * * . . . . * * * . . . * . * . . .↘ * . * . . . * * * . .
    . * . * . . . . . * * . . . * . * * .→↘ * * . * . . * * *
    . * * . . . . . . * * . * * * . * . . . *↓ * * . * . * . *
    . * . * * * . . . * . * . * . . * . . * *↘ . * . * . * * *
    . * * * . * . . * . . * . . * * * . . . . .↘ * . * * * . *
    . * * * * . * * . . . . . * . . . * . * * . .↘ * . . * * *
    * . . . * * * * . . . . . . . * . * . * * . * *↘ . * * * .
    . * . . . . . * . * * . * . . . * * . * * * * . *↘ . * . *
    * . * * * . * * . . . . . . . . * . . * . * . * . *↘ . * *
    . * . . . . . * . * . * * . * * . . * . * . * . . * .↘ . *
    * . . . * . . * . * * * . . * * . * . * . . . * . . * .↘ *
    . . . . . . . * * . * * . * * . * * . * . * . . * * * * *↓
    . . * . * . . . . . . . . . * . . . . . . * . . * * * . * .
    一、A*算法实现过程中的存储结构
    （1）    八个方向
    int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},{-1,-1},{0,-1},{1,-1},{1,0}} ;
    char dir_ch[8][3] = { "↑","↗","→","↘","↖","←","↙","↓" } ;
    这样存储8个方向的好处是，当知道AàB的方向为x时，就可以直接得到BàA的方向为（7-x）
    （2）    地图储存结构MAP
    typedef struct _MAP {
    int type ;             // 0:可行 1:障碍
    int status ;            // 0:未访问1:OPEN 2:CLOSE
    int dir_parent ;        // 指向前一结点dir （ 0—7）
    int g ;                // g（n），起点到当前结点的代价
    int h ;                // h（n），当前结点到终点的估价值
    int index ;            // 在heap中的结点索引号
    } MAP ;