[PHP] Gedankenhilfe: Navigationssystem

U

unregiert

abgemeldet
22 April 2006
451
26
Hallo

Ich würde gerne mal wissen, wie man so ein Navigationssystem programmiert. Bei der aktuellen Informatik-Olympiade der Schweiz gibt es gerade eine solche Aufgabe - Aber ich mach nicht mit.

Ich habe ein Labyrinth, welches so aussieht:

xxxxxxxxxxxxx.xxxxxx
xxxxxx...........xxx
xxxxxx.xxxxxx.xx.xxx
xxxxx..xxxxxx....xxx
xxxx...xxKxxxxxxxxxx
xxxxx.......xxxxxxxx
xxxxxxxxxxx.xxxxxxxx
xxxxxxxxxxx........x
xxxxxxxxxxxxxxxxxxxx

K ist Karl. Er ist in einem Labyrinth gefangen, und will raus. Er kennt das Labyrinth nicht, hat aber einen Plan davon, welcher aber so gross ist, dass er nicht selber verfolgen kann, wo er ist. Daher wäre ein Programm gescheiter.

Die Lösung wäre für den menschen einfach, aber wie bringe ich es dem PC bei? Wie schaffe ich es in einer C-ähnlichen Sprache - z.B. PHP, den Ausgang zu finden, oder simpler: Wie schaffe ich es in einem freien Raum, ohne Gegenstände/Hindernisse von Koordinate A zu B zu kommen? Naja, jetzt ist mir etwas gerade eingefallen: Das wäre relativ einfach *gg*.

Koordinate A: 50/47
Koordinate B: 13/87

Weg: -37 links, 40 runter

Trotzdem bleibt die Frage: Wie schaffe ich es, das gleiche in einem Labyrinth zu machen?

1. Aus Text - Array bilden
Ihr glaubt es nicht, aber es war schwer. Ja, ich wusste nicht, wie ich explode mit leerem Delimiter machen kann. Naja, jetzt funzt es, aber Frage 3.: Wie finde ich heraus, in welcher Dimension sich Karl befindet?
PHP: 
function makearray($lab)
{
  $y = explode("\n", $lab);
  
  foreach($y as $zeile)
  {
    $x = array();
    for($t = 0; $t < strlen($zeile); $t++)
    {
      $x[] = $zeile[$t];
    }
    foreach($x as $spalte)
    {
      if($spalte == "W") 
      {    
        $wert[] = "1";
      } elseif($spalte == "L") {
        $wert[] = "0";
      } elseif($spalte == "K") {
        $wert[] = "9";
      }
    }
    $labarray[] = $wert;
    unset($wert);
  }
  
  return $labarray;
}

