Ok... ich denke der Ansatz ist vielversprechend. Wobei in deinem Bild viele ausreichend große Durchgänge als Blockiert gekennzeichnet werden. Aber das wird dann nur noch ein Detail sein.

Habs mir komplizierter Vorgestellt und bin deshalb wohl damals auch nicht auf die simple Idee gekommen...

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Ok das Bild war nicht so optimal, man muß die Trennlinien zwischen den Bounding-Boxes besser hervorheben.

Auf denen darf man sich noch bewegen, da das Objekt durch die Vergrösserung der Bounding-Boxes auf einen Punkt zusammenschrumpft.

Ich hoffe es wird in der unteren Grafik etwas besser deutlich :




Viele Grüße
dj3hut1

_________________
Wenn Gauß heute lebte, wäre er ein Hacker.
Peter Sarnak, Professor an der Princeton University

ok so weit schonmal ganz gut.
ich hab jz noch die idee, dass man die waypoints nicht an der kompletten gerade verstreut sondern nur 4 stück um den start und zielpunkt.
dadurch würde er um das hindernis drumrumkommen.
jetzt könnte man noch auf nummer sicher gehn, und bei einer geradenlänge von >=1.5Y die gerade in stücken mit ner maximallänge von 1,5Y unterteilen und dort jeweils "links" und "rechts" je einen wegpunkt setzen.

was noch unklar ist
1: "links" und "rechts" würde ich mit dem normaleneinheitsvektor der geraden machen. den dann schon auf meinen abstand (z.b. 10px) skalieren und fertig
2: dann würde ich den normalenvektor der geraden verwenden, um die punkte neben der gerade zu verteilen. brauche ich auch die länge der geraden
3: ich muss von jeder linie im umkreis den abstand zu dem punkt, den ich setzen will berechnen.
ich brauch also eine formel, die mir den abstand punkt->strecke berechnet.
das könnte etwas rechenintensiv werden. meine einzige idee dazu ist:
a)normalenvektor der geraden bestimmen. schnittpunkt der 2 geraden (strecke und punkt mit normalenvektor) bestimmen.
prüfen, ob der auf der strecke liegt.
abstand schnittpunkt<>punkt berechnen
bei keinem schnittpunkt (punkt wäre also auf der verlängerten strecke) nehme ich den minimalabstand des punktes zu den beiden endpunkten der strecke

geth das schneller?
oder gibt es bessere ansätze?

A und B ist deine Strecke, P der Punkt. Die Funktion stammt aus meinen DirectX-Zeiten, aber was z.B. die Funktion D3DXVec3Subtract macht sollte ja relativ klar sein, ansonsten einfach fragen. Das ganze ist 3D, aber auf den ersten Blick würde ich sagen man kann einfach eine Dimension weglassen um es 2D zu machen. Z-Koordinate auf Null setzen geht auf jeden Fall.
(Quelle: functions_coolcat.pas)



Du musst die Funktion nur noch so umbauen das sie dir nicht den nächsten Punkt auf der Gerade ausgibt sondern eben den Abstand zu diesem Punkt.

_________________
Yeah!

mal ne Frage zum mathematischen Teil
was dort gemacht wird sollte folgendes sein:

C=vektor AP
V=vektor AB
d=|V|
V=v0 (einheitsvektor)
t=V*C

danach ist A+V*t der Punkt auf der Geraden, der dem Punkt P am nächsten ist
warum? was macht das skalarprodukt dort genau?

Ich versuche es mal kurz zu erklären:

Seien A und B Punkte auf der Gerade, P ein Punkt und X der Punkt mit dem kürzesten Abstand. Das bedeutet das Dreieck AXP hat einen rechten Winkel bei X (denn der kürzeste Abstand zwischen Punkt und Gerade ist immer eine Gerade, die orthogonal zur Anfangsgerade steht).
Alpha sei der Winkel zwischen AP und AB.

Dann gilt, da AB ja nur eine Verlängerung der Strecke AX ist:
AP * AB = |AP|*|AB|*cos(alpha)
Gleichzeitig gilt:
cos(alpha) = AK/HYP = |AX| / |AP|

AP * AB = |AP|*|AB|*|AX|/|AP| = |AB|*|AX|

Also gilt: |AX| = AP * AB / |AB|
für die Länge des Vektors AX.

In Vielfachen des Vektors AB:
t = |AX| / |AB|
Und das ganze in die Geradengleichung eingesetzt:
X = A + t * AB

Alles klar?

PS: Danke Coolcat, auf die Idee bin ich bis eben auch noch nicht gekommen. Und das obwohl ich das im Matheunterricht bis zum Erbrechen mit Hilfsebenen etc. machen durfte.

MfG

verdammt...
und das nach mathe-LK und wdhl des stoffes im 1.semester...
ok danke so weit

noch ne Frage zu dem Baum...
wie baue ich den (in Delphi) auf?

prinzip ist klar: jeder knoten hat 4 unterknoten
jedes blatt hat bis zu 5 linien/punkte
wäre soweit:


