Genau.
Beim Bild hätte ich allerdings an der Ecke innen auch einen Knoten gemacht.


Es gibt einen Fall wo der Algoithmus nicht optimal arbeitet. Und zwar, wenn es sehr große freie flächen ohne hindernis auf dem Weg zum Ziel gibt. Da freie Flächen keine Knoten enthalten, können sie nur "überwunden" werden, wenn hinter der "Freien Fläche" ein Hinderniss bzw. ein Knoten ist und der mit dem knoten auf der anderen Seite der freien Fläche verbunden ist.
Das Problem tritt dadurch auf, wenn man sagt "alle Knoten innerhalb eines bestimmten Radius mit einander verbinden, wenn sie nicht verdeckt sind." Ist die freie Fläche größer als der Radius, geht dann keine Kante durch diese "Wüste" .

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

Genau wegen diesem Problem verteile ich Knoten in einem einheitlichen Raster über die Map....

_________________
Yeah!

Jup... Man müsste das irgendwie sinnvoll kombinieren. So dass nur dort Knoten hinzugefügt werden, wo welche Fehlen.

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

_________________
Yeah!

ich würde es wenn dann eher andersrum machen: genau dann einen einfügen, wenn im radius von x kein andrer knoten ist...
weil ich die an den ecken nicht entfernen darf...

BTW: wie mache ich es am besten? z.zt. habe ich es so, dass jeder knoten mit jedem versucht wird zu verbinden. (habe nur die knoten an den ecken)
bei start und ziel mache ich es genauso: so viel wie möglich verbinden.

vorteil: kürzester weg wird gefunden. (ohne nachberechnungen, die ja doch wieder darauf hinauslaufen, strecken ohne hindernis zu finden)
nachteil: viele verbindungen-->lange suchzeit (u.u.)

Dann kannst du dir das Wegnetz fast sparen, da die Laufzeit für eine Wegsuche explodiert. Du musst eine maximale Entfernung festlegen. In einem Ansatz hatte ich diese 1.5*Rastergröße gewählt, damit diagonale Verbindungen im Raster noch möglich sind, mehr aber nicht.


Tja, wie willst du den wissen an welcher Stelle du prüfen willst ob im Radius x kein andere Knoten ist? Hm, einfach alle Positionen testen? Tja das sind zuviele...ein Raster also....ja, das war mein Vorschlag für dieses Problem...
Ich behaupte nicht, dass das nicht irgendwie geht, aber mir fällt kein Weg ein.

Edit: Wobei, da kommt mir eine Idee:
Für jeden bestehenden Wegpunkt beziehst du nicht nur die Entfernung mit ein, sondern auch irgendwie die Richtung. Z.B. wenn sich von einem Punkt p aus gesehen zwischen 30 und 90 Grad kein anderer Wegpunkt im Abstand x befindet, wird einer bei Entfernung 0,7*x und 60 Grad einer eingefügt.....irgendwie so.

_________________
Yeah!

da ich vorhatte nen A* algo drüberzujagen, war ich der meinung, dass das mit der laufzeit dann kein problem ist.
es wird ja vom starpunkt geguckt, welche felder erreichbar sind. die werden hinzugefügt (sofern nicht vorhanden)
aus der liste der zu bearbeitenden knoten wird dann derjenige betrachtet, der die möglichwerweise bester route bestimmt (entfernung von start über knoten bis geschätzt zum ziel ist am kleinsten)
bei ner einfach feldermap (karte nur aus quadratischen felder, nahbarfelder sind erreichbar, felder sind möglicherweise nicht begehbar) geht das sehr fix. er geht (im normalfall) gerade durch und macht kaum überflüssige berechnungen (je nach hindernislage)

was meinst du mit rastergröße?
ich habe eine mapauflösung in der 10px einer koordinate ingame entsprechen


