Assurez-vous que le labyrinthe de cartes avec ascenseurs peut être résolu?

Dans mon jeu, nous voyons les étages d'une maison de côté, et le héros peut prendre des ascenseurs - un ascenseur monte (jusqu'au prochain ascenseur vers le haut), ou descend (jusqu'au prochain ascenseur vers le bas), selon la flèche comme montré, et il y a toujours une paire d'exactement deux ascenseurs connectés. C'est la seule façon dont le héros peut se déplacer verticalement, bien qu'il puisse se déplacer librement horizontalement. La carte de la maison est une grille aléatoire de 11 x 5 avec différents éléments et des murs infranchissables à l'extrême gauche, à l'extrême droite et parfois dans l'une des deux positions centrales:

Ma question: comment puis-je m'assurer que la carte est toujours aléatoire mais toujours résoluble et que le héros, en commençant par le côté gauche de l'étage inférieur, peut toujours la quitter via n'importe quel ascenseur pointant vers le haut au dernier étage?

Pour ce que ça vaut, j'utilise le langage Lua pour le développement. Merci beaucoup!

Ce que vous voulez faire, c'est créer un graphique de telle sorte que chaque nœud soit une position d'élévateur, et les bords entre eux signifient que vous pouvez y marcher / soulever. Une fois que vous avez créé le graphique, vous pouvez utiliser dfs / bfs pour voir si vous pouvez passer du nœud de début au nœud de fin.

En utilisant votre exemple ci-dessus, j'ai fait une image de la façon dont le graphique ressemblerait. Les cercles verts signifient qu'il y a un ascenseur et les lignes vertes signifient que vous pouvez voyager d'un nœud à l'autre.

La différence entre ce que vous avez et un labyrinthe normal est simplement qu'il a des connexions non adjacentes verticalement. Je pense que ce que vous devriez regarder, ce sont des algorithmes de génération de labyrinthe basés sur des graphiques . Vous avez simplement besoin d'avoir un plus grand ensemble de «pièces adjacentes» ou de «murs possibles» que ne le fait un labyrinthe 2D ordinaire, en ce que chaque paire de cellules de grille de sol alignées verticalement qui n'a pas déjà d'ascenseur intermédiaire est adjacente. Vous pouvez modéliser cela sous forme de graphique où l'ajout d'arêtes de levage définies supprime accidentellement d'autres arêtes de levage possibles; certains algorithmes peuvent être confondus par cela, mais pas d'autres.