用A*算法实现英雄联盟中的自动寻路功能

  • 开发
  • 13

一、将地图转化为二维数组进行存储

在英雄联盟的游戏中，地图拥有很复杂的地形，这里为了简化我将地图分为可走的区域和不可走的区域，并利用工具将地图转化为100*100黑白像素图的形式

 采用Qt作为集成开发工具，利用Qt中的画图功能进行召唤师峡谷地图的显示与路径的绘制。利用函数读取图片将墙壁的信息转化为100*100的矩阵的形式。

int MainWindow::readfile() {
    QImage image("D:\\4ac4b06b54864fc08dc46da1e800b68a.png");
    if (image.isNull()) {
        qDebug() << "Failed to load image";
        return 1;
    }

    if (image.width() != 100 || image.height() != 100) {
        qDebug() << "Image size is not 100x100";
        return 1;
    }

    for (int y = 0; y < 100; ++y) {
        for (int x = 0; x < 100; ++x) {
            QRgb pixel = image.pixel(x, y);
            int red = qRed(pixel);
            int green = qGreen(pixel);
            int blue = qBlue(pixel);

            if (red == 255 && green == 255 && blue == 255) {
                pixelValues[y][x] = 0;
                Point[y][x].wall = 0;
            } else {
                pixelValues[y][x] = 1;
                Point[y][x].wall = 1;
            }
        }
    }
    return 0;
}

这样我们就将峡谷地图中的信息储存在了100*100的矩阵中。

二、A*算法的设计

A*算法的介绍

在获取到矩阵之后利用Qt的画图事件将图形绘制出来，如下图

 

A*算法最为核心的部分，就在于它的一个估值函数的设计上：

f(n)=g(n)+h(n)

其中f(n)是每个可能试探点的估值，它有两部分组成：

一部分，为g(n)，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。

另一部分，即h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值，h(n)设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为A*算法。

一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是：

1、搜索树上存在着从起始点到终了点的最优路径。

2、问题域是有限的。

3、所有结点的子结点的搜索代价值>0。

4、h(n)已知

当此四个条件都满足时，一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法，并一定能找到最优解。

  A*算法具有绝大部分情况能找到最优解，且时间复杂度较低的特点，在很多游戏的寻路算法中被采用。当我方英雄行进时，每一步都会调用A*算法，不断更新自己到目标点的最优路径，其中A*算法采用优先队列的形式，在当前节点周围没有合适路径时将此节点退出优先队列，并且在队列中寻找优先级最高的节点进行下一步操作。优先队列采用重载的方式，在比较启发值的时候优先比较当前节点到目标点的横坐标差的绝对值加上纵坐标差的绝对值，当距离敌人较近时会考虑敌人的位置改变参数，并将优先级设置为启发值加上已经走过的路径长度，当优先级相同时，会比较下一个节点到目标节点的几何距离，优先采用集合距离较近的节点。

通过重载优先队列的方法进行寻路

两个点之间无法直接采用优先队列进行比较，因此需要重载小于号

bool operator<(const Point1& p) const {

            int f1 = cost + heuristic(x, y); // 计算当前点的 启发函数值
            if(heuristic1(x,y)<20&&MainWindow::z==0) f1-=5*heuristic1(x,y);
            int f2 = p.cost + p.heuristic(p.x, p.y);
            if(heuristic1(p.x,p.y)<20&&MainWindow::z==0) f2-=5*heuristic1(p.x,p.y);
            if (f1 == f2) {
                double dist1 = std::sqrt(std::pow(x - x2, 2) + std::pow(y - y2, 2));
              double dist2 = std::sqrt(std::pow(p.x - x2, 2) + std::pow(p.y - y2, 2));
                return dist1 > dist2;
            }
            else {
                return f1 > f2;
            }
        }

        // 定义启发函数
        int heuristic(int x, int y) const {
            return std::abs(x2 - x) + std::abs(y2 - y);
        }
        int heuristic1(int x, int y) const {
        return std::abs(x3 - x) + std::abs(y3 - y);
         }

路径的记录与显示

创建一个100*100的int 类型数组path，将走过的路径标记为-3

