Ich möchte für ein Spiel eine wegfindung erstellen. Da ich schon eine sehr schnelle A* variante habe, würde ich die gern weiterverwenden.
Dafür brauche ich eine Karte mit Feldern gleicher größe (also simple koordinatenquadrate)
für jedes feld muss in der Karte ein wert stehen für begehbar/nicht begehbar

Diese karte möchte ich für eine (ziemlich große) ingame karte automatisch erstellen lassen. (das ganze wird noch in gebiete unterteil zwecks performance, aber das ist nicht so wichtig hier)
was ich habe ist folgendes:

1: Alles ist begehbar, außer
2: Alle Objekte sind durch Linien gegeben, die die Kollisionslinien darstellen. Sprich: eine solche Linie ist o.B.d.A. die Begrenzung eines Objektes und darf nicht be-/übertreten werden.
3: In den Terraindaten sind weitere Linien festgelegt, die ebenfalls nicht be-/übertreten werden dürfen
4: Objekte sind weiterhin durch Dreiecke gegeben, die deren grundfläche darstellen (z.b. den boden einer brücke über einen abgrund)
wenn ein solches dreieck vorhanden ist, dann ist auf dessen fläche lediglich eine kollision mit den linien dieses objectes möglich (also keine anderen objecte nach 2 und kein terrain nach 3)

Als beispiel:

Schwarz: Terrain
Rot: Kollisions linien nach 2
Grün: Kollisions linien nach 3
Blau: Objekt dreiecke (hier nur von einem Objekt)

Das könnte z.b. ein haus, ein paar Bäume, ein wasserlauf (begrenzt durch grün) und eine brücke darüber sein.

Schwierigkeit: die linien müssen nicht unbedingt follständig polygone umgrenzen (wodurch alles dazwischen als nicht begehbar markiert werden könnte) sondern auch einfach nur linien sein (falls, z.b. ein haus einen eingang hat)

Wie kann ich das in eine Karte umwandeln, z.b.:


Ich will diese Karte(n) einmal erzeugen (also zeit spielt keine rolle) und dann der spiellogik mitgeben.
jedoch soll das erzeugen auf diese weise mit diesen daten erfolgen.

Jemand ne gute idee?

PS: der A* nimmt auch wege über eck...also nicht nur hoch/runter,links/rechts sonder auch unten links...

Wäre es nicht einfacher, nicht die Knoten, sondern alle Kanten, die eine Linie schneiden, als begehbar/nicht begehbar zu markieren (= ihnen ein unendlich großes Gewicht zu verpassen)? Zwei Knoten auf verschiedenen Seiten einer Hauswand sind schließlich beide begehbar, der Weg zwischen ihnen allerdings nicht .

hm...
wie mach ich das dann mit der erstellung und wegfindung?
bisher habe ich ne karte gehabt. dann habe ich gesagt: bin am punkt X,Y
jetzt suche alle 8 felder rundrum ab und gucke in der karte ob diese begehbar sind oder nicht
falls ja-->hinzufügen

wie mache ich das mit kanten?
wie speicher ich die sinnvoll?
außerdem habe ich ja auch schräge linien...die kanten sind aber waagerecht und senkrecht
wie mach ich das dort?

BTW: Ich hatte vergessen zu sagen: ich will jeweils 10 pixel ingame zu einem feld zusammenfassen in meiner karte...
wegen geschwindigkeit

Hey,

mit Kanten ist nicht die Schnittkante zwischen 2 Quadraten gemeint, sondern eine Verbindung zwischen 2 Knoten.

Mir stellt sich erstmal die Frage, wie groß deine Karte werden soll, ein A* wird halt auch irgendwann langsam
Eine andere Frage ist, wie breit die "Linien" sein sollen, wenn du einfach nur so einen Graphen aufbaust und Knoten als unpassierbar markierst müsstest du ja auch dafür sorgen, dass schräge Kanten auch noch erkannt werden, also dieser Schritt nicht möglich ist:


Eine andere Möglichkeit wäre, sich die "Linien" direkt abzuspeichern, und zur Routenberechnung zu benutzen.
Hab da auch irgendwo mal ein Tutorial gesehen, das lief letztendlich darauf hinaus dass man ausnutzt, dass der kürzeste Weg entweder die Luftlinie ist, oder man sonst weiß, dass man sich irgendwo an Ecken entlanghangeln wird, weil jeder andere Weg länger wäre.

edit: hier war's
wiki.delphigl.com/in...utorial_pathfinding2

das feld ist ziemlich groß
ich glaube da war sogar was mit 1000*1000 feldern
mittels des A* algos geht das ganze halbwegs fix (zumindest ausreichend, also unter 1s)
der A* hat tatsächlich den nachteil, dass er nur 45° wege zulässt, aber keine anderen winkel, die aber dennoch möglich wären
das umgehe ich, indem ich die einzelnen knoten danach mittels breesenham algo und prüfung der verwendeten quadrate weiter vereinfache

in der hinsicht scheint das tutorial ja sehr passend zu sein...
wie aber kann ich eine solche karte automatisch erstellen?
dann kann ich auch nicht die eckpunkte nehmen, wie in dem tutorial, da ja am eckpunkt eine kollision vorliegt
ich müsste den punkt also ein stück außerhalb des objectes legen, was wiederum schwer feststellbar ist.
z.b. ist die brücke ja durch ihre geländer begrenzt. sie selbst ist begebar.
im gegenteil dazu sind bäume ja nicht begehbar

ich hätte es jetzt so gemacht, dass ich zuerst die geländelinien "zeichne", dann mittles der object dreiecke die stücken innerhalb dieser lösche, danach die object lininen zeichne
danach das ganze in ein raster lege und für jedes feld prüfe, ob dort eine linienstück ist, dass nicht gelöscht wurde
wäre ein grafische lösung und vermutlich etwas langsam...aber möglich
nur bleibt das auch von dir angesprochene problem: wann kann man zwischen 2 blockierten feldern hindurch? bzw besser: wie verhindert man das?

insgesammt gefällt mir die idee mit den nodes aber. einfach alle nodes abspeichern und dann statt den 8 umliegenden feldern die erreichbar nodes prüfen
was ich aber noch als problem sehe: was mache ich wenn start/ziel nicht auf einem node liegt? was ja die regel ist. welchen node nehme ich dann? kürzester abstand? dass kann dann aber u.u. eine beule auf der rückseite eines gebäudes sein, an dessen einer seite man grad steht

Im Omorphia-Source gibt's ne Backtracking-Unit, die auch extrem schnell ist (Fullscreen Map mit 1px*1px pro Feld in 2 Sekunden Initialisierung bei 1280x1024).

Der Trick dort geht aber in eine andere Richtung: Ichnutze den Kantengraphen von welchem Feld man auf welches gelangen kann. Kombiniert mit den Map-Daten und den Umrissen der Flächen kannst Du somit relativ einfach den Weg Anhand konvexer Flächen (Jede Fläche stellt ein begehbares Teilgebiet dar) eingrenzen und musst dann lediglich diese Gebiete anhand deren Kanten als Weg auffassen. Somit wird den Wegegraph unabhängig von der Mapgröße und hängt im Wesentlichen von der Map-Komplexität ah, wobei man selbst das mit einer Art Octree-Verfahren machen kann.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

ja an deine unit erinnere ich mich (hatte schonmal ein ähnliches problem )
was ich auch intressant finde, ist dieser ansatz: wiki.delphigl.com/in...utorial_pathfinding2

trotzdem brauche ich nochmal ne genauere erklärung zu deinem.
Was ich habe: eine karte mit strecken, die nicht begehbar sind
diese karte ist sehr groß. (gesammt glaube 12000*3000) kann aber in teilgebiete unterteilt werden(die immer noch groß sind)
jede wegsuche hat min. eine anderen startpunkt und fast immer einen anderen zielpunkt.

ein manuelles erstellen eines graphen kommt aufgrund der größe und komplexität nicht in frage

wenn es also möglich ist, die datenstruktur automatisch erstellen zu lassen (am besten beim laden des programms) und die eigendlich wegsuche sehr schnell geht, ist es eine alternative

