Abstandsberechung in einem offenen Netz

[Flips]

Hi,
nehmen wir an ich habe ein 2D-Netz in folgender Form, 8 * 8 Knoten:

Code:

o o o o o o o o
o o o o o o o o
o o o o o o o o
o x o o o o y o
o o o o o o o o
o o o o o o o o
o o o o o o o o
o o o o o o o o

Die Knoten sind horizontal und vertikal miteinander verbunden.
Dieses Netz soll offen sein, d.h. die Knoten links außen sind mit den Knoten rechts außen verbunden, ebenso die Knoten oben mit den Knoten unten.

In einem offenen Netz wäre der Abstand von X und Y -> 5
In einem geschlossenen Netz wäre er 3.

Wenn ich das Netz nun als 2D-Array programmiere und den Abstand via Pythagoras berechne, dann ist das in einem geschlossenen Netz ja ziemlich einfach.
Aber wie mache ich das in einem offenen Netz? Ich komme einfach nicht drauf.

Danke,
lg Flips

[jfheins]

Hmmm ...

ich würd es wohl so machen, dass ich das manuell prüfe. Ich bezweifele dass es da eine Möglichkeit gibt die wesentlich schneller ist ...

Delphi-Quellcode:

function Distance(A, B: TPoint) : Single;
var
  dx, dy: Cardinal;
const
  Meshsize = 8;
begin
  dx = Abs(A.X - B.X);
  dy = Abs(A.Y - B.Y);

  dx = ifthen(dx > (Meshsize / 2), Meshsize - dx, dx);
  dy = ifthen(dy > (Meshsize / 2), Meshsize - dy, dy);

  Result := Phythagoras(dx, dy);
end;

So in etwa :stupid:

[himitsu]

Delphi-Quellcode:

inner := ABS(X - Y) + 1;
outer := (8 - Y + X) mod 8 - 1;

abstand := Min(inner, outer)

x und y = mit 0 bassiertem Index (also 0..7)

ds wäre jetzt der Abstand in einer Richtung (hoff ich mal)
und wenn du so jeweils den Abstand in X- und Y-Richtung so ausrechnest und dieser verrechnest, dann sollte sich der absolute Abstand bestimmen lassen

[Sir Rufo]

Wie wäre es mit Horizonterweiterung?

Code:

. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . Y .|. . . . . . Y .|. . . . . . y .
. . . . . . . .|. . . . . . . .|. . . . . . . .
---------------+-------+-------+---------------
. . . . . . . .|o o o o|o o o o|. . . . . . . .
. . . . . . . .|o o o o|o o o o|. . . . . . . .
. . . . . . . .|o o o o|o o o o|. . . . . . . .
. . . . . . . .|o X o o|o o o o|. . . . . . . .
. . . . . . . .|o o o o|o o o o|. . . . . . . .
. . . . . . . .|o o o o|o o o o|. . . . . . . .
. . . . . . Y .|o o o o|o o Y o|. . . . . . y .
. . . . . . . .|o o o o|o o o o|. . . . . . . .
---------------+-------+-------+---------------
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . y .|. . . . . . y .|. . . . . . y .
. . . . . . . .|. . . . . . . .|. . . . . . . .

Code:

+-------+-------+-------+
|       |       |       |
|   A   |   B   |   C   |
|       |       |       |
+-------+---+---+-------+
|       | 1 | 2 |       |
|   D   +---E---+   F   |
|       | 3 | 4 |       |
+-------+---+---+-------+
|       |       |       |
|   G   |   H   |   I   |
|       |       |       |
+-------+-------+-------+

Zur Betrachtung benötigst du nur die Quadranten, die der Lage von X im Quadrant E am nächsten sind.
X in 1 => A,B,D,E
X in 2 => B,C,E,F
usw.
Berechne nun alle möglichen Strecken zwischen XY und nimm das Minimum.

cu

Oliver

[Cyf]

Wie wärs mit rekursiven Backtracking, bis die kürzeste Strecke gefunden ist. :mrgreen:

[himitsu]

@Sir Rufo: im Prinzip wird sowas bei meiner Rechnung schon teilweise gemacht (nach rects um einen Quadranten erweitert.)

Code:

0123456789
  X   Y

(Y - X) = innerL
(6 - 2) = 4
[3-4-5-6 > 4]

10 - (Y - X) = outerL
10 - (6 - 2) = 6
[7-8-9-0-1-2 > 6]

ansonsten ist ja Länge des Quadranten = innerL + outerL

[add]
@Cyf: 'ne manuell vorberechnte Tabelle, mit allen lösungen wäre das schnellste ... muß man sich dann nur noch schnell die richtige Lösung raussuchen (über 'nen 2-dimensionales Array recht leicht)

[inherited]

@Cyf: Das nennst du dann Bogotrace und deiner Signatur gerecht :mrgreen:

[sx2008]

Zitat:

Zitat von Flips

... und den Abstand via Pythagoras berechne

Ich glaube nicht, dass das in deinem Fall die richtige Rechenmethode ist.

Code:

o o o o o o o o
o o o o o o o o
o o o x o o o o
o o o o o o y o
o o o o o o o o
o o o o o o o o
o o o o o o o o
o o o o o o o o

Wie gross ist hier der "Abstand" von x nach y?
Ein Kästchen nach Süden und drei nach Osten macht 4.
Die Reihenfolge der Züge ist egal, es sind immer mindestens 4 Züge notwendig.

Oder wenn eine diagonale Bewegung erlaubt ist:
Diagonal nach Süd-Ost plus zwei nach Osten macht 3.

[Flips]

Hey wow, hab das Thema kurz außer acht gelassen und schon soviele Vorschläge^^ Danke euch :-D
Hab jetzt die Variante von jfheins genommen, geht wunderbar :-)

Und nochwas zu sx2008 Beitrag:
Ähm doch doch, die Entfernung soll nicht in Einheiten bezüglich des Netzes berechnet werden, sondern als wäre das Netz in ein Koordinatensystem eingebettet. Sodass zwischen zwei Punkten horizontal und vertikal der dimensionslose Abstand "1" ist, und somit diagonal der Abstand Wurzel 2.