大白话快速理解导航算法：gossip路径规划算法

先看一张图，该图又叫老鼠走迷宫的算法。

简单分析一下就是事先有一个迷宫的模型这个模型使用二维矩阵模拟，然后告诉老鼠入口和出口的位置，程序会自己

尝试路径的走法，直到走出去。

老鼠走迷宫一 
说明：
老鼠走迷宫是递回求解的基本题型，我们在二维阵列中使用2表示迷宫墙壁，使用1表示老鼠行走的路径，试以程
式求出由入口至出口的路径。

解法：
老鼠的走法有上，下，左，右四个方向，在每前进一格之后就选一个方向前进，无法前进时退回选择下一个可前
进方向，如此在阵列中依序测试四个方向，知道走到出口为至，这是返回的基本题，请直接看程式应就可以理解 

#include <stdio.h>
#include <stdlib.h>
int visit(int, int);
int maze[9][9] = {
{2, 2, 2, 0, 0, 0, 2, 2, 2},
{2, 0, 0, 0, 2, 0, 2, 2, 2},
{2, 0, 2, 0, 2, 0, 2, 2, 2},
{2, 0, 0, 2, 2, 0, 2, 2, 2},
{2, 2, 0, 2, 0, 0, 0, 0, 2},
{2, 0, 0, 2, 0, 0, 2, 0, 2},
{2, 2, 0, 2, 2, 2, 2, 0, 2},
{2, 0, 0, 0, 0, 0, 2, 0, 0},
{2, 2, 2, 2, 2, 2, 2, 2, 0}};
int startI = 1, startJ = 1; // 入口
int endI = 8, endJ = 8; // 出口
int success = 0;
int main(void) {
    int i, j;
    printf("显示迷宫：\n");
    for(i = 0; i < 9; i++) {
        for(j = 0; j < 9; j++)
        if(maze[i][j] == 2)
        printf("█");
        else
        printf(" ");
        printf("\n");
    }
if(visit(startI, startJ) == 0)
printf("\n没有找到出口！\n");
else {
printf("\n显示路径：\n");
for(i = 0; i < 9; i++) {
for(j = 0; j < 9; j++) {
if(maze[i][j] == 2)
printf("█");
else if(maze[i][j] == 1)
printf(">");
else
printf(" ");
}
printf("\n");
}
}
return 0;
}
int visit(int i, int j) {
maze[i][j] = 1;

if(i == endI && j == endJ)success = 1;
if(success != 1 && maze[i][j+1] == 0) {
  visit(i, j+1);
}

if(success != 1 && maze[i+1][j] == 0){
    visit(i+1, j);
}

if(success != 1 && maze[i][j-1] == 0){

    visit(i, j-1);
}

if(success != 1 && maze[i-1][j] == 0){

    visit(i-1, j);
}
if(success != 1)maze[i][j] = 0;
return success;
}

这里我们建立一个9x9的二维矩阵，其中2代表墙面，0代表路，程序里会先尝试往右走直到走到头，然后再往下走直到碰到墙。走过的路会将

矩阵的值变成1，代表老鼠已经尝试过，如果下走也遇到墙，则往回走，发现已经走过了，再往上走，直到4个方向都试过为一个回合，遇到墙就

会四面八方去尝试，直到走出去。最后把成功的路径画出来。

当然如果没有出口，也会告诉你没有没有合适的路径。

所以此模型的前提是知道迷宫的map,也就是建图的map.将map变成二维矩阵和距离值。

然后告诉底盘小车前进的距离，如果小车行驶无偏差，理想模型，即使不用雷达，只用里程计也是可以将路径规划出来的。

现实当中该如何建模呢？

如果我们所居住的屋子为9X9=81平米的房子。我们用软件或者手动编写一个矩阵，这个矩阵为9x9时，则代表每一个元素之间的距离为1米，

那么精度就是1米，如果矩阵为90x90 则每个单位之间的距离为1分米。我们就做个9x9的矩阵，

int maze[9][9] = {
{2, 0, 2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 0},
{2, 0, 0, 0, 0, 0, 0, 0, 0},
{2, 2, 2, 2, 2, 2, 2, 2, 2}};
上边的为两居室入口，右下边的为厨房入口，

假设我们让小车从厨房门口带一把杀猪刀运到厨房去，小车的路径会经过客厅然后到厨房。这个时候的路径规划通过gossip算法便可得知。

先向右走2米，再向下走3米，然后再向右走4米，再下走2米，再向右走1米，再向下走1米就到位置了，这就是路径规划，理想情况下只要下车能走出

90度的角度，加1米的精确位移。这个导航就不是问题了哈哈。

链接：https://pan.baidu.com/s/1yqG6UYm7lNYcdOoMyFxaLw 
提取码：rtqt 
复制这段内容后打开百度网盘手机App，操作更方便哦