Schleifen bei Niki

[dvor4k]

Hallo,
zurzeit behandeln wir im Informatikunterricht Schleifen in Niki20.
Beispielsweise sollen wir Niki in der folgenden Aufgabe alle Gegenstände aufsammeln und in dem Eck ganz unten rechts ablegen lassen:



Unser Lehrer ist uns dabei um ehrlich zu sein keine große Hilfe, sodass ich hier mal nachfrage:

Wie muss in diesem Fall eine Schleife aussehen, mit der Niki alle Gegenstände aufsammelt und in dem angegebenen Punkt ablegt? (Es geht dabei nicht speziell um dieses Beispiel, sondern um die Form, wie eine Schleife aussehen muss).

MfG, dvor4k

 

[CSANecromancer]

Wenn es um die generelle Schleifenform geht, dann sage ich das mal so:

X und Y sind ja ersichtlich, desweiteren muß der Roboter irgendeine Möglichkeit zur Erkennung der Feldbegrenzung haben und ein definiertes Startfeld haben (sonst wird das viel zu knifflig). Ich setze mal den Roboter auf 0, 0 (links oben).

In der reinen Programmierung würde das mit zwei for-Schleifen gemacht werden (wenn nicht sogar einfach mit foreach abgekürzt wird), aber bei der Robotik fällst du da leider auf die Nase, weil ein physischer Roboter keinen simplen "line feed", kennt, der ihn immer wieder an den Anfang der nächsten Zeile setzt. Daher würde ich ein Programm ungefähr dieser Art verwenden:

var
   direction: Integer;
   x, y: Integer;
   xMax, yMax: Integer;
procedure RunField;
begin
  direction := 1;
  x := 0;
  y := 0;
  xMax := (geeigneter Wert);
  yMax := (geeigneter Wert);

  // diese Schleife durchläuft das Feld von oben nach unten Zeile für Zeile
  while y < yMax do 
  begin
    MacheIrgenwasImFeld;
    // durch dieses kleine Konstrukt wird in jeder Zeile (wir sind ja hier innerhalb der
    // Schleife, welche die Zeilen durchläuft) jede einzelne Zelle abgefahren. Und zwar
    // immer abwechselnd von links nach rechts, dann wieder von rechts nach links usw.
    // Der Richtungswechsel wird mit Hilfe von direction gemacht.
    if x < xMax then
      x := x + direction
    else
    begin
      Inc(y);
      direction := -direction;
    end;

    // In der letzten Zeile fahre ich den Roboter ganz nach rechts.
    while x < xMax do
      Inc(x);

     MachDenAbschluss;
  end;
end;

 

[dvor4k]

Tut mir leid, aber mit deinem Code kann ich wenig anfangen
Vielleicht habe ich mich etwas unklar ausgedrückt. Hier habe ich allerdings ein spezielles Beispiel.
Das Arbeitsfeld sieht wie folgt aus:

Mein Programm so:

Program Lab;

uses dema;

Procedure rein;
 BEGIN
  WHILE vorne_frei DO vor;
   IF platz_belegt THEN
    BEGIN
     WHILE platz_belegt DO nimm_auf;
    END;
   IF NOT vorne_frei AND links_frei THEN drehe_links ELSE
    BEGIN
    IF NOT vorne_frei AND NOT links_frei THEN drehe_rechts;
    BEGIN
       IF NOT vorne_frei AND NOT links_frei AND NOT rechts_frei THEN drehe_um;
      END;
    END;
      rein;
    END;
    
    
    BEGIN
     rein;
    END.

dema ist meine Unit, die evtl nicht bekannten Befehle sind:
drehe_rechts --> drehe_links;drehe_links;drehe_links
drehe_um --> drehe_links;drehe_links

Der Roboter legt nun das Labyrinth zurück, kommt dann allerdings heraus und läuft durch die Schleife immer weiter im Kreis. Könnte mir jemand einen Tipp geben, wie ich eine REPEAT-Schleife einbauen könnte, damit Niki beim Verlassen des Labyrinths stehen bleibt?

 

[CSANecromancer]

Jetzt wird es interessant.

