-hrhr- naja, wer solchen Mist schreibt ?

Ich natürlich :D

Logischerweise ist das totaler Schwachsinn um das nur mal klarzustellen!
Wer's mir übel genommen hat, bei dem möcht' ich mich entschuldigen, aber das ganze lag mir gerade so auf der Zunge ;)

C ya!

Against TCPA | Resourcecode.de | Blender 3D | [ Darkzone | Pandorra | Alpine ]

Lol. Bei mir liegts jetzt in der Signatur...
Danke nochmals...

mann, kan cih vielleicht jetz ne ernshafte antwort bekommen?

„Und da wir uns ja seit heute etwas näher gekommen sind, kann ich nur sagen: Mir hilft da immer Norther volle Lautstärke (so wie jetzt), sodass die ganzen unrasierten, Wasserpfeife rauchenden, alternativen Wichsstudenten aus ihren, aus Bananenschalen und Abfall gebastelten, Sitzkissen fliegen.“

Hast du doch schon!

Die KI in SvenCoop ist in keinster Weise modifiziert.
Was da so intelligent aussieht sind wahrscheinlich die scripted sequences und die schlaue Platzierung der Waypoints, auf die die KI der Gegner zurückgreifen kann.

Against TCPA | Resourcecode.de | Blender 3D | [ Darkzone | Pandorra | Alpine ]

danke!

Zitat:

"1337" schaltet Bits für eine synchrone Datenabwicklung an der CROM-Schnittstelle ein und aktiviert somit eine hochsensible Transformation der Datenströme, die zum FPU führen. Diese werden dort assembliert und durch den Mainstream deines Mainboards direkt zur CPU weitergeschickt. Genau dieses Verfahren ermöglicht eine der besten Half-Life KI's!

„Und da wir uns ja seit heute etwas näher gekommen sind, kann ich nur sagen: Mir hilft da immer Norther volle Lautstärke (so wie jetzt), sodass die ganzen unrasierten, Wasserpfeife rauchenden, alternativen Wichsstudenten aus ihren, aus Bananenschalen und Abfall gebastelten, Sitzkissen fliegen.“

AyAyAy, ein paar von den Vorschlägen, speziell das mit dem Vis hab ich garnet geschnallt, deswegen hoffe ich einfach mal, daß ich nix altes Vorschlage:

Mein Vorschlag wäre einfach das Dijkstra's (Was für ein Zungenbrecher) Verfahren etwas zu erweitern, indem man einfach in einem festgelegtem Gitter z.Bb mit einem Abstand von 10 Feldern nichtsichtbare Wegpunkte anlegt, die einfach zu ihren benachbarten Wegpunkten die kürzeste Strecke inklusive der Ablaufdauer des Weges gespeichert haben , so daß im Prinzip die Pathfindingroutine nur den Weg von der Spielfigur zu den benachbarten Wegpunkten und den Weg vom Zielpunkt zu den benachbarten Wegpunkten direkt berechnen muß, während danach dann der kürzeste Weg zwischen den Wegpunkten berechnet wird, welcher abhängig von den Abständen der Wegpunkte zueinander entweder schneller beim berechnen oder schneller beim ablaufen für die Figur ist, darin läge auch die Skalierbarkeit. Sollte es ein besonders großer Level sein könnte das ganze mit den Wegpunkten noch einige Ebenen weitergführt werden (mit der dementsprechenden Speicherlast).

Die größte Schwäche hier dürfte wohl allerdings der Effizienzverlust sein, wenn ein Wegpunkt auf einem nicht erreichbaren Ort liegt und somit im Prinzip einen unendlich hohen Wert für die Ablaufänge liefert, wodurch der ein effizienter Weg knapp am Wegpunkt vorbei evtl ignoriert werden könnte. Das ganze könnte in einer ziemlichen Katastrophe ausarten, wenn mit ein wenig Pech sehr viele Wegpunkte auf nicht erreichbaren Stellen liegen.

Are you gonna miss me ?
Only until I go to the Newsstand and buy a Hustler

Und wenn ich scheiße gepostet habe, liegt's am Schlafmangel ;)

Are you gonna miss me ?
Only until I go to the Newsstand and buy a Hustler

Nun, für wirklich große Karten wäre es in der Tat nützlich, Metadaten zu speichern, eben so eine Art temporäre Wegpunkte. Ein interessantes Pathfindingverfahren lehnt sich an die Natur an.

Und zwar ist es ja so, daß Ameisen auf ihrer Spur irgendwelche Duftstoffe hinterlassen, an denen sich dann andere Ameisen orientieren. Die Duftstoffe verschwinden mit einer konstanten Geschwindigkeit. Die Duftstoffe auf einem langen Weg verschwinden demnach dann eher als solche auf einem kurzen Weg.

