Python course design

Many self circumvention wandering algorithms were searched before the course design, but the author's level and strength were limited, and he had some ideas at that time. Therefore, this paper mainly records the author's ideas. The program is relatively simple, so it should not be difficult to understand. I hope to have some inspiration for the students learning self circumvention algorithms, If there are mistakes, please correct them.

Experimental topic

Title: (using turtle simulation: self avoiding random walk)
(a) Self avoiding walk in a grid is a path from one point to another, and this path will not pass through the same point twice. Self avoiding walk has many applications in physics, chemistry and mathematics. It can be used to simulate chain entities, such as solvents and high molecular polymers. Write a Turtle program to display a random path from the center Point starts at a point on the boundary and ends at a point. Or end at the dead point (that is, the point is surrounded by four other points that have passed). Suppose that the size of this grid is 16 * 16.
(b) Then write a simulation program to show that with the expansion of the grid size, the probability of the path ending at the dead point will increase. The program simulates the change of the network size from 10 to 50. For each grid size, simulate 10000 self avoidance walks, and then display the probability of ending at the dead point. The output is as follows.
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%

1. General

Firstly, I analyze the requirements. According to the topic, I judge that there should be a grid first. Secondly, I realize random walk on the basis of the grid, and then avoid the previous grid through the algorithm. Therefore, I use coordinates and arrays. Generally speaking, it is a bit like the restriction of greedy snake. It can't hit the wall or itself, but it is relatively simple. Therefore, there is no reference to the algorithm of greedy snake, but it is simply mentioned in the notes. Snake's code CSDN has been written by many big guys, and I won't elaborate here.

2. Algorithm description

The evasion algorithm is mainly divided into three parts: first, it is necessary to make sure that you will not turn back when you walk at will. Second, it is necessary to make sure that this step is the lattice you have passed before, and then return to the previous lattice at a random step. Judge whether it is at the dead point at this time. If it is at the dead point, it will end. Three functions are defined. The turn function determines which direction to move forward and the drawing of the graph. A fixed direction is used to determine the coordinates. The main parameters are randomly varying self and self_avoid_xy realizes the determination of coordinates based on the original coordinates. The new coordinates are self_ avoid_ Positions implements adding the original coordinates into the array positions to store the path and judge whether the new coordinates are in the original coordinate array for self avoiding random walk. The above methods are to facilitate the function of custom random walk algorithm. The main idea of custom random walk is to determine the random walk in one direction first, and then limit the sept, Make it impossible for him to turn back, go to the point he has passed, store the previous random sept with the last variable, and then a random sept, If the turning back condition is satisfied (last == 0 and sept == 3 or last == 3 and sept == 0 or last == 1 and sept == 2 or last == 2 and sept == 1), the drawing will not be carried out for the next group. If the wall collision condition is satisfied (m == 400 or m == -400 or n == 400 or n == -400), the program will be bound. If this step is satisfied, it is a node that has gone (bool = list in positions, bool == True), return the coordinates to the previous state, and then proceed to the next group. When the coordinates pass through three adjacent points, the program will automatically stop.

Upper code (part of the comment code is used for debugging)

import random
import turtle
import numpy as np

#function
def turn(sept):
    if sept == 0:
        turtle.seth(0)
        turtle.pendown()
        turtle.forward(50)
    elif sept == 1:
        turtle.seth(90)
        turtle.pendown()
        turtle.forward(50)
    elif sept == 2:
        turtle.seth(-90)
        turtle.pendown()
        turtle.forward(50)
    else:
        turtle.seth(180)
        turtle.pendown()
        turtle.forward(50)

def self_avoid_xy(sept, m, n):

    if sept == 0:
        m = m + 50
    elif sept == 1:
        n = n + 50
    elif sept == 2:
        n = n - 50
    else:
        m = m - 50
    return m, n

def self_avoid_postions(postions, x, y, num):
    postions.insert(num, [x, y])
    return postions

#Table section
turtle.setup(900, 850, 0, 0)
y = 400
x = -400
turtle.penup()
turtle.speed("fastest")
turtle.pensize(5)
turtle.pencolor("yellow")
turtle.goto(-400, 400)
for i in range(17):

    turtle.pendown()
    turtle.forward(800)
    turtle.penup()
    y = y-50
    turtle.goto(-400, y)
turtle.penup()
turtle.right(90)
turtle.goto(-400, 400)
for i in range(17):

    turtle.pendown()
    turtle.forward(800)
    turtle.penup()
    x = x+50
    turtle.goto(x, 400)
turtle.penup()


#Snake part
turtle.goto(0, 0)
turtle.color("black")
turtle.speed(5)
turtle.home()
sept = 0
m = 0
n = 0
avoid = -1
postions = [[0, 0]]
num = 0
for i in range(100):
    #print("next group")
    last = sept
    sept = random.randint(0,  3)
    #print(last, sept)
    if last == 0 and sept == 3 or last == 3 and sept == 0 or last == 1 and sept == 2 or last == 2 and sept == 1:#Avoid looking back
        sept = last
        continue
    else:
        m, n = self_avoid_xy(sept, m, n)
        #print(m, n)
        #print(postions)
        if m == 400 or m == -400 or n == 400 or n == -400:
            print("gameover")
            turn(sept)
            break
        else:
            list = [m, n]
            #print(list)
            #print(list in postions)
            bool = list in postions
            if bool == True:
                #print(sept)
                if sept == 0:
                    m = m - 50
                elif sept == 1:
                    n = n - 50
                elif sept == 2:
                    n = n + 50
                else:
                    m = m + 50
                sept = last
                #print("true")
                #avoid = sept
                #print(avoid)
                continue
            else:
                #print("group i", i)
                #print(last)
                #print(sept)

                #if avoid == sept:
                 #   sept = last
                 #   num = num + 1
                 #   continue
                #else:
                #print("I drew it")
                avoid = avoid + 1
                turn(sept)
                num = num + 1
                count = i-avoid
                #count = count/i
                print("For lattice of size ", i, "the probability of dead-end paths is")
                print(count, "%")
            #print("I let go")
            postions = self_avoid_postions(postions, m, n, num)

turtle.done()

result

reference resources

Csdn:python learning notes (III) - the use of turtle Library
Python test instruction (2020-06-08)