想要实现的效果

给一个无限大小的矩阵(没有大小限制),给一个在这个矩阵范围内的起始位置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. 最后发现,有的障碍能绕过有的绕不过,最后死循环,因为一直在前进没有后退

研究第二天(失败)

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

但是随着测我发现一个问题, 在一定的条件下会将自己堵死,我仔细跟了下代码,发现是因为我之前做了一个不允许走重复的路线,也就是进去了出不来了

研究第三天(失败)

我昨天晚上在床上想了想怎么解决这被自己堵死了问题头疼...... ,然后我想了想自己如果在迷宫中走到一个墙角后,应该怎么办,当然是重走啊,将之前走过的路都清除,然后记录当前死路的位置,然后行走的过程中就绕过这个位置

然后感觉万事大吉了,基本上所有的任意障碍,我都能绕过去了最后到达终点, 然后我把路都堵死看看会出现啥效果

发现栈溢出了真nice,然后今天研究又失败了睡觉,明天在说

研究第四天(成功)

我晚上在床上想了想,怎么能判断,是绝路呢,没有任何路可以走呢? ......头更疼了, 想啊想,如果死路被我们绕过去了,那么肯定还会遇到新的死路,等全部的路都变为死路,那么肯定就会出现重复死路的现象,如果这个现象超过了2次那么是不是就可以认为是绝路了呢? ,灵感刚出来就赶紧去写了代码,然后运行发现真的是这样的呢?

但是我发现一个问题,很多时候如果障碍很多并且密级的话,需要将所有可能性都走,才能找到出路,几乎是穷举大部分的节点了,还携带一定的运气成分,并且如果矩阵很大,找到方向不对,那么需要试错很多次才能将正确的路径试出来,这样效率不高,如果在矩阵特别大的情况下这将是灾难 …,那么能不能有更好的方式呢?

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

研究第五天(提升效率)

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

当扩大后就能从可行走的路中找到从起始到终点的路径

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

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