Habaki

Un précédent article décrit les labyrinthes numériques définis dans une grille.

Comme le démontre filR Sensei link, il est possible d'en construire sur des géométriques plus excentriques. Comme par exemple l'une de ses créations:

Dans ces conditions, le codage du labyrinthe pour le script devient plus complexe. Ce n'est plus une simple grille.

J'ai choisi de construire un tableau des lignes que l'on peut parcourir en avant ou en arrière, sans coude.

Chaque ligne est un tableau qui restitue la suite des cases qui la compose.

Dans chaque élément, est codée la valeur du saut autorisée, ainsi qu'une éventuelle intersection avec une autre ligne.

Pour une intersection j'ajoute le numéro de la ligne qui intersecte ainsi que l'indice où a lieu l'intersection selon :

(ligne *100 + Indice) *100.

Pour l'image ci-dessus cela donne :

 // This Maze was created by filR (c) : Tortue
var Maze = new Array(                                        //Lines
  new Array("C",20202,1,6,31001,3,2,4,1,41002,4,6,21003,
            3,5,40202,2,5,1,2,30204,3,5),                    //1 circular
  new Array("A", 10202,2,5,30603,50203,40605,2,2,11303,"D"), //2
  new Array(6,12104,1,3,60102,20503,70106,3,5,10501,3),      //3
  new Array(4,11602,2,3,60301,20705,70304,1,2,11002,6),      //4
  new Array(60202,20603,70202),                              //5
  new Array(30502,50102,40501),                              //6
  new Array(30706,50302,40704)                               //7
  );

La première ligne est le cercle.

La deuxième est verticale et contient départ et Arrivée.

Le troisième est les pattes avant de la tortue.

Etc...

Voici une solution exprimée en une suite de positions par No de Ligne, Index dans la ligne:

MAZE by filR
----------
Start: L=2, Idx=11
L=2, Idx=10
L=1, Idx=16
L=1, Idx=14
L=1, Idx=11
L=1, Idx=7
L=1, Idx=5
L=3, Idx=11
L=3, Idx=8
L=3, Idx=5
L=3, Idx=3
L=3, Idx=2
L=3, Idx=6
L=2, Idx=8
L=2, Idx=6
L=2, Idx=3
End: L=2, Idx=1

Et voici le scrpt qui calcule les solutions .

Les solutions sont écrites dans des fichiers numérotés dont le chemin est donné dans FilePath.

/************************************************************************
   LABYRINTHE NUMERIQUE
 ************************************************************************
 Le labryrinthe est constitue d'une suite de lignes.
 Chaque ligne contient des cases.
 Dans cette version 2 les cases contiennent egalement les intersections
 avec d'autres lignes.
 Chaque case contient la valeur du saut autorise vers une autre case
 en avant, en arriere ou, sur une intersection, a gauche ou a droite.
 D signale une case depart (start point).
 A signale une case d'arrivee (end point).
 C en 1ere case signale que la ligne est circulaire.
 ************************************************************************
 20/12/2010 Habaki V2r02 : Toutes les solutions
 16/12/2010 Habaki V2r01 : Lignes
 14/05/2010 Habaki V1r01 : Creation
 ************************************************************************/
var ScriptName = "Labyrinthe Numerique II";

var Verbose = 1;
var SoluceNbMax = 10;  // Max nb of soluces to compute

// To store the result: FilePath + <SoluceNum> + ".txt"
var FilePath = "/c/images/photoshop/scripts/maze/Maze";
/*----------------------------------------------------------------------*
   Maze definition
 *----------------------------------------------------------------------*/
// Maze values at a position in a line :
//   Jump value
// + Intersection index * 100 in this line
// + Intersection line  * 10000
// + Already scaned (0,1) * 1000000
// Line and Index : [1..N]

// This Maze was created by filR (c) : Tortue
var Maze = new Array(      //Lines
  new Array("C",20202,1,6,31001,3,2,4,1,41002,4,6,21003,
            3,5,40202,2,5,1,2,30204,3,5),   //1 circular
  new Array("A", 10202,2,5,30603,50203,40605,2,2,11303,"D"), //2
  new Array(6,12104,1,3,60102,20503,70106,3,5,10501,3),  //3
  new Array(4,11602,2,3,60301,20705,70304,1,2,11002,6),  //4
  new Array(60202,20603,70202),     //5
  new Array(30502,50102,40501),     //6
  new Array(30706,50302,40704)     //7
  );
var Author = "filR";
/*----------------------------------------------------------------------*
   Vars
 *----------------------------------------------------------------------*/
var MaxJmp;   // Max jmp allowed in the maze
var NbMax = 99;   // Max nb of positions in a line
var PathFile;   // File to record the Path
var Starts;   // List of start positions
var Ends;   // List of end   positions

var Path = new Array();  // Soluce path
var Nb = 0;   // Current Soluce length
var SoluceNb = 0;  // Nb of found Soluces
var PosMax = 0;   // Nb of positions in the maze
var PosNb = 0;   // Nb of Scaned positions
/*----------------------------------------------------------------------*
   Line Value decoding
 *----------------------------------------------------------------------*/
function LineGet(v)
{
  return(Math.floor((v / 10000) % 100));
}
function IdxGet(v)
{
  return(Math.floor((v / 100) % 100));
}
function JmpGet(v)
{
  return(Math.floor(v % 100));
}
function Already(v)
{
  return(Math.floor(v / 1000000) != 0);
}
function AlreadySet(v)
{
  var lj;
 
  if (lj = LineGet(v)) {
    // Also set intersection
    Maze[lj-1][IdxGet(v)-1] += 1000000;
  }
  return(v + 1000000);
}
function AlreadyReset(v)
{
  var lj, vj;
 
  if (lj = LineGet(v)) {
    // Also reset intersection
    vj = Maze[lj-1][IdxGet(v)-1];
    vj = Math.floor(vj % 1000000)
    Maze[lj-1][IdxGet(v)-1] = vj;
  }
  return(Math.floor(v % 1000000));
}
/*----------------------------------------------------------------------*
   Record Path
 *----------------------------------------------------------------------*/
function PathRecord(LI)
{
  PathFile.writeln("L=" + LI[0] + ", Idx=" + LI[1]);
}
/*----------------------------------------------------------------------*
   Record a soluce
 *----------------------------------------------------------------------*/
function SoluceRecord(No)
{
  // Record Path from start into a File
  PathFile = File(FilePath + No + ".txt");
  // The first item is the Start, not a jump (Nb-1)
  alert("Maze soluce No " + No + " in " + (Nb-1) + " Jumps " +
        "\nRecorded into: " + PathFile);
  PathFile.open("w");
  PathFile.write("MAZE by " + Author + "\n");
  PathFile.write("\n----------\n");
  PathFile.write("Soluce " + No + " : ");
  for (n = 0; n < Nb; n++) {
    PathRecord(Path[n]);
  } // for
  PathFile.close();
}
/*----------------------------------------------------------------------*
                        GoTo a position
 Returns 0 if A is not found, else 1
 *----------------------------------------------------------------------*/
function GoTo(
 L,  // Line [1..Maze.length]
 I // Index in Line [1..Line.length]
 )
{
  var l, i, n;
  var val, jmp;
  var res;
  var line;
 
  // LI not inside the Maze : reject
  if (L < 1 || L > Maze.length) return(0);
  line = Maze[L-1];
  if (line[0] == "C") {
    // Circular
    while(I > line.length) I -= line.length-1;
    while(I < 2) I += line.length-1;
  } else {
    if (I > line.length) return(0);
    if (I < 1) return(0);
  }
 
  val  = line[I-1];
  if (val == "A") {
    // Arrivee
    Nb++;
    Path[Nb-1] = new Array(L, I);
    SoluceNb++;
    SoluceRecord(SoluceNb);
    if (SoluceNb > SoluceNbMax) return(1);
    return(0);
  }
  if (val == "D") val = 1; // Depart: default jump ==1
  if (Already(val)) return(0);
  if (Nb >= NbMax) return(0);
 
  PosNb++;
  Nb++;
  Path[Nb-1] = new Array(L, I);
  line[I-1] = AlreadySet(val);
 
  //if (Verbose) alert("GoTo:" + Nb + ", L=" + L + ", I=" + I);
 
  jmp = JmpGet(val);
  res = 0;
 
  // Forward
  res = GoTo(L, I+jmp);
  if (res) return(res);
 
  // Intersection
  if (l = LineGet(val)) {
    i = IdxGet(val);
    // Right
    res = GoTo(l, i+jmp);
    if (res) return(res);
    // Left
    res = GoTo(l, i-jmp);
    if (res) return(res);
  }
 
  // Backward
  res = GoTo(L, I-jmp);
  if (res) return(res);
 
  // Dead End
  Nb--;
  return(0);
}
/*----------------------------------------------------------------------*
   Main
 *----------------------------------------------------------------------*/
try {
 
  var l, i, n, DNum, j, v, line;
  var LI;
 
  // Positions of Starts and Ends
  // Maximum jump length
  MaxJmp = 0;
  Starts = new Array();
  Ends   = new Array();
  for (l=1; l <= Maze.length; l++) {
    line = Maze[l-1];
    if (line.length < 2) {
      alert("Line " + l + " length is too small !");
      Starts = new Array();
      break;
    }
    for (i=1; i <= Maze[l-1].length; i++) {
      n = line[i-1];
      if (n == "D") {
        Starts[Starts.length] = new Array(l,i);
      } else
      if (n == "A") {
        Ends[Ends.length] = new Array(l,i);
      } else
      if (n != "C") {
        j = JmpGet(n);
        if (j > MaxJmp) MaxJmp = j;
        if (!Already(n)) {
          PosMax++;
          line[i-1] = AlreadySet(n);
        }
      }
    }
  } // for
 
  alert("MAZE by " + Author + "\n"
      + "\n" + Starts.length + " D" + " at " + Starts
      + "\n" + Ends.length   + " A"  +  " at " + Ends
      + "\nNb of other positions=" + PosMax
      + "\nMaximum jump=" + MaxJmp
      , ScriptName);
 
  for (DNum=0;DNum < Starts.length;DNum++) {
    Nb = 0;
    PosNb = 0;
    Path = new Array();
    // Reset Already flag
    for (l=1; l <= Maze.length; l++) {
      line = Maze[l-1];
      for (i=1; i <= Maze[l-1].length; i++) {
        v = line[i-1];
        if (v != "D" && v != "A" && v != "C") {
          line[i-1] = AlreadyReset(v);
        }
      }  // for
    } // for
   
    res = GoTo(Starts[DNum][0], Starts[DNum][1]);
 
  } // for
  if (SoluceNb == 0) alert("No Soluce"
                           + "\nExplored positions: " + PosNb
                           );
  else {
    alert(SoluceNb + " Soluce(s). See files"
          + "\nExplored positions: " + PosNb
          );
  }
 
} catch (ex) {
  alert(ex.message, ScriptName);
}