Discussion :

[Invité]

Bien le bonjour en ce dernier jour de l'année !

La suite des péripéties de mon labyrinthe... J'ai souhaité créé un script de résolution de labyrinthe moi-même en me basant un peu sur l'idée d'un autre script, afin de vérifier que je n'ai bien qu'un seul chemin suite aux nombreuses modifications que j'ai apporté à ce labyrinthe sidewinder.
J'ai utilisé un système de récursion puisque c'est plus simple pour ma petite tête, mais voilà autant avec un petit labyrinthe ça marche, autant avec un gros ça plante !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
file = open("Maze.txt","r")
area = file.read().replace(',','').splitlines()
file.close()
air = [[int(x) for x in line] for line in area]
 
import sys, time
 
sys.setrecursionlimit(10000)
 
'''air = [[0,1,0,0,0,0,0,0,0],
        [0,1,0,0,1,1,1,1,0],
        [0,1,0,1,1,0,0,1,0],
        [0,1,1,1,0,1,1,1,0],
        [0,1,0,0,0,1,0,1,0],
        [0,1,1,1,1,1,1,1,0],
        [0,1,0,1,0,0,0,1,0],
        [0,0,0,0,0,0,0,1,0]]'''
 
area = [l.copy() for l in air]
 
start = (0,1)
end = (len(area)-1,len(area[-1])-2)
 
def print_area(tableau):
    for line in tableau:
        print(line)
    print('---------------')
    time.sleep(0.5)
 
path = []
def find_way(x, y):
    global path
    path.append((x, y))
    for X, Y in ((x+i, y+I) for i in range(-1,2) for I in range(-1,2) if (i,I) != (0, 0) and (not i or not I)):
        if area[X][Y]==area[x][y]-1 and X >= 0 and Y >= 0 and area[X][Y]:            
            find_way(X, Y)
            break
 
 
def next_step(x,y,pcds,visited,k=2):
    visited_copy = visited.copy()
    for X, Y in ((x+i, y+I) for i in range(-1,2) for I in range(-1,2) if (i,I) != (0, 0) and (not i or not I)):
        if (X, Y) != pcds :
            try:
                if area[X][Y]:
                    if (X,Y) not in visited_copy:
                        visited_copy.append(pcds)
                        area[X][Y]=k
                        #print_area(area)                    
                        next_step(X,Y,(x, y),visited_copy,k+1)                    
            except IndexError:
                print('bug :',X,Y)
                pass
 
 
print(time.ctime())
next_step(start[0], start[1], start, [])
 
#print_area(air)
#print_area(area)
find_way(end[0], end[1])
for x, y in path:
    air[x][y] = 9
#print_area(air)
 
with open("Maze_solved.txt","w") as file:
    for line in air:
        file.write(str(line)[1:-1].replace(',',''))
        file.write('\n')

Voici le message d'erreur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
File "C:\Users\toto\Desktop\Scripts\K_GAME\solver.py", line 50, in next_step
    next_step(X,Y,(x, y),visited_copy,k+1)
  [Previous line repeated 1955 more times]
  File "C:\Users\toto\Desktop\Scripts\K_GAME\solver.py", line 47, in next_step
    visited_copy.append(pcds)
MemoryError

Que se passe-t-il avec ces listes ?
Restent-elles en mémoire jusque la fin du programme et sature la RAM ?
Est-ce que c'est mon code qui est mal fichu (fortement probable) ?

Et finalement comment utiliser sa propre pile plutôt que de la récursion sans tourner en rond ? (Ce qui est peut-être déjà le cas avec mon script, j'ai fais juste quelques petits tests)

Merci et bon réveillon ou bonne année si vous lisez ceci début 2022. 🥳