用c++写一个astar算法

好的，我可以回答这个问题。A*算法是一种启发式搜索算法，用于在图形或网格中找到最短路径。以下是用C语言编写A*算法的基本步骤：

1. 定义节点结构体，包含节点坐标、父节点、G值和H值等信息。
2. 定义开放列表和关闭列表，用于存储待搜索和已搜索的节点。
3. 初始化起点节点，并将其加入开放列表。
4. 重复以下步骤直到找到终点节点或开放列表为空：
a. 从开放列表中选取F值最小的节点作为当前节点。
b. 将当前节点从开放列表中移除，并加入关闭列表。
c. 遍历当前节点的相邻节点，计算它们的G值、H值和F值。
d. 如果相邻节点已经在关闭列表中，则跳过。
e. 如果相邻节点不在开放列表中，则将其加入开放列表，并将当前节点作为其父节点。
f

相关问题

用C++写一段Astar算法

### 回答1：

我可以为您提供一段Astar算法的C语言代码：#include<stdio.h>
#include<stdlib.h>
#define MAX 20

int a[MAX][MAX],closed[MAX][MAX],open[MAX][MAX],x,y;
int xp,yp,x0,y0,minf,i,j;

void path(){

while(closed[xp][yp]!=1){
minf=999;
for(i=x-1;i<=x+1;i++){
for(j=y-1;j<=y+1;j++){
if(a[i][j]<minf && closed[i][j]!=1){
minf=a[i][j];
x0=i;
y0=j;
}
}
}
x=x0;
y=y0;
closed[x][y]=1;
open[x][y]=1;
}
}

int main(){

printf("Enter the no of rows and columns :\n");
scanf("%d%d",&xp,&yp);

for(i=0;i<xp;i++){
for(j=0;j<yp;j++){
printf("Enter the cost of (%d,%d) node :\n",i,j);
scanf("%d",&a[i][j]);
closed[i][j]=0;
open[i][j]=0;
}
}

printf("Enter the coordinates of the starting node :\n");
scanf("%d%d",&x,&y);
open[x][y]=1;
printf("The Path is :\n");
path();
printf("(%d,%d)",x,y);
i=x;
j=y;
do{
if(i-1>=0 && open[i-1][j]==1){
printf("(%d,%d)",i-1,j);
i=i-1;
}
else if(j+1<yp && open[i][j+1]==1){
printf("(%d,%d)",i,j+1);
j=j+1;
}
else if(i+1<xp && open[i+1][j]==1){
printf("(%d,%d)",i+1,j);
i=i+1;
}
else if(j-1>=0 && open[i][j-1]==1){
printf("(%d,%d)",i,j-1);
j=j-1;
}
}while(i!=x || j!=y);
return 0;
}

### 回答2：
A*算法是一种经典的寻路算法，用于在图形化网格中找到最短路径。以下是用C语言实现A*算法的代码段。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define ROW 10
#define COL 10

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

typedef struct {
    Node* elements[ROW * COL];
    int front;
    int rear;
} Queue;

Queue* create_queue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

void enqueue(Queue* queue, Node* node) {
    queue->elements[queue->rear] = node;
    queue->rear++;
}

Node* dequeue(Queue* queue) {
    Node* node = queue->elements[queue->front];
    queue->front++;
    return node;
}

int is_empty(Queue* queue) {
    return queue->front == queue->rear;
}

int heuristic(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

int isValid(int row, int col) {
    return row >= 0 && row < ROW && col >= 0 && col < COL;
}

int isObstacle(int grid[ROW][COL], int row, int col) {
    return grid[row][col] == 1;
}

void tracePath(Node* endNode) {
    Node* current = endNode;
    while (current != NULL) {
        printf("(%d, %d) ", current->row, current->col);
        current = current->parent;
    }
}

void aStar(int grid[ROW][COL], Node* start, Node* end) {
    int rowMoves[] = {-1, 0, 1, 0};
    int colMoves[] = {0, 1, 0, -1};
    
    int closedList[ROW][COL];
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            closedList[i][j] = 0;
        }
    }

    Queue* openList = create_queue();
    enqueue(openList, start);

    while (!is_empty(openList)) {
        Node* current = dequeue(openList);

        if (current->row == end->row && current->col == end->col) {
            printf("最短路径为: ");
            tracePath(current);
            return;
        }

        closedList[current->row][current->col] = 1;

        for (int i = 0; i < 4; i++) {
            int newRow = current->row + rowMoves[i];
            int newCol = current->col + colMoves[i];

            if (isValid(newRow, newCol) && !isObstacle(grid, newRow, newCol) && !closedList[newRow][newCol]) {
                Node* neighbor = (Node*)malloc(sizeof(Node));
                neighbor->row = newRow;
                neighbor->col = newCol;
                neighbor->parent = current;
                neighbor->g = current->g + 1;
                neighbor->h = heuristic(newRow, newCol, end->row, end->col);
                neighbor->f = neighbor->g + neighbor->h;

                enqueue(openList, neighbor);
            }
        }
    }

    printf("找不到路径");
}

int main() {
    int grid[ROW][COL] = {
        {0, 1, 0, 0, 0, 0, 1, 0, 0, 0},
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0},
        {0, 0, 0, 1, 0, 0, 0, 0, 1, 0},
        {0, 1, 0, 1, 0, 1, 1, 0, 1, 0},
        {0, 1, 0, 1, 0, 1, 0, 1, 0, 0},
        {0, 1, 0, 0, 0, 1, 0, 1, 1, 0},
        {0, 1, 0, 1, 0, 0, 0, 0, 1, 0},
        {0, 1, 0, 1, 1, 1, 0, 1, 1, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
        {0, 0, 1, 1, 1, 1, 1, 1, 1, 0}
    };

    Node* start = (Node*)malloc(sizeof(Node));
    start->row = 0;
    start->col = 0;

    Node* end = (Node*)malloc(sizeof(Node));
    end->row = 9;
    end->col = 9;

    aStar(grid, start, end);

    return 0;
}

