首次实现算法——自动寻路算法和扫地机器人算法

通过一周的努力,终于完成了这个算法 https://github.com/myth984/findWay

自动寻路算法:

起点通过试探的方式到达终点。

原理:

让计算机像人一样进行尝试道路是不是可以到达终点。于是我写了一个随机生成地图的类,基于boolean型的二维数组。模拟人在地图中试探的行动。

遇到问题:

地图数据与预想结果不一样,x、y轴混乱

解决方案

二维数组与我们经常用的数轴是不一样的,我想当然的以为 new boolean[height][width] 但实际上如果用二维数组来表达平面的话x,y是反的,应该写为new boolean[width][height]

遇到问题:

写了一个探索类,通过上下左右四方向来判断下一个点是否是可达,如果可达则进入该店,并记录下路径。人会陷入死循环,如 上下点皆为true 人的路线将会是上下上下上下上下....,

解决方案:

有考虑到通过查询记录来判断上一次的行动方向来进行判断,是否进行下一步方向,但是考虑到系统资源问题,我定义了一个全局变量来记录上一次行动方向,这样如果上次行走的方向是上,这次 的方向必须除了下的方向。避免了反复行动,节约了系统资源。

遇到问题:

如果进入死胡同则进行退回上一步操作,退回了上一步,还会进行上一步的下一步操作,造成死循环。

解决方案:

根据当前点的位置和上一步的位置,判断行动方向,避免造车死循环

遇到问题:

退回上一步不进入其他可达路。

解决方案:

因为考虑到不能破坏成功记录,我写了一个记录退回上一步的点的集合,也就是删掉点的结合,这样在退回上一步时,判断一下这个点之前是否被删掉过,如果第一次被删掉则退回上一步,如果被删掉一次说明会造成死循环,则再删掉当前点。

扫地机器人算法:

遍历所有从起点可达的点(扫除地面所有可以扫除的垃圾)

原理:

首先分析起点的四个方向上下左右的点是否可达(是否为true),如果是可达的话,进行记录。然后再对可达点进行递归分析(和起点的分析方式一样)。 如果遇到了终点,则说明该地图可以到达终点,并遍历了所有可达点。

遇到问题:

可达点重复加入集合

解决方案:

虽然Set集合不能加入相同元素,但是每一个点都是new出来的,在内存有各自的内存空间。我就重写了equal方法,不计算hashcode,通过逐个字段比较来确定两个对象是否相等。每次加入新元素的时候都进行一次equal在决定是否加入该元素。

收获:

  1. 收获匪浅,让自己的简历更突出了,有了更强的竞争力。
  2. 在写代码的时候尝试了用vi,并熟悉了vi的操作。
  3. 遇到了问题不要考虑首先如何解决问题,先考虑是不是方向上的问题,别白作功。
  4. 在编程技术上的掌握更是突飞猛进。

另外发现,我自己写的博客系统的登录session储存时间太短,文章还没写完就过期了,下一版本延迟session时间。

0 评论