Discussion :

[Invité]

Bonjour,
(Dsl pour le pavé)
J'utilise un algorithme Sidewinder pour réaliser un labyrinthe qui ressemble à ça mais en beaucoup plus grand :

Ce genre de labyrinthe est assez prédictif car il n'y a jamais de chemin remontant, j'ai donc entrepris la tâche de le complexifier le labyrinthe en créant des "détours" (cf. exemple qui suit).

Exemple :

(En vert clair les rajouts, en "fondu" les portions supprimées)

Seulement voila si un joueur tombe sur un chemin remontant alors il sait dores et déjà qu'il est sur la bonne piste, je voudrais donc rajouter des "pseudos-raccourcis" entre les "mauvais-chemins", ce qui donnera l'impression d'avoir des chemins qui remontent de temps en temps, mais (et c'est là où ça devient costaud) je ne veux pas créer de "vrai-raccourcis" au "bon-chemin" !

Exemple :

(En rouge ce que je ne veux pas, en bleu ce que je désire/tolère.)

L'idéal serait de calculer la longueur du "bon-chemin" à chaque ajout de "pseudo-raccourcis", histoire de ne pas rajouter de "vrai-raccourcis", mais il faut 20 minutes pour que le script de résolution de labyrinthe établisse le bon chemin, je crains donc que de calculer cette longueur à chaque rajout va être infiniment long !

Le fichier du labyrinthe est une liste de liste de 0 pour les murs, de 1 pour les chemins et de 9 pour le bon chemin !
Exemple :

Code :

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

1
2
3
4
5
6
7
[
[0,0,0,0,0,0],
[0,9,9,9,9,0],
[0,0,1,0,9,0],
[0,1,1,0,9,0],
[0,0,0,0,0,0]
]

Une idée qui me garantirait un bon résultat c'est de transformer toutes les "branches" du bon chemin en un numéro unique et permettre uniquement des raccourcis entre leurs sous-branches :

(A noter qu'en rouge clignotant ça ne serait presque pas trop gênant puisque ça rallongerait le chemin mais il n'y aurait pas réellement de choix si la bifurcation mène tout de même au bon chemin, non ?)

Si vous avez d'autres idées, je suis preneur !

Merci d'avance !

[Sve@r]

Bonjour

