Status on Fate 2/Fate 3d
Moderatoren: Xajorkith, erni, Asgard
- darklord
- Ritter/Amazone
- Beiträge: 588
- Registriert: Mi 18.07.2001 - 14:05
- Wohnort: Tower Tangramayne, links von New Magincia
- Kontaktdaten:
Wie hast du denn deine Kartenstruktur aufgebaut? Ein Array mit Haus oder nicht Haus?
Wenn du deine Karte auf einem einfachen Raster aufbaust, wird sich nix anderes daraus ergeben.
Ich hab die Map etwa so aufgebaut:
Alle Grafik ist als Objekt gespeichert, Häuser, Kreaturen, Büsche - alles.
Lade ich ein Szenario, steht da eine Liste mit Objekten, den zugehörigen Texturen und vier Mal 3D-Koordinaten für Nullpunktverschiebung, Position, Rotation und Skalierung.
Mein Boden besteht zwar nach wie vor aus einem rechteckigen Raster, aber bei der Verteilung und Orientierung der Objekte bin ich unabhängig.
Wenn du deine Karte auf einem einfachen Raster aufbaust, wird sich nix anderes daraus ergeben.
Ich hab die Map etwa so aufgebaut:
Alle Grafik ist als Objekt gespeichert, Häuser, Kreaturen, Büsche - alles.
Lade ich ein Szenario, steht da eine Liste mit Objekten, den zugehörigen Texturen und vier Mal 3D-Koordinaten für Nullpunktverschiebung, Position, Rotation und Skalierung.
Mein Boden besteht zwar nach wie vor aus einem rechteckigen Raster, aber bei der Verteilung und Orientierung der Objekte bin ich unabhängig.
Genau da lag mein Problem. Entweder ist eine Wand o.ä. vorhanden oder nicht. Dementsprechend kann man da lanlaufen oder nicht.
Deine Idee mit einer Liste ist nicht schlecht. Dennoch ergibt sich für mich das Problem, das z.B. ein Haus um 10 oder 87 Grad gedreht sein kann. Dementsprechend sollte der Held an der Wand entlang gehen können und nicht durch die Wand schauen.
Deine Idee mit einer Liste ist nicht schlecht. Dennoch ergibt sich für mich das Problem, das z.B. ein Haus um 10 oder 87 Grad gedreht sein kann. Dementsprechend sollte der Held an der Wand entlang gehen können und nicht durch die Wand schauen.
- darklord
- Ritter/Amazone
- Beiträge: 588
- Registriert: Mi 18.07.2001 - 14:05
- Wohnort: Tower Tangramayne, links von New Magincia
- Kontaktdaten:
Dann hast du noch keine echte Collision-Detection. Bei OpenGL ist das zwar etwas hampeliger als bei DirectX, sollte aber kein Problem sein.
Stell dir folgendes vor:
Du verwaltest alle deine statischen Objekte (aus denen die Szene zuammengesetzt ist, auch Structural genannt) in einer Liste - idealerweise eine Linked-List, geht aber auch anders.
Läßt man die NPCs mal weg und betrachtet nur den Avatar, wenn er sich bewegt, dann mußt du "nur" regelmäßig deine Liste abklappern (tust du sowieso beim rendern), ob sich deren Koordinate + Radius in gefährlicher Nähe zum Avatar befindet. Das ist die Spatial-Bounding-Box-Collision-Detection oder auch fast-bb-checking.
Alle Objekte die hierbei durchgefallen sind, können evtl. mit dem Avatar kollidieren, also muß hier eine genauere Kollisionserkennung durchgeführt werden. Diese genaue CD ist brfute force: jede Fläche des Avatar wird gegen jede Fläche des fraglichen Objekts gecheckt - bzw. deren Eckpunkte (die "Normale" davon, sie darf der des Avatars nicht entgegenlaufen).
Bei DirectX ist das recht einfach mit ein paar Loops und etwas Vektorarithmetik zu erledigen, bei OpenGL - kein Plan
Stell dir folgendes vor:
Du verwaltest alle deine statischen Objekte (aus denen die Szene zuammengesetzt ist, auch Structural genannt) in einer Liste - idealerweise eine Linked-List, geht aber auch anders.
Läßt man die NPCs mal weg und betrachtet nur den Avatar, wenn er sich bewegt, dann mußt du "nur" regelmäßig deine Liste abklappern (tust du sowieso beim rendern), ob sich deren Koordinate + Radius in gefährlicher Nähe zum Avatar befindet. Das ist die Spatial-Bounding-Box-Collision-Detection oder auch fast-bb-checking.
Alle Objekte die hierbei durchgefallen sind, können evtl. mit dem Avatar kollidieren, also muß hier eine genauere Kollisionserkennung durchgeführt werden. Diese genaue CD ist brfute force: jede Fläche des Avatar wird gegen jede Fläche des fraglichen Objekts gecheckt - bzw. deren Eckpunkte (die "Normale" davon, sie darf der des Avatars nicht entgegenlaufen).
Bei DirectX ist das recht einfach mit ein paar Loops und etwas Vektorarithmetik zu erledigen, bei OpenGL - kein Plan
So, lange war es hier still.
Nachdem ich viel mit C++ probiert habe (unter anderem auch mit diversen Game-Engines), ist mein Welt-Editor in der Entstehung.
Noch experimentiere ich mit 2 Triangles (booooh ey) , aber dies wird sich ändern, sobald ich in meiner Engine weitere Dreiecke setzen kann.
Für eine Kollisionsabfrage habe ich auch schon eine Idee (hier sei ein großes Lob an das Buch "TT-Trigonometrie" gerichtet).
Wenn keine unerwarteten Schwierigkeiten auftreten, könnte in ca. 2 Monaten (man muß ja zwischendurch auch Geld verdienen) der Boden unter Larvin incl. Wasser fertig sein.
Häuser, Teleports und andere Hindernisse werden erst zu einem späteren Zeitpunkt eingebaut.
Denksportaufgabe:
Der Boden von Fate 3D ist in Dreiecke aufgeteilt.
Frage 1: Wie kann ich berechnen, ob ich innerhalb eines Dreiecks bin?
Frage 2: wenn jeder Eckpunkt eines Dreiecks eine eigene Höhe hat, wie berechne ich die Höhe meiner Position?
Es wäre hilfreich, wenn man mich nicht (!) auf irgendwelche Matheforen verweisen würde, denn das hab ich (bis jetzt ohne Erfolg) auch schon getan.
(Berge und Täler zu durchlaufen ist garnicht so einfach)
Der Boden von Fate 3D ist in Dreiecke aufgeteilt.
Frage 1: Wie kann ich berechnen, ob ich innerhalb eines Dreiecks bin?
Frage 2: wenn jeder Eckpunkt eines Dreiecks eine eigene Höhe hat, wie berechne ich die Höhe meiner Position?
Es wäre hilfreich, wenn man mich nicht (!) auf irgendwelche Matheforen verweisen würde, denn das hab ich (bis jetzt ohne Erfolg) auch schon getan.
(Berge und Täler zu durchlaufen ist garnicht so einfach)
- darklord
- Ritter/Amazone
- Beiträge: 588
- Registriert: Mi 18.07.2001 - 14:05
- Wohnort: Tower Tangramayne, links von New Magincia
- Kontaktdaten:
Code: Alles auswählen
float cLandScape::InterpolateHeight(float x, float y)
{
float origin, ahead, right, cross, dist_ahead, dist_right, dist_cross;
x=x/TILESIZE;
y=y/TILESIZE;
if (x>=CurrentMap.SizeX-1)
x=CurrentMap.SizeX-1;
if (x<0)
x=0;
if (y>=CurrentMap.SizeY-1)
y=CurrentMap.SizeY-1;
if (y<0)
y=0;
origin= CurrentMap.nodes[abs(x)+(abs(y)*CurrentMap.SizeX)].elevation*TILESIZE/60;
ahead= CurrentMap.nodes[abs(x)+(abs(y+1)*CurrentMap.SizeX)].elevation*TILESIZE/60;
right= CurrentMap.nodes[abs(x+1)+(abs(y)*CurrentMap.SizeX)].elevation*TILESIZE/60;
cross= CurrentMap.nodes[abs(x+1)+(abs(y+1)*CurrentMap.SizeX)].elevation*TILESIZE/60;
dist_ahead = y-abs((int)y);
dist_right = x-abs((int)x);
dist_cross = sqrt((dist_right*dist_right)+(dist_ahead*dist_ahead));
ahead = (ahead-origin)*dist_ahead+origin;
right = (right-origin)*dist_right+origin;
cross = (cross-origin)*dist_cross+origin;
return ((ahead+right+cross)/3);
}
Die Routine benutzt einen simplen mathematischen Grundsatz, Pythagoras. Sind ja Dreiecke.
Die Routine ist nicht perfekt, aber ziemlich schnell und funktioniert recht gut. In origin, ahead, right und cross werden die absoluten Höhen der Gitternetzpunkte um die Position x,y gespeichert und dann wird nur ein gedachtes Dreieck konstruiert, das mit einer Kante senkrecht zum Kartenboden über bzw. unter der Position x,y steht. Dann muß man nur noch die Länge dieser Kante via Pythagoras errechnen und fertig.
- sircharles
- Moderator
- Beiträge: 1315
- Registriert: Di 30.01.2007 - 18:29
- Wohnort: Ulm
Hallo, Roy,
sorry, dass es solange gedauert hat, aber ich musste den Code erst ausgraben...
Derm Algorithmus ist egal, in welcher Reihenfolge die Punkte komen. Die seltsame Epsilon-Prüfung schützt nur vor nahezu senkrechten Kanten (hier läuft die links-rechts-Prüfung über die X-Koordinate).
Ich hoffe, das hilft Dir weiter.
Gruß,
Sir Charles
[Edit 23.6.: Kantenprüfung korrigiert.]
sorry, dass es solange gedauert hat, aber ich musste den Code erst ausgraben...
Der folgende Algorithmus funktioniert mit beliebigen Polygonen. Für Deine Dreiecke kannst Du ihn sicher vereinfachen. Es wird nacheinander jede Kante geprüft. Ist die Position nahe der Kante, wird eine links-rechts-Prüfung durchgeführt. Der Algorithmus ist für beliebige einfach zusammenhängende Gebiete geschrieben (also keine kreuzenden Kanten, was mit Dreiecken ohnehin nicht möglich ist. Vorsicht - direkt auf einer Kante oder ganz nah an einer Ecke wird als innerhalb angenommen, daher kann es sein, dass man in mehreren Dreiecken gleichzeitig ist!Roy hat geschrieben:Frage 1: Wie kann ich berechnen, ob ich innerhalb eines Dreiecks bin?
Code: Alles auswählen
bool Polygon::isInside(int x, int y)
{
bool isInside = false;
int next = 0;
const double Epsilon = 1.0E-20;
double denom = 0.0;
double grad = 0.0;
double yCoo = 0.0;
for (int i = 0; i < points.entries(); i++)
{
// if position is very close to the corner, consider it to be inside
double dist = sqrt ((points[i].x - x)*(points[i].x - x) +
(points[i].y - y)*(points[i].y - y));
if (dist < 0.1) return 1;
if (i == points.entries() - 1) next = 0;
else next = i + 1;
if (x >= points[i].x)
{
if (x < points[next].x)
{
denom = points[next].x - points[i].x;
if (fabs (denom) > Epsilon)
{
grad = (points[next].y - points[i].y) / denom;
yCoo = points[i].y + grad * (x - points[i].x);
if (y == yCoo) return true;
else if (y < yCoo) isInside = !isInside;
}
}
}
else
{
if (x >= points[next].x)
{
denom = points[next].x - points[i].x;
if (fabs (denom) > Epsilon)
{
grad = (points[next].y - points[i].y) / denom;
yCoo = points[i].y + grad * (x - points[i].x);
if (y == yCoo) return true;
else if (y < yCoo) isInside = !isInside;
}
}
}
}
return isInside;
}
Ich hoffe, das hilft Dir weiter.
Gruß,
Sir Charles
[Edit 23.6.: Kantenprüfung korrigiert.]
Zuletzt geändert von sircharles am Sa 23.06.2007 - 12:18, insgesamt 1-mal geändert.
- sircharles
- Moderator
- Beiträge: 1315
- Registriert: Di 30.01.2007 - 18:29
- Wohnort: Ulm
Äääh, umpf, Roy,
ich hab' den Code gerade selbst nochmal getestet. Im Prinzip funktioniert er (und die Drehrichtung der Dreiecke ist komplett egal), aber die Kantenprüfung funktioniert nicht ganz konsistent, wenn man exakt auf einer Kante steht. Da kann eine Kante ja sagen und eine andere nein. Ich habe im Code eine Zusatzprüfung auf Gleichheit eingebaut, die das bereinigt. Siehe oben. Mit der Modifikation reagieren jetzt alle Kanten gleich.
Arrgh, das kommt davon, wenn man ungetesteten Code veröffentlicht.
Sorry,
Sir Charles
ich hab' den Code gerade selbst nochmal getestet. Im Prinzip funktioniert er (und die Drehrichtung der Dreiecke ist komplett egal), aber die Kantenprüfung funktioniert nicht ganz konsistent, wenn man exakt auf einer Kante steht. Da kann eine Kante ja sagen und eine andere nein. Ich habe im Code eine Zusatzprüfung auf Gleichheit eingebaut, die das bereinigt. Siehe oben. Mit der Modifikation reagieren jetzt alle Kanten gleich.
Arrgh, das kommt davon, wenn man ungetesteten Code veröffentlicht.
Sorry,
Sir Charles
Es geht voran
Die Menüstrukturen stehen jetzt fast alle
Zur Zeit habe ich (aus Mangel an Können) folgendes hinten angestellt:
- Eine saubere Texturierung (Vieles ist verdreht und verschmiert)
Zur Not werde ich dies in Handarbeit machen müssen
Wo ich gerade dabei bin
Weiß jemand, wie man den "geographischen Mittelpunkt" eines beliebigen Dreiecks berechnet?
Die Menüstrukturen stehen jetzt fast alle
Zur Zeit habe ich (aus Mangel an Können) folgendes hinten angestellt:
- Eine saubere Texturierung (Vieles ist verdreht und verschmiert)
Zur Not werde ich dies in Handarbeit machen müssen
Wo ich gerade dabei bin
Weiß jemand, wie man den "geographischen Mittelpunkt" eines beliebigen Dreiecks berechnet?
- Dateianhänge
-
- Screenshot
- Fate3D.jpg (117.59 KiB) 420 mal betrachtet
- darklord
- Ritter/Amazone
- Beiträge: 588
- Registriert: Mi 18.07.2001 - 14:05
- Wohnort: Tower Tangramayne, links von New Magincia
- Kontaktdaten:
1. du meinst den "geometrischen" Mittelpunkt (;) jaja , ein Klugscheißer)
2. sieht ja schon sehr vielversprechend aus.
3. nur so eine Idee, aber wenn du die Fächer für die Charakterportraits etwas größer machst, verschwindet das leere Feld am linken Rand, außerdem hast du ja bei der Auflösung Platz genug.
4. Die Schrift sieht unklar aus. Du placierst die Schrift wahrscheinlich auch zweimal, einmal als Schatten und darüber als Farbe. Nimm eine dunklere Schattenfarbe und/oder eine andere Fordergrundfarbe zB Gold oder Gelb.
Zum geometrischen Mittelpunkt
Man nimmt eine beliebige Seite des Dreiecks (Vektor erstellen) und halbiert den. Vom neuen Endpunkt (der Mitte der Seite, die man gewählt hat) zieht man einen neuen Vektor zum gegenüberliegenden Eckpunkt (entweder mit den beiden Punkten 'erstellen' oder zum Vektor der halbierten Seite eine der beiden anderen Seiten addieren). Diesen Vektor muß man jetzt nur noch ebenfalls halbieren und der Endpunkt zeigt jetzt auf die geometrische Mitte.
Das ist geometrische Mathe pur, erwarte nicht, das auf Anhieb zu durchschauen, aber wenn man damit ein wenig arbeitet, notfalls im Copy&Paste Verfahren ohne genau zu wissen, warum das so heißen muß, gewöhnt man sich daran und das ist fast genausogut.
OpenGL besitzt, glaub ich, eine Mathe-Hilfsbibliothek mit vielen Vektor-Funktionen von 2D-Vektoren bis 4D-Vektoren. Wichtig sind da immer nur VecAdd, Normalize (= auf Länge 1.0f bringen) und DotProduct ( die ist besonders wichtig um den Winkel eines Dreiecks zur Lichtquelle oder dem Betrachter zu errechnen).
Keine Bange, vor diesem Part einer 3D-Engine hatte ich echt Schiß, aber das ist nicht wirklich soo wild und außerdem muß man sich damit nur einmal beschäftigen, danach ist ja alles fertig und man kann den Schamott getrost wieder vergessen.
2. sieht ja schon sehr vielversprechend aus.
3. nur so eine Idee, aber wenn du die Fächer für die Charakterportraits etwas größer machst, verschwindet das leere Feld am linken Rand, außerdem hast du ja bei der Auflösung Platz genug.
4. Die Schrift sieht unklar aus. Du placierst die Schrift wahrscheinlich auch zweimal, einmal als Schatten und darüber als Farbe. Nimm eine dunklere Schattenfarbe und/oder eine andere Fordergrundfarbe zB Gold oder Gelb.
Zum geometrischen Mittelpunkt
Man nimmt eine beliebige Seite des Dreiecks (Vektor erstellen) und halbiert den. Vom neuen Endpunkt (der Mitte der Seite, die man gewählt hat) zieht man einen neuen Vektor zum gegenüberliegenden Eckpunkt (entweder mit den beiden Punkten 'erstellen' oder zum Vektor der halbierten Seite eine der beiden anderen Seiten addieren). Diesen Vektor muß man jetzt nur noch ebenfalls halbieren und der Endpunkt zeigt jetzt auf die geometrische Mitte.
Das ist geometrische Mathe pur, erwarte nicht, das auf Anhieb zu durchschauen, aber wenn man damit ein wenig arbeitet, notfalls im Copy&Paste Verfahren ohne genau zu wissen, warum das so heißen muß, gewöhnt man sich daran und das ist fast genausogut.
OpenGL besitzt, glaub ich, eine Mathe-Hilfsbibliothek mit vielen Vektor-Funktionen von 2D-Vektoren bis 4D-Vektoren. Wichtig sind da immer nur VecAdd, Normalize (= auf Länge 1.0f bringen) und DotProduct ( die ist besonders wichtig um den Winkel eines Dreiecks zur Lichtquelle oder dem Betrachter zu errechnen).
Keine Bange, vor diesem Part einer 3D-Engine hatte ich echt Schiß, aber das ist nicht wirklich soo wild und außerdem muß man sich damit nur einmal beschäftigen, danach ist ja alles fertig und man kann den Schamott getrost wieder vergessen.
Diplomacy is the art of telling some-one to go to hell and he is happy to be on his way.
- sircharles
- Moderator
- Beiträge: 1315
- Registriert: Di 30.01.2007 - 18:29
- Wohnort: Ulm
Sorry, Darklord,darklord hat geschrieben:Zum geometrischen Mittelpunkt
Man nimmt eine beliebige Seite des Dreiecks (Vektor erstellen) und halbiert den. Vom neuen Endpunkt (der Mitte der Seite, die man gewählt hat) zieht man einen neuen Vektor zum gegenüberliegenden Eckpunkt (entweder mit den beiden Punkten 'erstellen' oder zum Vektor der halbierten Seite eine der beiden anderen Seiten addieren). Diesen Vektor muß man jetzt nur noch ebenfalls halbieren und der Endpunkt zeigt jetzt auf die geometrische Mitte.
da muss ich Dir leider etwas widersprechen. Deine Logik findet einen Punkt, der sicher innerhalb des Dreiecks liegt, aber nicht im Mittelpunkt. Je nachdem, von welcher Ecke Du ausgehst, kommt ein anderer Punkt raus.
Kurze Theorie:
Ein Dreieck hat zwei Mittelpunkte, einmal den Schnittpunkt der Winkelhalbierenden (das war der Umkreismittelpunkt, glaub' ich) und zum anderen der Schnittpunkt der Seitenhalbierenden (Schwerpunkt).
Roy, ersteren willst Du Dir bestimmt nicht antun (Winkel, igitt...), daher ist der Schwerpunkt wohl die bessere Lösung.
Ich hab hier einen schnellen Hack (in Java getestet), der das Problem in 2D löst. Für Deine Zwecke sollte das hoffentlich reichen, denn Schnittpunktberechnungen in 3D sind eklig...
Code: Alles auswählen
public Point Point::half() {
return new Point(x/2, y/2);
}
public Point Point::delta(Point3D p) {
return new Point(x-p.x, y-p.y);
}
private Point midpoint() {
Point p1 = points[1].delta(points[0]).half();
p1 = points[0].add(p1);
Point dir1 = points[2].delta(p1);
Point p2 = points[2].delta(points[1]).half();
p2 = points[1].add(p2);
Point dir2 = points[0].delta(p2);
float c1 = dir1.x*p1.y - dir1.y*p1.x;
float c2 = dir2.x*p2.y - dir2.y*p2.x;
float y = (c2*dir1.y - c1*dir2.y) / (dir1.y*dir2.x - dir2.y*dir1.x);
float x = 0;
if (dir1.y != 0) {
x = (dir1.x*y - c1) / dir1.y;
}
else {
x = (dir2.x*y - c2) / dir2.y;
}
return new Point(x,y);
}
Gruß,
Sir Charles
- darklord
- Ritter/Amazone
- Beiträge: 588
- Registriert: Mi 18.07.2001 - 14:05
- Wohnort: Tower Tangramayne, links von New Magincia
- Kontaktdaten:
Da muß ich dir wiederum widersprechen, Charly
Der geometrische Mittelpunkt ist IMMER der Schwerpunkt, es geht ja um das Zentrum der Symmetrie. Und den hab ich ja beschrieben, den Weg nutzt du ja auch in etwa in deiner Routine, wenn ich das mit n halben Auge (wg Uhrzeit) richtig sehe.
Wie das mit den Winkelhalbierenden ist, weiß ich nicht, ein solcher Mittelpunkt ist mir nicht bekannt.
Ist also schon richtig, was ich geschrieben habe, so bekommt man den geometrischen Mittelpunkt
Der geometrische Mittelpunkt ist IMMER der Schwerpunkt, es geht ja um das Zentrum der Symmetrie. Und den hab ich ja beschrieben, den Weg nutzt du ja auch in etwa in deiner Routine, wenn ich das mit n halben Auge (wg Uhrzeit) richtig sehe.
Wie das mit den Winkelhalbierenden ist, weiß ich nicht, ein solcher Mittelpunkt ist mir nicht bekannt.
Ist also schon richtig, was ich geschrieben habe, so bekommt man den geometrischen Mittelpunkt
- sircharles
- Moderator
- Beiträge: 1315
- Registriert: Di 30.01.2007 - 18:29
- Wohnort: Ulm
Absolut einverstanden.darklord hat geschrieben:Der geometrische Mittelpunkt ist IMMER der Schwerpunkt, es geht ja um das Zentrum der Symmetrie.
Bis hierher sind wir einer Meinung.darklord hat geschrieben:Man nimmt eine beliebige Seite des Dreiecks (Vektor erstellen) und halbiert den. Vom neuen Endpunkt (der Mitte der Seite, die man gewählt hat) zieht man einen neuen Vektor zum gegenüberliegenden Eckpunkt (entweder mit den beiden Punkten 'erstellen' oder zum Vektor der halbierten Seite eine der beiden anderen Seiten addieren).
Und hier trennen sich unsere Wege. Mit dem Halbieren schiesst Du nämlich übers Ziel hinaus. Der Schwerpunkt sitzt nie genau auf der Mitte dieser Linie (ausser, die Linie hat die Länge null, und dann ist das Dreieck zu einer Linie degeneriert). Deswegen die Schnittpunktberechnung.darklord hat geschrieben:Diesen Vektor muß man jetzt nur noch ebenfalls halbieren und der Endpunkt zeigt jetzt auf die geometrische Mitte.
Übrigens, die Berechnung in 3D ist doch nicht so schlimm:
Code: Alles auswählen
public Point3D Point3D::add(Point3D p) {
return new Point3D(x+p.x, y+p.y, z+p.z);
} // hatte ich vergessen, half() und delta() siehe oben
private Point3D midpoint3D() {
Point3D p1 = points[1].delta(points[0]).half();
p1 = points[0].add(p1);
Point3D v1 = points[2].delta(p1);
Point3D p2 = points[2].delta(points[1]).half();
p2 = points[1].add(p2);
Point3D v2 = points[0].delta(p2);
float t = (p2.y*v1.x - p1.y*v1.x - p2.x*v1.y + p1.x*v1.y) / (v2.x*v1.y - v2.y*v1.x);
return p2.add(new Point3D(v2.x*t, v2.y*t, v2.z*t));
}
Sir Charles