das prüft er alles vorher, bevor er ein schritt tut, und um das nen bissle schneller zu machen tut man einfach von allen nächsten den nehmen der am nahesten am ziel is (den 'aufwand' sozusagen berechnen, könnte man auch als pseudo schätzung, welcher wegpunkt als nächster wohl der beste is, bezeichnen), meistens bekommt man dann einen relativ guten weg *a-star afaik*. Die sauberste aber auch 1000x so rechenaufwendige methode is alle möglichkeiten durchzugehen.

Another1

...relaxing..atm =)
... und Schweiz suckt!

ja, richtig. und ich denke nicht das es mal an der zeit ist das beste AI system zu erfinden sondern noch ein paar jahre zu warten bis die CPU auch ein solches AI system handlen kann... und naja... das was die CPU rausholt steckt windows wieder ein... wenn alle jetzt noch win95 hätten währe das auch jetzt schon kein problem ;)

ob nun delphi, c oder java. kein programm lässt sich mit allen 3en gleichschnell entwickeln.

Ja genau, hier bietet sich A* an. Cyanide's Konzept mit den Wegpunkten ist ja eigentlich "nur" ein cleverer Trick, um die Anzahl der Wegpunkte auf die wirklich relevanten zu reduzieren: Wenn man auf eine Tile-Map einfach so A* losläßt hat man sehr viele (Breite*Höhe) Knotenpunkte im Graphen. Durch eben diesen Trick wird diese Zahl ordentlich reduziert, wodurch dann auch A* wiederum schneller laufen kann.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

is natürlich wahr.. okay, ich ändere mein konzept... jetzt werden an allen ecken nur von vornerein solche punkte hingerechnet und ich berechne trotzdem noch einen weg mit diesen wegpunkten. nach dem motte direkte linie und dann immer weiter aufteilen, bis eine mögliche strecke gefunden wurde (aber immer nur eckwegpunkte benutzen :) )

ja. das ist gena richtig. und wenn du die wegpunkte auswiegst dann wirst du auch das damit erreichen können was du mit der pro-lösung erreichst. welcher weg ist gefahren behafteter und welcher führt am schnellsten zu wichtigen punkten und gleichzeitig an kriesenpunkten vorbei... (wir wollen ja dem krieg als überzeugte pazifisten aus dem weg gehen *GGG* *scherz*)

btw. ich schröre nicht auf meine lösung, aber bisher hält sie stand *g*

ob nun delphi, c oder java. kein programm lässt sich mit allen 3en gleichschnell entwickeln.

Das einzige Problem, das noch besteht: Was macht man, wenn zwischen zwei Wegpunkten unebenes Terrain etc. liegt (also Terrain, dessen Kosten höher sind). Das ist aber überhaupt ein interessantes Problem. Wahrscheinlich kann man den schwerer passierbaren Bereich (Sumpf oder so) als "dichteres Medium" ansehen, und dann Formeln analog zur Brechung von Licht anwenden.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

na dazu ist ja der sog. kostenfaktor zuständig... der algorithmus versucht einen guten ausgleich zwischen kosten und umweg zu finden...

das ist in der tat interessant. so auf die schnelle fällt mir nur eines ein. du ziehst eine linie von punkt a nach punkt b. dann gehst du die linie durch... dabei setzt du gedanklich alle "0.5 einheiten (1ne einheit = eine tilelänge)" und rechnest die darunterliegenen untergründe zusammen. wenn der aufwand der dadurch rausgeht grösser ist als von weg 2 oder 3 dann gehe nicht dadurch... weiterhin könnte aber interessant sein die figur um den "sumpf" herumzuführen... muss ich mal drüber nachdenken

ob nun delphi, c oder java. kein programm lässt sich mit allen 3en gleichschnell entwickeln.

eben dafür gibts den kostenfaktor... der sumpf kostet was, also wird der nächstbeste weg gesucht... und ist alles andere blockiert, ist der wert des sumpfweges (wert=0.7) immer noch höher als wenn der andere weg blockiert ist (wert = 0). Dann nimmt der Computer weg Sumpf...
Die länge eines Umweges fließt natürlich auch in den wertfaktor/kostenfaktor ein... Dann kann der Computer ganz einfach entscheiden, welches der günstigste wert ist...

