Java-矩阵(自动导航-越过障碍)

深藏阁楼爱情的钟 2023-10-02 19:55 8阅读 0赞

### 想要实现的效果 ###

给一个无限大小的矩阵(没有大小限制),给一个在这个矩阵范围内的起始位置x,y 和结束位置x,y, 然后在给出了所有障碍的x,y标记点, ,然后从起始位置自动导航到终点 .

**注意:**

1.  不携带任何权重和距离, 只计算`起始x,y`和`终点的x,y` ,以及多个`障碍的x,y`
2.  障碍是随机的可以在运动过程中实时添加和减少的,而无数个障碍的x,y是可以绘制成任意形状的平面图的
3.  终点是可以随时移动的

**提示:** 想要导航,最核心的需要依据物体的8个方向进行尝试前进(东,南,西,北,东北,西北,西北,西南),然后根据一定的可能性和算法进行推算路径

//八个方向
        public static Map<String, int[]> map = new HashMap() {
        {
        
            put("东", new int[]{
        0, 1});  //右
            put("西", new int[]{
        0, -1}); //左
            put("北", new int[]{
        -1, 0}); //上
            put("南", new int[]{
        1, 0}); //下
            put("东北", new int[]{
        -1, 1}); //上右
            put("西北", new int[]{
        -1, -1}); //上左
            put("东南", new int[]{
        1, 1}); //下右
            put("西南", new int[]{
        1, -1}); //下左
        }};

### 研究第一天(失败) ###

1.  先写了最优路径,每次移动一步,然后成功到终点
2.  之后尝试添加障碍,编写代码遇到障碍自动改变方向
3.  以目标临近的4个方向(随机),尝试绕过障碍
4.  最后发现,有的障碍能绕过有的绕不过,最后死循环,因为一直在前进没有后退

![在这里插入图片描述][c6f1cd9116a54b878fbc736943a8c466.png]

### 研究第二天(失败) ###

我昨天晚上睡觉的时候想了想失败的原因,是因为每次只走一步而且只是目标的4个方向,那么在障碍将自己围住的时候会死循环,然后在第一天的代码基础上进行扩展,先进行了最优路径的前进,如果遇到障碍那么就进行8个方向随机前进,并且防止重复走相同的路径,当越过障碍重新尝试最优路径前进

![在这里插入图片描述][ed5c7110e01d4b949906049dc141e710.png]  
但是随着测我发现一个问题, 在一定的条件下会将自己堵死,我仔细跟了下代码,发现是因为我之前做了一个不允许走重复的路线,也就是进去了出不来了  
![在这里插入图片描述][2803c207e164473bb2439917d95c9a09.png]

### 研究第三天(失败) ###

我昨天晚上在床上想了想怎么解决这被自己堵死了问题`头疼......` ,然后我想了想自己如果在迷宫中走到一个墙角后,应该怎么办,当然是重走啊,将之前走过的路都清除,然后记录当前死路的位置,然后行走的过程中就绕过这个位置  
![在这里插入图片描述][968a2671f40e4a919e9a4a12059b7430.png]  
然后感觉万事大吉了,基本上所有的任意障碍,我都能绕过去了最后到达终点, 然后我把路都堵死看看会出现啥效果  
![在这里插入图片描述][e77c8252daa644c28849aad2e3ff352a.png]  
发现**栈溢出了真nice**,然后今天研究又失败了睡觉,明天在说

### 研究第四天(成功) ###

我晚上在床上想了想,怎么能判断,是绝路呢,没有任何路可以走呢? `......头更疼了`, 想啊想,如果死路被我们绕过去了,那么肯定还会遇到新的死路,等全部的路都变为死路,那么肯定就会出现重复死路的现象,如果这个现象超过了2次那么是不是就可以认为是绝路了呢? ,灵感刚出来就赶紧去写了代码,然后运行发现真的是这样的呢?  
![在这里插入图片描述][a61f23dc359b406a9a92c4d6fab6c45c.png]但是我发现一个问题,很多时候如果障碍很多并且密集的话,需要将所有可能性都走完,才能找到出路,几乎是穷举大部分的节点了,还携带一定的运气成分,并且如果矩阵很大,找到方向不对,那么需要试错很多次才能将正确的路径试出来,这样效率不高,如果在矩阵特别大的情况下这将是灾难 …,那么能不能有更好的方式呢?

感觉写着写着就脱离了基础算法了然后在各种算法原理上改造,之后穿插其他的算法去结合才能完成想要的效果,写着写着感觉`根AI一样了凸(艹皿艹 )`给计算机下达指令通过算法让计算机自己去探索和发现,在这个过程中都是未知的,而我们只是给他加了一些限定条件,保证大体上没有问题就行,后面的就交给计算机自己去试错不断的调整自己,最后完成目标

### 研究第五天(提升效率) ###

昨天晚上在床上想了想,我能不能给他做一个界限,让它在界限范围内先自行寻找,当界限都找完了,那么我们在扩大界限1.2倍,已走过的路不会重复在走,这样可以有效防止脱离正确路线太远了需要大量的尝试才能回来.

![在这里插入图片描述][99a18f9673c14124b109a5b46c0b0da8.png]当扩大后就能从可行走的路中找到从起始到终点的路径

![在这里插入图片描述][8cd7d667044c4a0c99ea34c741d28c97.png]

待更新..........................

![在这里插入图片描述][e2af4607da624cff9e7bf546663eaa91.gif]

点赞 -收藏-关注-便于以后复习和收到最新内容有其他问题在评论区讨论-或者私信我-收到会在第一时间回复如有侵权，请私信联系我感谢,配合,希望我的努力对你有帮助^\_^

![ceaefc422a4745479fc1e8cfd2bdb74e.jpg][]

[c6f1cd9116a54b878fbc736943a8c466.png]: https://img-blog.csdnimg.cn/c6f1cd9116a54b878fbc736943a8c466.png
[ed5c7110e01d4b949906049dc141e710.png]: https://img-blog.csdnimg.cn/ed5c7110e01d4b949906049dc141e710.png
[2803c207e164473bb2439917d95c9a09.png]: https://img-blog.csdnimg.cn/2803c207e164473bb2439917d95c9a09.png
[968a2671f40e4a919e9a4a12059b7430.png]: https://img-blog.csdnimg.cn/968a2671f40e4a919e9a4a12059b7430.png
[e77c8252daa644c28849aad2e3ff352a.png]: https://img-blog.csdnimg.cn/e77c8252daa644c28849aad2e3ff352a.png
[a61f23dc359b406a9a92c4d6fab6c45c.png]: https://img-blog.csdnimg.cn/a61f23dc359b406a9a92c4d6fab6c45c.png
[99a18f9673c14124b109a5b46c0b0da8.png]: https://img-blog.csdnimg.cn/99a18f9673c14124b109a5b46c0b0da8.png
[8cd7d667044c4a0c99ea34c741d28c97.png]: https://img-blog.csdnimg.cn/8cd7d667044c4a0c99ea34c741d28c97.png
[e2af4607da624cff9e7bf546663eaa91.gif]: https://img-blog.csdnimg.cn/e2af4607da624cff9e7bf546663eaa91.gif
[ceaefc422a4745479fc1e8cfd2bdb74e.jpg]: https://img-blog.csdnimg.cn/ceaefc422a4745479fc1e8cfd2bdb74e.jpg