opengl做Astart的搜索动画

以下是使用OpenGL实现A*算法搜索动画的示例代码：

首先，我们定义一个节点类，表示每个搜索节点：

class Node {
public:
    int x, y; // 坐标
    int g; // 起点到当前节点的代价
    int h; // 当前节点到终点的预估代价
    int f; // f = g + h
    bool blocked; // 是否障碍物
    Node* parent; // 父节点

    Node(int x, int y) : x(x), y(y), g(0), h(0), f(0), blocked(false), parent(nullptr) {}

    void calc_f() {
        f = g + h;
    }
};

然后，我们定义一个搜索类，表示A*算法搜索过程：

class AStarSearch {
public:
    AStarSearch(int width, int height);

    bool search(Node* start, Node* goal); // 开始搜索

    void set_heuristic(std::function<int(Node*, Node*)> heuristic); // 设置预估函数

    std::vector<Node*> get_path(); // 获取最短路径

    std::vector<Node*> get_closed_list(); // 获取关闭列表

    std::vector<Node*> get_open_list(); // 获取开放列表

private:
    int m_width, m_height;
    std::vector<Node*> m_nodes;
    std::function<int(Node*, Node*)> m_heuristic;
    std::vector<Node*> m_path;
    std::vector<Node*> m_closed_list;
    std::vector<Node*> m_open_list;

    Node* get_node(int x, int y);

    void init_nodes(); // 初始化节点
    void reset_nodes(); // 重置节点
    void add_to_open_list(Node* node); // 添加节点到开放列表
    void add_to_closed_list(Node* node); // 添加节点到关闭列表
    void calc_f(Node* node); // 计算节点的f值
    Node* get_lowest_f_node(); // 获取f值最小的节点
    void update_neighbors(Node* node, Node* goal); // 更新邻居节点
};

接下来，我们实现搜索类的成员函数：

AStarSearch::AStarSearch(int width, int height) : m_width(width), m_height(height) {
    init_nodes();
}

bool AStarSearch::search(Node* start, Node* goal) {
    reset_nodes();

    add_to_open_list(start);

    while (!m_open_list.empty()) {
        Node* current = get_lowest_f_node();

        if (current == goal) {
            // 找到终点
            m_path.clear();
            Node* node = current;
            while (node != nullptr) {
                m_path.push_back(node);
                node = node->parent;
            }
            std::reverse(m_path.begin(), m_path.end());
            return true;
        }

        add_to_closed_list(current);

        update_neighbors(current, goal);
    }

    // 没有找到路径
    return false;
}

void AStarSearch::set_heuristic(std::function<int(Node*, Node*)> heuristic) {
    m_heuristic = heuristic;
}

std::vector<Node*> AStarSearch::get_path() {
    return m_path;
}

std::vector<Node*> AStarSearch::get_closed_list() {
    return m_closed_list;
}

std::vector<Node*> AStarSearch::get_open_list() {
    return m_open_list;
}

Node* AStarSearch::get_node(int x, int y) {
    if (x < 0 || x >= m_width || y < 0 || y >= m_height) {
        return nullptr;
    }
    return m_nodes[x + y * m_width];
}

void AStarSearch::init_nodes() {
    for (int y = 0; y < m_height; ++y) {
        for (int x = 0; x < m_width; ++x) {
            m_nodes.push_back(new Node(x, y));
        }
    }
}

void AStarSearch::reset_nodes() {
    for (auto node : m_nodes) {
        node->g = 0;
        node->h = 0;
        node->f = 0;
        node->blocked = false;
        node->parent = nullptr;
    }
    m_path.clear();
    m_closed_list.clear();
    m_open_list.clear();
}

void AStarSearch::add_to_open_list(Node* node) {
    m_open_list.push_back(node);
}

void AStarSearch::add_to_closed_list(Node* node) {
    m_closed_list.push_back(node);
}

void AStarSearch::calc_f(Node* node) {
    node->calc_f();
}

Node* AStarSearch::get_lowest_f_node() {
    Node* lowest_f_node = nullptr;
    int lowest_f = INT_MAX;
    for (auto node : m_open_list) {
        if (node->f < lowest_f) {
            lowest_f = node->f;
            lowest_f_node = node;
        }
    }
    return lowest_f_node;
}