​
int MainWindow::search(int x1, int y1, int x2, int y2, int z, int path[100][100]) {
    int dist = 0;
    qDebug() << "Searching from (" << x1 << ", " << y1 << ") to (" << x2 << ", " << y2 << ")";
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
           
            path[i][j] = 0;
        }
    }

    std::priority_queue<Point1> pq;
    pq.push({x1, y1, 0});
    path[x1][y1] = -2;

    while (!pq.empty()) {
        Point1 current = pq.top();
        pq.pop();

        int x = current.x;
        int y = current.y;
        int cost = current.cost;

        if (x == x2 && y == y2) {
            int px = x, py = y;
            while (path[px][py] != -2) {
                int temp = path[px][py];
       path[px][py] = -3 ;
    
                px = temp / 100;
                py = temp % 100;
                dist++;
            }
            return dist;
        }

        if (x + 1 < 100 && Point[x + 1][y].wall == 0 && path[x + 1][y] == 0) {
            pq.push({x + 1, y, cost + 1});
            path[x + 1][y] = x * 100 + y;
        }
        if (x - 1 >= 0 && Point[x - 1][y].wall == 0 && path[x - 1][y] == 0) {
            pq.push({x - 1, y, cost + 1});
            path[x - 1][y] = x * 100 + y;
        }
        if (y + 1 < 100 && Point[x][y + 1].wall == 0 && path[x][y + 1] == 0) {
            pq.push({x, y + 1, cost + 1});
            path[x][y + 1] = x * 100 + y;
        }
        if (y - 1 >= 0 && Point[x][y - 1].wall == 0 && path[x][y - 1] == 0) {
            pq.push({x, y - 1, cost + 1});
            path[x][y - 1] = x * 100 + y;
        }
    }
    return -1;
}

​

在画图事件中将带有标记的方格标记为红色即可显示路径。

 三、（进阶版）采用躲避敌人的策略并进行动态画图

在问题一的部分中，我们已经做出了对基础路径算法的实现。在问题二中，我们需要考虑到实际游戏中敌人的到来并尽量避免他。

基础路径的算法中我们优先队列的比较是根据路径消耗与启发值函数的和来进行比较的，因此在问题二中，我们需要对优先队列的重载略作修改。

我们在设置逃避敌人的时候进行条件判断，如果距离估计小于20，则会考虑到敌人位置并将启发值减去与敌人的预估距离，如果距离估计大于20，则会正常调用问题一中的路径算法进行寻路。

而在敌人追逐我方玩家的算法中，不需要考虑敌人位置，调用此寻路算法时不会额外考虑敌人位置，只需要按照问题一中的简单寻路算法进行寻路即可。

利用一个计时器进行画图功能的动态化，每0.5秒执行路径更新的函数，在路径更新的函数里同时update来执行画图事件的重绘。在动态画图的过程中，随时可以改变我方英雄的位置，目标位置和敌方英雄的位置。将我方英雄到目的地的路径和敌方英雄到我方英雄的路径进行涂色，其中我方英雄显示的位置为绿色，而我方英雄到目标点的路径为红色，敌方

英雄到我方英雄的路径为蓝色。

 QPainter:

 QPainter类用于执行绘图操作，允许在主窗口上绘制形状、文本和图像。

 paintEvent:

  重写paintEvent方法来处理自定义绘图。每当需要重新绘制窗口时，该方法会被调用，确保视觉表示是最新的。

 QTimer:

  使用QTimer对象来触发定期的绘图更新，从而实现平滑的连续动画和游戏状态的实时更新。

四、源码

mainwindow.h

#ifndef MAINWINDOW_H
#define MAINWINDOW_H

#include <QMainWindow>
#include <QCoreApplication>
#include <QImage>
#include <QDebug>
#include <QBuffer>
#include <QVector>
#include <math.h>
#include <queue>
#include <cmath>
#include <QTimer>
#include <QThread>
#include <QPainter>
#include <QMouseEvent>

QT_BEGIN_NAMESPACE
namespace Ui { class MainWindow; }
QT_END_NAMESPACE

class MainWindow : public QMainWindow
{
    Q_OBJECT

public:
    static int x1;
    static int y1;
    static int x2;
    static int y2;
    static int x3;
    static int y3;
    static int xc1;
    static int yc1;
    static int z;
    int search(int x1, int y1, int x2, int y2, int z, int path[100][100]);


    struct Point1 {
        int x;
        int y;
        int cost;
        int wall = -1;
        int enemyX = 50;
        int enemyY = 50;
        int enemySpeed = 1;
        Point1() : x(0), y(0), cost(0) {}


        // 定义比较函数，用于优先级队列的排序
        bool operator<(const Point1& p) const {

            int f1 = cost + heuristic(x, y); // 计算当前点的 启发函数值
            if(heuristic1(x,y)<20&&MainWindow::z==0) f1-=5*heuristic1(x,y);
            int f2 = p.cost + p.heuristic(p.x, p.y);
            if(heuristic1(p.x,p.y)<20&&MainWindow::z==0) f2-=5*heuristic1(p.x,p.y);
            if (f1 == f2) {
                double dist1 = std::sqrt(std::pow(x - x2, 2) + std::pow(y - y2, 2));
              double dist2 = std::sqrt(std::pow(p.x - x2, 2) + std::pow(p.y - y2, 2));
                return dist1 > dist2;
            }
            else {
                return f1 > f2;
            }
        }

