Künstliche Intelligenz (KI) als Hobby / Artificial Intelligence (AI) as a Hobby

Facebook Group: Künstliche Intelligenz (KI) als Hobby

Berechnung des Manhattan-Abstandes in einer Tabelle mit PHP

Der Manhattan-Abstand in einer Tabelle oder z.B. einem Schachbrett ist die Anzahl der Felder, die man von einem Start-Feld zu einem Ziel-Feld gehen muss, wenn man nicht diagonal, sondern nur "hoch/runter" und "rechts/links" von Feld zu Feld gehen kann.

Schritt 1: Tabelle erzeugen (Zwei-dimensionales Array in PHP)

Jedes Schlüssel-Paar in dem Array stellt eine Koordinate dar. Dabei ist der erste Schlüssel im Array die Y-Koordinate. Die darauf folgenden Schlüssel der zweiten Stufe sind die X-Koordinaten (0-4). Der Wert wird mit 0 = normales Feld, 1 = blockiertes Feld gefüllt.

$map = array();
$map = array(
            array(0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0)
        );

Das Array kann schnell als übersichtliche Tabelle dargestellt werden, wobei Y von oben nach unten dargestellt wird, sodass X von links nach rechts aber Y von oben nach unten ansteigt:

Schritt 2: Ziel-Feld definieren

Ziel-Feld = Y2/X3

$ZielX = 3;
$ZielY = 2;

Schritt 3: Manhattan-Abstand jedes Feldes zum Ziel-Feld berechnen

Die Anzahl der Felder vom Feld zum Ziel wird mit der Manhattan-Formel berechnet: Manhattan-Abstand = BETRAG (FeldY-ZielX) + BETRAG (FeldX-ZielY).

$manhattan = array();
for($i = 0, $ni = count($map); $i < $ni; $i++){
	for($i2 = 0, $ni = count($map); $i2 < $ni; $i2++){
		$manhattan[$i][$i2] = (abs($i-$ZielX) + abs($i2-$ZielY) );
	};
};

Manhattan-Abstand als Tabelle: