在做这次课设之前搜索了很多自规避游走的算法，但是作者水平及实力有限，并且当时有一些自己的想法，因此本文主要是对作者的想法进行一个记录，程序相对简单，因此理解起来应该没什么困难，希望对接下来学习自规避算法的同学有一些启发，如果有错误也请各位大佬指正。

题目：（使用turtle仿真：自我规避随机游走） （a）在一个网格中的自我规避游走是一条从一点到另一点的路径，并且这条路径不会经过同一个点两次。自我规避游走在物理、化学和数学中有很多的应用。它可以用来模拟链状实体，例如溶剂和高分子聚合物。编写一个Turtle程序显示一条随机路径，该路径从中心点开始在边界上的某点结束。或者在死点处结束（即该点被其他已经经过的4个点包围）。假设这个网格的大小是16*16。 （b）再编写一个仿真程序来显示随着网格大小的扩大，路径在死点结束的概率将会提高。程序模拟网络大小从10变化到50。对于每一种网格大小，仿真10000次自我规避游走然后显示在死点结束的概率，输出如下所示。 For lattice of size 10, the probability of dead-end paths is 10.57% For lattice of size 11, the probability of dead-end paths is 14.09% …… For lattice of size 49, the probability of dead-end paths is 94.22% For lattice of size 50, the probability of dead-end paths is 94.33%

首先进行需求分析，根据题目我判断大体上首先要有网格，其次在网格的基础上实现随机游走，之后通过算法规避以前所走的格子，因此我用了坐标以及数组。总体来说有点像贪吃蛇的限制，撞墙及撞自身都不行，但相对来说还是比较简单的，因此并没有参考贪吃蛇的算法仅仅是在注释中简单提了一下。贪吃蛇的代码CSDN中有很多大佬都写过，在此也不再细说。

规避算法主要分为三部分：首先要确定在随意游走时不会回头，其次是确定在这一步是以前走过的格子后退回之前的格子在随机一步，在次判断是否在死点处，若在死点处则结束。定义了三个函数，turn函数确定了之后朝哪个方向前进和图形的绘制，采用了固定的方向以便进行坐标的确定，主要参数是随机变化的sept，self_avoid_xy实现了坐标的在原坐标基础上的确定新坐标，self_avoid_postions实现的是将原坐标加进数组postions中来储存路径和判断新的坐标是否在原坐标数组中以便进行自避免随机游走，以上方法都是为了方便自定义随机游走算法的函数，自定义随机游走的正题思路是先确定一个方向的随机游走，之后再对sept进行限制，使他不能进行回头，走到已走过的点，用last变量储存之前随机的sept，之后随机一个sept，若满足回头情况（last == 0 and sept == 3 or last == 3 and sept == 0 or last == 1 and sept == 2 or last == 2 and sept == 1）则不进行画图进行下一组，若满足撞墙情况（m == 400 or m == -400 or n == 400 or n == -400），则程序结束，若满足该步是已走节点（bool = list in postions ，bool == True），则将坐标退回到前一个状态然后进行下一组，当坐标相邻三点都走过则程序自动停止。

Csdn:python 学习笔记（三）—turtle库的使用 Python试验指导书（2020-06-08）