Habaki

Un labyrinthe numérique peut être représenté par une grille de nombres.

Chaque nombre d'une case donne la valeur du saut que l'on peut effectuer à partir de cette case vers une autre case.

Seuls les sauts verticaux et horizontaux sont autorisés, et en ligne droite (pas de coudes).

J'ai découvert ce type de labyrinthe par PhR Sensei link qui semble bien les avoir inventé (s'il existe une référence antérieure ailleurs, elle reste inconnue).

Bien entendu, avant d'utiliser un script, il vaut mieux essayer manuellement  de trouver une solution.  

Voici un exemple de parcours d'un tel labyrinthe:

Les cases marquées D servent de départ ( le saut à partir de ces cases vaut 1).  

Les cases marquées A représentent l'arrivée.

La coordonnée X est horizontale de gauche à droite (1..XMax)

La coordonnée Y est verticale de haut en bas (1..YMax)

La définition du labyrinthe est inscrite entre les lignes de tirets:

MAZE by PhR
|-X
Y
----------
DD2213
314312
322221
143124
212421
1412AA
----------
Start: X=2, Y=1
X=2, Y=2
X=3, Y=2
X=3, Y=6
X=4, Y=6
X=4, Y=4
X=5, Y=4
X=5, Y=6

Ce parcours a été calculé par le script qui suit.

Il n'y a pas d'optimisation particulière. Le script recherche un chemin à partir de l'arrivée et s'arrête dès qu'il en trouve un.

Le script contient directement, au début, la definition du labyrinthe et le chemin du fichier à remplir avec une solution.

Il doit donc être modifié pour choisir un autre labyrinthe ou un autre fichier.

Pour plus de labyrinthes suivez link. Allez voir aussi le Forum Photoshop-School link.  

/************************************************************************
   LABYRINTHE NUMERIQUE
 ************************************************************************
 Chaque case contient la valeur du saut autorise vers une autre case
 (Verticalement ou horizontalement seulement).
 D signale une case depart (start point).
 A signale une case d'arrivee (end point).
 ************************************************************************
 14/05/2020 Habaki V1r01 : Creation
 ************************************************************************/
var ScriptName = "Labyrinthe Numerique";

var Verbose = 0;
// To store the result
var FilePath = "/c/images/photoshop/psschool/maze/Maze.txt";
/*----------------------------------------------------------------------*
   Maze definition
  in a string
 *----------------------------------------------------------------------*/
// Chaque ligne (separee par \n) decrit une ligne du labyrinthe
// Each line (separated by \n) describes a line of the maze.

// This Maze was created by PhR (c)
var MazeSt = "DD2213\n314312\n322221\n143124\n212421\n1412AA";
var Author = "PhR";
/*----------------------------------------------------------------------*
   Vars
 *----------------------------------------------------------------------*/
var Maze = MazeSt.split("\n"); // Maze array
var SizeX = Maze[0].length; // Maze size (X)
var SizeY = Maze.length; // Maze size (Y)
var MaxJmp;   // Max jmp allowed in the maze
var NbMax = 50;   // Max nb of nodes in  a path
var Path = new Array();  // List of encountered nodes
var PathFile;   // File to record the Path
var Starts;   // List of start nodes
var Ends;   // List of end nodes

var Nb = 0;
/*----------------------------------------------------------------------*
   Record Path
 *----------------------------------------------------------------------*/
function PathRecord(XY)
{
  if (XY[2] == 0)
    PathFile.writeln("X=" + XY[0] + ", Y=" + XY[1]);
}
/*----------------------------------------------------------------------*
                        From
 Move backwards
 Returns 0 if D is not found, else 1
 *----------------------------------------------------------------------*/
function From(XY)
{
  var x, y, n;
  var X = XY[0];
  var Y = XY[1];
  var jmp;
  var res;
 
  for (n=0;n < Nb; n++) {
    if (Path[n][0] == X && Path[n][1] == Y) return(0);
  } // for
 
  if (Nb >= NbMax) return(0);
  Nb++;
  Path[Nb-1] = XY;
 
  if (Verbose) alert("From:" + Nb + ", X=" + X + ", Y=" + Y);
 
  y = Y;
  for (x =  (MaxJmp >= X ? 1: X-MaxJmp);
       x <= (X+MaxJmp >= SizeX ? SizeX: X+MaxJmp);
       x++) {
    if (x == X) continue;
    jmp = Maze[y-1][x-1];
    if (jmp == "A") continue;
    if (jmp == "D" && (x == X+1 || x == X-1)) {
      if (Verbose) alert("Got it: " + "(" + x + "," + y + ")" + " " + Nb + " Steps");
      Path[Nb] = new Array(x, y, 0);
      return(1);
    }
    jmp = parseInt(jmp);
    if (x == X-jmp || x == X+jmp) {
      res = From(new Array(x, y, 0));
      if (res==1) return(res);
    }
  } //for
  x = X;
  for (y =  (MaxJmp >= Y ? 1: Y-MaxJmp);
       y <= (Y+MaxJmp >= SizeY ? SizeY: Y+MaxJmp);
       y++) {
    if (y == Y) continue;
    jmp = Maze[y-1][x-1];
    if (jmp == "A") continue;
    if (jmp == "D" && (y == Y+1 || y == Y-1)) {
      if (Verbose) alert("Got it: " + "(" + x + "," + y + ")" + " " + Nb + " Steps");
      Path[Nb] = new Array(x, y, 0);
      return(1);
    }
    jmp = parseInt(jmp);
    if (y == Y-jmp || y == Y+jmp) {
      res = From(new Array(x, y, 0));
      if (res == 1) return(res);
    }
  } //for
  if (Verbose) alert("Dead end: " + "(" + x + "," + y + ")" + " " + Nb + " Steps");
  XY[2] = 1; // Nowhere to go
  return(0);
}
/*----------------------------------------------------------------------*
   Main
 *----------------------------------------------------------------------*/
try {
 
  var x, y, n;
  var XY
 
  // Maximum jmp length
  MaxJmp = 0;
  Starts = new Array();
  Ends = new Array();
  for (x=1; x <= SizeX; x++) {
    for (y=1; y <= SizeY; y++) {
      n = Maze[y-1][x-1];
      if (n == "D") {
        Starts[Starts.length] = new Array(x,y,0);
      } else
      if (n == "A") {
        Ends[Ends.length] = new Array(x,y,0);
      } else {
        n = parseInt(n);
        if (n > MaxJmp) MaxJmp = n;
      }
    }
  } // for
  //if (Verbose)
    alert("MAZE by " + Author + "\n"
        + "Width=" + SizeX
        + ", Height=" + SizeY
        + "\nStart(s)=" + Starts.length
        +   ", End(s)=" + Ends.length
        + "\nMaximum jump=" + MaxJmp
        , ScriptName);
 
  // Scan
  Nb = 0;
  for (n=0;n < Ends.length;n++) {
    res = From(Ends[n]);
    if (res==1) break;
  } /* for */
 
  // Record Path from start into a File
  PathFile = File(FilePath);
  alert("Maze soluce recorded into: " + FilePath);
  PathFile.open("w");
  PathFile.write("MAZE by " + Author + "\n");
  PathFile.write("|-X\nY\n");
  PathFile.write("----------\n");
  PathFile.write(MazeSt);
  PathFile.write("\n----------\n");
  PathFile.write("Start: ");
  for (n = Path.length; n ; n--) {
    PathRecord(Path[n-1]);
  } /* for */
  PathFile.close();
 
} catch (ex) {
  alert(ex.message, ScriptName);
}