tja...wie füge ich die zusammen?
und wie baue ich den baum? z.b. wenn ich nen leeren baum habe. in den füge ich nach und nach punkte ein (ebn sobald die feststehen), dann muss ich ja gelegendlich mal ein blatt umsortieren und nen baum drüberhängen...

kann mir das grad nicht vorstellen, wie das gehn soll

Jedes Blatt kann beliebig viele Linien/Punkte aufnehmen.

Du beginnst damit, dass du dem Wurzelknoten einfach mal alle Linien/Punkte zuweist. Dann geht es einfach weiter mit der folgenden Regel:
Enthält ein Knoten mehr als, sagen wir 8 Linien/Punkte, wird dieser Knoten rekursiv unterteilt. D.h. du testet einfach für jeden der vier Kinder ob die jeweilige Linie mit der BoundingBox kollidiert. Wenn das der Fall ist wird die Linie dem Kindknoten zugeordnet. Eine Linie kann so auch mehreren Knoten zugeordnet werden. Das machst du einfach rekursiv solange bis entweder aller Blätter weniger als 8 Linien haben oder du eine maximale Tiefe (zur Sicherheit, falls sich z.B. mehrere Linien in einem Punkt schneiden) erreicht wurde.

_________________
Yeah!

ja das prinzip habe ich verstanden. aber soll das ganze dann so aussehen:


dann hätte ich ja in jedem ast nochmal die ganzen linien/punkte

Das Array kann doch leer sein?

_________________
Yeah!

ja stimmt...aber ein dynamisches array hat ja doch overhead...
weiß ne genau wo die daten gespeichert sind, aber min 4 Byte von dem Pointer auf die structur
aber gut. die sind dann auch egal
werds erstmal soweit probieren

Wenn ich dich recht verstehe, dann willst du deine Objekte "feiner" unterteilen, um auf nummer sicher zu gehen, dass ein möglichst direkter Weg gefunden wird.
Das ist aber weder nötig, noch werden die Wege dadurch besser.

Der Algorithmus mit den "BB-Eckpunkte" basiert auf der Überlegung, wie man sich in unbekanntem Gelände auch als Mensch fortbewegt.
Dort sind die Eckpunkte die Grenzen von Hindernissen bzw. "Sichtkanten" wie z.B. Hausecken. Wenn du möglichst effizient um eine Hausecke rumlaufen willst, dann läufst du auf sie zu um dann, sobald du hinter die Hausecke gucken kannst, zum nächsten derartigen Punkt zu laufen (oder zum Ziel).
Falls die ein Fall bekannt ist, wo mehr Eckpunkte bei gerade Objekten bessere Navigation zur Folge hat dann würde ich den gern wissen. Runde Formen muss man anders unterteilen, da sonst die Eckpunkte der Boundingbox zu weit vom eigentlichen Objekt entfernt liegen.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

ich hatte vor, die idee von coolcat zu nehmen, aber die anzahl der wegpunkte zu reduzieren.
weil die idee den vorteil hat, dass ich auch teleporter benutzen kann durch (mehr oder weniger) manuelles einfügen zusätzlicher verbindungen.

bei den BB versteh ich noch nicht ganz, wie das ganze am ende funktionieren soll.
wenn du den algo (also vorbereitung und wegsuche) mal als pseudocode formulieren kannst, kann ich das vl ebsser einschätzen

"Mein Algorithmus" ist der aus dem Tutorial, halt nur mit einem Vorberechnungsschritt.
Entweder die Bounding Boxen sind bereits im Datenmodell der "Hindernisse" enthalten, oder aber du musst die erst erstellen.
Wenn dein "Level" aus linien besteht, dann ist dies recht leicht. Du musst einfach nur jeweils 2 Punkte links und recht vom Ende einer Linie postieren. Fertig. Optimieren kannst du das ganze noch, wenn du Linien die aneinanderstoßen am Schnittpunkt nur 2 Navigationspunkte spendierst anstatt 4 (da jeweils 2 aufeinander liegen).

Start und ziel sind dann ebenfalls noch Navigationspunkte. Allerdings welche, die dynamisch ins Netz eingefügt werden.

Und wenn dir das Raster aus dem Tutorial zu grob ist, kannst du auch einfach das "OpenGL Gitter" nehmen. Also quasi eine beliebig hohe Auflösung.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

also praktisch: an jedem ende einer linie 2 punkte erstellen (sofern diese nicht zu nah an einer anderen linie sind)

also so(s. Anhang)

dann soweit wie möglich verbinden (immer wenn kein SP mit einer linie vorhanden ist)

bei der wegsuche dann
start/ziel je als wegpunkt mit einbinden und so weit möglich verbinden

die boundingboxen sind nur dafür da, unnötige linienschnittpunkt-prüfungen zu vermeiden (da wenn linie nicht in BB-->linie schneidet nicht linie in BB)


so weit richtig verstanden?