自動尋路之A星演算法+Qt開發圖形界面

專案演示

最近筆者學習了一個新的知識，因為是車輛行業的研究生，對無人車、嵌入式物聯網、機器人很感興趣，所以在科研之余學習了一下A星演算法，用時三個星期的周末，寫了一個基于A星演算法的游戲圖形界面demo，其效果如圖:

A星演算法理論

無人車的路徑規劃問題涉及到A星演算法、卡爾曼濾波演算法、SLAM建圖仿真等技術，其中A星演算法應用到不僅是車輛的路徑規劃上，其在游戲行業有著很廣泛的應用，比如lol中，我們想要控制自己的人物到地圖上的某一點去，那么我們只需點擊目的地，則人物會自動的按照演算法算出來的最優路徑進行自動導航到達我們指定的位置，在本專案中，沒有向游戲中的地圖那么復雜，筆者建立了簡單的網格地圖，來簡單模擬游戲中的路徑規劃，

如上圖中起點終點所示，黑色為障礙物，最優路徑則為黃色區域，其演算法核心即為啟發式搜索，通過公式F=G+H得出：其中F叫做路徑代價，G則為起點到當前點已經付出的代價累加，H為當前點到終點的預計代價，在這里我們假設每個方格為10×10的大小，那么G分為直線代價（10）和斜線代價（14），H為當前點到終點的預計代價并且無視障礙，那么像圖中所示起點的下一步的代價總和已經可以計算得出，就這樣每一步都執行8次代價計算（有障礙物則舍棄），選擇代價總和最小的走，直到終點，

Qt中代碼講解

創建地圖

地圖的創建很簡單，用一個二維陣列即可，首先定義行數和列數，在這里我將定義一個列舉變數，令FLOOR為0，WALL為1，

int map[ROWS][COLS]={
            {WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL},
            {WALL,PERSON,FLOOR,FLOOR,FLOOR,WALL,FLOOR,FLOOR,FLOOR,FLOOR,FLOOR,WALL},
            {WALL,FLOOR,FLOOR,FLOOR,FLOOR,WALL,FLOOR,FLOOR,FLOOR,FLOOR,FLOOR,WALL},
            {WALL,FLOOR,FLOOR,FLOOR,WALL,WALL,FLOOR,FLOOR,WALL,FLOOR,FLOOR,WALL},
            {WALL,FLOOR,FLOOR,WALL,FLOOR,WALL,FLOOR,WALL,FLOOR,FLOOR,FLOOR,WALL},
            {WALL,FLOOR,FLOOR,WALL,FLOOR,WALL,FLOOR,WALL,FLOOR,FLOOR,FLOOR,WALL},
            {WALL,FLOOR,FLOOR,WALL,FLOOR,WALL,FLOOR,WALL,FLOOR,FLOOR,FLOOR,WALL},
            {WALL,FLOOR,FLOOR,FLOOR,FLOOR,FLOOR,FLOOR,WALL,FLOOR,FLOOR,FLOOR,WALL},
            {WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL},
};

獲取地圖中任意點的坐標（終點坐標獲取）

因為我們的目的地是自己設定的，所以此專案中我通過滑鼠點擊地圖的位置獲取坐標作為我們設定的目的地：

if((p_x<(pt_x+SIZE/2))&&(p_x>(pt_x-SIZE/2))&&(p_y>(pt_y-SIZE/2))&&(p_y<(pt_y+SIZE/2)))
            {
                str = QString("%1 , %2").arg(pt[i][j].x()).arg(pt[i][j].y());
                  p_end.row=i;
                  p_end.col=j;
                  

                  /*設定顯示在label中坐標的顏色*/
                  QPalette pa;
                  pa.setColor(QPalette::WindowText,Qt::red);
                  ui->label->setPalette(pa);

                ui->label->setText(str);//顯示
            }

        }

        }

因為地圖是采取網格式的，所以在程式中進行了判斷，當滑鼠點擊到某個網格中任意一點時，則將目的地坐標設定為此網格的中心坐標，

通過鍵盤控制人物移動，并獲取人物當前坐標（起點坐標獲取）

筆者在地圖里通過WSAD鍵可以控制人物的上下左右移動，并且每次移動時將此時人物所在的坐標賦給起點，label中可以顯示此時人物的坐標，

