PImage b;
PFont font;
int x, y;
Knoten [] knoten = new Knoten[ 100 ];
Knoten ausgangsknoten;
Knoten ziel;
int zaehler=0;
Knoten startKnoten;
// Strings?

void setup(){
  size( 634, 759 );
  b = loadImage("Lageplan.gif");
  initialisiere();
}

void mouseClicked(){
  if(ausgangsknoten == null){
    ausgangsknoten = findeNaechstenKnoten();
    ausgangsknoten.markierePunkt();
  }
  else {
    if (ziel == null){
      ziel = findeNaechstenKnoten();
      ziel.markierePunkt();
    }
    suchePfad();
  }
}

public Knoten findeNaechstenKnoten(){
  int zaehler = 2;
  Knoten naechsterKnoten = knoten[1];
  while(zaehler < knoten.length && knoten[zaehler]!= null){
    if(knoten[zaehler].berechneMausDistanz(mouseX, mouseY) < naechsterKnoten.berechneMausDistanz(mouseX, mouseY)){
      naechsterKnoten = knoten[zaehler];
    }
    zaehler++;
  }
  return naechsterKnoten;
}

void draw(){
  image(b,0,0);

  int zaehler = 1;
  while( zaehler < 19){
    knoten[zaehler].zeichneDich();
    zaehler++;
  }
}

