游戏主程序分析

发表于 分类于

介绍

游戏规则：

  1. 如果一个cell周围(以它为中心3x3)有2或3个其他cell则存活，否则死亡
  2. 如果一个无cell的方格周围有3个cell，则在此生长出一个cell

Version 0

介绍

  1. 以cell list为基础遍历整个2-D list，计算每个rectangle周围cell数量并判断是否需要change color，如是则cell.change标记true
  2. 再次遍历list，switch cell.change为true的rectangle

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#check cell's next state by its neighbors (3 neighbors born, 2 and 3 neighbors survival)
def check_state(cell,row,column):
    global cell_list
    global row_max
    global column_max
    cell_num=0

    for i in range(-1,2):
        if row+i<0 or row+i>row_max-1: #out of range
            continue
        else:
            for j in range(-1,2):
                if column+j<0 or column+j>column_max-1: #out of range
                    continue
                else:
                    if cell_list[row+i][column+j].liveCell: #live cell
                        cell_num=cell_num+1

    if cell.liveCell: #live cell
        cell_num=cell_num-1 #remove itself
        if cell_num==2 or cell_num==3: #survive
            pass
        else:
            cell.change=True
            #print("change "+str(row)+" "+str(column)+str(cell_num))
    else: #no cell
        if cell_num==3: #new cell
            cell.change=True
            #print("change "+str(row)+" "+str(column))

#command of start button, start the game in each 1s
def start_game(count):
    global beginning

    if beginning: #start sign
        global cell_list
        global row_max
        global column_max

        for row in range(row_max):
            for column in range(column_max):
                check_state(cell_list[row][column],row,column)

        for row in range(row_max):
            for column in range(column_max):
                if cell_list[row][column].change: #need be changed
                    cell_list[row][column].switch_color()

        if count==0:
            root.destroy()

        #run start_button again after 100ms
        root.after(100,start_game,count) #caution: start_button has no returns hence no () in needed here (or recursion error happens)
    else: #get stop sign
        pass

效率

@profile start_game(count)
Total time: 8.20841 s

Hits Time Per Hit % Time Line Contents
101 593.8 5.9 0.0 if beginning: #start sign
5252 2155.9 0.4 0.0 for row in range(row_max):
597516 187218.2 0.3 2.3 for column in range(column_max):
592365 7321122.0 12.4 89.2 check_state(cell_list[row][column],row,column)
5252 1487.2 0.3 0.0 for row in range(row_max):
597516 176765.3 0.3 2.2 for column in range(column_max):
592365 266698.4 0.5 3.2 if cell_list[row][column].change: #need be changed
12985 238116.0 18.3 2.9 cell_list[row][column].switch_color()
101 39.1 0.4 0.0 if count==0:
1 10066.3 10066.3 0.1 root.destroy()
101 4152.7 41.1 0.1 root.after(100,start_game,count-1) #caution: start_button has no returns hence no () in needed here (or recursion error happens)

查找neighbors占总时间89.2%感觉可以优化，有太多无效查找。

Version 1

介绍

  1. 基于cell_list遍历list，找出所有cell.liveCell为True的cell并使它周围rectangle的cell.neighbor +1
  2. 再次遍历，找出需要change的cell并直接调用cell.switch()覆盖改变

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#mark cell's neighbor numbers
def find_neighbor(cell,row,column):
    if cell.liveCell: #live cell
        global cell_list
        global row_max
        global column_max

        for i in range(-1,2):
            if row+i<0 or row+i>row_max-1: #out of range
                continue
            else:
                for j in range(-1,2):
                    if column+j<0 or column+j>column_max-1: #out of range
                        continue
                    else:
                       cell_list[row+i][column+j].neighbor+=1
        
        cell.neighbor-=1 #multi added

    else: #no cell
        pass

#check cell state. 3 neighbors born, 2 and 3 neighbors survival
def check_state(cell):
    neighbors=cell.neighbor #get neighbor number

    if cell.liveCell:
        if neighbors !=2 and neighbors !=3: #dead
            cell.switch_color()
    else:
        if neighbors == 3: #born
            cell.switch_color()

    cell.neighbor=0 #init

#command of start button, start the game in each 1s
def start_game(count):
    global beginning

    if beginning: #start sign
        global cell_list
        global row_max
        global column_max

        for row in range(row_max):
            for column in range(column_max):
                find_neighbor(cell_list[row][column],row,column)

        for row in range(row_max):
            for column in range(column_max):
                check_state(cell_list[row][column])

        if count==0:
            root.destroy()

        #run start_button again after 100ms
        root.after(100,start_game,count) #caution: start_button has no returns hence no () in needed here (or recursion error happens)
    else: #get stop sign
        pass

效率