meine idee war: setze im abstand Z je in X und Y richtung einen wegpunkt gdw. im umkreis von Z kein wegpunkt ist

weil wegpunkte später zu löschen, würde zu dem problem führen, dass ich evtl. nicht mehr um kanten drumrumkomme.

mein problem ist, dass ich die anzahl der wegpunkte möglichst gering halten wollte. die anzahl der verbindungen ist weniger das problem, da der A* das dann schon macht (hoffe ich) nur dauert das erstellen z.T. sehr lange...
denn wenn ich in jedem rasterpunkt (falls das eine koordinate meint) einen wegpunkt setze, habe ich für jede koordinate einen wegpunkt.
die map insgesammt ist 23000x6000 koordinaten groß (wobei es wie gesagt gebiete gibt, so dass ich die map dort jeweils in kleinere stücke aufteilen kann)

PS: Im anhang mal meine Unit für den QuadTree mithilfe dessen ich die wegpunkte erstelle.
Ich kontrolliere erst, ob ein wegpunkt gültig ist, und füge ihn dann ein.
in der einfügen procedure wird erst getestet, ob in der nähe schon einer ist. sonst wird er an der richtigen stelle eingefügt
vl kann die ja mal jmd kontrollieren

Also zu aller erst mal die Feststellung:

Wenn du nur die BB-Knoten an den Hindernissen hast, hast du erstmal ein gültiges Netz welches dir hilft einen Weg um die Hindernisse herum zu finden.

Das Problem ist, du musst teste ob jeder Knoten mit jedem Verbunden ist. Das kann u.U. lange dauern.

Wenn du die Suche nach Nachbarknoten auf einen Radius eingrenzt, kann es passieren, dass Wege über große Freiflächen nicht gefunden werden.

Identifizieren, ob große freiflächen existieren kannst du mit einem Quadtree.
Du legst einfach alle Knoten in einen Quadtree ab. Die Quadtrees sind am Raster ausgerichtet. Falls es ein Quadtree-Blatt gibt, welches keine Knoten enthält, platzierst du einen Knoten (möglichst) im Zentrum des Blattes.

Auf die Art sollte der gesammte Level mit Knoten bedeckt werden. Wie groß die Blätter des Quadtrees sind hängt vom Radius ab den du beim "finde Nachbarknoten" nutzt.

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

das problem wenn ihc nur BB knoten verwende ist, dass ich nicht durch einen durchgang durchkomme.
z.b. bei dem tor durch die mauer in die stadt rein oder bei 2 schrägen objecten, deren BBs den durchgang dazwischen so verschließen

ich werde versuchen, einen mittelweg zu finden. also mit möglichst wenig punkten auszukommen
aber ich denke am ende wird es so sein, dass ich in einem bestimmten abstand punkte vertreuen muss...

Mal mal die beiden beispiele auf. Das mit den schrägen ist glaub ich gar kein Problem. Wir gehen ja mittlerweile von BoundingBoxen auf Linienebene aus.

Das Tor ist was besonderes. Wenn da keine Lücke in der Mauer ist, dann musst du diese Knoten gesondert behandeln. D.h., wenn du feststellst, dass ein Knoten zu einem Tor gehört, dann kann eine Kante zu allen anderen Torknoten dieses Tores gezogen werden, auch wenn dabei eine Linie gekreuzt wird.

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

BB auf linienebene?
wenn es keine AABB ist, dann wäre eine berechnung und kollisionserkennung der selben ziemlich aufwendig...

im Anhang hab ich mal ein paar mögliche problem objecte aufgemalt
jede farbe=ein object

rot: tor
dunkelblau: brücke (mitte ist begehbar, geländern nicht )
grün: weiteres geteiltes object (Bsp: marktplatz mit säulen)
schwarz/hellblau: object nicht geschlossen. 2 objecte an/übereinander (felsen)
rosa: problem mit BB und durchgängen. oberer teil auf objectebene, unterer auf linienebene