Allerdings hab ich sowas noch nie in Spielen angewandt gesehen, und wie immer gilt auch hier daß solche Algorithmen zwar vielleicht nett aussehen in irgendwelchen wissenschaftlichen Arbeiten, aber in der Praxis eben doch Probleme mitbringen.

Ein gezieltes ablegen von temporären Wegpunkten ist aber sicher dennoch sehr nützlich.

Eine andere, sehr kreative, Methode habe ich schon vor einiger Zeit auf einer Webseite beschrieben gesehen. Diese Methode geht aber von einer komplett statischen Karte aus (d.h. keine sprengbaren Brücken, keine abholzbaren Wälder usw.). Dabei wird die Karte in Zonen unterteilt (von einer Art Compiler und so). Die Anzahl der Zonen sollte nicht allzu groß sein (vielleicht 100 oder so).

Danach wird für jede Zone eine Kartenebene berechnet in der gespeichert ist, in welche Richtung sich eine Einheit bewegen muß, die diese Zone betreten muß.

Dafür braucht man bei 8 Bewegungsrichtungen 4 Bit (man sollte ja so Dinge wie: Ziel nicht erreichbar und Ziel erreicht oder Nahe am Ziel auch speichern können). Dieser Algorithmus müßte natürlich noch mit einem Algorithmus zum Ausweichen von anderen Einheiten und Gebäuden überlagert werden, dann ist er aber bei weitem der Geschwindigkeitseffizienteste. Einziges Problem: Bei einer 10k x 10k-Karte braucht man für jede Ebene 50MB RAM ;)

cu,
Prefect

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

mom... das allererste beispiel bringt mich gerade so auf ne idee... da gibt es doch ne möglichkeit wie man das ganze sauheftig optimieren kann :)))

nehmen wir an wir haben nur vierecke. jetzt bildet euch mal beispiel 1 in die köpfe und lass den floddfill krams weg. setzt mal an alle ecken die es gibt nen wegpunkt... also bei alles die folgende muster erfüllen

OX
WO

XO
OW

OW
XO

WO
OX

so. jetzt dürfte nach meinen wirren vorstellungen jede ecke nen punkt quer gegenüber sein. jetzt kann man das mit dem floodfill wiederholen. aber diesmal werden nur die punkte mit zahlen verbunden die wiederum die zielpunkte sehen können. das dürfte die ganze geschichte um ein vielfaches verschnellert haben. ;)

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

Ich verstehe zwar deine OWX nicht so ganz, aber wenn ich deine Rede richtig interpretiere schlägst du einen Algorithmus vor, bei dem einfach an der Ecke jedes Hindernisses ein Waypoint gesetzt wird. Natürlich ergibt sich dann dadurch ein Graph (also eine Verbindung von Waypoints) zwischen all diesen Waypoints, von dem aus man alle Teile der Map erreichen kann.

Das ist in der Tat eine funktionierende Möglichkeit, die hauptsächlich in Situationen verwendet werden kann, bei denen man keine Tilemap hat, sondern einfach eine Menge Hindernisse, die nicht an irgendeinem Gitter ausgerichtet sind (also z.B. ein 3D-Shooter). Aber man könnte das natürlich auch für Tilemaps verwenden - ein kleines bißchen Vorbereitung wäre notwendig, und schon hätte man eine Möglichkeit, lange Distanzen schnell zu überbrücken.

Auf gewisse Weise ist das so eine Art Top-Down Pathfinding, wie es ja schon angesprochen wurde. Der genaue Algorithmus würde nämlich so aussehen:
- suche die Waypoints, die vom Startpunkt aus sichtbar sind (und berechne den Aufwand, um dort hin zu gelangen)
- suche die Waypoints, die vom Endpunkt aus sichtbar sind
- suche mit Hilfe von Dijkstra's oder A* den kürzesten Weg durch den Graphen der Waypoints

Das könnte tatsächlich sehr gut funktionieren. Einziger Haken ist hier (wie bei so vielen anderen Methoden auch): Was soll passieren, wenn die Karte dynamisch ist (z.B. durch abholzbare / wachsende Wälder etc...)

cu,
Prefect

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