        // 定义启发函数
        int heuristic(int x, int y) const {
            return std::abs(x2 - x) + std::abs(y2 - y);
        }
        int heuristic1(int x, int y) const {
        return std::abs(x3 - x) + std::abs(y3 - y);
         }
        Point1(int x, int y, int cost)
            : x(x), y(y), cost(cost) {}
    };

    Point1 Point[100][100];

    MainWindow(QWidget* parent = nullptr);
    ~MainWindow();

    int readfile();
    int step = 0;
    int dist[100][100]{ 100000 };
    int path1[100][100]{ -1 };
    int path2[100][100]{ -1 };

    int pixelValues[100][100];

    void paintEvent(QPaintEvent* event) override;
    int absolute(int x);
    void search1(int &xc, int &yc, int x2, int y2, int step);
    bool search3(int x1, int y1, int x2, int y2);
    void mousePressEvent(QMouseEvent* event) override;
    void resetSearch();
    void startSearchLoop();
    void search2(int &xc, int &yc, int x2, int y2, int step);

private slots:
    void on_pushButton_clicked();
    void updatePath();

private:
    Ui::MainWindow* ui;
    QTimer* timer;
    Point1 current;
    bool searchComplete;
};

#endif // MAINWINDOW_H

mainwindow.cpp

#include "mainwindow.h"
#include "./ui_mainwindow.h"

int MainWindow::x1 = 0;
int MainWindow::y1 = 0;
int MainWindow::x2 = 0;
int MainWindow::y2 = 0;
int MainWindow::x3 = 0;
int MainWindow::y3 = 0;
int MainWindow::z = 0;

MainWindow::MainWindow(QWidget* parent)
    : QMainWindow(parent)
    , ui(new Ui::MainWindow)
{
    readfile();
    ui->setupUi(this);

    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            Point[i][j].x = i;
            Point[i][j].y = j;
            path1[i][j] = 0;
            path2[i][j] = 0;
        }
    }

    timer = new QTimer(this);
    connect(timer, &QTimer::timeout, this, &MainWindow::updatePath);
    timer->setInterval(500);
    timer->start();
}

int MainWindow::readfile() {
    QImage image("D:\\4ac4b06b54864fc08dc46da1e800b68a.png");
    if (image.isNull()) {
        qDebug() << "Failed to load image";
        return 1;
    }

    if (image.width() != 100 || image.height() != 100) {
        qDebug() << "Image size is not 100x100";
        return 1;
    }

    for (int y = 0; y < 100; ++y) {
        for (int x = 0; x < 100; ++x) {
            QRgb pixel = image.pixel(x, y);
            int red = qRed(pixel);
            int green = qGreen(pixel);
            int blue = qBlue(pixel);

            if (red == 255 && green == 255 && blue == 255) {
                pixelValues[y][x] = 0;
                Point[y][x].wall = 0;
            } else {
                pixelValues[y][x] = 1;
                Point[y][x].wall = 1;
            }
        }
    }
    return 0;
}

void MainWindow::updatePath() {
    step++;
    search1(x1, y1, x2, y2, step);
    z=1;
    search2(x3, y3, x1, y1, step);
    z=0;
    update();
}

int MainWindow::search(int x1, int y1, int x2, int y2, int z, int path[100][100]) {
    int dist = 0;
    qDebug() << "Searching from (" << x1 << ", " << y1 << ") to (" << x2 << ", " << y2 << ")";
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            if ((path[i][j] == -3 || path[i][j] == -7) && z == 2) continue;
            if (path[i][j] == -4 && z == 1) continue;
            path[i][j] = 0;
        }
    }

    std::priority_queue<Point1> pq;
    pq.push({x1, y1, 0});
    path[x1][y1] = -2;

    while (!pq.empty()) {
        Point1 current = pq.top();
        pq.pop();

        int x = current.x;
        int y = current.y;
        int cost = current.cost;

        if (x == x2 && y == y2) {
            int px = x, py = y;
            while (path[px][py] != -2) {
                int temp = path[px][py];
                path[px][py] = (z == 1) ? -3 : -4;
                px = temp / 100;
                py = temp % 100;
                dist++;
            }
            return dist;
        }

        if (x + 1 < 100 && Point[x + 1][y].wall == 0 && path[x + 1][y] == 0) {
            pq.push({x + 1, y, cost + 1});
            path[x + 1][y] = x * 100 + y;
        }
        if (x - 1 >= 0 && Point[x - 1][y].wall == 0 && path[x - 1][y] == 0) {
            pq.push({x - 1, y, cost + 1});
            path[x - 1][y] = x * 100 + y;
        }
        if (y + 1 < 100 && Point[x][y + 1].wall == 0 && path[x][y + 1] == 0) {
            pq.push({x, y + 1, cost + 1});
            path[x][y + 1] = x * 100 + y;
        }
        if (y - 1 >= 0 && Point[x][y - 1].wall == 0 && path[x][y - 1] == 0) {
            pq.push({x, y - 1, cost + 1});
            path[x][y - 1] = x * 100 + y;
        }
    }
    return -1;
}

