Hallo.
Ich habe vohin einen Script entworfen, der raus bekommen soll, ob der NPC innerhalb von 5 WPs steht oder nicht.
Aber etwas klappt nicht so ganz, und ich weiß nicht was es sein könnte.
Ich habe mir gedacht, dass mancheiner das Script vielleicht nutzen möchte und eröfffne dafür halt einen Thread.
Sobald er funktioniert, kann sich jeder bedienen.
Hier der Code
Code:
FUNC INT Npc_GetDistToWPNet (VAR C_NPC NPC, VAR STRING wpName1,, VAR STRING wpName2,, VAR STRING wpName3,, VAR STRING wpName4,, VAR STRING wpName5,)
{
var INT A;
var INT B;
var INT C;
var INT D;
var INT E;
A = Npc_GetDistToWP (NPC, wpName1,);
B = Npc_GetDistToWP (NPC, wpName2,);
C = Npc_GetDistToWP (NPC, wpName3,);
D = Npc_GetDistToWP (NPC, wpName4,);
E = Npc_GetDistToWP (NPC, wpName5,);
if (Npc_GetDistToWP (NPC, wpName1,)<= B
&& Npc_GetDistToWP (NPC, wpName1,)<= C
&& Npc_GetDistToWP (NPC, wpName1,)<= D
&& Npc_GetDistToWP (NPC, wpName1,)<= E)
&& (Npc_GetDistToWP (NPC, wpName2,)<= A
&& Npc_GetDistToWP (NPC, wpName2,)<= C
&& Npc_GetDistToWP (NPC, wpName2,)<= D
&& Npc_GetDistToWP (NPC, wpName2,)<= E)
&& (Npc_GetDistToWP (NPC, wpName3,)<= B
&& Npc_GetDistToWP (NPC, wpName3,)<= A
&& Npc_GetDistToWP (NPC, wpName3,)<= D
&& Npc_GetDistToWP (NPC, wpName3,)<= E)
&& (Npc_GetDistToWP (NPC, wpName4,)<= B
&& Npc_GetDistToWP (NPC, wpName4,)<= C
&& Npc_GetDistToWP (NPC, wpName4,)<= A
&& Npc_GetDistToWP (NPC, wpName4,)<= E)
&& (Npc_GetDistToWP (NPC, wpName5,)<= B
&& Npc_GetDistToWP (NPC, wpName5,)<= C
&& Npc_GetDistToWP (NPC, wpName5,)<= D
&& Npc_GetDistToWP (NPC, wpName5,)<= A)
{
return TRUE;
};
return FALSE;
};
Vermutlich bin ich noch nicht ganz wach und es liegt an irgendetwas Offensichtlichen.
(WPs müssten in genau gleichen Abständen zueinander stehen oderso.)
Vielleicht kommt ja einer von euch auf die Lösung.
mfg Oparilames
Oparilames nachdem er seinen Gesellenbrief erhalten hat:
»Das war's mit dir, du Mistvieh!«
Das Script soll herausfinden, ob ein Npc innerhalb eines Fünfecks von WPs steht, richtig? Das ist nicht ganz leicht und auf Anhieb kann ich dir keine Lösung angeben, aber ich kann dir begründen, weshalb deine Methode falsch ist:
Nur wenn der Spieler von allen WPs gleichweit entfernt ist, liefert deine Methode TRUE.
Seien a,b zwei beliebige WPs und dist(x) der Abstand des Npcs von x, dann forderst du:
(dist (a) <= dist(b)) und (dist(b) <= dist(a)) was gleichbedeutend ist mit
(dist (a) == dist (b))
für alle Paare (a,b).
Übrigens ist dein Code nichtmal syntaktisch korrekt. Du hast zahlreiche unnötige Kommata.
was genau möchtest du damit denn erreichen?
möchtest du, wie sekti es meinte ein fünfeck absuchen?
und sollen alle wps bestimmt sein?
warum setzt du dann nicht einfach einen wp in die mitte der anderen wps und fragst die entfernung zu diesem ab?
Ja ein Fünfeck möchteich absuchen.
Und praktisch wäre das insofern, dass man halt jeden WP nehmen kann - man könnte z.B. Khorinis einzäunen oder Prüfen oder der Held das Sumpflager in G1 betreten hat.
Es wäre schon gut, wenn alle 5 genannt werden würden, aber ich denke wenn man ein -1, erstellt, würde einer der Wps eben wegfallen.
Stimmt die Komma sind überflüssig, danke Sektenspinner.
hab ich mir's doch gedacht: Alle WPs müssen bisher gleich weit weg sein...
Das soll natürlich nicht so sein, hmm...
Oparilames nachdem er seinen Gesellenbrief erhalten hat:
»Das war's mit dir, du Mistvieh!«
Ich habe nochmal drüber nachgedacht:
Für den allgemeinen Fall (also keine bestimmte geometrische Form) und ohne Zusatzinformationen (z.B. Position der WPs) ist das Problem nicht lösbar.
Selbst mit diesem Informationen bzw. in den Spezialfällen wird das, wenn nicht (aufgrund der Einschränkungen von Gothic) verdammt schwierig, dann zumindest verdammt fummlig. Es gibt weder die Wurzelfunktion noch Trigonometrische Funktionen. Klar kann man sich das irgendwie selbst bauen, aber das Ergebnis rechtfertigt den Aufwand wahrscheinlich nicht.
Der beste Ansatz ist vermutlich das Gebiet, auf dass du prüfen willst aus Kreisen zusammenzufummeln und dann eine ver"oder"te Abfrage auf die Zentren zu machen.
Ich denke ich habe die Lösung. Bedingung dafür ist allerdings das Daedalus eine Funktion bereitstellt mit der sich die Distanz von einem WP zum anderen Abfragen lässt. Sehen wir uns nun mal eine Skizzze eines Fünfecks an (Anhang).
Die Position des Spielers ist rot markiert, die Distanzen zu den einzelnen WPs grün markiert. Wir erkennen das unser konvexes Fünfeck, wie jedes andere konvexe N-Eck aus N * Dreicken besteht, aus 5 * Dreiecken besteht.
Wenn wir uns ein solches Dreieck anschauen sehen wir dass c + b < a sein muss damit es ein Dreieck ist bzw. wir wissen das sich der Spieler innerhalb oder außerhalb des Fünfecks befindet. Wenn wir das aber für alle 5 Dreiecke abfragen und a immer größer als c + b ist wissen wir dass sich der Spieler im Fünfeck befindet. In Code ausgedrückt:
Rein mathematisch ist das imo durchaus möglich.
Ob man das in Daedalus dann auch umsetzen kann - ich wage erstmal keine Behauptungen anzustellen. Soll sich jemand anders den Kopf darüber zerbrechen.
Entscheidend ist folgendes:
Befindet sich der Punkt im Fünfeck ABCDE, so kann seine Entfernung zu A höchsten AB, AC, AD oder AE sein.
Code:
if (AP < AB|AC|AD|AE)
&& (BP < BA|BC|BD|BE)
& (CP < CA|CB|CD|CE)
& (DP < DA|DB|DC|DE)
& (EP < EA|EB|EC|ED)
--> Punkt P liegt im Fünfeck
[syntaktisch auf keinen Fall korrekt, hat auch keinen Anspruch darauf]
Die Theorie ist genau die von Sektenspinner. Man zeichne vier Kreise um jeden Punkt, mit einem Radius, der der Entfernung zu jeweils einem anderen Punkt entspricht.
Liegt der fragliche Punkt P in mindestens einem von den Kreisen, so liegt er im Fünfeck.
Ich hoffe mir ist kein Denkfehler unterlaufen, aber das müsste so stimmen.
Alle fragen sich wie kann ich noch schöner werden,
aber keiner fragt sich für wen.
Bleibt das Problem, dass die Distanzen von WP zu WP zu Fuß ermittelt werden müssen, da Gothic dafür keine Funktion bereit stellt.
Mit meinem Vorschlag "aus Kreisen zusammenfummeln" meinte ich auch etwas viel primitiveres, als das Gebiet auf ein abgerundetes Fünfeck zu prüfen.
Ich dachte daran, einfach eine Vereinigung von Kreisen zu nehmen, die das Gebiet ungefähr abdecken. Das heißt eine Abfrage wie: "In der Nähe vom Marktplatz" oder "in der Nähe vom Tempel" oder "in der Nähe der Mine" = "Irgendwo in der Stadt".
Wenn die Stadt nicht allzu unförmig ist, kann man sie schon ganz gut annähern. Genau wird das natürlich nicht.
Mit so einer Methode habe ich in Velaya geprüft ob Velaya während der Krankheit "Blattern" im Seuchengebiet (Hafenviertel) ist. Letztendlich war es ein großer Kreis wobei an den "Ecken" noch etwas drangebaut war.
Ich hatte vor langer Zeit mal ein ähnliches vor. Da ging es darumeine Party von mehreren NPC´s zu begleiten, allerdings nicht den vorgeschriebenen Weg zu verlassen. Sie mußten sich also auch innerhalb eines bestimmten Gebietes befinden. [Bild: MAP_NEWWORLD_wps_zu_Akil.JPG]
Sumpfkrautjunkie hat damals interessante Möglichkeiten gezeigt die einzelnen Entfernungen zu den WP´s zu bestimmen. Damals (vor knapp 2 Jahren) hab ich allerdings eher "nur Bahnhof" verstanden und mein "Problem" anders gelöst (NPC´s gehen selbständig zum Ziel). Mittlerweile bin ich am Überlegen ob ichs nicht doch so versuche wie damals angedacht:
Vielleicht hilft der damalige Thread ja weiter. Wie gesagt, Sumpfi hatte da einige Gedanken die für Dich interessant sein könnten.
Also ich würde erstmal über ein 3eck nachdenken, bevor ich über ein 5eck nachdenke.
Dreieck ABC; Npc N
wenn NA <= AB && NA <= AC
&& NB <= AB && NB <= BC
&& NC <= AC && NC <= BC
für ein 5eck muss die Anfrage halt 3 mal genutzt werden.
AB, AC, und BC müssen bekannt sein, also sich aus den Koordinaten aus dem Spacer ergeben.
Jetzt gibt es nurnoch das Problem, dass das ganze 3 dimensional ist.
Also ich würde erstmal über ein 3eck nachdenken, bevor ich über ein 5eck nachdenke.
Nette Idee.
Dreieck ABC; Npc N
wenn NA <= AB && NA <= AC
&& NB <= AB && NB <= BC
&& NC <= AC && NC <= BC
für ein 5eck muss die Anfrage halt 3 mal genutzt werden.
Das ist eine ähnliche Idee, wie Shadowblade bereits präsentiert hat (also Dreieck mit abgerundeten Kanten). Aber beides sind nur Abschätzungen.
Man denke sich ein längliches Dreieck ABC mit weit entferntem Punkt C.
Es sei der Spieler nahe an C aber innerhalb des Dreiecks, dann ist (NA > AB) und dein Algorithmus liefert FALSCH obwohl WAHR herauskommen müsste.
Anderer Richtung: Man denke sich ein gleichseitiges Dreieck ABC und der Spieler stehe in der Mitte der Seite a. Der Algorithmus liefert WAHR. Aber wenn der Spieler nun einen ganz kleinen Schritt nach draußen macht, liefert er weiterhin WAHR. Dein Code ist also in keine der beiden Seiten korrekt. Da ist Shadowblades Version noch besser, denn da gilt zumindest die Implikation:
Punkt im Dreieck -> Code liefert WAHR
zuverlässig. (nicht aber die Umkehrung)
Wenn ich das Problem exakt lösen wollte (was ich für unnötig halte) würde ich folgendermaßen vorgehen:
Wir befinden uns in der Ebene. Sei eine Gerade AB definiert durch die Punkte A und B. Sei C ein weiterer Punkt der Ebene und N ein Objekt. Dann entscheidet folgender Algorithmus ob C und N auf der selben Seite der Geraden liegen:
Code:
/* Folgende Abbildungen seien gegeben:
[nichts ungewöhnliches, nur der Völlständigkeit halber]
dist: (Punkt X Punkt) -> R | zu zwei Punkten wird ihr Abstand ermittelt (reele Zahl)
dist: (Punkt X Objekt) -> R | zu einem Punkt und einem Objekt wird ihr Abstand ermittelt (reele Zahl)
turn90: Punkt -> Punkt | Drehung um 90° gegen den Uhrzeigersinn. (x,y) -> (-y,x). Als Vektor zu verstehen.
+: (Punkt X Punkt) -> Punkt | zwei Punkte werden komponentenweise addiert, dabei kommt ein neuer Punkt heraus (Subtraktion mit "-" entsprechend definiert)
*: (R X Punkt) = (Punkt X R) -> Multiplikation eines Punktes (als Vektor zu verstehen) mit einer Zahl. Division entsprechend.
Insbesondere vermeide ich im Algorithmus:
Zugriffe aus die Position von N (in Gothic für Npcs nicht möglich)
Trigonometrische Funktionen (in Gothic nicht vorhanden)
Gebraucht werden aber:
Die Positionen aller Begrenzungspunkte
*/
bool selbeSeite (Punkt A, Punkt B, Punkt C, objekt N){/* Cosinussatz rückwärts */
cos_alpha = (- dist(B,N)² + dist(A,N)² + dist(A,B)²) / (2*dist(A,B)*dist(A,N));
Punkt M;
M = A + cos_alpha*dist(A,N)*(B-A)/dist(A,B);
Punkt Ns;
Ns = M + turn90(A-B)*dist(M,N)/dist(A,B)
return (dist (C,N) < dist (C,Ns));
}
bool imDreieck (Punkt A, Punkt B, Punkt C, objekt N){
if (selbeSeite (A, B, C, N))
&& (selbeSeite (B, C, A, N))
&& (selbeSeite (C, A, B, N)){
return TRUE;
}
return FALSE;
}//Vorraussetzung: konvexes Fünfeck!
bool ImFuenfeck (Punkt A, Punkt B, Punkt C, Punkt D, Punkt E, objekt N){
if (selbeSeite (A, B, C, N))
&& (selbeSeite (B, C, D, N))
&& (selbeSeite (C, D, E, N))
&& (selbeSeite (D, E, A, N))
&& (selbeSeite (E, A, B, N)){
return TRUE;
}
return FALSE;
}
Wobei die Punkte jeweils gegen den Uhrzeigersinn anzugeben sind (im Rechtshändigen Koordinatensystem). Das liegt an der Funktion "turn90", die sonst falsch herum dreht.
Die Konstruktion der Funktionen imDreieck und imFuenfeck ergeben sich einfach aus der Funktion selbeSeite: Ein Punkt liegt genau dann in einem Vieleck, wenn er bezüglich jeder Kante auf der richtigen Seite liegt.
Ich hoffe ich habe nicht selbst einen Denkfehler drin und hoffe ferner, dass ich keine wesentlich leichtere Lösung übersehen habe.
Trotzdem ich glaube, dass der Algorithmus von der Idee her korrekt ist, verbleibt obiger Code vorsorglich ohne Gewähr.
Wenn man in Gothic mit Vektoren rechnen könnte, wär das hier bestimmt hilfreich. So nur interessant für alle die tiefer in die Materie hinein wollen :P...
Ich hab mal grafisch ausprobiert, was am ehesten einem Dreieck nahe kommen würde (siehe Anhang), und ich finde, da könnte man eigentlich gleich 'nen Kreis nehmen. Zur Erläuterung des Bildes: Die einen Kreise bilden die Fläche mit dem jeweils kleinstmöglichen Abstand zu einem der Nachbarpunkte, die anderen mit dem jeweils größtmöglichen. Ich finde dieser Bereich ist von der Form und Größe her nicht so gut zu kontrollieren, als dass man ihn zur Vereinfachung einsetzen könnte .
Geändert von DJonnyS (24.11.2008 um 22:42 Uhr)
Grund: natürlich den Anhang vergessen.....
Wenn man in Gothic mit Vektoren rechnen könnte, wär das hier bestimmt hilfreich
Das Problem sind weniger die Vektoren, die kann man sich bauen, sondern einfach die Tatsache, dass man keinen Zugriff auf die Koordinaten des Spielers hat.
Wobei das ein lösbares Problem ist. Auch ohne Sinus und Cosinus kann man diese mit weit entfernten Wegpunkten zumindest gut annähern.
Wenn Gothic intern Standardfloats und Integer zur Berechnung verwendet, werden in Größenordnungen von 80 km die einzelnen cm noch gut aufgelöst.
Man kann man davon ausgehen, dass mit
"WP1" steht an (-80.000.00,0) //also 80 km in X-Richtung
"WP2" steht an (0,-80.000.00) //also 80 km in Z-Richtung
Die Position des Helden ungefähr:
(dist(hero,"WP1") - 80.000.00, dist(hero,"WP2") - 80.000.00)
ist. Die y-Position (Höhe) wird bei WPs nicht berücksichtigt.
Man erhält ein (im Bereich des Ursprungs) leicht verzerrtes Koordinatensystem in dem Geraden noch ungefähr gerade sind.
Trotzdem kann man sich dann weit ab des Ursprungs (schon wenige km) nicht mehr darauf verlassen, dass die Spacerkoordinaten ungefähr mit den berechneten Koordinaten übereinstimmen. Was aber kein großes Problem ist, da man ohnehin keinen Zugriff auf Spacerkoordinaten hat.
Ich habe mir dazu mal ein Bild malen lassen (siehe Anhang) und man sieht, das die Linen in der Nähe des Ursprungs durch den großen Abstand von den WPs nahezu parallel sind und zudem fast senkrecht aufeinander stehen, das heißt hier hat man fast karthesische Koordinaten.
Mit einer Wurzelfunktion (die man sich auch bauen kann) wird man sogar noch besser und kann sich den Spacerkoordinaten auch für weiter entfernte Punkte schrittweise annähern.
Ausgehend davon kann man auch die Vorschläge auf der Internet Seite nutzen, die du gepostet hast.
Ich finde dieser Bereich ist von der Form und Größe her nicht so gut zu kontrollieren, als dass man ihn zur Vereinfachung einsetzen könnte .
Stimmt schon. Schöne Skizze dazu übrigens.
Aber wir haben ja jetzt "bessere" Vorschläge. Allerdings kann ich mir nicht viele Anwendungen dafür vorstellen.
Letztendlich ist das wohl reine Spielerei.
Bist du dir sicher, dass die Höhe bei WPs nicht mit einbezogen wird, und das auch nicht bei der Distanzberechnung?
Denn dann wäre das Problem ja sehr einfach zu lösen, indem man sich mit 2 WPs sein eigenes Koordinatensystem baut. Durch die beiden WPs geht ja eine Spiegelachse, so dass man die WPs so platzieren muss, dass die Welt nur auf einer Seite der Achse liegt, und somit jede (DistanzWP1 zu DistanzWP2) -Kombination einzigartig ist. Davon ausgehend lassen sich dann durch den Satz des Pythagoras für die beiden WPs eine x- und eine y-Position berechnen (relativ zur Strecke WP1-WP2). Zur Verdeutlichung hab ich mal ein Bild gemalt .
Das negative Ereignis müsste man in dem Fall durch entsprechende Abfragen frühzeitig eliminieren, sonst wär der Rechenaufwand nicht gerechtfertigt .
Stimmt, mit Wurzelfunktion ist da vermutlich die beste Lösung. Und da findet man rekursiv schnell Näherungswerte mit der Formel:
Code:
gesucht: Wurzel von x.
Es sei:
f(a) = (a + x/a) / 2
Setze
a_0 = x
a_1 = f(a_0)
a_2 = f(a_1)
a_3 = f(a_2)
[...]
Bei mehrmaligem Anwenden der Funktion auf ihr eigenes Funktionsergebnis konvergiert der resultierende Wert gegen Wurzel X.
Zitat von DJonnyS
Bist du dir sicher, dass die Höhe bei WPs nicht mit einbezogen wird, und das auch nicht bei der Distanzberechnung?
Bin mir nicht sicher... Ich kann mich auch irren aber irgendwas war da.
Zitat von DJonnyS
Davon ausgehend lassen sich dann durch den Satz des Pythagoras für die beiden WPs eine x- und eine y-Position berechnen (relativ zur Strecke WP1-WP2).
Mir ist es nicht gleich ins Auge gesprungen, da hab ich es mal niedergeschrieben. Siehe Anhang.
Interessant ist aber folgendes: Um auf p und q zu kommen muss man keine Wurzel ziehen! Nur für h wäre das nötig. Das heißt, wenn man den Vorgang zweimal macht, einmal entlang der X und einmal entlang der Y Achse kommt man ganz ohne Wurzelziehen aus und hat die Position des Spielers.
Benutzer, die ihr Benutzerkonto per E-Mail bestätigen müssen
Registriert seit
Nov 2006
Ort
Reichstädt, Dresden
Beiträge
257
???
Das ist doch Kindergartenkram... ^^
Ich weis ni ob das schon gepostet wurde (Hab die hälfte gelesen)...Aber ich glaub es geht darum ob der npc in einen fünfeck aus Wp's steht oder ni.
Mit anderen worten: Kreuzungszahl HIER
In diesen Algo wird eine virtuelle linie nach rechts vom NPC aus geschossen. Jetzt wird jeder WP mit dem nächsten verglichen. Dh. eine linie wird zwischen punkt 1 und 2.... zwischen punkt 2 und 3 usw. gebildet.
Wenn Linie/Strecke von WP1 zu WP2 die Linie vom npc schneidet, dann zählt ne varibale hoch. Dieser vorgang wird für jede verbindung der WP's durchgeführt.
Am ende wird überprüft, ob die Zahl gerade oder ungerade ist:
Wenn iAnzahlSchnitte MOD 2 = 0 dann is der Npc draußen, Wenn 1 dann drin....
Es gibt zwar ein paar sonderregelungen, aber die werden hier kaum zutreffen ^^
Oder was meint ihr?
Stimmt, mit Wurzelfunktion ist da vermutlich die beste Lösung. Und da findet man rekursiv schnell Näherungswerte mit der Formel:
Daedalus kann doch nicht mit Floats rechnen
Mein Mathe-Lehrer meinte, es gäbe eine Methode, bei der man auf Dezimalwerte verzichten kann: http://www.diaware.de/html/wurzel.html
Wobei man hier wohl, falls man es überhaupt umsetzen kann, ziemlich viel mit % arbeiten muss.
Oh, äh, in der Tat, habe es gerade probiert und er mag es ja wirklich nicht. Ist mir niemals aufgefallen, zumal float Konstanten ja auch in manche Funktionen eingesetzt werden können...
Also das zu implementieren macht bestimmt keinen Spaß.
Dann lieber einfach mit integern rechnen oder wenn einem das zu ungenau ist (cm sind aber schon ziemlich genau!) dann baut man sich Entweder selbst Fließkommazahlen oder baut sich Festkommazahlen, wenn man keine Lust darauf hat.
Ich schätze mal, es wäre leichter, an den Grenzen des Fünfecks Triggerzonen zu einzusetzen, die eine entsprechende Variable umsetzen - der Aufwand wäre sehr viel niedriger.
Alle fragen sich wie kann ich noch schöner werden,
aber keiner fragt sich für wen.
World of Players
[Script]Gebietabsuchen?
. Was hab ich mir nur dabei gedacht?
Zitat von Nodrog
.
![[Bild: Kyrus1final_low.jpg]](http://upload.worldofplayers.de/files3/Kyrus1final_low.jpg){kind=link}
![[Bild: MAP_NEWWORLD_wps_zu_Akil.JPG]](http://upload.worldofplayers.de/files2/MAP_NEWWORLD_wps_zu_Akil.JPG){kind=link}