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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
| <!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>Labyrinthe express</title>
<style>
table{margin:20px auto;border-collapse:collapse;}
td{background-color:white;border:1px solid black;width:25px;height:25px;}
.black{background-color:black}
.white{background-color:white}
.red{background-color:red}
#console{text-align:center}
#noway, #yes{margin:10px;text-align:center;color:lime;font-weight:bold;font-size:25px}
</style>
<script>
window.addEventListener("load",()=>{
// bouton permettant de générer le labyrinthe
// avec une largeur comprise entre 10 et 100 cases (grille carrée)
document.getElementById("go").addEventListener("click",(e)=>{
console.time("temps")
e.target.disabled=true;
document.getElementById("yes").textContent=""
const c=document.getElementById("c");
const large=parseInt(document.getElementById("large").value,10);
if(large < 10 || large > 100 || isNaN(large)){
alert("Entre 10 et 100...");e.target.disabled=false;return
}
// vidage du précédent labyrinthe, éventuellement
while(c.lastChild){c.removeChild(c.lastChild)};
// création du tableau html correspondant au nombre saisi
const tab=document.createElement("table"), tb=document.createElement("tb"),
tr=document.createElement("tr"), td=document.createElement("td");
let t=[];
for(let i=0;i<large;i++){
let r=tr.cloneNode();
for(let j=0;j<large;j++){
// tableau t = cases du labyrinthe
let c=td.cloneNode();t.push(large*i+j);c.title=large*i+j+1;r.appendChild(c);
if(large>30 && large<50){c.style.width=c.style.height="15px";}
else if(large>=50 && large<75){c.style.width=c.style.height="10px";}
else if(large>=75){c.style.width=c.style.height="5px";}
};
tb.appendChild(r);
};
c.appendChild(tab);tab.appendChild(tb);
const cel=tab.getElementsByTagName("td");
// t2 contient la moitié des cases de t (aléatoire)
// t3 contiendra tous les parcours possibles
// t4 contiendra chaque dernière case des parcours
let t2=new Set(), t3=[], t4=new Set();
let bis=t.slice();
for(let i=large*large/2-1;i>0;i--){
let h=Math.floor(Math.random()*bis.length);t2.add(bis[h]);bis.splice(h,1)
}
// les cases correspondantes dans t sont noircies
t.forEach((v,i,ta)=>{if(t2.has(i)){ta[i]="no";cel[i].classList.add("black")}else ta[i]=[]})
// On s'assure qu'au moins une case du haut est disponible pour le départ
let haut=0;
for(let i=0;i<large;i++){if(t[i]=="no"){haut++}};
if(haut==large){
let choix=Math.floor(Math.random()*large);
t[choix]=[];cel[choix].classList.add("white");
t[choix+large]=[];cel[choix+large].classList.add("white");
}
// On s'assure qu'au moins une case du bas est disponible pour l'arrivée
let bas=0;
for(let i=t.length-large;i<t.length;i++){if(t[i]=="no"){bas++}};
if(bas==large){
let choix=Math.floor(Math.random()*large)+t.length-large;
t[choix]=[];cel[choix].classList.add("white");
t[choix-large]=[];cel[choix-large].classList.add("white");
}
// définition des possibilités de déplacement pour chaque case blanche (maximum 8 directions)
// t3 contiendra tous les parcours possibles
for(let i=t.length-1;i>0;i--){if(t[i]!="no"){
if(i<t.length-1 && t[i+1]!="no" && cel[i+1] && (i+1)%large!=0){t[i].push(i+1)}
if(i>0 && t[i-1]!="no" && cel[i-1] && i%large!=0){t[i].push(i-1)}
if(i<t.length-large && t[i+large]!="no"){t[i].push(i+large)}
if(i>=large && t[i-large]!="no"){t[i].push(i-large)}
if(i<t.length-large-1 && t[i+large+1]!="no"&& (i+large+1)%large!=0){t[i].push(i+large+1)}
if(i>large && t[i-large-1]!="no" && i%large!=0){t[i].push(i-large-1)}
if(i<=t.length-large && t[i+large-1]!="no"&& i%large!=0){t[i].push(i+large-1)}
if(i>=large && t[i-large+1]!="no" && (i-large+1)%large!=0){t[i].push(i-large+1)}
}}
// Choix d'une case de départ, en haut, et d'arrivée, en bas
let debut, fin;
// tableau des débuts possibles et des fins possibles
let tdeb=[], tfin=[];
for(let i=0;i<large;i++){if(t[i]!="no" && t[i].length!=0){tdeb.push(i)}};
debut=tdeb[Math.floor(Math.random()*tdeb.length)];
for(let i=t.length-large;i<t.length;i++){if(t[i]!="no" && t[i].length!=0){tfin.push(i)}};
fin=tfin[Math.floor(Math.random()*tfin.length)];
// La case de départ sera à l'origine de tous les parcours
t3[0]=[debut];
// flag indiquant si la case de fin est atteinte
let end;
// fonction rappelée autant de fois que nécessaire
function run(arg){
// test de victoire
if(t4.has(fin)){
for(let i=0;i<t3.length;i++){
if(t3[i].pop()==fin){
for(j=0;j<t3[i].length;j++){
cel[t3[i][j]].classList.add("red");
cel[fin].classList.add("red");};
e.target.disabled=false;end=true;
document.getElementById("yes").textContent=
`Parcours de la case ${debut+1} à la case ${fin+1} en ${t3[i].length+1} coups.`;
break;
}
}};
if(!end){
arg++;
let long=t3.length;
// ajout au tableau des parcours de toutes les nouvelles possibilités
// un seul parcours par case finale
for(let i=0;i<long;i++){
let last=t3[i][t3[i].length-1];
for(let j=0;j<t[last].length;j++){
if(!t4.has(t[last][j])){
t3.push([...t3[i],t[last][j]]);t4.add(t[last][j])
}
}
};
// élimination des parcours provisoires sans issue
for(let i=0;i<t3.length;i++){if(t3[i].length-1<arg){t3.splice(i,1);i--}};
// s'il n'y a pas de nouvelle case, c'est que la grille est bloquée
// et on indique l'échec de la recherche!
if(!t3[0]){
document.getElementById("noway").textContent=
`Aucun passage possible entre la case ${debut+1} et la case ${fin+1}!`;
let trans=1;
let invis=setInterval(()=>{
document.getElementById("noway").scrollIntoView();
if(trans>0){trans-=0.1;document.getElementById("noway").style.opacity=trans}
else{document.getElementById("noway").textContent="";e.target.disabled=false;clearInterval(invis)}
},250);
cel[debut].classList.add("red");cel[fin].classList.add("red");
return
};
run(arg)
}
};
run(0);
console.timeEnd("temps")
},false)
},false)
</script>
</head>
<body>
<ul>
<li>Fabriquez une nouvelle grille carrée (entre 10 et 100 lignes).</li>
<li>On peut passer d'une zone blanche à une autre dans les 8 directions.</li>
<li>Si un chemin existe entre le point haut et le point bas de la grille, il apparaîtra.</li>
<li>Ce sera aussi la solution optimale.</li>
<li>S'il n'y a pas de solution, vous serez averti.</li>
</ul>
<div id="c"></div>
<div id="noway"></div>
<div id="yes"></div>
<div id="console">
<input id="large" type="number" />
<input id="go" type="button" value="Générer un labyrinthe" />
</div>
</body>
</html> |
Sortie de labyrinthe
Répondre avec citation
Partager