程序员经验分享-hwhale

使用联机搜索求解Wumpus World

2023-11-06

使用 JavaScript 重写的算法网页：
https://yuqingxiong.github.io/Wumpus-World-Problem/
github仓库地址：
https://github.com/YuqingXiong/Wumpus-World-Problem

题目描述

Wumpus World PEAS 描述：
性能度量：
gold +1000, death -1000-
1 per step, -10 for using the arrow
环境描述：
Squares adjacent to wumpusare smelly
Squares adjacent to pit are breezy
Glitter iffgold is in the same square
Shooting kills wumpus if you are facing it
Shooting uses up the only arrow
Grabbing picks up gold if in same square
Releasing drops the gold in same square
传感器：Stench, Breeze, Glitter, Bump, Scream
执行器：Left turn, Right turn, Forward, Grab, Release, Shoot

Wumpus世界的PEAS描述
- 性能度量：金子+100，死亡-1000，每一步-1，用箭-10
- 环境：4×4网格，智能体初始在[1,1]，面向右方，金子和wumpus在[1,1]之外随机均匀分布
- 执行器：左转，右转，前进，捡起，射箭
    - 智能体可向前、左转或右转
    - 智能体如果进入一个有陷阱或者活着的wumpus的方格，将死去。
    - 如果智能体前方有一堵墙，那么向前移动无效
    - Grab：捡起智能体所在方格中的一个物体
    - Shoot：向智能体所正对方向射箭(只有一枝箭)
- 传感器：
    - Smell：在wumpus所在之外以及与之直接相邻的方格内，智能体可以感知到臭气。
    - Breeze：在与陷阱直接相邻的方格内，智能体可以感知到微风。
    - Glitter(发光)：在金子所处的方格内，智能体可以感知到闪闪金光。
    - 当智能体撞到墙时，它感受到撞击。
    - 当wumpus被杀死时，它发出洞穴内任何地方都可感知到的悲惨嚎叫。

目标：找到金子并获得最高的分数（即使死去）；

此题为人工智能的课程设计题目之一，目的是使用联机搜索的方法，自己设计具体的搜索算法的细节。可能每个人对于游戏目标的追求不相同，有些人的算法设计更注重于安全性，所以即使找不到金子，也可以回家。但是我更注重于在相对安全的情况下获取金子然后回家，即使在寻找金子的过程中有很大概率掉进陷阱。

界面效果

在这里插入图片描述

算法