wie kann ich also z.B. deinen algo nutzen?
woher nehme ich kanten?
ich hätte ja eher eine anzahl an formen (quadrate, rechtecke oder dreiecke) von denen ich höchstens sagen kann, ob in ihnen eine kollisionslinie ist, wodurch es nicht begehbar ist
möglich wäre dann, alle begehbaren zu speichern und zusätzlich als kanten die einzutragen, die original direkt aneinanderliegen

schwierigkeit, die ich noch sehe: die benachbarte form muss immer vom mittlepunkt aus direkt erreicht werden...sonst passiert es vl, dass ich auf einmal durch ein blockiertes durchgehe.

Der Trick meines Algos ist, dass jeder Knoten in meinem Graphen eine Knoten, jeder Übergang von einer Fläche zu einer anderen eine Kante ist. Für die Wegsuche musst du nun deinen Standpunkt in die beiden zu Start und Endpunkt gehörigen Flächen umwandeln, für diese Flächen den schnellsten Weg suchen und dann anhand dieser Folge von Flächen den darauf kürzesten Weg ermitteln.

Die Generierung der Datenstruktur kann hierbei im Wesentlichen automatisch erfolgen, wenn du die Begrenzungskanten für jede Fläche bereits kennst (bin ich mal von ausgegangen, basierend auf deiner Beschreibung oben). Wenn du die Begrenzungen kennst, musst du aus diesen zuerst Flächen bauen (dürfen Polygone sein im ersten Schritt) und zerlegst diese zusätzlich in kleinere (konvexe) Polygone, sollte eine Fläche konkav sein (Direkte Wege gehen nur für konvexe Figuren über Geraden).

Wegfindung dann zuerst am 1. Graphen (der mit den beliebigen Flächen), danach für jedes gefundene (konkave) Polygon zusätzlich am zweiten Graphen (für den Weg innerhalb der Fläche) und zuletzt dann die gefundenen Punkte wieder in die Real-Koordinaten überführen und dabei die Strecke ggf. vereinfachen ...

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

uff...
hättest du eine skizze, so dass ich das sehen kann?
kann mir grade schwer vorstellen, wie du das meinst.

alles was ich kenne sind strecken...die machen nicht unbedingt einen sinn in der landschaft...
weiß nicht, wie ich daraus (für die wegfindung) sinnvolle flächen generiere

z.b. sowas hier:

Um jede Linie hast Du immer auch einen gewissen Rand, da du nicht "in der Mauer" gehen kannst. Diese Ränder rund um deine Linien bilden gewisse Grundflächen, die nicht begangen werden können. Für deine Wegfindungsmap brauchst Du nun nicht die Wege, die nicht begangen werden können, sondern deren Umkehrung. Dazu verbindest du jegliche nicht begehbaren Flächen miteinander. Die daraufhin entstehende(n) Flächen teilst Du so ein, dass diese keine "Löcher" mehr aufweisen. Dafür gibt es entsprechende Algorithmen, die IMHO im DGL-Wiki erklärt sein müssten (Stichwort Konkave in Konvexe Polygone umwandeln .

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Danke für deine Bemühungen. Hab mich weiter damit beschäftigt, aber da ich bei deiner Variante zu viele Fragen hab, um es sinnvoll alleine hinzubekommen, geschweige dann fehler zu finden, nehm ich doch wieder meinen A* algo.

Habs aber aufgegeben quadratische Felder zu nehmen und mir einen Graphen erstellt. 20k Knoten sollte mit A* locker machbar sein.
Sollte es am Ende keine guten Ergebnisse liefern, werde ich mich trotzdem mit deinem befassen. Dann werden viele Fragen dazu auftauchen

Ok rest in neuem Thread

Neuen Thread hier bitte als Follow-Up markieren ... TIA.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

der neue Thread hat nur bedingt was mit dem hier zu tun. darum nur ne notiz am rande
ist ja ne neue frage

außerdem hab ich den grad erst geschrieben
www.delphi-forum.de/....php?p=578351#578351

was heißt "TIA"?