四种寻路算法比较

四种算法是DFS, BFS, Heuristic DFS, Heuristic BFS (A*)
用了两张障碍表，一张是典型的迷宫：

char Block[SY][SX] = {
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1},
        {1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1},
        {1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1},
        {1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1},
        {1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1},
        {1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
        {1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
        {1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

char Block[SY][SX] = {
        {1,1,1,1,1,1,1,1,1,1,1 },
        {1,0,1,0,1,0,0,0,0,0,1 },
        {1,0,1,0,0,0,1,0,1,1,1 },
        {1,0,0,0,0,0,1,0,0,0,1 },
        {1,0,0,1,0,0,1,0,0,1,1 },
        {1,0,1,0,0,1,0,1,0,0,1 },
        {1,0,0,0,0,0,0,0,1,0,1 },
        {1,0,1,0,0,0,1,0,1,0,1 },
        {1,0,0,1,0,0,1,0,0,0,1 },
        {1,1,1,1,1,1,1,1,1,1,1 }
};

#include <iostream.h>
#include <memory.h>
#include <stdlib.h>

#define SX 11 //宽
#define SY 10 //长

int dx[4] = {0, 0, -1, 1}; //四种移动方向对x和y坐标的影响
int dy[4] = { -1, 1, 0, 0};

/*char Block[SY][SX]= //障碍表
{{ 1,1,1,1,1,1,1,1,1,1,1 },
{ 1,0,1,0,1,0,0,0,0,0,1 },
{ 1,0,1,0,0,0,1,0,1,1,1 },
{ 1,0,0,0,0,0,1,0,0,0,1 },
{ 1,0,0,1,0,0,1,0,0,1,1 },
{ 1,0,1,0,0,1,0,1,0,0,1 },
{ 1,0,0,0,0,0,0,0,1,0,1 },
{ 1,0,1,0,0,0,1,0,1,0,1 },
{ 1,0,0,1,0,0,1,0,0,0,1 },
{ 1,1,1,1,1,1,1,1,1,1,1 }};*/

char Block[SY][SX]= //障碍表
{{ 1,1,1,1,1,1,1,1,1,1,1 },
{ 1,0,1,0,1,0,0,0,0,0,1 },
{ 1,0,1,0,0,0,1,0,1,1,1 },
{ 1,0,0,0,1,0,1,0,0,0,1 },
{ 1,0,1,1,0,0,1,0,0,1,1 },
{ 1,0,1,0,1,1,0,1,0,0,1 },
{ 1,0,0,0,0,0,0,0,1,0,1 },
{ 1,0,1,0,1,0,1,0,1,0,1 },
{ 1,0,0,1,0,0,1,0,1,0,1 },
{ 1,1,1,1,1,1,1,1,1,1,1 }};

int MaxAct = 4; //移动方向总数
char Table[SY][SX]; //已到过标记
int Level = -1; //第几步
int LevelComplete = 0; //这一步的搜索是否完成
int AllComplete = 0; //全部搜索是否完成
char Act[1000]; //每一步的移动方向，搜索1000步，够了吧？
int x = 1, y = 1; //现在的x和y坐标
int TargetX = 9, TargetY = 8; //目标x和y坐标
int sum1 = 0, sum2 = 0;

void Test();
void Back();
int ActOK();
int GetNextAct();

void main() {
    memset(Act, 0, sizeof(Act)); //清零
    memset(Table, 0, sizeof(Table));
    Table[y][x] = 1; //做已到过标记
    while (!AllComplete) { //是否全部搜索完
        Level++;
        LevelComplete = 0; //搜索下一步
        while (!LevelComplete) {
            Act[Level] = GetNextAct(); //改变移动方向
            if (Act[Level] <= MaxAct)
                sum1++;
            if (ActOK()) { //移动方向是否合理
                sum2++;
                Test(); //测试是否已到目标
                LevelComplete = 1; //该步搜索完成
            } else {
                if (Act[Level] > MaxAct) //已搜索完所有方向
                    Back(); //回上一步
                if (Level < 0) //全部搜索完仍无结果
                    LevelComplete = AllComplete = 1; //退出
            }
        }
    }
}

void Test() {
    if ((x == TargetX) && (y == TargetY)) { //已到目标
        for (int i = 0; i <= Level; i++)
            cout << (int) Act[i]; //输出结果
        cout << endl;
        cout << Level + 1 << " " << sum1 << " " << sum2 << endl;
        LevelComplete = AllComplete = 1; //完成搜索
    }
}

int ActOK() {
    int tx = x + dx[Act[Level] - 1]; //将到点的x坐标
    int ty = y + dy[Act[Level] - 1]; //将到点的y坐标
    if (Act[Level] > MaxAct) //方向错误？
        return 0;
    if ((tx >= SX) || (tx < 0)) //x坐标出界？
        return 0;
    if ((ty >= SY) || (ty < 0)) //y坐标出界？
        return 0;
    if (Table[ty][tx] == 1) //已到过？
        return 0;
    if (Block[ty][tx] == 1) //有障碍？
        return 0;
    x = tx;
    y = ty; //移动
    Table[y][x] = 1; //做已到过标记
    return 1;
}

void Back() {
    x -= dx[Act[Level - 1] - 1];
    y -= dy[Act[Level - 1] - 1]; //退回原来的点
    Table[y][x] = 0; //清除已到过标记
    Act[Level] = 0; //清除方向
    Level--; //回上一层
}

int GetNextAct() //找到下一个移动方向。这一段程序有些乱，
//仔细看!
{
    int dis[4];
    int order[4];
    int t = 32767;
    int tt = 2;
    for (int i = 0; i < 4; i++)
        dis[i] = abs(x + dx[i] - TargetX) + abs(y + dy[i] - TargetY);
    for (i = 0; i < 4; i++)
        if (dis[i] < t) {
            order[0] = i + 1;
            t = dis[i];
        }
    if (Act[Level] == 0)
        return order[0];
    order[1] = -1;
    for (i = 0; i < 4; i++)
        if ((dis[i] == t) && (i != (order[0] - 1))) {
            order[1] = i + 1;
            break;
        }
    if (order[1] != -1) {
        for (i = 0; i < 4; i++)
            if (dis[i] != t) {
                order[tt] = i + 1;
                tt++;
            }
    } else {
        for (i = 0; i < 4; i++)
            if (dis[i] != t) {
                order[tt - 1] = i + 1;
                tt++;
            }
    }

    if (Act[Level] == order[0])
        return order[1];
    if (Act[Level] == order[1])
        return order[2];
    if (Act[Level] == order[2])
        return order[3];
    if (Act[Level] == order[3])
        return 5;
}