Status on Fate 2/Fate 3d

[darklord]

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.

[Roy]

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.

[darklord]

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

[Roy]

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.

[erni]

Dann mal ran und sich nicht durch die Fummelei ablenken lassen

[darklord]

DER heiße Tipp: Gamedev.net
Hier gibts Artikel zu allen Themen rund ums Spieleprogrammieren.

[Roy]

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)

[darklord]

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);
}

CurrentMap ist die Datenstruktur der Bodenkarte, darin sind die Member SizeX/SizeY, welche die Größe der Karte in Gitternetzpunkten angibt. Der Meber Nodes[] enthält die Höhe, Farbe usw. des jeweiligen Gitternetzpunktes. Die Konstante TILESIZE definiert, wieviele World-Space Einheiten die Gitternetzpunkte auseinander liegen. nodes.elevation ist die Höhe des Punktes, in meiner Engine wird die Höhe allerdings reduziert, damit ich keine Klippen bekomme - deshalb "elevation*TILESIZE/60".
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.

[Roy]

danke für die schnelle Hilfe

[sircharles]

Hallo, Roy,
sorry, dass es solange gedauert hat, aber ich musste den Code erst ausgraben...

Frage 1: Wie kann ich berechnen, ob ich innerhalb eines Dreiecks bin?

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!

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;
}

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.]

[Roy]

Sehr gut
ich kam schon nach darklords Code ins Schwitzen, meine Welt umstellen zu müssen.

Viiiiiiiiiiiiiiielen Dank für die Hilfe

[sircharles]

Äää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

[Roy]

sircharles,

deine routine klappt hervorragend

danke

... und wieder bin ich ein kleines stückchen weiter

ach ja,

die Routine von darklord habe ich jetzt auch soweit begutachtet und überarbeitet,
daß sie meinen Bedürfnissen entspricht. Ist nicht perfekt, aber funktioniert.

[darklord]

Wie gesagt, ist nicht allzu genau und damit nicht Ego-Shooter tauglich, sollte sie aber auchnicht sein.

[Roy]

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?

[darklord]

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.

[Roy]

@darklord:
zu1) *gröööhl*
zu 3) ist noch nicht endgültig
zu 4) liegt leider an der Schrift. Schatten sind da noch nicht drin. Aber ich werde mal sehen, was sich da noch machen läßt.

Zum geometrischen Mittelpunkt
!!!!!!!!!!!!!!!!!danke!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

[sircharles]

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.

Sorry, Darklord,
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);
    }

Diese Routine liefert definitiv den Schwerpunkt eines Dreiecks (es könnte sein, dass sie bei besonders degenerierten Dreiecken - Dritter Punkt liegt auf der Geraden durch die beiden anderen - auf die Nase fällt, aber normalerweise funktioniert sie).

Gruß,
Sir Charles

[darklord]

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

[sircharles]

Der geometrische Mittelpunkt ist IMMER der Schwerpunkt, es geht ja um das Zentrum der Symmetrie.

Absolut einverstanden.

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).

Bis hierher sind wir einer Meinung.

Diesen Vektor muß man jetzt nur noch ebenfalls halbieren und der Endpunkt zeigt jetzt auf die geometrische Mitte.

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.

Ü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));
    }

Gruß,
Sir Charles