Karl wäre jetzt bei $array[4][9] zu finden, aber wie finde ich [4][9] heraus? Suchen wäre zu ressurcenfressend :(
 
Zuletzt bearbeitet:
unregiert schrieb:
Trotzdem bleibt die Frage: Wie schaffe ich es, das gleiche in einem Labyrinth zu machen?
Zum Vergrößern anklicken....
Das war neulich eine Aufgabe bei mir in Algorithmik.
Rekursiv durchprobieren: Stößt du gegen ne Wand, false zurückgeben, ansonsten alle 4 Richtungen durch rekursiven Aufruf mit neuen Koordinanten weiterlaufen, bis du entweder am Ausgang bist (Juhuu) oder du in allen Richtungen false hast und am Ende wieder am Startpunkt bist (kein Ausgang). Sicher nicht effizient, aber es funktioniert.
edit: Wichtig: Merk dir den Weg, den du gelaufen bist, sonst läufst du in die Endlosschleife, falls das Labyrinth einen Kreis besitzt.

unregiert schrieb:
Ihr glaubt es nicht, aber es war schwer.
Zum Vergrößern anklicken....
Ich hätte alle Strings aus den Zeilen konkateniert und dann n str_replace() drüber gehauen, wenn du unbedingt numerische Zeichen haben willst.

Da du es aber so schon hast, geht die nächste Frage leichter:
unregiert schrieb:
Karl wäre jetzt bei $array[4][9] zu finden, aber wie finde ich [4][9] heraus? Suchen wäre zu ressurcenfressend :(
Zum Vergrößern anklicken....
Suchen ? Du läuft doch schon beim Arraybasteln alles durch. Wenn du Karl hast, merk dir einfach im wievielten Durchgang du bist bzw. besser: statt foreach() for() benutzen, dann hast du deine Koordinaten in der Zählervariable.
 
Funktion abgeändert, damit er mir array([Array mit Koordinaten], [Feldarray]) zurückgibt, um Karls position zu ermitteln. Nun, ich wollte überprüfen, ob er das macht, macht er aber nicht :(

PHP: 
function makearray($lab)
{
  $y = explode("\n", $lab);
  $ycount = 0;
  foreach($y as $zeile)
  {
    $x = array();
    for($t = 0; $t < strlen($zeile); $t++)
    {
      $x[] = $zeile[$t];
    }
    $xcount = 0;
    foreach($x as $spalte)
    {
      if($spalte == "W") 
      {    
        $wert[] = "1";
      } elseif($spalte == "L") {
        $wert[] = "0";
      } elseif($spalte == "K") {
        $whoiscarl = array($xcount, $ycount);
        $wert[] = "9";
      }
      $xcount++;
    }
    $labarray[] = $wert;
    unset($wert);
    $ycount++;
  }
  
  return array($whoiscarl, $labarray);
}

list($poscarl, $labarray) = makearray($lab);

$xpos = $poscarl[0];
$ypos = $poscarl[1];
$chose = $labarray[$xpos];
$chose = $chose[$ypos];
echo $chose;
 
$chose = $labarray[$xpos];
$chose = $chose[$ypos];
Zum Vergrößern anklicken....
Andersrum: Du hast in der ersten Dimension die Y-Koordinate, in der zweiten die X.
PHP: 
$chose = $labarray[$poscarl[1]][$poscarl[0]];
P.S. who = wer, where = wo :biggrin:
 
ice-breaker schrieb:
Neija als ich das in Flash mal gemacht habe, hat mir der A*-Algorithmus sehr geholfen.
Eigentlich relativ einfach und wird viel eingesetzt (natürlich gibt es noch bessere)
Zum Vergrößern anklicken....

Genau, das ist eine klassische Fragestellung aus der Graphentheorie. Beschäftige dich mal ein wenig mit Wegeproblemen, in diesem Fall mit dem Kürzeste-Wege-Problem.

Ist ein sehr interessantes Aufgabengebiet, auch beruflich im Bereich Operations Research und Decission Support. ;)

Gruß, Zera
 
Bitte nicht schlagen.
PHP: 
<?php
    
function makearray($lab)
{
  $y = explode("\n", $lab);
  $ycount = 0;
  foreach($y as $zeile)
  {
    $x = array();
    for($t = 0; $t < strlen($zeile); $t++)
    {
      $x[] = $zeile[$t];
    }
    $xcount = 0;
    foreach($x as $spalte)
    {
      if($spalte == "W") 
      {    
        $wert[] = "1";
      } elseif($spalte == "L") {
        $wert[] = "0";
      } elseif($spalte == "K") {
        $whoiscarl = array($xcount, $ycount);
        $wert[] = "9";
      }
      $xcount++;
    }
    $labarray[] = $wert;
    unset($wert);
    $ycount++;
  }
  
  return array($whoiscarl, $labarray);
}

function whereyoucango($ypos, $xpos, $labarray)
{
  // ueberprueft, welche wege "befahrbar" sind
  if($labarray[($ypos-1)][$xpos] == 0)
  {
    $newpos = array(($ypos-1), $xpos);
  }
  if($labarray[$ypos][($xpos-1)] == 0)
  {
    $newpos = array(($ypos), ($xpos-1));
  }
  if($labarray[($ypos+1)][$xpos] == 0)
  {
    $newpos = array(($ypos+1), $xpos);
  }
  if($labarray[$ypos][($xpos+1)] == 0)
  {
    $newpos = array(($ypos), ($xpos+1));
  }
  
  // wenn keines existiert -> bewegliches labyrinth?
  if(!isset($newpos))
    return false;
  else
    return $newpos;
}

function isakreuzung($ypos, $xpos, $labarray, $kreuzungarray, $isif = FALSE)
{
  // nach freie wege suchen und in array tun
  if($labarray[($ypos-1)][$xpos] == 0)
  {
    $newpos[] = array(($ypos-1), $xpos, $ypos, $xpos);
  }
  if($labarray[$ypos][($xpos-1)] == 0)
  {
    $newpos[] = array(($ypos), ($xpos-1), $ypos, $xpos);
  }
  if($labarray[($ypos+1)][$xpos] == 0)
  {
    $newpos[] = array(($ypos+1), $xpos, $ypos, $xpos);
  }
  if($labarray[$ypos][($xpos+1)] == 0)
  {
    $newpos[] = array(($ypos), ($xpos+1), $ypos, $xpos);
  }
  
  // check ob welche existieren
  if(count($newpos) == 0 OR count($newpos) == 1)
    return false;
  else {
    foreach($newpos as $kreuzung)
    {
      // überprüft, ob er diesen weg schonmal belief
      if(!in_array($kreuzgung, $kreuzungarray))
      {
        $returnarray[] = $kreuzung;
      }
    }
    
    // zufällig eines aus den möglichen wegen nehmen
    return $returnarray[rand(0, (count($returnarray)-1))];
  }
}
?>

Hauptdatei:
PHP: 
<?php
include("lab.lib.php");
$lab = 
"WWWWWWWWWWWWWLWWWWWW
WWWWWWLLLLLLLLLLLWWW
WWWWWWLWWWWWWLWWLWWW
WWWWWLLWWWWWWLLLLWWW
WWWWLLLWWKWWWWWWWWWW
WWWWWLLLLLLLWWWWWWWW
WWWWWWWWWWWLWWWWWWWW
WWWWWWWWWWWLLLLLLLLW
WWWWWWWWWWWWWWWWWWWW";

list($poscarl, $labarray) = makearray($lab);

$xpos = $poscarl[0];
$ypos = $poscarl[1];
$kreuzungarray = array();
if(!isakreuzung($ypos, $xpos, $labarray, $kreuzungarray, $isif = TRUE))
{
  print_r(whereyoucango($ypos, $xpos, $labarray));
  
  $newpos = whereyoucango($ypos, $xpos, $labarray);
  $oldypos = $ypos;
  $oldxpos = $xpos;
  $ypos = $newpos[0];
  $xpos = $newpos[1];
  
  if(isakreuzung($ypos, $xpos, $labarray, $kreuzungarray, $isif = TRUE))
  {
    $kreuzungarray[] = array($oldypos, $oldxpos, $ypos, $xpos);
    $newpos = isakreuzung($ypos, $xpos, $labarray, $kreuzungarray);
    $ypos = $newpos[0];
    $xpos = $newpos[1];
    print_r(isakreuzung($ypos, $xpos, $labarray, $kreuzungarray));
  }
}

?>

Meine eigentliche Idee: Er schaut, ob es eine Kreuzung ist, oder nur ein einfacher Weg ist. Wenn es nur ein einfacher Weg ist, nimmt er den, der Fremd seiner Herkunft ist. Sonst überprüft eine Funktion, ob er an dieser Kreuzung schon mal war, wenn ja, nimmt er die anderen mögliche Wege. Ist vielleicht falsch umgesetzt, bestimmt sogar *gg*.
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben