[Back to MISC SWAG index] [Back to Main SWAG index] [Original]

    (* 30-8-97 : Solve 'Maze' With the Start and the End Position *)
    (* By RRC2 (Ramon/Rodrigo Roman Castro) Soft, Malaga, Spain. *)
    (*  - For: RPG programmers in every languages // Programadores de JDR.
        - Used in : BP 7.0.
        - Status : FreeWare, Can be Changed if You want.
        - Request : If you use it, please put our name in the credits.
        - Disclaimer : Code Full Tested. We aren't responsible of the damage
       that this code can do in your computer.
        - Sorry : We have a very bad English.
        - Comments :They're in English and Spanish. I'm Spanish, and Spanish is in
       the first five languages talken on the world, Did you know ?. Learn It!.
        - ATTENTION: I Don't Know if this Algorithm have been created before our
       discovery, but I don't see it on Anywhere. *)

    (*  Imagine that you are making an RPG Game and you need a way
       enemies->objetives ( The Players ) in a maze structure.
        We have discovered an algorithm that can give a way to bad guys in
       a Rectangular map with or within Obstacles.
       This is.....

       THE MONIGOTES ALGORITHM
       =======================
       It's based in BackTracking Algorithm.
         Think that in every position of the terrain there's a byte that shows
       a direction:       1 North
                      4 West 2 East
                          3 South
         We start with the idea that my initial position in the terrain is a
       monigote (rag figure, I Think), and when it can, it expands himself wri-
       ting this directions in the terrain:
                     3                      1
                   2 M 4 -> We don't write 4 2 (We must find the way Obj->BG, see:
                     1                      3   Now, What we have?)
         It Can't expand if there's an wall or another direction written in the
       square we wanted to go.
       Now we start with a loop:
       -------------------------
         The directions previously created ( in the previous loop ) transforms
       into monigotes, and they expand themselves (see above).
         This loop ends when a monigote is beside the objective.
       Example:
       --------                    3          33         33
                        3         234        2344       2344     B = Bad Guy
             B W       2M4W       2M4W       2M4W       2M4W     O = Objective
          O    ->    O  1  ->   O  1   ->  O  1   ->  O  11      M = Monigote
                                                                 W = Wall
        No Loop     1¦ Loop         2¦    L   o   o   p.........

       Now, What we have?
       ------------------
         We have in the terrain the way Objective->Badguy written. So, starting
       in the position of the monigote that were beside the Obj., we find this
       way, put it into a vector, change the directions and put the vector
       in a new vector with interchanging beginning and end ( We want BadGuy->
       Objetive ! ).
       What returns algorithm
       ----------------------
         A vector with the way BadGuy->Objetive. You can't take a Wrong Way.
       Tehcnical Details
       -----------------
       --Who are the directions that I need to transform into monigotes?
         They're in a Linked List, PuntActuales, So we transform them into
       monigotes and next they're cleared.
       --And the directions created?
         They're also in another Linked List, SigPunteros. It will transform into
       PuntActuales in the start of the a loop.
       Praise( Ja,Ja ;) )
       ------------------
       It's a Finstro of algorithm !. (Finstro:Word that means nothing in English,
       and nothing in Spanish ! [ Viva Chiquito de la Calz� :) ])
       Disclaimer
       ----------
         This algorithm was created in 30-8-97, 11:00->4:00(night), so if it
       isn't optimal, sorry.
    *)

    Program AlgoritmoMonigotes;

    Uses Crt;

    Const MAXMOV          = 30; (* The maximum movements I Can do *)
          MAXIMO          = 20; (* Dimensions of the Terrain *)
          INIX            = 1; (* X Coordinate of the Bad Guy *)
          INIY            = 12; (* Y Coordinate of the Bad Guy *)
          OBJX            = 15;  (* X Coordinate of the Objective *)
          OBJY            = 9; (* Y Coordinate of the Objective *)
          DISTANCIAMAXIMA = 1;  (* Reserved *)

    Type  TSolucion = Array[1..MAXMOV] Of Integer; (* Vector with Solution *)
          TPantalla = Array[1..MAXIMO,1..MAXIMO] Of Byte; (* Terrain *)
          TPosicion = Record (* Position in X and Y *)
                        X,Y:Integer;
                      End;

    (* Maze-Type Terrain *)
    Const Pantalla:TPantalla =
    ((1,1,1,9,1,1,1,9,1,1,1,1,9,1,9,1,1,1,1,1),
     (1,1,1,1,1,9,1,1,1,1,9,9,9,1,9,9,9,9,1,1),
     (9,1,1,1,1,1,1,1,1,1,9,9,9,1,9,1,1,9,9,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,9,1),
     (1,1,9,1,1,1,1,9,1,1,9,1,9,9,1,1,1,9,1,1),
     (1,1,1,1,1,9,1,9,1,1,1,1,1,1,1,1,1,9,1,1),
     (9,1,1,1,9,9,1,9,9,9,9,9,1,9,9,1,1,9,1,9),
     (1,1,1,1,1,1,1,1,1,9,1,1,1,1,1,1,1,1,1,9),
     (9,1,9,1,1,9,1,9,1,1,1,1,9,1,1,9,9,1,9,9),
     (1,1,9,1,1,9,1,1,9,1,1,1,9,1,1,1,9,1,9,1),
     (9,1,1,1,1,1,1,1,9,1,1,1,9,1,9,1,1,1,1,1),
     (1,1,1,1,9,9,9,1,1,1,9,1,9,1,9,9,9,9,1,1),
     (1,1,9,1,1,9,1,1,1,1,9,1,9,1,9,1,1,9,9,1),
     (9,1,9,1,1,9,1,9,9,1,1,1,1,1,1,1,1,1,9,9),
     (1,1,9,1,9,9,1,9,1,9,9,9,9,9,9,1,1,9,1,1),
     (9,1,9,1,1,1,1,9,1,1,1,1,1,1,1,1,1,1,1,1),
     (9,1,9,9,9,9,1,1,9,9,9,9,9,9,9,1,1,9,9,9),
     (1,1,1,1,9,1,1,1,1,9,1,1,1,1,1,1,1,1,1,9),
     (1,1,1,1,1,1,1,1,1,9,1,1,1,1,1,1,1,1,1,9),
     (9,9,9,9,9,9,9,1,9,9,9,9,9,9,9,9,9,9,9,9));

    (* Terrain Within Obstacles *)
    (* Const Pantalla:TPantalla =
    ((1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),
     (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1));*)

    Var   Fondo        :TPantalla;
          Mov          :Integer;
          MovTotal     :Integer;
          Exito        :Boolean;
          Ini,Obj      :TPosicion;
          i            :Integer;
          Solucion     :TSolucion;

    (* This procedure create the terrain with the Const Pantalla *)
    Procedure InicializarPantallas;
    Var i,j:Byte;
        Pant:TPantalla;
    Begin
      Fondo:=Pantalla;
    End;

    (* This procedure Paints the Terrain onto the screen *)
    Procedure PintarPantallas;
    Var i,j:Byte;
    Begin
      For i:=1 to MAXIMO Do
          For j:=1 to MAXIMO Do
              Begin
                GotoXy(i,j);
                Case Fondo[i,j] Of
                   1:Write('°');
                   9:Begin
                       TextColor(RED);
                       Write('Û');
                       TextColor(LIGHTGRAY);
                     End;
                End;
              End;
      GotoXY(OBJX,OBJY);Write(CHR(1));
      GotoXY(INIX,INIY);Write('Y');
    End;

    (* This procedure paints the solution given in the vector Solucion *)
    Procedure PintarMovimientos(Solucion:TSolucion;MovTotal:Integer);
    Var Pos:TPosicion;
        i:Integer;
    Begin
      Pos:=INI;
      For i:=1 to MovTotal Do
          Begin
            Case Solucion[i] Of
                 1:Dec(Pos.Y);
                 2:Inc(Pos.X);
                 3:Inc(Pos.Y);
                 4:Dec(Pos.X);
            End;
            GotoXy(Pos.X,Pos.Y);
            TextColor(DarkGray);
            Case Fondo[Pos.X,Pos.Y] Of
                 1:Write('°');
            End;
            TextColor(LightGray);
          End;
    End;

    (* This function says if I can Step On a Square *)
    Function SiPisar(ActualX,ActualY:ShortInt):Boolean; (* ¨ Puedo Pisar ? *)
    Begin
      SiPisar:= (ActualX>0) And (ActualX<=MAXIMO) And
                (ActualY>0) And (ActualY<=MAXIMO) And
                (Fondo[ActualX,ActualY] <> 9); (* 9-> Wall // Muro *)
    End;

    (*-----------------------------------------------------------------------*)
    (*------------------ALGORITHM//ALGORITMO---------------------------------*)
    (*-----------------------------------------------------------------------*)
    (*   BusqMonigote: The Algorithm. Returns TRUE if there's a way
           \-----> Devuelve si hay un camino
       Inicio: is the position of the Bad Guy, // Pos. Malo
       Objetivo: is the objective position, // Posicion objetivo
       PMov: is the squares you can move, // Casillas que puedo mover
       VAR Solucion: is the vector with the solution, // Array con la solucion
       VAR Movtotal: is the movements you have Done, // Movimientos realizados
       Fondo: is the Terrain // El terreno donde nos movemos
    *)
    Function BusqMonigote(Inicio,Objetivo:TPosicion;PMov:Integer;
                          Var Solucion:TSolucion;Var MovTotal:Integer;
                          Fondo:TPantalla):Boolean;

    Const MAYOR = (MAXIMO*MAXIMO)+1;
    Type PRegistro     = ^TRegistro;
         TLista        = PRegistro;
         TElemento     = TPosicion;
         TRegistro     = Record
                          Zona:TElemento;
                          Sig:TLista;
                         End;
         TAlgMonigote  = Array[1..MAXIMO,1..MAXIMO] Of Byte;

         TRejSolucion  = Array[1..MAYOR] Of Integer; (* Guardo Solucion Total *)
         (* Saves the entire Way *)
       (* Asi encuentra hasta el camino mas raro *)
       (* With this vector it can find even the strangest Way *)

    Var PuntActuales:TLista;
        SigPunteros:TLista;
        Actual:TPosicion;
        Indice:TLista;
        AlgMonigote:TAlgMonigote;
        PosVictoria:TPosicion;
        SolucionTmp:TRejSolucion;
        Contador:Integer;
        CBucle:Integer;
        Contador2:Integer;

    (* Distancia measure the distance | Mide distancia entre blanco y objetivo *)
        Function Distancia(ActualX,ActualY:ShortInt;Objetivo:TPosicion):Byte;
        Begin
          Distancia:=Abs(ActualX-Objetivo.X)+Abs(ActualY-Objetivo.Y);
        End;

        (* Initiate vars and pointers *)
        Procedure InicializoListasYVariables;
        Var x,y:Integer;
        Begin
         PuntActuales:=NIL;
         SigPunteros:=NIL;
         Indice:=NIL;
         Actual:=Inicio;
         PosVictoria.X:=MAXIMO+1;
         PosVictoria.Y:=MAXIMO+1;
         For x:=1 To MAXIMO Do
             Solucion[x]:=0;
         For x:=1 To MAYOR Do
             SolucionTmp[x]:=0;
         For x:=1 To MAXIMO Do
             For y:=1 To MAXIMO Do
              Begin
                AlgMonigote[x,y]:=0;
              End;
        End;

    (* Here stars Procedures of Pointers and Linked Lists *)
        (* Insert_Begin // Inserta en el frente de una lista enlazada *)
        Procedure MeterFrente(Var Lista:TLista;Ele:TElemento);
        Var Tmp:TLista;
        Begin
          New(Tmp);
          Tmp^.Zona:=Ele;
          Tmp^.Sig:=Lista;
          Lista:=Tmp;
        End;

        (* Pop_Begin // Saca un elemento del inicio de la lista enlazada *)
        Procedure SacarFrente(Var Lista:TLista;Var Ele:TElemento);
        Var Tmp:TLista;
        Begin
          If Lista<>NIL Then
             Begin
              Tmp:=Lista;
              Lista:=Tmp^.Sig;
              Ele:=Tmp^.Zona;
              Dispose(Tmp);
             End;
        End;

        (* Eliminate List // Elimina la lista enlazada *)
        Procedure EliminoLista(Var Lista:TLista);
        Var Tmp:TLista;
        Begin
          While Lista<>NIL Do
            Begin
                Tmp:=Lista;
                Lista:=Tmp^.Sig;
                Dispose(Tmp);
            End;
        End;
    (* End of Linked List Procedures and Functions *)

        (* Procedure that writes the directions when monigotes are expanding *)
        Procedure ComprobarBordes(Pos:TPosicion;Var AlgMonigote:TAlgMonigote;
                                  Var PosVictoria:TPosicion);
        Var EleTmp:TPosicion;
        Begin
             (* Check Distance // Chequea la distancia al objetivo *)
             If (Distancia(Pos.X,Pos.Y,Objetivo) <= DISTANCIAMAXIMA) And
                (Distancia(Pos.X,Pos.Y,Objetivo) <> 0) Then
                PosVictoria:=Pos
             Else
             Begin
          (*1*)If SiPisar(Pos.X,Pos.Y-1) And
                  (AlgMonigote[Pos.X,Pos.Y-1]=0) Then
                Begin
                  AlgMonigote[Pos.X,Pos.Y-1]:=3;
                  EleTmp.X:=Pos.X;
                  EleTmp.Y:=Pos.Y-1;
                  MeterFrente(SigPunteros,EleTmp);
                End;
          (*2*)If SiPisar(Pos.X+1,Pos.Y) And
                  (AlgMonigote[Pos.X+1,Pos.Y]=0) Then
                Begin
                  AlgMonigote[Pos.X+1,Pos.Y]:=4;
                  EleTmp.X:=Pos.X+1;
                  EleTmp.Y:=Pos.Y;
                  MeterFrente(SigPunteros,EleTmp);
                End;
          (*3*)If SiPisar(Pos.X,Pos.Y+1) And
                  (AlgMonigote[Pos.X,Pos.Y+1]=0) Then
                Begin
                  AlgMonigote[Pos.X,Pos.Y+1]:=1;
                  EleTmp.X:=Pos.X;
                  EleTmp.Y:=Pos.Y+1;
                  MeterFrente(SigPunteros,EleTmp);
                End;
          (*4*)If SiPisar(Pos.X-1,Pos.Y) And
                  (AlgMonigote[Pos.X-1,Pos.Y]=0) Then
                Begin
                  AlgMonigote[Pos.X-1,Pos.Y]:=2;
                  EleTmp.X:=Pos.X-1;
                  EleTmp.Y:=Pos.Y;
                  MeterFrente(SigPunteros,EleTmp);
                End;
             End;
        End;

    Begin
      InicializoListasYVariables;
      (* Pongo las primeras direciones // Puts the First Directions *)
      ComprobarBordes(Inicio,AlgMonigote,PosVictoria);

    (* INICIO ALGORITMO // ALGORITHM STARTS *)
      (* Chequeo PosVictoria o fin del chequeo *)
      While ((PosVictoria.X=MAXIMO+1) And (PosVictoria.Y=MAXIMO+1)) And
            (SigPunteros<>NIL) Do
        Begin
          EliminoLista(PuntActuales);
          PuntActuales:=SigPunteros;
          SigPunteros:=NIL;
          (* Salgo al encontrar el 1§ o ninguno *)
          While (PuntActuales<>NIL) And
                ((PosVictoria.X=MAXIMO+1) And (PosVictoria.Y=MAXIMO+1)) Do
            Begin
              SacarFrente(PuntActuales,Actual);
              ComprobarBordes(Actual,AlgMonigote,PosVictoria);
            End;
        End; (* Fin del Algoritmo en Si *)
      EliminoLista(PuntActuales);
      EliminoLista(SigPunteros);
    (* FIN DEL ALGORITMO // ALGORITHM ENDS *)

    (*   Ahora paso la solucion al Array Solucion. Escribo el camino completo en
       SolucionTmp ( Invirtiendo las direcciones, ya que busco de principio a
       fin ) y luego escribo en Solucion "Invirtiendo el vector" *)
    (*   Now I pass the Solution ( It's in the AlgMonigote Vector ) to Solucion,
       using SolucionTmp (-> It Have the entire Way ) like a bridge *)

      If (PosVictoria.X=MAXIMO+1) And (PosVictoria.Y=MAXIMO+1) Then
         BusqMonigote:=False (* No encontre camino // There's no way *)
      Else Begin (* Encontre camino // There's a way *)
             Actual:=PosVictoria;
             Contador:=1;
             While (Actual.X<>Inicio.X) OR (Actual.Y<>Inicio.Y) Do
             (* Busco el camino del final al principio, transformando *)
               Begin
                 Case AlgMonigote[Actual.X,Actual.Y] Of (* Cambio direcciones *)
                      1:SolucionTmp[Contador]:=3;
                      2:SolucionTmp[Contador]:=4;
                      3:SolucionTmp[Contador]:=1;
                      4:SolucionTmp[Contador]:=2;
                 End;
                 Inc(Contador);
                 Case AlgMonigote[Actual.X,Actual.Y] Of
                      1:Dec(Actual.Y);
                      2:Inc(Actual.X);
                      3:Inc(Actual.Y);
                      4:Dec(Actual.X);
                 End;
               End;(* Del While *)(* Saco Contador con el Num. de Movs Total+1 *)

             Contador2:=1;
             For CBucle:=Contador-1 DownTo 1 Do
             (* Ahora cambio direccion del camino de Fin-inicio a Inicio-Fin *)
             (* Meto solo el movimiento que tengo *)
               Begin
                 If (Contador2 <= PMov) And (SolucionTmp[CBucle]<>0) Then
                   Begin
                     Solucion[Contador2]:=SolucionTmp[CBucle];
                     Inc(Contador2);
                   End;
               End; (* Del For *)
             MovTotal:=Contador2-1; (* Mov Realizados *)
             BusqMonigote:=TRUE;
           End;
    End;

    Begin
      TextColor(LightGray);
      Ini.X:=INIX;
      Ini.Y:=INIY;
      Obj.X:=OBJX;
      Obj.Y:=OBJY;
      ClrScr;
      InicializarPantallas;
      PintarPantallas;
      Exito:=BusqMonigote(INI,OBJ,MAXMOV,Solucion,MovTotal,Fondo);
      GotoXy(1,22);
      For i:=1 to Movtotal Do
          Write(Solucion[i]);
      GotoXy(1,23);
      Write('Way finded//Hay camino: ',Exito,'. Movements//Movimientos -> ',MovTotal);
      ReadKey;
      PintarMovimientos(Solucion,MAXMOV);
      ReadKey;
    End.
    (* There's no RPG programmers there?. Contact SWAG, leshe. *)

[Back to MISC SWAG index] [Back to Main SWAG index] [Original]