absolut richtig. schau aber mal volgendes problem: zwischen 2 punkten liegt passierbarer untergrund. sonst würden hindernisseckpunkte gesetzt sein. dieser untergrund kann aber vieschiedene eigenschaften haben. also muss man wohl oder übel das auch noch mit berechnen :-/

ob nun delphi, c oder java. kein programm lässt sich mit allen 3en gleichschnell entwickeln.

oder du setzt die wegpunkte intelligent, so das er wenn z.B anner grenze von Kosten=1 untergrund zu kosten=2 untergrund noch kein wegpunkt gesetzt wird, aber ab 3 kostenpunkte unterschied das wie nen hindernis gehandelt wird und genau an der grenze nen wegpunkt hingepackt wird.

Another1

...relaxing..atm =)
... und Schweiz suckt!

Hmm... auch das sind interessante Lösungsansätze. Ich persönlich würde ja auf die Brechungsgesetze schwören (sobald ich die Formeln mal raus hab ;)). Man müßte die verschiedenen Methoden mal vergleichen.

Auf jeden Fall muß man bei meiner Methode nicht mit Wegpunkten rumpfuschen - die Wegpunkte bleiben wo sie sind.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

ja... stell dann mal deine lösung vor. es würde mich wirklich interessieren !

ob nun delphi, c oder java. kein programm lässt sich mit allen 3en gleichschnell entwickeln.

.. mit den wegpunkten und dynamischen maps ..

Wenn zb. der Wald auf nem Feld abgeholzt ist wird eine message gesendet .. (muss je eh sein um das pic in geholzten wald statt normalen zu verwandeln)
und mit der message schickt man einfach einen 2ten boolean an das prog also:

Sub Holzing (:-)

'Abgeholzt:
pic223.245 = abgeholzt '(bild des tiles in "abgeholz" ändern

var223.245 = True '(die koordinate 223.245 ist also jetzt "walkable")

nun ist 1. das pic geändert und die KI kann dieses stück wald als Weg verwenden. -> Der Wegpunkt, der evtl. in der Nähe ist wir einfach auf das neue "freie" Feld verschoben!

greez Longbow

_______________
cooldata.org - real bugware

... uhmhum

Another1

...relaxing..atm =)
... und Schweiz suckt!

anders:

vorher ->
pic[223, 245] = WALD;
wert[223, 245] = UNPASSABEL; // UNPASSABEL = 0

message weil geholzt ->
pic[223, 245] = GRASLAND;
wert[223, 245] = GRASLAND_WERT; // GRASLAND_WERT = 1

und bitte vergesst den kostenfaktor und bleibt beim wertfaktor...

kostenfaktor = wertfaktor ;)

ob nun delphi, c oder java. kein programm lässt sich mit allen 3en gleichschnell entwickeln.

Das hört sich ja ganz passabel an, aber ich glaube du meintest "UNPASSIERBAR" in deinem Codebeispiel (sorry *g*).

Ansonsten ist das alles schön und gut, aber die Waypoints muß man trotzdem irgendwie neu berechnen...

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

naja... zwischen den zwei wegpunkten kann man dann halt dynamisch was berechnen...

( unpassierbar, unpassabel, wo ist da schon der unterschied :) )

was haltet ihr mal von folgendem project: OpenAI ! :D
*folgendem wird nicht mit v geschrieben ich blödkopp*

ob nun delphi, c oder java. kein programm lässt sich mit allen 3en gleichschnell entwickeln.

Ich glaube, daß gibt's sogar schon irgendwo. Das Problem ist: Man kann schlecht eine universelle KI programmieren. Eins der schwierigsten Probleme beim Schreiben von KI (damit meine ich jetzt keine Algorithmen a la Pathfinding) ist es, vernünftige Interfaces zu finden - gerade bei so Dingen wie neuronalen Netzen.

Von daher läßt sich eine universelle KI kaum machen...

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

*lol*... wenn du dih mit neuronalen netzen auseinander setzt dann kannst du das mit OpenAI vergessen ;)))))))))))))))))
ich dachte da wirklich eher an pathfinding ! neuronale netze kannst du bei cyborgs besser gebrauchen ;)) (wie bau ich ein brötchen ?)

bei den functions die ich gedacht hatte übergibst du nen array indem alle wegpunkte drin sind die ereichbar sind... du bekommst die richtung zurück in die du laufen musst und die entfernung zum nächsten punkt. alle wegpunkte haben einen wert der angibt wie schwer es ist einen wegpunkt zu passieren. also bei 2 wegpunkten zwischen denen sumpf liegt wird zu dem weg ein aufschlag berechnet ! usw...