void MainWindow::search1(int &xc, int &yc, int x2, int y2, int step) {
    search(xc, yc, x2, y2, 1, path1);
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    qDebug()<<"敌人位置"<<x3<<y3;
    qDebug()<<"我方位置"<<x1<<y1;

    for (int i = 0; i < 4; i++) {
        int nx = x1 + dx[i];
        int ny = y1 + dy[i];
        if (nx >= 0 && nx < 100 && ny >= 0 && ny < 100 && path1[nx][ny] == -3) {
            xc = nx;
            yc = ny;
            path1[nx][ny] = -7;
            if (x1 == x2 && y1 == y2) {
                return;
            }
            break;
        }
    }
}

void MainWindow::search2(int &xc, int &yc, int x2, int y2, int step) {
    search(xc, yc, x2, y2, 2, path2);
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    for (int i = 0; i < 4; i++) {
        int nx = x3 + dx[i];
        int ny = y3 + dy[i];
        if (nx >= 0 && nx < 100 && ny >= 0 && ny < 100 && path2[nx][ny] == -4) {
            xc = nx;
            yc = ny;
            path2[nx][ny] = -8;
            if (xc == x2 && yc == y2) {
                return;
            }
            break;
        }
    }
}

void MainWindow::paintEvent(QPaintEvent* event) {
    QMainWindow::paintEvent(event);

    QPainter painter(this);
    int cellSize = 6;

    for (int i = 0; i < 100; ++i) {
        for (int j = 0; j < 100; ++j) {
            QRect cellRect(j * cellSize, i * cellSize, cellSize, cellSize);
            QColor color;

            if (pixelValues[i][j] == 1 && path1[i][j] != -3 && path2[i][j] != -4) {
                color = Qt::black;
            } else if (pixelValues[i][j] == 0 && path1[i][j] != -3 && path2[i][j] != -4) {
                color = Qt::white;
            } else if (path1[i][j] == -3) {
                color = Qt::red;
            } else if (path1[i][j] == -7) {
                color = Qt::green;
            } else if (path2[i][j] == -4) {
                color = Qt::blue;
            } else if (path2[i][j] == -8) {
                color = Qt::blue;
            }

            painter.fillRect(cellRect, color);
            painter.drawRect(cellRect);
        }
    }
}

void MainWindow::mousePressEvent(QMouseEvent* event) {
    int x = event->y() / 6;
    int y = event->x() / 6;
    if (event->button() == Qt::LeftButton) {
        x1 = x;
        y1 = y;
    } else if (event->button() == Qt::RightButton) {
        x2 = x;
        y2 = y;
    } else if (event->button() == Qt::MiddleButton) {
        x3 = x;
        y3 = y;
    }
    qDebug() << "Mouse clicked at: (" << x << ", " << y << ")";
}

void MainWindow::on_pushButton_clicked() {
    x3 = ui->lineEdit_5->text().toInt();
    y3 = ui->lineEdit_6->text().toInt();
    updatePath();
}

MainWindow::~MainWindow() {
    delete ui;
}

阅读全部

相关推荐

  3. Unity3D 游戏中的自动寻路有怎样的算法详解

    2024-07-19 23:32:01       54 阅读

  5. 数字孪生项目中的导航片及寻路实现算法的探索

    2024-07-19 23:32:01       47 阅读

  10. 自然语言：python实现自然语言处理中计算文件中的英语字母的熵

    2024-07-19 23:32:01       40 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-19 23:32:01       52 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-19 23:32:01       54 阅读

  9. 在Django里面运行非项目文件

    2024-07-19 23:32:01       45 阅读

  19. Python语言-面向对象

    2024-07-19 23:32:01       55 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-19 23:32:01       50 阅读

热门阅读

  2. MySQL零散拾遗（三）

    2024-07-19 23:32:01       18 阅读

  5. ArcEngine 非SDE方式加载postgis数据

    2024-07-19 23:32:01       18 阅读

  7. C语言习题~day32

    2024-07-19 23:32:01       17 阅读

  10. 安康古韵长，汉水碧波扬

    2024-07-19 23:32:01       14 阅读

  17. python单继承和多继承实例讲解

    2024-07-19 23:32:01       16 阅读

  21. Linux的常用命令大全

    2024-07-19 23:32:01       15 阅读

  30. salesforce 通过 schedule job 去执行需要http访问外部网站的代码并更新自定义字段有什么原因可能导致失败

    2024-07-19 23:32:01       16 阅读