Prerequisite: This article implements the AI Snake Battle by itself, plus the human-machine battle, and readers can add computers VS computers and players VS players on the basis again (in fact, after the human-computer battle is finished, these two are nothing, the idea is the same )
Realize the effect:
Specific functions:
1. Smart mode: the computer plays by itself (eats food by yourself)
2. Human-computer battle: computer and human operation (add a keyboard controlled snake on the basis of the previous step)
Implementation environment:
Pycharm + Python3.6 + Curses + Win10
Specific process:
One: Configuration environment:
Curses: Reference link (Cp represents the local Python environment, don’t make a mistake)
(Stackoverflow is really a very good place)
two:
1. Source of inspiration + reference link:
http://www.hawstein.com/posts/snake-ai.html (Chrome sometimes cannot be opened, but Firefox can be opened)
2. Algorithm ideas:
A* Algorithm: https://www.cnblogs.com/21207-iHome/p/6048969.html (I have contacted it before, and the lecturer at the time said it was an automatic path finding algorithm. I felt it was the same as BFS+DFS, but the result was unexpected It is actually A* algorithm)
BFS+DFS (omitted)
The first step is to be able to make a basic snake and be familiar with the environment of Curses (it is better not to use special characters for snakes and food, which will cause pixel delay in the windows environment, which is very ugly)
#cursesOfficial Manual: https://docs.python.org/3.5/library/curses.html#module-curses #curses Reference Manual: https://blog.csdn.net/chenxiaohua/article/details/2099304
Specific ideas:
After familiarizing with the relevant commands in Curses, there is basically nothing. Make sure that the next button you press will not cause the snake to die. Make sure that the food is not on the snake after the snake eats food. Make sure that the snake will die when it touches itself and the frame. If you press other keys, it will cause the head It was inserted twice, causing the snake to die. (See code analysis for details)
1 #!/usr/bin/env python
2 # -*- coding: utf-8 -*-
3 # @Time: 2018/11/5 17:08
4 # @Author: Empirefree
5 # @File: greedy snake-01.py
6 # @Software: PyCharm Community Edition
7
8 #curses Official Manual: https://docs.python.org/3.5/library/curses.html#module-curses
9 #curses Reference Manual: https://blog.csdn.net/chenxiaohua/article/details/2099304
10
11 # Basic idea: while loop, let the snake go right (until the key is pressed, if you press other keys, the snake head will be inserted into the snake repeatedly once,
12 # Then the second cycle will exit), the snake grows automatically every time, but every time no food is eaten, it will pop the tail (snake is placed in the dict, similar to a linked list), the key check is to press the arrow keys
13 # Pressing the arrow keys also exists to judge whether there is an error (press up and then down), and then for the death situation is to touch the surrounding and yourself
14
15 # 1. Movement of snakes and changes after eating food
16 # 2. Keys: press other keys and arrow keys
17 # 3. Judgment of death
18
19 import curses
20 import random
21
22 # Turn on curses
23 def Init_Curse():
24 global s
25 s = curses.initscr()
26 curses.curs_set(0) #Visibility cursor, wrongly written wow
27 curses.noecho()
28 curses.cbreak() #Get a response immediately
29 s.keypad(True) #Special processing key position, return KEY_LEFT
30
31 #Close and return to the terminal
32 def Exit_Curse():
33 curses.echo()
34 curses.nocbreak()
35 s.keypad(False)
36 curses.endwin()
37
38 def Start_Game():
39 # Window operation
40 y, x = s.getmaxyx() # y, x in curses
41 w = curses.newwin(y, x, 0, 0)
42 w.keypad(1)
43 w.timeout(100)
44
45 # Initialize the position of the snake and store it in dict
46 snake_x = int(x/4)
47 snake_y = int(y/2)
48 snake = [[snake_y, snake_x], [snake_y, snake_x-1], [snake_y, snake_x-2]]
49
50 # Initialize food
51 food_pos = [int(y/2), int(x/2)]
52 w.addch(food_pos[0], food_pos[1],'@') # Use @ to display food characters
53
54 key = curses.KEY_RIGHT # Get the right arrow key
55
56 # Start, why do I feel that True is better than 1
57 while True:
58 next_key = w.getch() # Wait for input, return integer
59 print(next_key,'QAQ')
60 # Prevent Error
61 if next_key != -1:
62 if key == curses.KEY_RIGHT and next_key != curses.KEY_LEFT
63 or key == curses.KEY_LEFT and next_key != curses.KEY_RIGHT
64 or key == curses.KEY_DOWN and next_key != curses.KEY_UP
65 or key == curses.KEY_UP and next_key != curses.KEY_DOWN:
66 key = next_key
67
68 # The snake dies, when the snake head touches the snake body or the wall
69 if snake[0][0] in [0, y] or snake[0][1] in [0, x] or snake[0] in snake[1:]:
70 # print(snake[0], snake[1]) Pressing other keys will cause new_head to be inserted twice and exit
71 curses.endwin()
72 print('!!!Game over!!!')
73 quit()
74
75 #Key move
76 tempy = snake[0][0]
77 tempx = snake[0][1]
78 new_head = [tempy, tempx]
79 if key == curses.KEY_RIGHT:
80 new_head[1] += 1
81 elif key == curses.KEY_LEFT:
82 new_head[1] -= 1
83 elif key == curses.KEY_UP:
84 new_head[0] -= 1
85 elif key == curses.KEY_DOWN:
86 new_head[0] += 1
87 snake.insert(0, new_head) #Keep the snake head, update the snake head according to the button
88
89 #Food location
90 if snake[0] == food_pos:
91 food_pos = None
92 while food_pos is None:
93 new_food = [random.randint(1, y-1), random.randint(1, x-1)]
94 if new_food not in snake:
95 food_pos = new_food
96 w.addch(food_pos[0], food_pos[1],'@') #Add food again to ensure that the food is not on the snake
97 else:
98 tail = snake.pop() #dict directly pop the tail
99 w.addch(tail[0], tail[1], '')
100
101 w.addch(snake[0][0], snake[0][1],'Q')
102
103 if __name__ =='__main__':
104 Init_Curse()
105 Start_Game()
106
107 print('QAQ')
108 Exit_Curse()
Basic Snake3. Code analysis:
[Red is the function required by the code]
(Every time the snake takes a step, it updates the board distance between snake and food, involving board_rest (update the distance of each non-snake element from food) and board_refresh (this article uses the BFS algorithm)), find best_move, and then let the snake move.
If you can eat food (find_safe_way ): ----> release the virtual snake (virtual_shortest_move) (to prevent the snake from being killed by itself after eating the food)
If the virtual snake has eaten the food, it can still find its tail (go out) (is_tail_inside)
Eat food directly (choose_shortest_safe_move)
On the contrary, unable to get out:
Just follow the tail (follow_tail) is like going up and down all the time, it will never die, but the snake has no spirituality at all.
If you can't eat food
Follow the tail (the farthest way (
choose_longest_safe_move
)), four directions (if it is A* algorithm, you need to change 8 directions to 4 directions)
If the appeal method does not work, it involves a ny_possible_move and picks the shortest distance (this will involve eating yourself to death, which needs improvement)
(Through the above methods, you can create a basic AI greedy snake, of course, there are still many details to consider)
Error:
win = curses.newwin(HEIGHT, WIDTH, 0, 0)
_curses.error: curses function returned NULL
Reason: under Pycharm (or cmd or exe is too small and needs to be enlarged)
1 #!/usr/bin/env python
2 # -*- coding: utf-8 -*-
3 # @Time: 2018/11/16 14:26
4 # @Author: Empirefree
5 # @File: Greedy Snake-03.py
6 # @Software: PyCharm Community Edition
7
8 import curses
9 from curses import KEY_RIGHT, KEY_LEFT, KEY_UP, KEY_DOWN
10 from random import randint
11
12 # It must be made into a global situation, otherwise too much data will be used
13 # 1. Initialization interface
14 # 2. Update the map to determine whether you can eat food
15 # 3. If you can eat it, release the virtual snake (here is also designed to update the map (board_reset), record the distance (board_refresh) operation)
16 # 3.1 If the virtual snake eats food and has a path away from the snake's tail (eat directly), otherwise, it will chase the snake's tail
17 # 3.2 If you can't eat it, chase the snake's tail
18 # 4. Update best_move, change the distance
19 ############################################# #######################################
20 # of:
21 print('********************************************** ****************************')
22 print('*****************!!! Welcome to use AI Snake!!!***************** ********')
23 print ( '***************** Author: George Hu Joe *********************')
24 print('*****************Tool: Pycharm *********************')
25 print('*****************Time: 2018/11/16 14:26 ******************* *')
26 print('***************** (Press Esc to end the snake game) ******************** **')
27 print('********************************************** ****************************')
28 # venue
29 HEIGHT, WIDTH = map(int, input('Please enter the length and width [20 40]:').split())
30 FIELD_SIZE = HEIGHT * WIDTH
31
32 #snake and food
33 HEAD = 0
34 FOOD = 0
35 UNDEFINED = (HEIGHT + 1) * (WIDTH + 1)
36 SNAKE = 2 * UNDEFINED
37
38 # 4.directions of movement
39 LEFT = -1
40 RIGHT = 1
41 UP = -WIDTH
42 DOWN = WIDTH
43
44 # error code
45 ERR = -1111
46
47 # Use a one-dimensional array to represent two-dimensional things
48 # board represents the rectangular field for snake movement
49 # Initialize where the snake head is at (1,1), row 0, row HEIGHT, column 0, WIDTH column is a fence, unavailable
50 # The initial snake length is 1
51 board = [0] * FIELD_SIZE
52 snake = [0] * (FIELD_SIZE + 1)
53 snake[HEAD] = 1 * WIDTH + 1
54 snake_size = 1
55 # tmpsnake is the virtual snake
56 tmpboard = [0] * FIELD_SIZE
57 tmpsnake = [0] * (FIELD_SIZE + 1)
58 tmpsnake[HEAD] = 1 * WIDTH + 1
59 tmpsnake_size = 1
60
61 # food: food position (0~FIELD_SIZE-1), initially at (3, 3)
62 # best_move: direction of movement
63 food = 3 * WIDTH + 3
64 best_move = ERR
65
66 # Movement direction array
67 mov = [LEFT, RIGHT, UP, DOWN]
68 # Received keys and scores
69 key = KEY_RIGHT
70 score = 1 # The score also indicates the length of the snake
71
72 #cuesesinitialization
73 curses.initscr()
74 win = curses.newwin(HEIGHT, WIDTH, 0, 0)
75 win.keypad(1)
76 curses.noecho()
77 curses.curs_set(0)
78 win.border(0)
79 win.nodelay(1)
80 win.addch(food//WIDTH, food% WIDTH,'@')
81
82 ############################################## #######################################
83 #Judge whether it is empty (can go)
84 def is_cell_free(idx, psize, psnake):
85 return not (idx in psnake[:psize])
86
87
88 # Check whether a certain position idx can move in the move direction
89 def is_move_possible(idx, move):
90 flag = False
91 if move == LEFT:
92 flag = True if idx% WIDTH> 1 else False
93 elif move == RIGHT:
94 flag = True if idx% WIDTH <(WIDTH-2) else False
95 elif move == UP:
96 flag = True if idx> (2 * WIDTH-1) else False # i.e. idx/WIDTH> 1
97 elif move == DOWN:
98 flag = True if idx <(FIELD_SIZE-2 * WIDTH) else False # i.e. idx/WIDTH <HEIGHT-2
99 return flag
100
101
102 # Calculate the path length of each non-SNAKE element in the board to the food, and judge whether the food can be found
103 def board_reset(psnake, psize, pboard):
104 for i in range(FIELD_SIZE):
105 if i == food:
106 pboard[i] = FOOD
107 elif is_cell_free(i, psize, psnake): # The position is empty
108 pboard[i] = UNDEFINED
109 else: # The position is a snake body
110 pboard[i] = SNAKE
111
112
113 # Breadth first search traverses the entire board,
114 # Calculate the path length of each non-SNAKE element in the board to the food
115 def board_refresh(pfood, psnake, pboard):
116 queue = []
117 queue.append(pfood)
118 inqueue = [0] * FIELD_SIZE
119 found = False
120 # After the while loop is over, except for the body of the snake,
121 # The length of the path from the number code in each of the other squares to the food
122 while len(queue) != 0:
123 idx = queue.pop(0)
124 if inqueue[idx] == 1: continue
125 inqueue[idx] = 1
126 for i in range(4):
127 if is_move_possible(idx, mov[i]):
128 if idx + mov[i] == psnake[HEAD]:
129 found = True
130 if pboard[idx + mov[i]] <SNAKE: # If the point is not the body of a snake
131
132 if pboard[idx + mov[i]]> pboard[idx] + 1:
133 pboard[idx + mov[i]] = pboard[idx] + 1
134 if inqueue[idx + mov[i]] == 0:
135 queue.append(idx + mov[i])
136
137 return found
138
139
140 #Snake head start, choose the farthest path according to the 4 areas of the snake (safer)
141 def choose_shortest_safe_move(psnake, pboard):
142 best_move = ERR
143 min = SNAKE
144 for i in range(4):
145 if is_move_possible(psnake[HEAD], mov[i]) and pboard[psnake[HEAD] + mov[i]] <min:
146 min = pboard[psnake[HEAD] + mov[i]]
147 best_move = mov[i]
148 return best_move
149
150
151 # Starting from the snake head, according to the element value in the board,
152 # Choose the farthest path from the 4 area points around the snake head
153 def choose_longest_safe_move(psnake, pboard):
154 best_move = ERR
155 max = -1
156 for i in range(4):
157 if is_move_possible(psnake[HEAD], mov[i]) and pboard[psnake[HEAD] + mov[i]] <UNDEFINED and pboard[psnake[HEAD] + mov[i]]> max:
158 max = pboard[psnake[HEAD] + mov[i]]
159 best_move = mov[i]
160 return best_move
161
162
163 # Check if you can chase the snake's tail, that is, there is a path between the snake's head and the snake's tail
164 # To avoid the snake head from falling into a dead end
165 # Virtual operation, carried out in tmpboard, tmpsnake
166 def is_tail_inside():
167 global tmpboard, tmpsnake, food, tmpsnake_size
168 tmpboard[tmpsnake[tmpsnake_size-1]] = 0 # Virtually turn snake tail into food (because it is virtual, it is done in tmpsnake, tmpboard)
169 tmpboard[food] = SNAKE # The place where food is placed is treated as a snake
170 result = board_refresh(tmpsnake[tmpsnake_size-1], tmpsnake, tmpboard) # Find the path length from each position to the tail of the snake
171 for i in range(4): # If the snake head and the snake tail are close together, return False. That is, I can’t follow_tail, chase the snake tail
172 if is_move_possible(tmpsnake[HEAD], mov[i]) and tmpsnake[HEAD] + mov[i] == tmpsnake[
173 tmpsnake_size-1] and tmpsnake_size> 3:
174 result = False
175 return result
176
177
178 # Let the snake head run one step towards the snake tail
179 # No matter what the snake body is blocking, run in the direction of the snake tail
180 def follow_tail():
181 global tmpboard, tmpsnake, food, tmpsnake_size
182 tmpsnake_size = snake_size
183 tmpsnake = snake[:]
184 board_reset(tmpsnake, tmpsnake_size, tmpboard) # reset virtual board
185 tmpboard[tmpsnake[tmpsnake_size-1]] = FOOD # Let snake tail become food
186 tmpboard[food] = SNAKE # Let the food place become a snake body
187 board_refresh(tmpsnake[tmpsnake_size-1], tmpsnake, tmpboard) # Find the path length from each position to the snake's tail
188 tmpboard[tmpsnake[tmpsnake_size-1]] = SNAKE # restore snake tail
189
190 return choose_longest_safe_move(tmpsnake, tmpboard) # Return to the running direction (let the snake head move 1 step)
191
192
193 # When all kinds of plans fail, just find a feasible direction to go (1 step),
194 def any_possible_move():
195 global food, snake, snake_size, board
196 best_move = ERR
197 board_reset(snake, snake_size, board)
198 board_refresh(food, snake, board)
199 min = SNAKE
200
201 for i in range(4):
202 if is_move_possible(snake[HEAD], mov[i]) and board[snake[HEAD] + mov[i]] <min:
203 min = board[snake[HEAD] + mov[i]]
204 best_move = mov[i]
205 return best_move
206
207 #Virtual snake movement
208 def shift_array(arr, size):
209 for i in range(size, 0, -1):
210 arr[i] = arr[i-1]
211
212 #Generate new food
213 def new_food():
214 global food, snake_size
215 cell_free = False
216 while not cell_free:
217 w = randint(1, WIDTH-2)
218 h = randint(1, HEIGHT-2)
219 food = h * WIDTH + w
220 cell_free = is_cell_free(food, snake_size, snake)
221 win.addch(food//WIDTH, food% WIDTH,'@')
222
223
224 # The real snake walks 1 step towards pbest_move in this function
225 def make_move(pbest_move):
226 global key, snake, board, snake_size, score
227 shift_array(snake, snake_size)
228 snake[HEAD] += pbest_move
229
230 # Press esc to exit, getch also guarantees the fluency of the drawing, without it, you will only see the final result
231 win.timeout(10)
232 event = win.getch()
233 key = key if event == -1 else event
234 if key == 27: return
235
236 p = snake[HEAD]
237 win.addch(p//WIDTH, p% WIDTH,'*')
238
239 # If the newly added snake head is the food location
240 # Increase the length of the snake by 1, generate new food, reset the board (because the original path length is no longer used)
241 if snake[HEAD] == food:
242 board[snake[HEAD]] = SNAKE # New snake head
243 snake_size += 1
244 score += 1
245 if snake_size <FIELD_SIZE: new_food()
246 else: # If the newly added snake head is not the location of food
247 board[snake[HEAD]] = SNAKE # New snake head
248 board[snake[snake_size]] = UNDEFINED # Snake tail becomes a space
249 win.addch(snake[snake_size]//WIDTH, snake[snake_size]% WIDTH, '')
250
251
252 #Virtual snake shortest movement
253 def virtual_shortest_move():
254 global snake, board, snake_size, tmpsnake, tmpboard, tmpsnake_size, food
255 tmpsnake_size = snake_size
256 tmpsnake = snake[:] # If tmpsnake=snake directly, then both point to the same place
257 tmpboard = board[:] # The length of the path from each position to the food in the board is no longer required.
258 board_reset(tmpsnake, tmpsnake_size, tmpboard)
259
260 food_eated = False
261 while not food_eated:
262 board_refresh(food, tmpsnake, tmpboard)
263 move = choose_shortest_safe_move(tmpsnake, tmpboard)
264 shift_array(tmpsnake, tmpsnake_size)
265 tmpsnake[HEAD] += move # Add a new position in front of the snake head
266 # If the position of the newly added snake head is exactly the position of the food
267 # Increase the length by 1, reset the board, and the food position becomes part of the snake (SNAKE)
268 if tmpsnake[HEAD] == food:
269 tmpsnake_size += 1
270 board_reset(tmpsnake, tmpsnake_size, tmpboard) # After the virtual operation, the position of the snake on the board
271 tmpboard[food] = SNAKE
272 food_eated = True
273 else: # If the head of the snake is not the position of food, the newly added position is the head of the snake, and the last one becomes a space
274 tmpboard[tmpsnake[HEAD]] = SNAKE
275 tmpboard[tmpsnake[tmpsnake_size]] = UNDEFINED
276
277
278 # If there is a path between the snake and the food, call this function
279 def find_safe_way():
280 global snake, board
281 safe_move = ERR
282 # Virtually run once, because the path between the snake and the food has been ensured, the execution is effective
283 # Get the position of the virtual snake in the board after running, namely tmpboard, see label101010
284 virtual_shortest_move() # The only place where the function is called
285 if is_tail_inside(): # If there is a path between the snake head and the tail after the virtual operation, select the shortest path operation (1 step)
286 return choose_shortest_safe_move(snake, board)
287 safe_move = follow_tail() # Otherwise follow_tail 1 step virtually, if it can be done, return true
288 return safe_move
289
290 if __name__ =='__main__':
291
292 while key != 27:
293 win.border(0)
294 win.addstr(0, 2,'Score:' + str(score) + '')
295 win.timeout(10)
296 # Receive keyboard input, while also making the display smooth
297 event = win.getch()
298 key = key if event == -1 else event
299 # Reset matrix
300 board_reset(snake, snake_size, board)
301
302 # If the snake can eat food, board_refresh returns true
303 # In addition to the snake body (=SNAKE) in the board, the other element values indicate the shortest path length from this point to the food
304 if board_refresh(food, snake, board):
305 best_move = find_safe_way() # The only calling place for find_safe_way
306 else:
307 best_move = follow_tail()
308
309 if best_move == ERR:
310 best_move = any_possible_move()
311 # The above thought once, only one direction is drawn, and one step is taken
312 if best_move != ERR:
313 make_move(best_move)
314 else:
315 break
316
317 curses.endwin()
318 print("
Score: "+ str(score))
Greedy Snake-02On the basis of the above, it is also necessary to introduce the basic greedy snake made in the first step
Details: 1. How to score points with the snake after the keyboard snake is added (only need to return, but the new_food() needs to be changed)
1 # Create new food 2 def new_food(): 3 global food, snake_size, myfood 4 cell_free = False 5 while not cell_free: 6 food1 = [random.randint(1, HEIGHT-2), random.randint(1, WIDTH-2)] 7 w = randint(1, WIDTH-2) 8 h = randint(1, HEIGHT-2) 9 myfood = [h, w] 10 food = h * WIDTH + w 11 if (is_cell_free(food, snake_size, snake) and [w, h] not in snake1): 12 cell_free = True 13 win.addch(food//WIDTH, food% WIDTH,'@')
2. I haven't said that since many variables need global after the snake joins, the variables look very troublesome (readers must be mentally prepared)
3. The win.timeout() in curses is to control the speed of the snake
It seems that there is nothing more, but I think of it more. I didn’t add two snakes that can’t collide with each other (readers can also make two maps, and then see how the AI snake and your own snake operate, I put it in one map)
Recommendations of previous wonderful articles:
------------------- End -------------------
Welcome everyone to like , leave a message, forward, reprint, thank you for your company and support
Thousands of waters and thousands of mountains are always in love, can you click [ Looking ]
/Today's message topic/
Just say a word or two~~
*Disclaimer: This article is organized on the Internet, and the copyright belongs to the original author. If the source information is wrong or infringes on rights, please contact us for deletion or authorization.