richtig. der grösste aufwand bei dem ganzen wird sicherlich sein, dass die waypoints herausfinden müssen welche weiteren waypoints sie erreichen können. nimmst du jetzt beispielsweise ein tile raus hast du in jedem fall min. 2 neue waypoints die sich aus der lücke bilden. wenn du jetzt nur noch für die neuen waypoints herausfindest welche waypoints erreicht werden können dann ist das in der performance kaum zu merken. jetzt kann man vielleicht nicht die karte in berreiche teilen und speichern welche waypoints welche berreiche sehen (bzw. welche berreiche welche waypoints...). das würde heissen das die neu entstandenen waypoints nur noch die punkte abrechnen müssen die in ihrem berreich gespeichert sind. die bereiche solten auch in gewissen zeitabständen neu nachgerechnet werden , da sich bei einer wand die aus bäumen besteht sich einiges ändern kann wenn es diese wand nicht mehr gibt :) da gibt es so einiges was man machen kann.

das ist nicht soo das problem. nehmen wir mal an das sich ein feld verschiebt oder auf einmal nicht mehr da ist.

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

Zu dem 2D-Waypointsystem noch was, es währe wirklich wunderbar, wenn du alternative Wegsystem .... mit einbauen würdest, also meinetwegen, wenn das Objekt an einem Feld (zB Wasser) angekommen ist, dann programmiere das bitte so, dass er per random .. ein von verschiedenen constant bleibende Richtungen einschlägt also in diesem Beispiel zwischen 1;2 und 2 entscheidet (2 bedeutet alternativer Weg, der sich abhängig von der Landschaft automatisch ergeben sollte).
Dann speicherst du einfach ob 0 bis 8 (richtung) und in diese Richtet er sich dann kontinuirlich also so, dass du eventuell sogar einen Zwischenwegpunkt setzt also:

x = nicht passierbar

2-1-x [Ziel]
3-[0]-x
3-2-x

--->
[Wegpunkt]
2-1-x [Ziel]
3-[0]-x
4-5-x

......

da bei spielt es keine Rolle wo der Wegpunkt ist, da er immer wieder neu gesetzt werden kann also, wenn er hängt dann einfach neuen setzten ....
So und mir liegt nur viel daran, dass er die Richtung einhält, da ich die KI von den meisten Spielen HASSSSE !! um es mal in Worten aus zu drücken.
Da meiner Meinung nach 90% aller Spiele so eine simple Wegpunktmatrix ... haben, dass die Gegner immer von der selben richtung angreifen ...
Also mache am besten noch dazu, dass die Wegpunkte auch noch durch den Gegner beeinflusst werden !! also wenn mehrere Einheiten auf der selben Stelle in einem schlechten Verhältnis zum Gegner sterben, dann adde Punkte !! like this:

0000011223344555555544332211000000
0001122334455[PUNKT]55443322110000
0000011223344555555544332211000000

und so weiter ...
in dem du jedem Wegpunkt eine zweite nicht konstante Variable gibst, die frei beeinflussbar ist.....

Die können ja dann nach einer Weile neu berechnet werden, also wenn eine Einheit nach einem bestimmten Zeitpunkt wieder an der Stelle ankommt und 20 min vergangen sind dann lässt da Objekt den Wert neu berechnen. Also
fl_Add = max(fl_Add-1,0); ..
Egal, das wollte ich nur mal loswerden, wenn ihr schon so heiß über Wegpunktsysteme diskutiert

Being in john Malkovich
.....

hat aber einen grossen nachteil. wenn du nen grosses C hast und in der mitte stehst kommst du nach meiner lösung schneller ans ziel. ich zeige gleich graphisch was ich meine...

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

Es soll ja auch nicht der sinn darin liegen schneller ans Ziel zu kommen, sondern den Feind effektiver zu bekämpfen.

Being in john Malkovich
.....

here is comes: (ohne das grosse c ;))

wir haben ein feld voller tiles

und natürlich wände (bitte nicht fragen wo die herkommen... die sind einfach da *g*)

dann setzen wir hellgrüne punkte an die ecken von allen endpunkten.

jetzt wollen wir wissen welche punkte welche punkte sehen können.

und welche der startpunkt sehen kann *fg* (das gleiche eigentlich auch für den endpunkt... vergessen)

der erste g-punkt (was ein wortspiel) ist überflüssig. der rest läuft nach dem aller ersten prinzip. da das eine schon ziehmlich optimierte lösung ist, kann man diese auch pro zug in echtzeit anwenden. und ich denke man kann es auch mit anothergb02's lösung verknüpfen. man braucht dafür nur lange nicht so viel speicher :) (denk an die 10000x10000 tile's) ;)

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

Ich hab einen ähnlichen Vorschlag, allerdings braucht der Mapper da nicht die grünen Punkte zu plazieren:

Das ganze läuft in wenigen Schritten ab:
Jeder Geländetyp bekommt eine Wertigkeit zugeordnet: unpassierbar = 0, Sumpf = 0,3, Prärie = 0,9, Grasland = 1
1. Es wird eine direkte Linie zwischen Start- und Endpunkt berechnet
2. Falls was im Weg ist (var < 1):
{
1. Es wird eine Schleife initialisiert, die solange läuft, bis eine Route zum
Endpunkt ohne Kollisionen möglich ist:
{
1. Wir rechnen einen zwischen-Wegpunkt ein, der da liegt, wo das
Hindernis vorbei ist.
2. Aus der Anzahl der zu laufenden Felder und dem Durchschnitt der
Geländewertigkeit wird ein Quotient ermittelt.
3. Falls Qutient größer als gewünschter Wert dann nehmen wir diesen
Weg!
4. Falls nichts im Weg, Schleifenbedingung WAHR
}
} sonst { JUHUU! }

öhm... der mapper braucht diese punkte nicht zu setzen. und ich würde fast annehmen das deine methode sehr rechenaufwändig ist. denk mal an echtzeit und an die 10000x10000 tiles *g*

schau einfach mal in welchem muster die grünen punkte gesetzt wurden. is ne super einfache regel. *g*

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

Hmm, Cyanide, hast du davon auch ne lauffähige Demoversion, oder ist das jetzt nur Konzeptgrafik made in Paint? ;)

Ich denke, DHCC könnte nen Tutorial über Pathfinding durchaus vertragen...

cu,
Prefect

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

öhm... immo steht das nur in meinem kopf geschrieben... ich könnt da was machen. frage ich nur c oder delphi *GGG*

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

Ich gehe mal davon aus, daß C besser ankommt ;p

cu,
Prefect

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

CY4N1D3

Zu deinem System:
Ich bin eigentlich der Meinung, dass du der Mr. X das schon mal genau so beschrieben hast/hat -> via mache an allen Ecken einen Wegpunkt ..... ;D
Naja egal, wenn du meinst, dass man das nochmal bildlich brauch :D
;DDDDDDDDDDDDDDD

Being in john Malkovich
.....

Zitat:

Prefect postete
Hmm, Cyanide, hast du davon auch ne lauffähige Demoversion, oder ist das jetzt nur Konzeptgrafik made in Paint? ;)

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

aber das problem bei cyanide ist, das man zwar eine verbindung zwischen den einzelnen wegpunkten hat, aber keinen leitfaden wie man von punkt 1 zu punkt 2 kommt... es könnte dann also passieren, dass von punkt blau der computer sich im kreis dreht, immer über die grünen punkte, er braucht aber einen klaren leitfaden, welchen wegpunkt er als nächstes betreten muss, und das ist das problem...

???

das versteh ich nun garnicht ! der computer würde sich nach meinem beispiel GARNICHT bewegen, würde es keinen weg zum ziel geben ! und die punkte werden ja nach dem system #1 verbunden. das ist nur pathfinding. was der gegner tut wenn er keinen direkten weg zum feind findet is ja ihm überlassen. es dürfte aber keinen punkt in der map geben die kein wegpunkt sehen kann. es kann nur sein das manche wegpunkte sich nicht erreichen können. beispiel ein senkrechter strich durch die map. bei einer map ohne hindernisse gibt es keine wegpunkte. aber eich keine hindernisse, so das der feind direct zum gegner laufen kann ;) und alle probleme die du mit dieser pathfindign variante hast, hast du mit jeder anderen auch. nur kannst du diese ohne grossartige performance probleme ändern (anderen weg berechnen und co.) :)

wie gesagt. du kommst an jeden erreichbaren punkt der map in jedem fall. nur ist es vielleicht komplizierter zu sagen: wenn weg nicht existiert dann mach dir einen. wie beispielsweise bäume fällen (warcraft). die 2 transporter auf der brücke ist nachwie vor nen lustiges beispiel das eintreten kann. wenn man gegnerische einbeiten die einen selber nicht bekämpfen können und die man auch nicht angreifen kann dann kann man diese ja als potenzielle hindernisse betrachten. für einen transproter sind alle einheiten potenzielle hindernisse. (ausser menschen, die kann man überfahren *g*)

gibt es noch ein beispiel dieser art ?

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

cyanide... ich meine das problem da ist, das du auch einen leitfaden brauchst, welcher punkt als nächster angesteuert werden soll... du weißt zwar, das der nie gegen eine wand laufen wird, aber wenn der jetzt mehrere wegpunkte zur auswahl hat, welchen wird er dann nehmen? das ist ja noch nicht bekannt...