btw... ähnlich kannst du das mit vectoren dann auch in 3d anwenden !

man kann das ganze ja so simpel halten das man aus den gegebenen funktionen noch selber was zubauen kann... das würde gehen

ob nun delphi, c oder java. kein programm lässt sich mit allen 3en gleichschnell entwickeln.

Cy:
Zu deinem "ersten" Vorschlag:
Ich habe mal ne Funktion gebastelt, die genau das testet -> alle 10 "klicks"
wird die Steigung und Neigung ... getestet und danach wird dann festgestellt, ob das passierbar ist oder net und es lief wunderbar :D Und da man das ja nur bei jeder Neuberechung des Phades machen muss, ist das net so rechenaufwendig gewesen, da dass ehh nur so alle 30 sek oder so gemacht wurde .....

LoL hier ist meine erste "Hitengine", die ich mit Delphi gecodet habe als ich 13/14 war -> da habe ich gerade angefangen zu proggen
Das "Spiel" (Das was da von existierte) war 2D und der hat einfach alle Punkte in nem Array gespeichert und um zu testen, ob da ne Wand ist oder net musste man dann einfach nur noch das Folgende machen:
if(MapArray[Player->origin.x][Player->origin.y] == Blabla)
Jop das hat wunderbar funktionnier und war nicht rechenaufwendig, aber das dumme daran war, dass es ein Wenig mem schluckte :D
Egal, dass kann man dann vielleicht in 10 Jahren benutzen, wenn man 60 Gb Ram hat.

Zurück zum Phatfinding
Jo Das mit dem universellen Bot, der ohne Wegpunkte auskommt ist so eine Sach für sich. Ich war selber mal so "verrückt" und habe das "in Angriff genoommen". Das Problem dabei ist nur, dass der Bot für eine "Kastenengine" war und man dadurch wenigstens noch irgendwie eine Logik in die Gengend bringen konnte, aber bei den neuen Spielen ist das ja so, dass man riiesige Landschaften haben muss mit noch größeren Details (Also Häuser/Städte ....) ....
Und dann bring dem Bot mal bei in Solchen Landschaften durch kleine Höhlen, wenn nötig ... zu krauchen ....

Ahh ja und ich bin der Meinung, dass das Durchrechnen der Wegpunkte net mal so Rechenaufwendig ist ! Wenn man dem Bot zB. das nur alle 10 Sek... (In Abhängigkeit der Entfernung !!, da sie erst im Kampf/wenn sie sichtbar sind mit/von einem "Menschen" relgelmäßig die Umgebung testen müssen)machen lässt und der dann einen Zwischenstand abspeichert , also dass er nicht jedes mal vom Neuen beginne darf -> In etwa so, dass man in einem Kampf .... nur die in der unmittelbaren Umgebung liegenden Wegpunkte zwischenspeichert und somit nur diese Betrachtet ...

Being in john Malkovich
.....

*lol* ich ahbe das zuhause schon noch ne ecke weiteroptimiert... aber langsam wirds richtig kompliziert... aber insgesammt 40% weniger rechenaufwand und nur noch GANZ WENIGE punkte *fg* habe dabei einfach um einen eckpunkt ein quadrat gezogen. aber is nicht ganz so einfach wie sich das jetzt anhört ;) ich bin aber von dem fall ausgegangen das auf dem weg von punkt a zu punkt b eine schwer passierbare strecke ist. diese wird dann mittels schnittpunktberechnung und umführung so berechnet das man genau sagen kann: ist es sinnvoller um den sumpf zu laufen oder mitten durch... und dabei nur die hälfte der wegpunkte halt :D

ob nun delphi, c oder java. kein programm lässt sich mit allen 3en gleichschnell entwickeln.

. klar ist, wenn du zwar einen sumpf vor dir hast mit ca. 5 Schritten und drumrum braucht man ca. 30 sollte die ki auch entscheiden was nu besser ist... also wenn der sumpf keinen schaden bringt sondern nur zeit wäre das wohl besser!

____
zu den Wegpunkten

warum sollen die neu berechnet werden? wenn ein feld frei wird wird der Wegpunkt einfach verschoben ...

greez

_______________
cooldata.org - real bugware