这段代码实现了A*算法在一个10x10的网格中寻找路径。网格中1代表障碍物，0代表可通行区域。算法会输出从起点(0, 0)到终点(9, 9)的最短路径。

### 回答3：
A*算法是一种启发式搜索算法，常用于路径规划问题。在使用C语言编写A*算法时，需要实现以下几个关键的步骤：

1. 定义表示地图的数据结构：使用二维数组或类似的数据结构表示地图，其中不同的元素代表不同的地形或障碍物。

2. 定义表示节点的数据结构：每个节点需要包含位置坐标、代价函数值、启发函数值和指向父节点的指针等信息。

3. 实现代价函数和启发函数：代价函数用于评估从起始点到当前节点的代价，启发函数用于估计从当前节点到目标点的代价。

4. 初始化起始节点和目标节点：设置起始节点的坐标，并创建一个空的开放列表和关闭列表。

5. 将起始节点加入到开放列表中。

6. 重复以下步骤，直到开放列表为空或找到目标节点：
a. 从开放列表中选择代价函数值最小的节点作为当前节点。
b. 将当前节点从开放列表中移除，并将其加入到关闭列表中。
c. 对当前节点的邻居节点进行遍历，计算其代价函数值和启发函数值，并更新节点信息。
d. 如果邻居节点已经在关闭列表中，跳过该节点。
e. 否则，如果邻居节点已经在开放列表中，并且新的路径代价更高，则跳过该节点。
f. 否则，将邻居节点加入到开放列表中，更新其父节点为当前节点。

7. 从目标节点开始，按照父节点指针一直追溯回起始节点，即可得到找到的最佳路径。

使用C语言实现A*算法需要灵活运用数据结构和指针操作，同时需要根据实际情况进行合理的优化，以提高算法的效率和性能。

用c++写一个A*寻路算法

好的，以下是一个简单的C语言实现的A*寻路算法：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define ROW 10
#define COL 10

typedef struct Node {
    int x, y;
    int f, g, h;
    struct Node *parent;
} Node;

Node *openList[ROW * COL];
Node *closeList[ROW * COL];
int openLen = 0, closeLen = 0;
int map[ROW][COL] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

int isObstacle(int x, int y) {
    if (x < 0 || x >= ROW || y < 0 || y >= COL) {
        return 1;
    }
    return map[x][y];
}

int calcG(Node *node) {
    int g = 0;
    while (node->parent) {
        g += abs(node->x - node->parent->x) + abs(node->y - node->parent->y);
        node = node->parent;
    }
    return g;
}

int calcH(Node *node, Node *end) {
    return abs(node->x - end->x) + abs(node->y - end->y);
}

int calcF(Node *node, Node *end) {
    return calcG(node) + calcH(node, end);
}

void insertOpenList(Node *node) {
    int i;
    for (i = 0; i < openLen; i++) {
        if (openList[i]->f > node->f) {
            break;
        }
    }
    for (int j = openLen; j > i; j--) {
        openList[j] = openList[j - 1];
    }
    openList[i] = node;
    openLen++;
}

Node *popOpenList() {
    Node *node = openList[0];
    for (int i = 0; i < openLen - 1; i++) {
        openList[i] = openList[i + 1];
    }
    openLen--;
    return node;
}

void insertCloseList(Node *node) {
    closeList[closeLen++] = node;
}

int isInCloseList(Node *node) {
    for (int i = 0; i < closeLen; i++) {
        if (closeList[i]->x == node->x && closeList[i]->y == node->y) {
            return 1;
        }
    }
    return 0;
}

void freeList(Node **list, int len) {
    for (int i = 0; i < len; i++) {
        free(list[i]);
    }
}

void printPath(Node *node) {
    while (node) {
        printf("(%d, %d) ", node->x, node->y);
        node = node->parent;
    }
    printf("\n");
}

void aStar(int startX, int startY, int endX, int endY) {
    Node *start = (Node *)malloc(sizeof(Node));
    start->x = startX;
    start->y = startY;
    start->f = 0;
    start->g = 0;
    start->h = 0;
    start->parent = NULL;
    insertOpenList(start);

    while (openLen > 0) {
        Node *cur = popOpenList();
        if (cur->x == endX && cur->y == endY) {
            printPath(cur);
            freeList(openList, openLen);
            freeList(closeList, closeLen);
            return;
        }
        insertCloseList(cur);

        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                int x = cur->x + i;
                int y = cur->y + j;
                if (isObstacle(x, y) || isInCloseList(&(Node){x, y})) {
                    continue;
                }
                Node *node = (Node *)malloc(sizeof(Node));
                node->x = x;
                node->y = y;
                node->parent = cur;
                node->g = calcG(node);
                node->h = calcH(node, &(Node){endX, endY});
                node->f = calcF(node, &(Node){endX, endY});
                insertOpenList(node);
            }
        }
    }

    printf("No path found.\n");
    freeList(openList, openLen);
    freeList(closeList, closeLen);
}

int main() {
    map[1][1] = 1;
    map[2][1] = 1;
    map[3][1] = 1;
    map[4][1] = 1;
    map[5][1] = 1;
    map[6][1] = 1;
    map[7][1] = 1;
    map[8][1] = 1;
    map[9][1] = 1;

    aStar(0, 0, 9, 9);

    return 0;
}

这是一个简单的A*寻路算法实现，可以在一个10x10的地图上找到起点到终点的最短路径。