Ce que tu veux faire ressemble au problème du voyageur de commerce et aura la même complexité (pourquoi le bleu serait toléré? Parce que l'ouverture créée donne sur un chemin ne menant nulle part mais pour détecter que ça ne mêne nulle part ça va être chaud, surtout appliqué à chaque mur possiblement ouvert => ça va exploser ta ram)

Ici http://mathsoup.xyz/mathsoup.xyz/con...%C3%A8ves.html il est expliqué comment créer un labyrinthe.
D'après ce que je vois, l'auteur commence par créer un labyrinthe totalement fermé (toutes les cases fermées sur 4 côtés et donc isolées les unes des autres). Ensuite il ouvre un chemin entre A et B. Et enfin il ouvre des chemins aléatoires ne menant nulle part. A mon avis ça sera plus rapide. A chaque ouverture possible suffit de vérifier si l'ouverture ne donne pas sur une case "9"...

[Invité]

Bonjour

Ce que tu veux faire ressemble au problème du voyageur de commerce et aura la même complexité (pourquoi le bleu serait toléré? Parce que l'ouverture créée donne sur un chemin ne menant nulle part mais pour détecter que ça ne mêne nulle part ça va être chaud, surtout appliqué à chaque mur possiblement ouvert => ça va exploser ta ram)

Ici http://mathsoup.xyz/mathsoup.xyz/con...%C3%A8ves.html il est expliqué comment créer un labyrinthe.
D'après ce que je vois, l'auteur commence par créer un labyrinthe totalement fermé (toutes les cases fermées sur 4 côtés et donc isolées les unes des autres). Ensuite il ouvre un chemin entre A et B. Et enfin il ouvre des chemins aléatoires ne menant nulle part. A mon avis ça sera plus rapide. A chaque ouverture possible suffit de vérifier si l'ouverture ne donne pas sur une case "9"...

Je pense que c'est bon ! Mais j'y suis allé comme un bourrin !

Première étape : mettre un numéro a usage unique pour toutes les branches qui partent du "bon chemin"


A la place des 7 et 8 c'est un numéro unique pour chaque branche (sauf si elle parte du même 9, j'ai pas réussi à faire autrement et je ne pense pas qu'elle puisse se rencontrer puisque le chemin traverse tout le labyrinthe), voici le code (ça me dérangerait pas que quelqu'un, @Sve@r à tout hasard , me donne la version avec générateur, vu que je ne suis pas à l'aise avec les générateurs) :

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
70
71
72
73
74
75
76
import time, sys
sys.setrecursionlimit(50000)
 
file = open('maze.txt','r')
area = file.read().replace(',','').splitlines()
file.close()
area = [[int(x) for x in l] for l in area]
 
for x, line in enumerate(area):
    if x < 3 or x == 1499:
        pass
    else:
        for y, obj in enumerate(line):
            if y < 2 or y == 1499:
                pass
            else:
                if obj == 9 :
                    ids = (x,y)
                    break
        break
 
nb = 10    
 
def look_around(coords):
    x, y = coords
    if area[x-1][y] == 1:
        area[x-1][y] = nb
        look_around((x-1,y))        
    if area[x+1][y] == 1:
        area[x+1][y] = nb
        look_around((x+1,y))
    if area[x][y-1] == 1:
        area[x][y-1] = nb        
        look_around((x,y-1))
    if area[x][y+1] == 1:
        area[x][y+1] = nb
        look_around((x,y+1))    
 
def find_other_nine(coords):
    global nb, pcd
    x, y = coords
    if area[x-1][y] == 9 and (x-1, y) != pcd :
        pcd = coords
        return x-1, y
    if area[x+1][y] == 9 and (x+1, y) != pcd :
        pcd = coords
        return x+1, y
    if area[x][y-1] == 9 and (x, y-1) != pcd :
        pcd = coords
        return x, y-1
    if area[x][y+1] == 9 and (x, y+1) != pcd :
        pcd = coords
        return x, y+1
 
print('Start :',ids)
pcd = ids[0]-1,ids[1]
 
while ids != (1498, 1498):
    look_around(ids)
    nb += 1
    ids = find_other_nine(ids)
    #print(ids)
 
print('end')
 
string = ''
for line in area:
    string+=str(line).replace(' ','')[1:-1]
    string+='\n'
 
#string = string.replace('9','1')
#string = string.replace('2','1')
 
file = open('new_maze.txt','w')
file.write(string)
file.close()

Question subsidiaire : est-ce que mettre sys.setrecursionlimit(50000) ou sys.setrecursionlimit(2500) ça change quelque chose ? Je dis ça parce que j'ai eu un truc bizarre pdt un long moment.

Seconde étape : Rajouter des raccourcis là où il faut


Le code est relativement simple, j'y ai rajouté une randomisation et une vérification pour rajouter un "raccourci" au milieu d'un mur et pas juste à côté d'un chemin.

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
import random, time
import winsound
 
file = open("7_remixed_solved_branchified_unique.txt","r")
area = file.read().splitlines()
file.close()
area = [[int(x) for x in l.split(',')] for l in area] 
 
def obj_and_one_near(X,Y):
    liste = [True for line in area[X-3:min(1499,X+4)] if line[Y+1:min(1498,Y+3)]!=[0, 0]] + [False]
    #print(liste[0])
    return liste[0]
 
area2 = area.copy()
for x, line in enumerate(area):
    if x < 5 or x == 1499:
        continue
    for y, obj in enumerate(line):
        if y > 1495 or not obj:
            continue
        if line[y:y+4]==[obj,0,0,obj]:
            if not obj_and_one_near(x,y):            
                if random.randint(0,4) == 1:
                    area2[x][y:y+4] = [obj,2,2,obj]
                    #print('ici',x,y)
 
file = open("7_+shortcuts.txt","w")
for line in area2:
    file.write(str(line).replace(" ","")[1:-1])
    file.write('\n')
file.close()
 
 
winsound.MessageBeep()

@Sve@r en tout cas ton premier lien sur l'autre topic, ça m'a permis d'initier cette réflexion ! J'ai retrouvé ce lien https://www.astrolog.org/labyrnth/algrithm.htm#create pour voir les alternatifs au labyrinthe "parfait" et je suis tombé sur celui dit en "braid"... Bref !

[Invité]

N.B :

Ensuite il ouvre un chemin entre A et B. Et enfin il ouvre des chemins aléatoires ne menant nulle part. A mon avis ça sera plus rapide. A chaque ouverture possible suffit de vérifier si l'ouverture ne donne pas sur une case "9"...

C'est plus pour un labyrinthe "parfait", non ?
Comme dis sur certains sites, les labyrinthes parfaits sont des belles oeuvres algorithmiques mais souvent plus faciles à résoudre que ceux qui ne le sont pas.
Voici un labyrinthe bactracké récursif que j'avais utilisé initialement, il est censé être plus dur qu'un sidewinder car non biaisé mais en réalité il me paraît 1000 fois plus facile :

N'importe quel idiot le réussira sans se tromper une seule fois !

[Sve@r]

Je pense que c'est bon ! Mais j'y suis allé comme un bourrin !

Bah, tant que ça marche...

(ça me dérangerait pas que quelqu'un, @Sve@r à tout hasard , me donne la version avec générateur, vu que je ne suis pas à l'aise avec les générateurs)

Ben un générateur c'est remplacer "création de tableau" par ledit générateur.
Exemple de base

Code python :

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

1
2
3
4
5
def genere1(n):
	tab=list()
	for i in range(n):
		tab.append(n)
	return tab

Exemple avec générateur

Code python :

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

1
2
3
def genere2(n):
	for i in range(n):
		yield n

On remplace bêtement la modification du tableau par le yield. Et en plus ça ne change absolument rien pour l'appelant, de son côté c'est totalement transparent. Il peut faire for x in genere1(125) ou for y in genere2(350) au choix.
Or dans ton code, à aucun moment tu ne renvoies de tableau. Donc pas de tableau renvoyé = pas de générateur

Ceci dit, ton code comporte quelques défauts. Déjà mettre des fonctions au milieu du code ça rend le truc difficilement lisible et maintenable. Séparer les choses c'est écrire des fonctions pour chaque chose. Une fonction pour générer le labyrinthe. Une autre pour ouvrir un chemin. Une troisième pour ouvrir les leurres. Ensuite ne reste plus qu'à emboiter.

Code python :

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

1
2
3
4
file = open("7_remixed_solved_branchified_unique.txt","r")
area = file.read().splitlines()
file.close()
area = [[int(x) for x in l.split(',')] for l in area]

Code python :

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

1
2
with open("7_remixed_solved_branchified_unique.txt","r") as fp:
	area = [[int(x) for x in l.split(',')] for l in fp.read().splitlines()]

Code python :

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

1
2
3
4
def obj_and_one_near(X,Y):
	liste = [True for line in area[X-3:min(1499,X+4)] if line[Y+1:min(1498,Y+3)]!=[0, 0]] + [False]
	#print(liste[0])
	return liste[0]

Pourquoi générer toute une liste pour ne retourner que son premier élément ??? Retourne directement si le premier truc est vrai ou pas !!!

Code python :

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

1
2
3
4
5
file = open("7_+shortcuts.txt","w")
for line in area2:
	file.write(str(line).replace(" ","")[1:-1])
	file.write('\n')
file.close()

Code python :

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

1
2
3
with open("7_+shortcuts.txt","w") as fp:
	for line in area2:
		print(str(line).replace(" ","")[1:-1], file=fp)

Question subsidiaire : est-ce que mettre sys.setrecursionlimit(50000) ou sys.setrecursionlimit(2500) ça change quelque chose ? Je dis ça parce que j'ai eu un truc bizarre pdt un long moment.

Ca change la profondeur de récursion. Mais si je dois en arriver là alors je remplace carrément la récursivité par une pile, au-moins je ne crains plus la limite (et tant pis si ça crâme ma ram).

N'importe quel idiot le réussira sans se tromper une seule fois !

Il me semble que dans ce dernier labyrinthe, le chemin rouge n'a pas vraiment beaucoup d'ouvertures annexes. Je n'ai jamais créé de labyrinthe mais il me semble que pour créer les impasses il faut(drait?) partir du chemin de base...

[Invité]

Ouai je n'ai pas pris l'habitude d'utiliser with open(...) vu que je n'ai jamais vraiment eu de bugue. Mon code n'est pas propre, j'ai collé les trucs comme ça venait dans ma tête.
J'aime bien déplacer des bouts de code dans des fonctions qui portent un nom qui résume bien ce que ça fait, même si c'est complètement inutile... comme find_other_nine(coords) !

Et sinon, je pensais pouvoir améliorer à l'aide d'un générateur cette partie récursive sans avoir à augmenter la limite de récursion :

Code Python :

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
def look_around(coords):
    x, y = coords
 
    if area[x-1][y] == 1:
        area[x-1][y] = nb
        look_around((x-1,y))    
 
    if area[x+1][y] == 1:
        area[x+1][y] = nb
        look_around((x+1,y))
 
    if area[x][y-1] == 1:
        area[x][y-1] = nb        
        look_around((x,y-1))
 
    if area[x][y+1] == 1:
        area[x][y+1] = nb
        look_around((x,y+1))

J'ai cru lire quelques parts qu'un générateur était meilleur pour gérer ça.. J'ai sûrement mal lu !
Si ça peut intéresser quelqu'un (clairement au dessus de mon niveau) : Fixpoint for Iterators
Lien trouvé sur ce topic : Can generators be recursive?

Mais si je dois en arriver là alors je remplace carrément la récursivité par une pile, au-moins je ne crains plus la limite (et tant pis si ça crâme ma ram).

Si tu le dis !
J'avais créé un autre code sans récursivité beaucoup plus long et compliqué à cerner, avec une boucle while mais j'ai lâché l'affaire quand j'ai vu que ça ne fonctionnait pas correctement... (Que faire lors de bifurcation en T ?!) Bref j'ai pas poussé plus loin la réflexion vu le temps que j'avais déjà passé dessus...
Il y a peut-être moyen de combiner récursion et "pile" en capturant les positions parcourues dans une liste globale (ou un tableau 2D) et en recommençant la récursion à l'endroit ou on était avant d'atteindre la limite en utilisant un try: except: ?
Pas infini mais déjà beaucoup plus important :

Code Python :

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

1
2
3
4
5
6
7
8
9
10
11
12
def test(n):
	global N
	n+=1
	N = n
	print(n)
	test(n)
 
def toto(n):
	try:
		test(n)
	except:
		toto(N)

Bon par contre adapté ça à mon code, ça doit pas être simple ! ^^
Finalement sys.setrecursionlimit(50000)c'est pas mal !

[Sve@r]

J'aime bien déplacer des bouts de code dans des fonctions qui portent un nom qui résume bien ce que ça fait, même si c'est complètement inutile... comme find_other_nine(coords) !

Oui c'est bien. De petites fonctions qui font un truc et que tu peux appeler de partout où tu as besoin dudit truc. Le plus dur est de faire la part des choses entre "ce truc est-il faisable directement ou faut-il une fonction". En général, je mets une fonction si le truc commence à avoir besoin d'une boucle ou d'un if avec beaucoup d'opérations derrière.

Et sinon, je pensais pouvoir améliorer à l'aide d'un générateur cette partie récursive sans avoir à augmenter la limite de récursion :

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
def look_around(coords):
    x, y = coords
 
    if area[x-1][y] == 1:
        area[x-1][y] = nb
        look_around((x-1,y))    
 
    if area[x+1][y] == 1:
        area[x+1][y] = nb
        look_around((x+1,y))
 
    if area[x][y-1] == 1:
        area[x][y-1] = nb        
        look_around((x,y-1))
 
    if area[x][y+1] == 1:
        area[x][y+1] = nb
        look_around((x,y+1))

J'ai l'impression qu'il s'agit d'un algorithme de remplissage...


Ici divers algorithmes équivalents dont certains avec pile => https://fr.wikipedia.org/wiki/Algori..._par_diffusion

J'ai cru lire quelques parts qu'un générateur était meilleur pour gérer ça.. J'ai sûrement mal lu !
Si ça peut intéresser quelqu'un (clairement au dessus de mon niveau) : Fixpoint for Iterators
Lien trouvé sur ce topic : Can generators be recursive?

Oui, un générateur peut être récursif. Faut juste se souvenie que l'appel récursif retournant donc un générateur ne peut pas être simplement utilisé tel quel (on ne peut pas écrire n=fct(...) car fct() ne retourne pas un élément mais un ensemble d'éléments) et donc il faut boucler sur ses éléments retournés, ou se contenter de next() si on est certain que le générateur ne génère qu'un seul éléments
Exemple avec la factorielle

Code python :

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
#!/usr/bin/env python3
# coding: utf-8
 
def fact1(n):
	if n == 0: return 1
	return n * fact1(n-1)
 
def fact2(n):
	if n == 0:
		yield 1
		return
 
	for x in fact2(n-1):
		yield n * x
 
def fact3(n):
	if n == 0:
		yield 1
		return
 
	yield n * next(fact3(n-1))
 
print(fact1(5))
print(next(fact2(5)))
print(next(fact3(5)))