Könnte mir jemand einen Tipp geben, wie ich eine REPEAT-Schleife einbauen könnte, damit Niki beim Verlassen des Labyrinths stehen bleibt?

Das geht imho ohne Variableneinsatz schlicht und ergreifend nicht. Der Roboter muß sich auf irgendeine Weise merken können a) wieviele Schritte er zurück gelegt hat oder b) daß er eine geraume Zeit geradeaus läuft, ohne irgendwo anzuecken.

Variante A geht dann in Richtung Backtracking. Im simpelsten Schritt (und bei diesem Labyrinth ausreichend) würde es reichen, beim Reingehen zu zählen, wie oft der Roboter vorwärts gehen kann (unabhängig der Richtungen). Sobald er weder geradeaus, links noch rechts kann, hat er das Ende des Labyrinths erreicht und muß dann nur wieder den Weg rausfinden und dabei so viele Schritte zurück legen, wie er für den Weg rein gebraucht hat. Dann steht er wieder am Anfang, nur daß er jetzt aus dem Labyrinth raus schaut statt rein.

Variante B würde ich einfach einen Zähler machen, der sich bei jedem Vorwärts erhöht und bei jeder Drehung auf 0 resettet wird. Sobald der Zähler - sagen wir mal - 10 erreicht hat, bedeutet das, daß der Roboter 10 Schritte stur geradeaus gegangen ist. Wenn das Labyrinthlayout bekannt ist und man weiß, daß es keine so langen Geraden da drin gibt, dann könnte man eine Gerade der Länge 10 als Indiz annehmen, daß der Roboter das Labyrinth verlassen hat und draußen rumrennt. Ist aber meiner Meinung nach die unsauberste Methode.

Wenn du eine noch ausgefeiltere Variante C (echtes Backtracking) verwenden willst, dann kann ich dir für den Einstieg diesen Link der TU Berlin empfehlen.
Wenn es noch etwas detaillierter und genauer sein darf, dann wirst du bei der Uni Erlangen fündig, da wird dann auch noch weiterführende Literatur angegeben.

 

[dvor4k]