/*上下左右控制程序*/
void MainWindow::gameControl(enum Direction dir)
{

    //QPoint p = QCursor::pos();//獲取滑鼠的絕對位置
    QString str;
    if (dir == UP) { // 上方向
        if (map[man.y - 1][man.x] == FLOOR ) { // 上方向為地板
            changeMap(man.y, man.x, FLOOR); // 原位置換為地板
            changeMap(man.y - 1, man.x, PERSON); // 上方向位置換為人
             str = QString("%1 , %2").arg(pt[man.y-1][man.x].x()).arg(pt[man.y-1][man.x].y());
             p_start.row=man.x-1;
             p_start.col=man.y;
             ui->label->setText(str);//顯示
        }
    }
     else if(dir == DOWN)
        {
            if (map[man.y + 1][man.x] == FLOOR ) { // 下方向為地板
                changeMap(man.y, man.x, FLOOR); // 原位置換為地板
                changeMap(man.y + 1, man.x, PERSON); // 上方向位置換為人
                str = QString("%1 , %2").arg(pt[man.y+1][man.x].x()).arg(pt[man.y+1][man.x].y());
                p_start.row=man.x+1;
                p_start.col=man.y;
                ui->label->setText(str);//顯示
        }
        }
    else if(dir == LEFT)
       {
           if (map[man.y][man.x-1] == FLOOR ) { // 左方向為地板
               changeMap(man.y, man.x, FLOOR); // 原位置換為地板
               changeMap(man.y , man.x-1, PERSON); // 左方向位置換為人
               str = QString("%1 , %2").arg(pt[man.y][man.x-1].x()).arg(pt[man.y][man.x-1].y());
               p_start.row=man.x;
               p_start.col=man.y-1;
               ui->label->setText(str);//顯示
       }
       }
    else if(dir == RIGHT)
       {
           if (map[man.y ][man.x+1] == FLOOR ) { // 右方向為地板
               changeMap(man.y, man.x, FLOOR); // 原位置換為地板
               changeMap(man.y , man.x+1, PERSON); // 右方向位置換為人
               str = QString("%1 , %2").arg(pt[man.y][man.x+1].x()).arg(pt[man.y][man.x+1].y());
               p_start.row=man.x;
               p_start.col=man.y+1;
               ui->label->setText(str);//顯示
       }
       }
}

A*核心演算法代碼

代碼的核心部分采用N叉樹結構，即先將起點作為樹的根，其次分出8個樹枝，分別對應下一步的8個坐標方向，在這8個中將有障礙物的剔除，其余比較代價最小的那一個點，然后再將這個點作為樹根，再依次向下伸張，直到達到終點，最后再依次獲得之前所走路徑的坐標，程式中用到了C++中STL中的vector容器，

通過選取終點，利用QTimer實作自動尋路功能

此時演算法核心已經完成，接下來實作圖形化界面：
通過滑鼠事件獲取到終點后，此時路徑上的坐標已經獲得，則設定一個定時器，改變人物的位置

void MainWindow::start()
{
    if(p_end.col==0&&p_end.row==0)
    {

    }
    else
    {
     timer =new QTimer(this);
        timer->start(1000);
        connect(timer,&QTimer::timeout,this,&MainWindow::road);
    }
}

每次經過1秒，進行road函式，人物坐標變換一次

void MainWindow::road()
{
     if(j>0)
     {
         changeMap(p_road[j-1].row,p_road[j-1].col,PERSON);
         changeMap(p_road[j].row,p_road[j].col,FLOOR);
         j--;
     }
     else
         timer->stop();
}

Qt界面美化，封裝完成

在界面中設定了一些按鈕的自定義，添加了界面背景的背景圖，地圖的資源圖等

/******************************設定視窗格式**********************************/
    //設定視窗格式
    this->setWindowFlag(Qt::FramelessWindowHint);
    //設定陰影
    QGraphicsDropShadowEffect *shadow =new QGraphicsDropShadowEffect(this);

    ui->centralwidget->setGraphicsEffect(shadow);
    shadow-> setBlurRadius(10);
    shadow-> setColor(Qt::black);
    shadow-> setOffset(0);
    //父視窗設定透明
    this->setAttribute(Qt::WA_TranslucentBackground);
    /**************************************************************************/

到此專案基本完成，如果有需要交流和源代碼的小伙伴可以加下我的vx：17362997119，希望能跟大佬們多交流交流！！