void AStarSearch::update_neighbors(Node* node, Node* goal) {
    for (int dy = -1; dy <= 1; ++dy) {
        for (int dx = -1; dx <= 1; ++dx) {
            if (dx == 0 && dy == 0) {
                continue;
            }
            Node* neighbor = get_node(node->x + dx, node->y + dy);
            if (neighbor == nullptr) {
                continue;
            }
            if (neighbor->blocked) {
                continue;
            }
            if (std::find(m_closed_list.begin(), m_closed_list.end(), neighbor) != m_closed_list.end()) {
                continue;
            }

            int g = node->g + std::abs(dx) + std::abs(dy);
            bool is_better = false;
            if (std::find(m_open_list.begin(), m_open_list.end(), neighbor) == m_open_list.end()) {
                // 第一次访问邻居节点
                neighbor->h = m_heuristic(neighbor, goal);
                is_better = true;
                add_to_open_list(neighbor);
            } else if (g < neighbor->g) {
                // 已经访问过邻居节点，但是当前路径更优
                is_better = true;
            }

            if (is_better) {
                neighbor->parent = node;
                neighbor->g = g;
                calc_f(neighbor);
            }
        }
    }
}

最后，我们使用OpenGL绘制搜索过程的动画：

void draw_node(Node* node, float size) {
    if (node->blocked) {
        glColor3f(0.3f, 0.3f, 0.3f);
    } else {
        glColor3f(1.0f, 1.0f, 1.0f);
    }
    glBegin(GL_QUADS);
    glVertex2f(node->x - size, node->y - size);
    glVertex2f(node->x + size, node->y - size);
    glVertex2f(node->x + size, node->y + size);
    glVertex2f(node->x - size, node->y + size);
    glEnd();
}

void draw_path(std::vector<Node*> path, float size) {
    if (path.empty()) {
        return;
    }
    glColor3f(1.0f, 0.0f, 0.0f);
    glLineWidth(2.0f);
    glBegin(GL_LINE_STRIP);
    for (auto node : path) {
        glVertex2f(node->x, node->y);
    }
    glEnd();

    for (auto node : path) {
        draw_node(node, size * 1.5f);
    }
}

void draw_lists(std::vector<Node*> open_list, std::vector<Node*> closed_list, float size) {
    for (auto node : open_list) {
        glColor3f(0.0f, 1.0f, 0.0f);
        draw_node(node, size * 0.8f);
    }
    for (auto node : closed_list) {
        glColor3f(0.0f, 0.0f, 1.0f);
        draw_node(node, size * 0.8f);
    }
}

void draw_search(AStarSearch& search, float size) {
    glClear(GL_COLOR_BUFFER_BIT);

    for (auto node : search.m_nodes) {
        draw_node(node, size);
    }

    draw_lists(search.get_open_list(), search.get_closed_list(), size);
    draw_path(search.get_path(), size);

    glutSwapBuffers();
}

void idle() {
    glutPostRedisplay();
}

void reshape(int w, int h) {
    glViewport(0, 0, w, h);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glOrtho(0, w, h, 0, -1, 1);
    glMatrixMode(GL_MODELVIEW);
}

int main(int argc, char** argv) {
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE);
    glutInitWindowSize(640, 480);
    glutCreateWindow("A* Search");

    AStarSearch search(40, 30);
    search.set_heuristic([](Node* a, Node* b) {
        return std::abs(a->x - b->x) + std::abs(a->y - b->y);
    });

    search.get_node(10, 15)->blocked = true;
    search.get_node(11, 15)->blocked = true;
    search.get_node(12, 15)->blocked = true;
    search.get_node(13, 15)->blocked = true;
    search.get_node(14, 15)->blocked = true;

    glutDisplayFunc([&]() {
        draw_search(search, 10.0f);
    });
    glutReshapeFunc(reshape);
    glutIdleFunc(idle);

    glutMainLoop();
    return 0;
}

以上代码可以在OpenGL窗口中绘制网格地图、搜索路径、开放列表和关闭列表，通过设置障碍物和启动搜索，可以实时显示搜索过程的动画效果。