void initialisiere(){
  knoten[ 1 ] = new Knoten( "A", 257, 18 );
  knoten[ 2 ] = new Knoten( "B", 297, 229 );
  knoten[ 3 ] = new Knoten( "C", 93, 151 );
  knoten[ 4 ] = new Knoten( "D", 504, 55 );
  knoten[ 5 ] = new Knoten( "E", 515, 677 );
  knoten[ 6 ] = new Knoten( "F", 301, 629 );
  knoten[ 7 ] = new Knoten( "G", 548, 447 );
  knoten[ 8 ] = new Knoten( "H", 328, 374 );
  knoten[ 9 ] = new Knoten( "I", 22, 290 );
  knoten[ 10 ] = new Knoten( "K", 389, 529 );
  knoten[ 11 ] = new Knoten( "L", 603, 234 );
  knoten[ 12 ] = new Knoten( "M", 25, 42 );
  knoten[ 13 ] = new Knoten( "N", 359, 110 );
  knoten[ 14 ] = new Knoten( "O", 200,726  );
  knoten[ 15 ] = new Knoten( "P", 250,445 );
  knoten[ 16 ] = new Knoten( "X", 207, 133 );
  knoten[ 17 ] = new Knoten( "Y", 430, 407  );
  knoten[ 18 ] = new Knoten( "Z", 430, 233 );

  knoten[ 1 ].fuegeKanteHinzu( knoten[ 2 ], 69 );
  knoten[ 1 ].fuegeKanteHinzu( knoten[ 4 ], 36 );
  knoten[ 1 ].fuegeKanteHinzu( knoten[ 12 ], 36 );
  knoten[ 1 ].fuegeKanteHinzu( knoten[ 13 ], 22 );

  knoten[ 2 ].fuegeKanteHinzu( knoten[ 4 ], 64 );
  knoten[ 2 ].fuegeKanteHinzu( knoten[ 8 ], 30 );
  knoten[ 2 ].fuegeKanteHinzu( knoten[ 9 ], 34 );
  knoten[ 2 ].fuegeKanteHinzu( knoten[ 16 ], 26 );
  knoten[ 2 ].fuegeKanteHinzu( knoten[ 18 ], 32 );

  knoten[ 3 ].fuegeKanteHinzu( knoten[ 9 ], 40 );
  knoten[ 3 ].fuegeKanteHinzu( knoten[ 12 ], 31 );
  knoten[ 3 ].fuegeKanteHinzu( knoten[ 16 ], 23 );

  knoten[ 4 ].fuegeKanteHinzu( knoten[ 11 ], 95 );
  knoten[ 4 ].fuegeKanteHinzu( knoten[ 13 ], 20 );

  knoten[ 5 ].fuegeKanteHinzu( knoten[ 6 ], 79 );
  knoten[ 5 ].fuegeKanteHinzu( knoten[ 7 ], 60 );
  knoten[ 5 ].fuegeKanteHinzu( knoten[ 10 ], 31 );
  knoten[ 5 ].fuegeKanteHinzu( knoten[ 14 ], 102 );

  knoten[ 6 ].fuegeKanteHinzu( knoten[ 10 ], 29 );
  knoten[ 6 ].fuegeKanteHinzu( knoten[ 14 ], 14 );
  knoten[ 6 ].fuegeKanteHinzu( knoten[ 15 ], 57 );

  knoten[ 7 ].fuegeKanteHinzu( knoten[ 10 ], 58 );
  knoten[ 7 ].fuegeKanteHinzu( knoten[ 11 ], 58 );
  knoten[ 7 ].fuegeKanteHinzu( knoten[ 17 ], 30 );

  // H
  knoten[ 8 ].fuegeKanteHinzu( knoten[ 9 ], 65 );
  knoten[ 8 ].fuegeKanteHinzu( knoten[ 10 ], 31  );
  knoten[ 8 ].fuegeKanteHinzu( knoten[ 11 ], 106 );
  knoten[ 8 ].fuegeKanteHinzu( knoten[ 15 ], 34 );
  knoten[ 8 ].fuegeKanteHinzu( knoten[ 17 ], 29 );

  // I
  knoten[ 9 ].fuegeKanteHinzu( knoten[ 12 ], 43 );
  knoten[ 9 ].fuegeKanteHinzu( knoten[ 15 ], 55 );

  // K
  knoten[ 10 ].fuegeKanteHinzu( knoten[ 15 ], 25 );
  knoten[ 10 ].fuegeKanteHinzu( knoten[ 17 ], 20 );

  // L
  knoten[ 11 ].fuegeKanteHinzu( knoten[ 18 ], 40 );

  // M
  knoten[ 12 ].fuegeKanteHinzu( knoten[ 16 ], 12 );

  // N
  knoten[ 13 ].fuegeKanteHinzu( knoten[ 16 ], 29 );
  knoten[ 13 ].fuegeKanteHinzu( knoten[ 18 ], 30 );

  // O
  knoten[ 14 ].fuegeKanteHinzu( knoten[ 15 ], 91 );

  //Y
  knoten[ 17 ].fuegeKanteHinzu( knoten[ 18 ], 23 );

  // Zurueck
  knoten[ 2 ].fuegeKanteHinzu( knoten[ 1 ], 69 );
  knoten[ 4 ].fuegeKanteHinzu( knoten[ 1 ], 36 );
  knoten[ 12 ].fuegeKanteHinzu( knoten[ 1 ], 36 );
  knoten[ 13 ].fuegeKanteHinzu( knoten[ 1 ], 22 );

  // B
  knoten[ 4 ].fuegeKanteHinzu( knoten[ 2 ], 64 );
  knoten[ 8 ].fuegeKanteHinzu( knoten[ 2 ], 30 );
  knoten[ 9 ].fuegeKanteHinzu( knoten[ 2 ], 34 );
  knoten[ 16 ].fuegeKanteHinzu( knoten[ 2 ], 26 );
  knoten[ 18 ].fuegeKanteHinzu( knoten[ 2 ], 32 );

  //C
  knoten[ 9 ].fuegeKanteHinzu( knoten[ 3 ], 40 );
  knoten[ 12 ].fuegeKanteHinzu( knoten[ 3 ], 31 );
  knoten[ 16 ].fuegeKanteHinzu( knoten[ 3 ], 23 );

  // D
  knoten[ 11 ].fuegeKanteHinzu( knoten[ 4 ], 95 );
  knoten[ 13 ].fuegeKanteHinzu( knoten[ 4 ], 20 );

  // E
  knoten[ 6 ].fuegeKanteHinzu( knoten[ 5 ], 79 );
  knoten[ 7 ].fuegeKanteHinzu( knoten[ 5 ], 60 );
  knoten[ 10 ].fuegeKanteHinzu( knoten[ 5 ], 31 );
  knoten[ 14 ].fuegeKanteHinzu( knoten[ 5 ], 102 );

  // F
  knoten[ 10 ].fuegeKanteHinzu( knoten[ 6 ], 29 );
  knoten[ 14 ].fuegeKanteHinzu( knoten[ 6 ], 14 );
  knoten[ 15 ].fuegeKanteHinzu( knoten[ 6 ], 57 );

  // G
  knoten[ 10 ].fuegeKanteHinzu( knoten[ 7 ], 58 );
  knoten[ 11 ].fuegeKanteHinzu( knoten[ 7 ], 58 );
  knoten[ 17 ].fuegeKanteHinzu( knoten[ 7 ], 30 );

  // H
  knoten[ 9 ].fuegeKanteHinzu( knoten[ 8 ], 65 );
  knoten[ 10 ].fuegeKanteHinzu( knoten[ 8 ], 31  );
  knoten[ 11 ].fuegeKanteHinzu( knoten[ 8 ], 106 );
  knoten[ 15 ].fuegeKanteHinzu( knoten[ 8 ], 34 );
  knoten[ 17 ].fuegeKanteHinzu( knoten[ 8 ], 29 );

  // I
  knoten[ 12 ].fuegeKanteHinzu( knoten[ 9 ], 43 );
  knoten[ 15 ].fuegeKanteHinzu( knoten[ 9 ], 55 );

  // K
  knoten[ 15 ].fuegeKanteHinzu( knoten[ 10 ], 25 );
  knoten[ 17 ].fuegeKanteHinzu( knoten[ 10 ], 20 );

  // L
  knoten[ 18 ].fuegeKanteHinzu( knoten[ 11 ], 40 );

  // M
  knoten[ 16 ].fuegeKanteHinzu( knoten[ 12 ], 12 );

  // N
  knoten[ 16 ].fuegeKanteHinzu( knoten[ 13 ], 29 );
  knoten[ 18 ].fuegeKanteHinzu( knoten[ 13 ], 30 );

  // O
  knoten[ 15 ].fuegeKanteHinzu( knoten[ 14 ], 91 );

  //Y
  knoten[ 18 ].fuegeKanteHinzu( knoten[ 17 ], 23 );


  //ausgangsknoten= knoten[ 9 ];
  //ziel = knoten[ 14 ];
}

