C語言實現A*尋路算法：從鏈表操作到完整代碼詳解

編輯：關於C語言

前言

近期在MTK斯凱冒泡平台進行遊戲開發時，遇到了自動尋路需求。A*算法因其原理簡單、效率高，成為首選方案。雖然網上有大量C語言實現，但經測試多存在各種問題，難以直接用於商業項目，因此決定自行實現。本文將分享從數據結構設計到核心邏輯的完整實現過程，特別適合從Java轉向嵌入式C開發的程序員參考。

核心數據結構設計

A*算法需要維護OPEN表和CLOSED表，C語言無內建集合類，採用前插式單向鏈表實現。定義節點結構體Node包含代價值（f、g、h）、座標（row、col）、方向及父節點指針；鏈表節點Stack包含節點指針與下一節點指針。

typedef struct Node {
    int f, g, h;
    int row, col;
    int direction;
    struct Node *parent;
} Node, *Lnode;

typedef struct Stack {
    Node *npoint;
    struct Stack *next;
} Stack, *Lstack;

鏈表核心操作詳解

1. 節點插入（前插法）

新節點總是插在頭節點與首個數據節點之間，實現O(1)插入：

void PutintoOpen(Node *suc) {
    Stack *temp = (Stack *)malloc(sizeof(Stack));
    temp->npoint = suc;
    temp->next = Open->next;
    Open->next = temp;
}

2. 取出最小F值節點並刪除

遍歷OPEN表尋找f值最小節點，從鏈表中移除並釋放鏈表節點內存：

Node *getNodeFromOpen() {
    Lstack temp = Open->next, min = Open->next, minp = Open;
    Node *minx;
    if (temp == NULL) return NULL;

    while (temp->next != NULL) {
        if (temp->next->npoint->f < min->npoint->f) {
            min = temp->next;
            minp = temp;
        }
        temp = temp->next;
    }
    minx = min->npoint;
    temp = minp->next;
    minp->next = minp->next->next;
    free(temp);
    return minx;
}

3. 鏈表遍歷查找

判斷節點是否已在OPEN/CLOSED表中：

Node *BelongInOpen(Node *suc) {
    Lstack temp = Open -> next;
    if (temp == NULL) return NULL;
    while (temp != NULL) {
        if (Equal(suc, temp->npoint))
            return temp->npoint;
        temp = temp->next;
    }
    return NULL;
}

4. 鏈表銷毀與內存釋放

程序結束時需釋放所有動態分配的節點及鏈表節點：

void printfOpenData() {
    Lstack temp = Open -> next;
    Node *p_node;
    if (temp == NULL) return;
    while (temp != NULL) {
        Lstack head = temp;
        temp = temp->next;
        p_node = head->npoint;
        printf("Open庫數據！[%d,%d]\n", p_node->col, p_node->row);
        free(p_node);
        free(head);
        Open->next = temp;
    }
    printf("\nOpen庫數據全部清除\n");
}

完整A*算法實現

單文件main.c包含地圖數據、啟發式函數（曼哈頓距離）、鄰居節點生成、主尋路循環等完整邏輯。關鍵函數：

getH()：計算啟發式代價
isCanMove()：檢測格子可通行性
creatSeccessionNode()：生成/更新鄰居節點
seachSeccessionNode()：擴展四個方向鄰居
getPath()：主循環，提取最小f節點並擴展直到達到目標

工程化改造建議

將main()改為接口函數，接受地圖數據、尺寸、起終點座標：

void autoPathfinding(uint16 *MD, uint8 map_w, uint8 map_h,
                     int16 startX, int16 startY,
                     int16 destinationX, int16 destinationY);

並將isCanMove()改為根據實際地圖數據判斷：

BOOL isCanMove(int col, int row) {
    if (col < 0 || col >= cols) return FALSE;
    if (row < 0 || row >= rows) return FALSE;
    return isCanGoByMapTile(MapData[col * rows + row]);
}