@profile start_game(count)
Total time: 2.48149 s

Hits Time Per Hit % Time Line Contents
101 551.8 5.5 0.0 if beginning: #start sign
5252 2651.8 0.5 0.1 for row in range(row_max):
597516 242416.2 0.4 9.8 for column in range(column_max):
592365 1028903.5 1.7 41.5 find_neighbor(cell_list[row][column],row,column)
5252 1716.3 0.3 0.1 for row in range(row_max):
597516 196414.3 0.3 7.9 for column in range(column_max):
592365 993903.4 1.7 40.1 check_state(cell_list[row][column])
101 41.0 0.4 0.0 if count==0:
1 10520.8 10520.8 0.4 root.destroy()
101 4375.6 43.3 0.2 root.after(100,start_game,count-1) #caution: start_button has no returns hence no () in needed here (or recursion error happens)

时间缩短70%，优化成功。之后尝试缩短check_state里查找目标cell用时，如建立一个list储存neighbors为3的rectangle，和liveCell的坐标以减小无效查找。

Version 2

介绍

  1. 在left click operation时更新liveCell_list，start loop
  2. 根据liveCell_list精准找到live cell并使周围cell.neighbor+1，记录cell.neighbor=3的无生命cell到newBorn_list
  3. 分析liveCell_list里cell的cell.neighbor，去除neighbor不为2和3的cell，更新cell state
  4. 记录更新newBorn_list的cell state
  5. 合并liveCell_list和newBorn_list，清空newBorn_list和cell.neighbor

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#mark cell's neighbor numbers by liveCell_list, and build newBorn_list
def find_neighbor():
    global cell_list
    global newBorn_list
    global liveCell_list

    global row_max
    global column_max

    for [row,column] in liveCell_list:
        for i in range(-1,2):
            if row+i<0 or row+i>row_max-1: #out of range
                continue
            else:
                for j in range(-1,2):
                    if column+j<0 or column+j>column_max-1: #out of range
                        continue
                    else:
                        n_row=row+i
                        n_column=column+j
                        cell_list[n_row][n_column].neighbor+=1

                        if not cell_list[n_row][n_column].liveCell: #newBorn_list only reocrd coord where have no life
                            if cell_list[n_row][n_column].neighbor==3:
                                newBorn_list.append([n_row,n_column])
                            elif cell_list[n_row][n_column].neighbor==4:
                                newBorn_list.remove([n_row,n_column])
            
        cell_list[row][column].neighbor-=1 #multi added

#check live cell state, remove dead cell out of liveCell_list. 2 and 3 neighbors survival
def check_liveCell_state():
    global cell_list
    global liveCell_list
    new_liveCell_list=[]

    for [row,column] in liveCell_list:
        neighbors=cell_list[row][column].neighbor #get neighbor number

        if neighbors !=2 and neighbors !=3: #dead
            cell_list[row][column].switch_state()
        else: #survive
            new_liveCell_list.append([row,column])

    liveCell_list=new_liveCell_list

#operate nre born cell in newBorn_list
def new_born_cell():
    global newBorn_list

    for [row,column] in newBorn_list:
        cell_list[row][column].switch_state()

#combine liveCell_list and newBorn_list together, clear cell.neighbors and newBorn_list
def pre_nextLoop():
    global cell_list
    global liveCell_list
    global newBorn_list

    liveCell_list=liveCell_list+newBorn_list
    newBorn_list.clear()

    for list in cell_list:
        for cell in list:
            cell.neighbor=0

#command of start button, start the game in each 1s
def start_game(count):
    global beginning

    if beginning: #start sign
        find_neighbor()
        check_liveCell_state()
        new_born_cell()
        pre_nextLoop()
        
        if count==0:
            root.destroy()

        #run start_button again after 100ms
        root.after(100,start_game,count-1) #caution: start_button has no returns hence no () in needed here (or recursion error happens)
    else: #get stop sign
        pass

效率

@profile start_game(count)
Total time: 0.963228 s

Hits Time Per Hit % Time Line Contents
101 461.4 4.6 0.0 if beginning: #start sign
101 492614.4 4877.4 51.1 find_neighbor()
101 144015.7 1425.9 15.0 check_liveCell_state()
101 121916.5 1207.1 12.7 new_born_cell()
101 190508.8 1886.2 19.8 pre_nextLoop()
101 83.5 0.8 0.0 if count==0:
1 9204.7 9204.7 1.0 root.destroy()
101 4422.6 43.8 0.5 root.after(100,start_game,count-1) #caution: start_button has no returns hence no () in needed here (or recursion error happens)

时间消耗减少63%，对待大canvas，少live cell有巨大优势。但list处理中newBorn_list.remove()比想象中更花时间，如有大量cell交互改变可能会有较大问题。