void suchePfad(){
  println( "Start: " + ausgangsknoten.name + " Ziel: " + ziel.name );

  Warteschlange ws = new Warteschlange();
  ws.fuegeKnotenEin(ausgangsknoten);

    while(ws.gibErstesElementZurueck()!=ziel){
    Knoten bearbeiten = ws.gibErstesElementZurueck();
    bearbeiten.markiereKnoten();
    ws.entferneKnoten(bearbeiten);

    Kante [] aktuelleKanten = bearbeiten.kanten;

      int zaehler = 0;
    while( zaehler < aktuelleKanten.length && aktuelleKanten[zaehler] != null){
      Knoten aktuellerKnoten = aktuelleKanten[zaehler].nachbar; // Knoten werden als Nachbarn hinzugefuegt
      if(aktuellerKnoten.istMarkiert() == false){
        if(aktuellerKnoten.gibEntfernungZurueck() > bearbeiten.gibEntfernungZurueck() + aktuelleKanten[zaehler].entfernung || aktuellerKnoten.gibEntfernungZurueck() == 0){
          aktuellerKnoten.entfernung = bearbeiten.gibEntfernungZurueck() + aktuelleKanten[zaehler].entfernung;
          aktuellerKnoten.vorgaengerImPfad = bearbeiten;
        }
        ws.entferneKnoten(aktuellerKnoten);
        ws.fuegeKnotenEin(aktuellerKnoten);
      }
      zaehler++;
    }
  }


  if( ws.gibErstesElementZurueck() == ziel ){
    println( "Der kuerzeste Weg ist:" );
    ziel.gibPfadAus();
  }
}