Alles klar. Schon einmal besten Dank für die Auskunft. Das Programm soll nur leider so konzipiert sein, dass es auch in einem Labyrinth unbekannten Layouts läuft, also scheidet Variante B aus. Die Variante C werde ich mir auf jeden Fall mal anschauen, bin mir aber nicht sicher ob ich dem gewachsen bin..
Variante A habe ich ähnlich schon einmal angedacht, allerdings dann mit zwei REPEAT-Schleifen (die erste soll den Grundbefehl so lange ausführen, bis Niki das Ende das Labyrinths erreicht hat, die andere dann vom Herzen des Labyrinths so lange bis die Bedingung links_frei AND rechts_frei AND vorne_frei erfüllt ist.
Die Alternative, Niki die gleiche Anzahl Schritte heraus machen zu lassen wie herein scheint daher die beste, leider bin ich nur nicht ausreichend bewandert, um das zu programmieren. Daher wäre ich dir dankbar, wenn du kurz ausführen könntest, wie man diese Art des Backtracking in Niki einbindet

 

[CSANecromancer]

Da versuche ich gerne zu helfen, jedoch erst wieder morgen, ich muß jetzt off gehen.
Aber damit du was zum Grübeln hast und evtl. einen Prototypen basteln kannst, hier in (sehr kurzer) Kurzform so mal die Basics:

1. Der Roboter bekommt ein Array.
2. In dieses Array werden alle Schritte protokolliert, also nicht nur Vorwärts sondern auch die Drehungen.
3. Rennt der Roboter in eine Sackgasse, dann kann er mit Hilfe dieses Arrays seine Schritte bis zur letzten Kreuzung zurück verfolgen und dabei auch gleich aus dem Array rauslöschen.
4. Erreicht der Roboter sein Ziel, dann ist in seinem Array ein direkter Weg quer durch das Labyrinth gespeichert. Das muß nicht unbedingt der kürzeste sein, aber es ist ein gangbarer Weg.

Einfach mal in Ruhe durchdenken und evtl. auch selbst mal etwas an 1, 2 Beispielen ausprobieren (genau das werde ich nämlich morgen auch machen müssen ) und mal schauen, was wir da zusammen bekommen.

 

[CSANecromancer]

So, ich habe mir mal kräftig Gedanken gemacht und nochmal den Ursprungspost durchgelesen. Damit ich mich nicht völlig vergallopiere, hier mal ein paar grundlegende Anmerkungen dazu:

Wenn es um eine reine Schleifenprogrammierung geht, dann kann man ein komplexes Labyrinth vollständig vergessen. Das Zurechtfinden in einem Labyrinth inkl. Backtrackings ist schon ordentliche Programmierung und geht über ein simples Schleifenkonstrukt weit hinaus. Einfachste Formationen, wie z.B. diese Spirale können auch mit einer Schleife aufgelöst werden, aber bereits hier sind Variablen angebracht (wenn auch noch nicht zwingend notwendig). Ich habe mir das Niki-Programm gezogen und in der Hilfe gelesen, daß Variablen darin nicht verwendet werden können. Da du von einem "Lehrer" geschrieben hast, gehe ich mal davon aus, daß die Aufgabe ca. Schulniveau hat. Was bedeutet, daß vollständiges Backtracking wohl rausfällt.

Das grundlegende Problem ist, daß wir eine Komplettübersicht über das Labyrinth haben (durch die Draufsicht), der Roboter jedoch nicht. Somit würde der Roboter theoretisch eine Art künstliches Gedächtnis benötigen, um sich seinen Weg durch ein richtiges Labyrinth zu merken (ganz abgesehen von den Tatsachen, daß Labyrinth nicht gleich Labyrinth ist und es auch mehrere verschiedene Methoden gibt, um Labyrinthe zu knacken) und so etwas zu programmieren ist - abhängig von der Aufgabenstellung - nicht unbedingt trivial und innerhalb der Niki-Umgebung aufgrund der fehlenden Variablen nicht umsetzbar.

Also gehe ich jetzt mal von zwei möglichen Aufgabenstellungen aus:
1. Der Roboter soll schleifengesteuert einfach das gesamte Feld abfahren, alles einsammeln, was er findet und dann das Zeug an einem bestimmten Punkt abliefern.
2. Der Roboter soll einen bestimmten, durch Wände begrenzten Weg abfahren können, der Rest analog zu 1.

Das allererste, was ich bei so einer Entwicklung mache, ist, mir erstens Gedanken zu machen, was genau das Problem ist und welche Möglichkeiten mir zur Verfügung stehen. Ich gehe mal exemplarisch Aufgabe 1 durch.

Was habe ich also?
Ich habe:
- eine Arena, die am Rand begrenzt ist und innerhalb derer sich der Roboter bewegt.
- einen Roboter mit sehr eingeschränktem Befehlssatz und ziemlich eingeschränkten Sensoren.
- ein Feld (rechts unten), auf dem die "Beute" hinterher abzuliefern ist.
- die Anforderung, daß alle Einzelfelder der Arena angefahren, untersucht und leergegrast werden müssen.

Nicht gerade viel. Vielleicht fällt auf, daß von einer Anfangsposition des Roboters keine Rede ist, die nehme ich also nicht als gegeben hin.

Was ich also brauche ist:
- eine ordentliche Anfangsposition
- ein Muster, wie ich die Arena durchlaufen will
- eine Möglichkeit, zum Zielfeld zu kommen

Damit lässt sich schon mal ein bißchen Rumpfcode schreiben:

PROGRAM Variante1;

PROCEDURE drehe_rechts;
BEGIN
    drehe_links;
    drehe_links;
    drehe_links;
END;

PROCEDURE drehe_um;
BEGIN
    drehe_links;
    drehe_links;
END;

BEGIN
END.

Nichts weltbewegendes. Ich kenne deine Unit "dema" nicht, aber da dürfte wohl ähnliches drin stehen.
Erstmal will ich die Anfangsposition festlegen. Ich möchte, daß der Roboter grundsätzlich links unten steht und nach Norden schaut, bevor er anfängt, die Arena abzulaufen. Und genau das mache ich auch so. Ich bringe den Roboter nach links,

    WHILE NOT westwaerts DO drehe_links;
    WHILE vorne_frei DO vor;

dann nach unten

    drehe_links;
    WHILE vorne_frei DO vor;

und drehe ihn schließlich so, daß er wieder nach Norden schaut.

drehe_um;

Das Ganze wird in eine Prozedur verpackt, die ich dann aufrufen kann und die mir jederzeit dafür sorgt, daß der Roboter nach links unten gebracht wird, egal wo er steht/stand und welche Ausrichtung er hat/te:

PROCEDURE Niki_nach_links_unten;
BEGIN
    WHILE NOT westwaerts DO drehe_links;
    WHILE vorne_frei DO vor;
    drehe_links;
    WHILE vorne_frei DO vor;
    drehe_um;
END;

Da es um Schleifenkonstrukte geht, hast du hier schon mal die ersten drei Schleifen:
1. Den Roboter drehen, bis er nach Westen schaut.
2. Vorwärts, bis es nicht mehr weiter geht.
3. Nochmal vorwärts, bis es nicht mehr geht.
Bei allen drei Schleifen ist auch schön die Abbruchbedingung zu sehen. "Mache etwas bis". Alternativ dazu gibt es auch "Mache etwas solange".

Ok, weiter geht's. Mit Hilfe von Niki_nach_links_unten kann ich jetzt also immer von einer festen Ausgangsposition ausgehen und dementsprechend den Weg durch die Arena planen. Am einfachsten erscheint es mir, so vorzugehen:
- Von Süden nach Norden fahren bis zum Anschlag.
- Umdrehen (und dabei eine Reihe weiter nach rechts rutschen).
- Von Norden nach Süden fahren bis zum Anschlag.
- Umdrehen (und dabei eine Reihe weiter nach rechts rutschen).
- Das Ganze so oft wiederholen, bis es nicht mehr geht.

Das Schwammigste an diesen ganzen Formulierungen ist die Abbruchbedingung "bis es nicht mehr geht". Woran lässt sich erkennen, daß "es nicht mehr geht"?
Wenn ich mir einfach die Arena betrachte und den Weg anschaue, den der Roboter zurück legen würde, so käme er am Schluß rechts oben raus mit einer Nordausrichtung. Das ist das letzte Feld, das er erreichen kann. Aber genau durch diese Charakteristiken kann ich dieses Feld erkennen:
- Ausrichtung des Roboters nach Norden
- Er kann nicht mehr weiter nach Norden fahren
- Zur Rechten des Roboters ist eine Wand.
Das schwammige "bis es nicht mehr geht" kann ich also auflösen in

  ... nordwaerts AND NOT vorne_frei AND NOT rechts_frei

Jetzt kann ich schon anfangen die große Schleife zu formulieren, die da lautete "Mache das alles, bis es nicht mehr geht":

REAPEAT
BEGIN
END
UNTIL nordwaerts AND NOT vorne_frei AND NOT rechts_frei;

Jetzt füge ich alles mal ein bißchen in das Programm ein, welches dann so aussieht:

PROGRAM Variante1;

PROCEDURE drehe_rechts;
BEGIN
    drehe_links;
    drehe_links;
    drehe_links;
END;

PROCEDURE drehe_um;
BEGIN
    drehe_links;
    drehe_links;
END;

PROCEDURE Niki_nach_links_unten;
BEGIN
    WHILE NOT westwaerts DO drehe_links;
    WHILE vorne_frei DO vor;
    drehe_links;
    WHILE vorne_frei DO vor;
    drehe_um;
END;

BEGIN
  Niki_nach_links_unten;

  REPEAT
  BEGIN
  END
  UNTIL nordwaerts AND NOT vorne_frei AND NOT rechts_frei;

  Niki_nach_Links_unten;
END.

Das zweite Niki_nach_links_unten ist drin, damit ich nach getaner Arbeit den Roboter wieder "nach Hause" schicken kann.

So. Was sollte der Roboter machen, solange er unterwegs ist? Genau. Alles aufsammeln.

IF Platz_belegt THEN nimm_auf;

Aber Moment! Durch diese Anweisung nimmt der Roboter genau einmal etwas von dem Feld auf, auf dem er steht. Er soll aber alles aufheben. Das lässt sich auch so formulieren: "Solange etwas da ist, nimm es auf". Und da ist schon wieder das magische Wort "solange", mit dem sich eine Schleifenbedingung formulieren lässt:

  WHILE Platz_belegt DO nimm_auf;

Wenn das Feld abgegrast ist, dann soll der Roboter ein Feld vorfahren. Aber was ist, wenn er den Rand erreicht (entweder den Nord- oder den Südrand)? Dann kann er ja nicht mehr weiter vorwärts. Als entweder kann er fahren oder nicht. Zwei Möglichkeiten. Das schreit geradezu nach einem IF...THEN...ELSE:

IF vorne_frei THEN vor
ELSE

ELSE... ja, else was? Wenn er nicht vorwärts fahren kann, dann soll er eine kleine Kurve fahren. Davon gibt es zwei, zum einen, wenn er an den Nordrand stößt, zum anderen beim Südrand.
Hier mal die Formulierung für die Kehre, wenn der Roboter an den Nordrand gestoßen ist:

drehe_rechts;
vor;
drehe_rechts;

Für den Südrand sieht es ähnlich aus und der Ordnung halber packe ich diese beiden Vorgänge in eigene Prozeduren:

PROCEDURE Kehre_rechtsrum;
BEGIN
  drehe_rechts;
  vor;
  drehe_rechts;
END;

PROCEDURE Kehre_linksrum;
BEGIN
  drehe_links;
  vor;
  drehe_links;
END;

Prima. Wenn der Roboter also nicht mehr weiter nach vorne fahren kann, dann muß ich nur schauen, ob er von Norden nach Süden unterwegs war oder umgekehrt und muß die entsprechende Kehre durchführen:

  IF nordwaerts THEN Kehre_rechtsrum
  ELSE Kehre_linksrum;

Und damit habe ich schon meine Hauptarbeitsschleife:

  REPEAT
  BEGIN
    WHILE Platz_belegt DO nimm_auf;

    IF vorne_frei THEN vor
    ELSE
      IF nordwaerts THEN Kehre_rechtsrum
      ELSE Kehre_linksrum;
  END
  UNTIL nordwaerts AND NOT vorne_frei AND NOT rechts_frei;

Wenn der Roboter seine Arbeit getan hat, ist er mit Nordausrichtung in der rechten oberen Ecke. Seine Beute soll er aber rechts unten abladen. Daher lasse ich ihn noch da hin fahren, bevor aller Schotter abgeworfen wird:

drehe_um;
WHILE vorne_frei DO vor;
WHILE hat_Vorrat DO gib_ab;

Fertig.

Das komplette Programm sieht dann so aus:

PROGRAM Variante1;

PROCEDURE drehe_rechts;
BEGIN
    drehe_links;
    drehe_links;
    drehe_links;
END;

PROCEDURE drehe_um;
BEGIN
    drehe_links;
    drehe_links;
END;

PROCEDURE Niki_nach_links_unten;
BEGIN
    WHILE NOT westwaerts DO drehe_links;
    WHILE vorne_frei DO vor;
    drehe_links;
    WHILE vorne_frei DO vor;
    drehe_um;
END;

PROCEDURE Kehre_rechtsrum;
BEGIN
  drehe_rechts;
  vor;
  drehe_rechts;
END;

PROCEDURE Kehre_linksrum;
BEGIN
  drehe_links;
  vor;
  drehe_links;
END;

BEGIN
  Niki_nach_links_unten;

  REPEAT
  BEGIN
    WHILE Platz_belegt DO nimm_auf;

    IF vorne_frei THEN vor
    ELSE
      IF nordwaerts THEN Kehre_rechtsrum
      ELSE Kehre_linksrum;
  END
  UNTIL nordwaerts AND NOT vorne_frei AND NOT rechts_frei;

  drehe_um;
  WHILE vorne_frei DO vor;
  WHILE hat_Vorrat DO gib_ab;

  Niki_nach_links_unten;
END.

Ich hoffe, ich konnte dir damit etwas mehr Verständnis für Programmentwicklung und Schleifenkonstrukte geben. Variante 2 mit der Spirale kannst du dir ja selber ausknobeln.