参考代码(https://github.com/Marko-M/wumpus-world/)
上述代码是没有界面设计的，我在理解代码实现算法后，使用qt实现了可视化。主要借鉴了代码中对周围点的标记方法，使用二进制下的0，1对某种标记是否存在进行判断。

基本思想

使用联机搜索进行求解，联机问题在执行时，需要计算和行动交叉进行。联机搜索需要智能体能够记住先前的状态，不能访问下一个状态。下面是算法的基本流程：

  • （1）随机生成金子，怪兽，陷阱的位置，且它们的位置各不相同。
  • （2）从起始点开始DFS，更新当前点的信息，对当前点的四个邻居根据已有信息进行评估，选择最有利的邻居点走下去。
  • （3）评估标准为：
    首先寻找四周安全的点，如果没有则在地图上寻找最近安全点(BFS实现）
    如果没有安全点，则去往没有怪兽和陷阱的这些相对安全的点。
    如果没有相对安全的点，则去往有怪兽的点杀死怪兽。
    如果没有怪兽，则随机选择一个未被访问的点走下去，虽然很可能调入陷阱。
  • （4）重复上述过程直到找到金子然后最短路径回家或者掉入陷阱死亡。

需求分析

1、使用联机搜索算法进行求解。
2、随机生成地图上陷阱，怪兽和金子的位置。
3、智能体可以感知周围信息，得到金子获得最高的分数。
4、图形化界面展示智能体的移动和当前获得的分数及状态。

模块设计

（1）RandInt模块：生成一个[l, r]之间且不在except中的随机整数。
（2）RandPoint模块：生成一个在矩形l,r之内且不在except中的随机点。
（3）PutFlag模块：为指定世界的某个点放陷阱，怪兽，臭气，微风等标志。
（4）GetNeighborPosition模块：得到周围点的坐标。
（5）Dfs模块：使用Dfs的框架实现联机搜索算法。
（6）Bfs模块：bfs获得从src到tar的最短路径，用于计算最近的安全点和回家的最短路。
（7）UpdateNeighborsInformation模块：每走到一个新的点，则更新邻居节点的信息。
（8）GetBfsPath模块：根据在BFS算法中记录的路径，得到搜索到的路径结果并存储。
（9）ShowPath模块：根据记录的路径展示最终的智能体在地图上的路线。
（10）CreatWorld模块：随机生成一个世界，包含3个陷阱，1个怪兽，1个金子，坐标随机。

模块间的调用关系:
在这里插入图片描述

存储结构设计

（1）随机生成的地图每一个点都通过一个12位的标记向量表示这个点的已知信息，通过二进制中的每个比特位是否为1表示是否有这个标记。

标记名称 当前点 安全 已访问 发光 臭气 微风 怀疑金子 怀疑陷阱 怀疑怪兽 金子 陷阱 怪兽
二进制位 1 2 3 4 5 6 7 8 9 10 11 12
十进制值 1 2 4 8 16 32 64 128 256 512 1024 2048

算法设计

运行程序后，创建WumpusWorld类的对象调用类的构造函数，在类的构造函数中进行世界的随机生成和初始界面显示。
当用户点击Game Start按钮时，调用按钮响应函数，在按钮响应函数ButtonClick()中调用ShowPath模块开始联机搜索然后进行搜索路径的显示。

算法流程图：
在这里插入图片描述

文件结构

在这里插入图片描述
资源文件中的图片是直接在网上搜索下载下的怪兽，金子，陷阱等图片还有一些通过PPT制作的按钮图片和文字图片。

代码

mainwindow.h文件代码

#ifndef MAINWINDOW_H
#define MAINWINDOW_H

#include <QMainWindow>
#include <QTime>
#include <QTest>

#include <QDebug>
#include <QPushButton>
#include <QMessageBox>
#include <QLabel>

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <map>

using namespace std;

#define ROW_NUM			4		// 行数
#define COL_NUM			4		// 列数
#define GOLD_NUM		1		// 金子数
#define CAVE_NUM		3		// 陷阱数
#define WUMPUS_NUM		1		// 怪兽数
#define FLAG_NUM		12		// 标记向量的比特位数量

#define CURRENT			1		// 当前点
#define SAFE			2		// 安全
#define VISITED			4		// 已访问
#define GLITTER			8		// 发光
#define STENCH			16		// 臭气
#define BREEZE			32		// 微风
#define GOLD_SUSPECT	64		// 怀疑有金子
#define CAVE_SUSPECT	128		// 怀疑有陷阱
#define WUMPUS_SUSPECT	256		// 怀疑有怪兽
#define GOLD			512		// 金子
#define CAVE			1024	// 陷阱
#define WUMPUS			2048	// 怪兽

#define GOLD_VALUE		1000	// 金子价值
#define WUMPUS_COST		10		// 怪兽消耗
#define DEATH_COST		1000	// 死亡消耗
#define STEP_COST		1		// 行动消耗

#define Point pair<int, int>	// pair存储点坐标
#define xx first				// x坐标
#define yy second				// y坐标


namespace Ui {
class MainWindow;
}

class WumpusWorld : public QMainWindow
{
    Q_OBJECT
public:
    QList<QLabel *> map_label;    // 地图
    QLabel *score_get;            // 分数显示
    QLabel *state;                // 当前状态
public:
    explicit WumpusWorld(QWidget *parent = 0);
    ~WumpusWorld();
    int RandInt(int l, int r, vector<int> except);					// 生成一个[l, r]之间且不在except中的随机整数
    Point RandPoint(Point l, Point r, vector<Point> except);		// 生成一个在矩形l,r之内且不在except中的随机点
    void PutFlag(int world[ROW_NUM][COL_NUM], Point pos, int flag);	// 放标志
    void GetNeighborPosition(Point pos, vector<Point> &neighbor);	// 得到周围点的坐标
    void Dfs(Point current);										// 联机搜索算法
    int Bfs(Point src, Point tar, bool record);						// bfs获得从src到tar的最短路径
    void UpdateNeighborsInformation(Point current);					// 更新邻居点的信息
    void GetBfsPath(Point cur, Point begPos, Point tar, map<Point, Point> bfs_path);
    void ShowPath();               // 展示agent路径
    void CreatWorld();             // 随机生成一个WumpusWorld

private:
    int real_world[ROW_NUM][COL_NUM];	// 真实世界
    int agent_world[ROW_NUM][COL_NUM];	// 代理世界

    Point cave_position[CAVE_NUM];		// 陷阱坐标
    Point wumpus_position[WUMPUS_NUM];	// 怪兽坐标
    Point gold_position[GOLD_NUM];		// 金子坐标

    Point path_record[100];			// 路径记录
    Point start;	// 起始点坐标

    bool find_gold;	// 是否找到金子
    bool game_over;	// 是否游戏结束
    int score;		// 当前分数
    int step_cnt;   // 步数

private:
    Ui::MainWindow *ui;

public slots:
    void ButtonClick(); // 游戏开始信号
};
#endif // MAINWINDOW_H

main.cpp

#include "mainwindow.h"
#include <QApplication>

int main(int argc, char *argv[])
{
    QApplication a(argc, argv);
    WumpusWorld w;
    w.show();
    return a.exec();
}

mainwindow.cpp

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

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

    /* ======================= 图形界面部分 ===================== */
    setWindowTitle("WumpusWorld");  //设置窗体名
    setFixedSize(900, 600);   //设置窗体大小
    setWindowIcon(QIcon(":/logo.png")); //设置窗体图标
    //设置窗体背景为白色
    QPalette palette(this->palette());
    palette.setColor(QPalette::Background, Qt::white);
    this->setPalette(palette);

    srand((unsigned int)time(0));	//初始化随机种子
    CreatWorld();


    // 信息
    QLabel *infor = new QLabel(this);
    infor->setGeometry(state->pos().x() + 15, state->pos().y() + 70, 150, 250);
    infor->setStyleSheet("border-image:url(:/information.png);");
}

void WumpusWorld::CreatWorld()
{
    /* ==================== WumpusWorld初始化 ================== */
    start.xx = 0, start.yy = 0;	// 起始点(0, 0)
    vector<Point> except;		// 非法访问点
    except.push_back(start);	// 将起始点不可再访问
    Point l{1, 1}, r{ ROW_NUM - 1, COL_NUM - 1 };	// 边界点
    find_gold = false;
    game_over = false;
    step_cnt = 0;

    for (int i = 0; i < ROW_NUM; ++i) {
        for (int j = 0; j < COL_NUM; ++j) {
            real_world[i][j] = 0;
            agent_world[i][j] = 0;
        }
    }

    // 生成陷阱位置
    for (int i = 0; i < CAVE_NUM; ++i) {
        cave_position[i] = RandPoint(l, r, except);
        except.push_back(cave_position[i]);
    }

    // 生成怪兽位置
    for (int i = 0; i < WUMPUS_NUM; ++i) {
        wumpus_position[i] = RandPoint(l, r, except);
        except.push_back(wumpus_position[i]);
    }

    // 生成金子位置
    for (int i = 0; i < CAVE_NUM; ++i) {
        gold_position[i] = RandPoint(l, r, except);
        except.push_back(gold_position[i]);
    }

    vector<Point> neighbor;	// 当前点的邻居坐标
    // 生成世界
    for (int i = 0; i < ROW_NUM; ++i) {
        for (int j = 0; j < COL_NUM; ++j) {
            // 陷阱检查
            for (int k = 0; k < CAVE_NUM; ++k) {
                if (i == cave_position[k].xx && cave_position[k].yy == j) {
                    PutFlag(real_world, cave_position[k], CAVE);	// 放陷阱
                    GetNeighborPosition(cave_position[k], neighbor);// 获取邻居坐标
                    while (!neighbor.empty()) {	// 陷阱的邻居点都打上微风标记
                        PutFlag(real_world, neighbor[neighbor.size() - 1], BREEZE);
                        neighbor.pop_back();
                    }
                }
            }

            // 怪兽检查
            for (int k = 0; k < WUMPUS_NUM; ++k) {
                if (i == wumpus_position[k].xx && j == wumpus_position[k].yy) {
                    PutFlag(real_world, wumpus_position[k], WUMPUS);  // 放怪兽
                    GetNeighborPosition(wumpus_position[k], neighbor);// 获取邻居坐标
                    while (!neighbor.empty()) {	// 怪兽的邻居点都打上臭气标记
                        PutFlag(real_world, neighbor[neighbor.size() - 1], STENCH);
                        neighbor.pop_back();
                    }
                }
            }

            // 金子检查
            for (int k = 0; k < GOLD_NUM; ++k) {
                if (i == gold_position[k].xx && j == gold_position[k].yy) {
                    PutFlag(real_world, gold_position[k], GOLD);	// 放金子
                    GetNeighborPosition(gold_position[k], neighbor);// 获取邻居坐标
                    while (!neighbor.empty()) {
                        PutFlag(real_world, neighbor[neighbor.size() - 1], GLITTER);
                        neighbor.pop_back();
                    }
                }
            }
        }
    }
    /* =============== 程序输出界面显示生成的世界 ================= */

    for (int i = 0; i < CAVE_NUM; ++i) printf("%d. cave corrd: (%d, %d)\n", i, cave_position[i].xx, cave_position[i].yy);
    for (int i = 0; i < WUMPUS_NUM; ++i) printf("%d. wumpus corrd: (%d, %d)\n", i, wumpus_position[i].xx, wumpus_position[i].yy);
    for(int i = 0; i < GOLD_NUM; ++ i) printf("%d. gold corrd: (%d, %d)\n", i, gold_position[i].xx, gold_position[i].yy);

    // 显示世界
    for (int i = 0; i < ROW_NUM; ++i) {
        for (int j = 0; j < COL_NUM; ++j) {
            if ((real_world[i][j] & CAVE) == CAVE) printf("C ");
            else if ((real_world[i][j] & WUMPUS) == WUMPUS) printf("W ");
            else if ((real_world[i][j] & GOLD) == GOLD) printf("G ");
            else printf("O ");
        }
        printf("\n");
    }

    /* =============== 图形界面显示生成的世界 ================= */
    int w = 140, h = 140, px = 0, py = 0;
    for(int i = 0; i < ROW_NUM; ++ i){
        for(int j = 0; j < COL_NUM; ++ j){
            QLabel *label = new QLabel(this);
            map_label.push_back(label);
            px = i * w + 30, py = j * h + 30;
            label->setGeometry(px, py, w, h);   // 设置坐标和大小
            if ((real_world[i][j] & CAVE) == CAVE) label->setStyleSheet("border-image:url(:/cave.png);");
            else if ((real_world[i][j] & WUMPUS) == WUMPUS) label->setStyleSheet("border-image:url(:/monster.png);");
            else if ((real_world[i][j] & GOLD) == GOLD) label->setStyleSheet("border-image:url(:/gold.png);");
            else label->setStyleSheet("border-image:url(:/grid.png);");
        }
    }
    map_label[0]->setStyleSheet("border-image:url(:/agent.png);");
    // 开始按钮
    QPushButton *startBut = new QPushButton(this);
    startBut->setGeometry(650, 30, 210, 70);
    startBut->setStyleSheet("border-image:url(:/start.png);");
    connect(startBut, SIGNAL(clicked(bool)), this, SLOT(ButtonClick()));//为每个按钮添加响应函数

    // 分数标签
    QLabel *score_label = new QLabel(this);
    score_label->setGeometry(startBut->pos().x(), startBut->pos().y() + 70, 210, 60);
    score_label->setStyleSheet("border-image:url(:/score.png);");

    // 分数
    score_get = new QLabel(this);
    score_get->setGeometry(score_label->pos().x(), score_label->pos().y() + 50, 210, 60);
    score_get->setStyleSheet("qproperty-alignment: 'AlignVCenter|AlignHCenter';font-size:50px;color:rgb(31, 93, 173);font-family:黑体");
    score_get->setText("0");

    // 当前状态
    QLabel *state_text = new QLabel(this);
    state_text->setGeometry(score_get->pos().x(), score_get->pos().y() + 70, 210, 60);
    state_text->setStyleSheet("border-image:url(:/state.png);");

    state = new QLabel(this);
    state->setGeometry(state_text->pos().x(), state_text->pos().y() + 50, 210, 50);
    state->setStyleSheet("border-image:url(:/waiting.png);");
}

void WumpusWorld::ButtonClick()
{
    ShowPath();
}
int WumpusWorld::RandInt(int l, int r, vector<int> except)
{
    int result = 0;
    do {
        result = rand() % (r - l + 1) + l;	// 随机数生成
    } while (std::find(except.begin(), except.end(), result) != except.end());

    return result;
}

Point WumpusWorld::RandPoint(Point l, Point r, vector<Point> except)
{
    Point result;
    do {
        result.xx = RandInt(l.xx, r.xx, vector<int>{});	// x坐标
        result.yy = RandInt(l.yy, r.yy, vector<int>{});	// y坐标
    } while (std::find(except.begin(), except.end(), result) != except.end());
    return result;
}

void WumpusWorld::PutFlag(int world[ROW_NUM][COL_NUM], Point pos, int flag)
{
    // 如果已访问则其他的传感器标志置零
    if (pos.xx < 0 || pos.xx >= ROW_NUM || pos.yy < 0 || pos.yy >= COL_NUM) {
        return;
    }
    if (flag == VISITED) {
        world[pos.xx][pos.yy] &= ~SAFE;
        world[pos.xx][pos.yy] &= ~CAVE_SUSPECT;
        world[pos.xx][pos.yy] &= ~GOLD_SUSPECT;
        world[pos.xx][pos.yy] &= ~WUMPUS_SUSPECT;
    }
    world[pos.xx][pos.yy] |= flag;	// 放标记
}

void WumpusWorld::GetNeighborPosition(Point pos, vector<Point> &neighbor)
{
    int Next[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };// 上，下，左，右
    for (int i = 0; i < 4; ++i) {
        int next_x = pos.xx + Next[i][0];	// 邻居点x坐标
        int next_y = pos.yy + Next[i][1];	// 邻居点y坐标
        if (next_x >= 0 && next_x < ROW_NUM && next_y >= 0 && next_y < COL_NUM) {// 边界检查
            neighbor.push_back({ next_x, next_y });
        }
    }
}

void WumpusWorld::Dfs(Point current)
{
    vector<Point> neighbors;
    path_record[step_cnt++] = current;
    agent_world[current.xx][current.yy] |= real_world[current.xx][current.yy];	// 获取当前点信息
    if ((agent_world[current.xx][current.yy] & GOLD) == GOLD) {	//如果遇到了金子
        find_gold = true;
        return;
    }
    if ((agent_world[current.xx][current.yy] & CAVE) == CAVE) {	// 掉进了洞穴
        game_over = true;
        return;
    }
    PutFlag(agent_world, current, VISITED);	// 当前点已访问
    UpdateNeighborsInformation(current);	// 更新周围点的信息
    agent_world[current.xx][current.yy] &= ~CURRENT;	// 不在当前点

    int Next[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };// 上，下，左，右
    for (int i = 0; i < 4; ++i) {
        int next_x = current.xx + Next[i][0];	// 邻居点x坐标
        int next_y = current.yy + Next[i][1];	// 邻居点y坐标
        if (next_x >= 0 && next_x < ROW_NUM && next_y >= 0 && next_y < COL_NUM) {// 边界检查
            neighbors.push_back({ next_x, next_y });
        }
    }
    for (int i = 0; i < neighbors.size(); ++i) {	// 周围可能有金子
        if ((agent_world[neighbors[i].xx][neighbors[i].yy] & GOLD) == GOLD) {
            PutFlag(agent_world, neighbors[i], CURRENT);
            Dfs(neighbors[i]);	// 下一步
            if (find_gold || game_over) return;
        }
    }
    // 周围没有金子
    if (find_gold == false) {
        vector<Point> safe_place;
        for (int i = 0; i < neighbors.size(); ++i) {
            if (((agent_world[neighbors[i].xx][neighbors[i].yy] & SAFE) == SAFE)		// 安全
                && ((agent_world[neighbors[i].xx][neighbors[i].yy] & VISITED)  == 0)) { // 未访问
                safe_place.push_back(neighbors[i]);
            }
        }
        if (safe_place.size() > 0) {	// 存在安全区域
            int rand_next_pos = rand() % safe_place.size();	// 随机选择一个安全区域
            PutFlag(agent_world, safe_place[rand_next_pos], CURRENT);
            Dfs(safe_place[rand_next_pos]);	// 下一步
            if (find_gold || game_over) return;
        }else {		// 没有安全区域，寻找最近的安全地带
            Point nearest_safe_pos = { -1, -1 };	// 最近的安全点初始化
            for (int i = 0; i < ROW_NUM; ++i) {
                for (int j = 0; j < COL_NUM; ++j) {
                    if ((agent_world[i][j] & SAFE) == SAFE) {
                        if (nearest_safe_pos == Point{ -1, -1 })	// 第一个安全的点
                            nearest_safe_pos = { i, j };
                        else {
                            int dismin = Bfs(current, nearest_safe_pos, false); // 最近安全点距离
                            int discur = Bfs(current, Point{ i, j }, false);	// 当前安全点距离
                            if (discur < dismin) {	// 当前安全点更近
                                nearest_safe_pos = { i, j };	// 更新最近安全点
                            }
                        }
                    }
                }
            }
            // 机器人地图上有安全点
            if (nearest_safe_pos != Point{-1, -1}) {
                PutFlag(agent_world, nearest_safe_pos, CURRENT);
                Bfs(current, nearest_safe_pos, true);	// 记录行动路线
                Dfs(nearest_safe_pos);	// 下一步
                if (find_gold || game_over) return;
            }else {	// 没有安全点，选择一个相对安全的地点
                vector<Point> good_neighbor;
                for (int i = 0; i < neighbors.size(); ++i) {
                    if(((agent_world[neighbors[i].xx][neighbors[i].yy] & VISITED)  == 0)	// 未被访问
                        && ((agent_world[neighbors[i].xx][neighbors[i].yy] & CAVE) == 0)	// 没有陷阱
                        && ((agent_world[neighbors[i].xx][neighbors[i].yy] & WUMPUS) == 0)) // 没有怪兽
                        good_neighbor.push_back(neighbors[i]);
                }

                if (good_neighbor.size() > 0) {	// 有相对安全的点
                    int rand_next_goodpos = rand() % (good_neighbor.size());	// 随机选取一个相对安全的点
                    Dfs(good_neighbor[rand_next_goodpos]);	// 下一步
                    if (find_gold || game_over) return;
                }else {	// 没有相对安全的点，选择杀死怪兽
                    vector<Point> kill_pos, cave_pos;
                    for (int i = 0; i < neighbors.size(); ++i) {
                        if ((agent_world[neighbors[i].xx][neighbors[i].yy] & VISITED) == 0) // 未被访问过
                            if((agent_world[neighbors[i].xx][neighbors[i].yy] & WUMPUS) == WUMPUS) {	// 是怪兽
                            kill_pos.push_back(neighbors[i]);
                            }else {
                                cave_pos.push_back(neighbors[i]);
                            }
                    }
                    if (kill_pos.size() > 0) {	// 存在怪兽则杀死怪兽
                        int kill_wumpus = rand() % kill_pos.size();
                        vector<Point> wumpus_neighbors;
                        GetNeighborPosition(kill_pos[kill_wumpus], wumpus_neighbors);
                        agent_world[kill_pos[kill_wumpus].xx][kill_pos[kill_wumpus].yy] &= ~WUMPUS;// 取消怪兽标记
                        // 将杀死的怪兽周围的臭气标记取消
                        for (int i = 0; i < wumpus_neighbors.size(); ++i) {
                            agent_world[wumpus_neighbors[i].xx][wumpus_neighbors[i].yy] &= ~STENCH;
                        }
                        PutFlag(agent_world, kill_pos[kill_wumpus], CURRENT);
                        Dfs(kill_pos[kill_wumpus]);	// 下一步
                        if (find_gold || game_over) return;
                    }else if(cave_pos.size()){	// 没有怪兽只有陷阱
                        int jump_cave = rand() % cave_pos.size();
                        PutFlag(agent_world, cave_pos[jump_cave], CURRENT);
                        Dfs(cave_pos[jump_cave]);
                    }
                }
            }
        }
    }
}

int WumpusWorld::Bfs(Point src, Point tar, bool record)
{
    // 上下左右四个方向
    int Next[4][2] = { {0, 1}, {0, -1}, {-1, 0},{1, 0} };
    int steps = 0;
    map<Point, Point> bfs_path;
    bool flag = false;
    if ((agent_world[tar.xx][tar.yy] & VISITED) == 0) {
        agent_world[tar.xx][tar.yy] |= VISITED;
        flag = true;
    }

    queue<Point> Q;
    Q.push(src);
    bool vis[ROW_NUM][COL_NUM];	// 遍历标记
    memset(vis, false, sizeof(vis));
    vis[src.xx][src.yy] = true;
    while (!Q.empty()) {
        Point cur = Q.front();
        Q.pop();
        ++steps;
        if (cur == tar) {
            break;
        }
        for (int i = 0; i < 4; ++i) {
            int dx = cur.xx + Next[i][0];   // 下一个点的坐标
            int dy = cur.yy + Next[i][1];
            if (dx >= 0 && dx < ROW_NUM && dy >= 0 && dy < COL_NUM && ((agent_world[dx][dy] & VISITED) == VISITED )&& vis[dx][dy] == false) {
                if (record == true)	// 需要记录路径
                    bfs_path[Point{ dx,dy }] = cur;
                vis[dx][dy] = true;
                Q.push({ dx, dy });
            }
        }
    }
    if (record == true) {   // 需要记录则根据搜索路径找到搜索结果
        GetBfsPath(tar, src, tar, bfs_path);
    }
    if(flag) agent_world[tar.xx][tar.yy] &= ~VISITED;// 取消访问标记
    return steps;   // 返回最短路径长度
}

void WumpusWorld::GetBfsPath(Point cur, Point begPos, Point tar, map<Point, Point> bfs_path)
{
    if (cur == begPos) {
        return;
    }
    GetBfsPath(bfs_path[cur], begPos, tar, bfs_path);
    if(cur != tar) path_record[step_cnt++] = cur;
}

void WumpusWorld::ShowPath()
{
    Dfs(start);

    if (find_gold) {
        Bfs(gold_position[0], start, true);
        path_record[step_cnt++] = start;
    }
    for (int i = 0; i < step_cnt; ++i) {
        int pos_index = path_record[i].xx * ROW_NUM + path_record[i].yy;
        map_label[pos_index]->setStyleSheet("border-image:url(:/agent.png);");
        QTest::qWait(400);
        if((real_world[path_record[i].xx][path_record[i].yy] & CAVE) == CAVE){  // 当前点是陷阱
            map_label[pos_index]->setStyleSheet("border-image:url(:/deathagent.png);");
        }
        if(i != step_cnt - 1){
            map_label[pos_index]->setStyleSheet("border-image:url(:/grid.png);");
            score -= STEP_COST;
            if(path_record[i + 1] == start){    // 下个点是起点
                state->setStyleSheet("border-image:url(:/back.png);");
            }
            else if((real_world[path_record[i + 1].xx][path_record[i + 1].yy] & WUMPUS) == WUMPUS){  // 下一个点是怪兽
                score -= WUMPUS_COST;
                real_world[path_record[i + 1].xx][path_record[i + 1].yy] &= ~WUMPUS;
                state->setStyleSheet("border-image:url(:/kill.png);");
            }
            else if((real_world[path_record[i + 1].xx][path_record[i + 1].yy] & GOLD) == GOLD){ // 下一个点是金子
                score += GOLD_VALUE;
                state->setStyleSheet("border-image:url(:/findgold.png);");
            }
            else if((real_world[path_record[i + 1].xx][path_record[i + 1].yy] & CAVE) == CAVE){ // 下一个点是陷阱
                score -= DEATH_COST;
                state->setStyleSheet("border-image:url(:/death.png);");
            }
            else{
                state->setStyleSheet("border-image:url(:/move.png);");
            }
            score_get->setText(QString::number(score));
        }
        printf("(%d, %d)\t", path_record[i].xx, path_record[i].yy);
    }
}

void WumpusWorld::UpdateNeighborsInformation(Point current)
{
    vector<Point> neighbors;
    GetNeighborPosition(current, neighbors);
    int curx = current.xx, cury = current.yy;
    for (int i = 0; i < neighbors.size(); ++i) {
        int nx = neighbors[i].xx;
        int ny = neighbors[i].yy;
        if ((agent_world[nx][ny] & SAFE) == 0 && (agent_world[nx][ny] & VISITED) == 0) {	   // 不安全且未被访问
            if ((agent_world[curx][cury] & BREEZE) == BREEZE) {	// 有微风
                if ((agent_world[nx][ny] & CAVE_SUSPECT) == CAVE_SUSPECT) {
                    PutFlag(agent_world, neighbors[i], CAVE);
                }
                else {
                    PutFlag(agent_world, neighbors[i], CAVE_SUSPECT);
                }
            }

            if ((agent_world[curx][cury] & STENCH) == STENCH) {	// 有臭气
                if ((agent_world[nx][ny] & WUMPUS_SUSPECT) == WUMPUS_SUSPECT) {
                    PutFlag(agent_world, neighbors[i], WUMPUS);
                }
                else {
                    PutFlag(agent_world, neighbors[i], WUMPUS_SUSPECT);
                }
            }

            if ((agent_world[curx][cury] & GLITTER) == GLITTER) {	//有闪光
                if ((agent_world[nx][ny] & GOLD_SUSPECT) == GOLD_SUSPECT) {
                    PutFlag(agent_world, neighbors[i], GOLD);
                }
                else {
                    PutFlag(agent_world, neighbors[i], GOLD_SUSPECT);
                }
            }

            if (((agent_world[curx][cury] & BREEZE) == 0) && ((agent_world[curx][cury] & STENCH)== 0)) {	 // 没有微风和臭气则安全
                PutFlag(agent_world, neighbors[i], SAFE);
                // 删除其他非必要标记
                agent_world[nx][ny] &= ~CAVE_SUSPECT;
                agent_world[nx][ny] &= ~WUMPUS_SUSPECT;
                agent_world[nx][ny] &= ~CAVE;
                agent_world[nx][ny] &= ~WUMPUS;
            }
        }
    }
}

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

运行结果及分析

1、根据算法智能体每走一步都会更新信息，然后将周围点进行标记，这样的话被标记两次为怀疑陷阱的地方就会被标记为陷阱，被怀疑为怪兽两次的地方被标记为怪兽。
2、由于算法每次优先选取安全的点进行移动，有时候往往有更短的路线可以移动但是由于最短路线上有未知的没有到达的点所以导致了线路变长，扣分增多。
3、根据测试，在多数情况下智能体都可以避开陷阱和怪兽，至多杀死怪兽从而找到金子。但是在少数情况下由于金子的位置过于偏僻（比如被怪兽和陷阱所包围）的时候，智能体只能依靠随机的选择，这样死亡的概率大大增加。
4、联机搜索可以解决实时的问题，但是由于知道的信息随时更新，具有太强的随机性，所以有时候得到的解往往不那么理想。

使用说明

点击Game Start按钮，智能体开始移动。Score显示当前分数，State显示当前智能体的状态，一共有6个状态分别为：Waiting to start（等待游戏开始）；Move(智能体移动)；Find Gold!(找到金子)；DEATH(智能体掉入陷阱死亡)；KillMonster (智能体杀死怪兽)；BackHome(智能体找到金子后回到起始点)。

每次运行程序智能体只行走一次，当想要生成下一个WumpusWorld时需要关闭程序后重新运行就会生成新的地图，然后点击Game Start按钮。

完整项目文件下载

工程代码文件：
CSDN下载：https://download.csdn.net/download/qq_45364953/15164347

demo:
百度网盘：https://pan.baidu.com/s/1S-mlO7_pJ4oFsWHr_7MzXw
提取码：r4t6

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

学业课程学习

算法

使用联机搜索求解Wumpus World 的相关文章

  • mybatis复杂sql查询——多对一和一对多处理

    以学生表 Student 和教师表 Teacher 为例 其中tid为外键约束 多对一处理 按查询嵌套处理 相当于sql中的子查询 思路 1 查询所有的学生信息 2 根据查询出来的学生信息中的tid 查找教师信息 子查询 查询学生信息以及对

随机推荐

  • 660 48

    1 基础预备 渐近线分类和公式 2 求函数的定义域 注意1 x gt 2 的求法 当时就错了两次 3 按照公式 对正无穷 和 负无穷进行验证 另外 水平渐近线 与 斜渐近线 互斥 二者无法共存

  • 解决IDEA无法安装插件的问题

    进入2018年以来 在IDEA插件中心中 安装插件经常安装失败 报连接超时的错误 如下 我们发现连接IDEA的插件中心使用的是https的链接 我们在浏览器中使用https访问插件中心并不能访问 而使用普通的http是可以访问插件中心的 因

  • 监控系统平台服务器,服务器监控平台系统

    服务器监控平台系统 内容精选 换一换 监控是保持云耀云服务器可靠性 可用性和性能的重要部分 通过监控 用户可以观察云耀云服务器资源 为使用户更好地掌握自己的云耀云服务器运行状态 公有云平台提供了云监控 您可以使用该服务监控您的云耀云服务器

  • 解决No module named 'pymysql'问题

    我使用的是Anaconda3 在项目中导入pymysql时报错 说明没有安装pymysql 安装就可以了 使用 conda install pymysql 正常情况应该是这样 这就安装成功了 如果你出现了这种情况

  • python向Excel读取一行数据

    pandas 1 0之前读取是用的ix 后来改为iloc或者loc 如下 import pandas as pd df pd read excel 1 xlsx sheet name student 可以通过sheet name来指定读取的

  • runtime.h-Functions-Working with Classes (二)

    文章目录 Working with Classes 二 class getIvarLayout class getWeakIvarLayout class addMethod class replaceMethod class addIva

  • JDK8安装及系统变量配置（包含错误处理）

    jdk安装 一 下载JDK 二 安装 三 配置系统变量 四 可能遇到的问题 1 显示已经安装的问题 或者 读取注册表项值失败 2 原因 3 解决 五 验证安装成功 一 下载JDK JDK下载官网 二 安装 双击之后 一直下一步就ok 三 配

  • 【JAVA+oracle】数据库综合型实验----教务管理系统

    前言 这次实验用到了很久没写的javaswing 其中各种组件的使用可谓是花了一番工夫复习 其中遇到最大的问题是如何将java和oracle进行连接 这个问题搞了我一个晚上 一开始用的是eclipse 代码是没问题的 死活连不上 第二天把代

  • springboot当中配置mybatis分页插件

    这篇文章主要介绍了spring boot集成pagehelper 记录使用pagehelper的两种配置方式 目录 一 直接使用pagehelper 1 导入依赖 2 配置pagehelper 3 代码写法 二 使用pagehelper s

  • GPT2训练自己的对话问答机器人

    GPT2训练自己的对话问答机器人 1 环境搭建 2 理论研究 3 模型训练与测试 3 1语料tokenize 3 2用GPT2训练数据 3 3人机交互 4 效果展示 1 环境搭建 这里我搭建了虚拟的3 6环境 conda create n

  • 学会搭建小程序生鲜商城，开启生鲜电商新模式

    电商平台的出现 为人们带来了极大的便利 然而 传统的电商平台已经不能满足消费者对于购物体验的要求 如今 小程序生鲜商城因其轻量化 高效率等特点 成为了众多卖家的首选 本文将介绍如何学会搭建小程序生鲜商城 并以一个实际案例作为例子 解析运用技

  • python控制台输入、输出

    python控制台输入 输出 上一篇文章 python 注释 变量 类型 下一篇文章 Python运算符 比较 逻辑运算符 1 输出 简单输出 print 我是简单的字符串输出 控制台运行结果 我是简单的字符串输出 格式化输出 age 18

  • jenkins shell脚本执行权限不够解决办法

    自己服务器搭建jenkins执行操作的时候 没有相应的权限 解决这个问题的时候 做了一些笔记分享给大家 1 查看jenkins默认用户 vi etc sysconfig jenkins 复制代码 找到JENKINS USER发现默认用户je

  • JDBC入门

    JDBC基础部分 问题一 JDBC是什么 为什么会存在JDBC 作用是什么 JDBC Java DataBase Connection 是用于跟数据库进行交互的 由JDK统一提供 可以为多种关系型数据库提供统一的标准 但是是各大厂商进行实例

  • 亚信科技AntDB数据库携“U8C+AntDB联合产品”亮相“2023全球商业创新大会”，开启生态合作新篇章

    8月18 19日 近万人齐聚上海国家会展中心 带着对数字化 数智化趋势和热点的关注 以满腹热情投身到以 数据驱动 智能运营 为主题的 2023全球商业创新大会 共商新技术条件下企业信息化出现的新课题 新挑战 共享数智化升级创新成果 亚信科技

  • 【Python】TXT文本文件转换成JSON格式

    主要分为两个部分 1 txtToJson 函数读取指定路径下的所有文件 转换成如下格式 name1 content1 name2 content2 2 saveInJsonFile 函数将处理好的json格式数据和保存的文件路径作为函数参数

  • Android数据加密之MD5加密

    一 前言 项目中无论是密码的存储或者说判断文件是否是同一文件 都会用到MD5算法 今天来总结一下MD5加密算法 二 什么是MD5加密 MD5英文全称 Message Digest Algorithm 5 翻译过来是 消息摘要算法5 由MD2

  • c语言结构体变量所占字节计算,【C语言】结构体占用字节数及存储与空间分配...

    我们都知道在数据类型中 char类型占1个字节 short占2个字节 int占4个字节 long占8个字节等等 在计算结构体大小时需要考虑其内存布局 结构体在内存中存放是按单元存放的 每个单元多大取决于结构体中最大基本类型的大小 下面我们看

  • 网络工程师常用的命令整理-windows版，还不快收藏起来

    一 ping命令 1 ping ping是最常用的实用程序之一 用来确定网络的连通性 ping是个使用频率极高的实用程序 主要用于确定网络的连通性pi 如果ping通一个地址 那么基本可以排除物理层数据链路层的故障等 ping 的命令格式通

  • 使用联机搜索求解Wumpus World

    使用 JavaScript 重写的算法网页 https yuqingxiong github io Wumpus World Problem github仓库地址 https github com YuqingXiong Wumpus Wo

热门标签