2D einheit um gegenstände herumlaufen

nuclearspider

Also.

ich habe folgendes proble.
ich programmiere ein 2D game. jetzt will ich eineh einheit laufen lassen, das klappt auch wunderbar.
aber die einheit läuft natürlich durch alles durch. (häuser etc.)

die einheiten - struktur sieht (bis jetzt) so aus:

struct einheit{
	int x, y;                          // in pixel 
	int w, h;                          // in pixel 
	float direction;                   // wert von 0° - 360°
	int targetx, targety;              // wo die einheit hin soll
	int speed;                         // geschwindigkeit
	int energy, energymax;             // energie der einheit
	int dontcollwithx, dontcollwithy;  // ich weiss, schlecht programmiert.
                                           // aber sonst kollitiert die einheit
                                           // mit sich selbst...
	bool selected;                     // einehit ausgewählt???
	int koordx, koordy;                // position im KoSy
};
struct einheit einheiten[MAX_EINHEITEN];

außerdem hab ich eine collisionsmap:

int collisionsmap[80][42];

die einehiten werden so bewegt:

einheiten[i].x = einheiten[i].x + int(einheiten[i].speed*cos(einheiten[i].direction*pi/180));
einheiten[i].y = einheiten[i].y + int(einheiten[i].speed*sin(pi*einheiten[i].direction/180));

wie die einheiten gedreht werden lasse ich heir jetzt weg.

ich habe schon probiert, die einheit (zumindest wenn sie von links nach rechts geht) um das haus herum gehen zu lassen:

if((einheiten[i].direction >= 0 && einheiten[i].direction < 90)
   || (einheiten[i].direction > 270 && einheiten[i].direction <= 360))
{		  
    if(collisionsmap[(einheiten[i].x/32*2)+2][einheiten[i].y/32*2] == 2)
	einheiten[i].direction = 90;			
}

aber da gibt es einen schönheitsfehler:
wenn ich bei klick1 klicke, geht es.

_________
     X     |         |          "klick2"
  einheit  |  HAUS   |              X
           |_________|
                                "klick1"
                                  X

aber wenn ich weiter oben, bei klick2 klicke, bleibt die einheit an der unteren kante des hauses hängen.

wie kann ich das ändern???
würdet ihr das problem (um das haus herumgehen) anderst angehen?? wenn ja, wie???

DANKE

TGGC

Das Ganze ist etwas kompliziert um es in einem kurzen Posting zu erklären. Du solltest dir ein paar Bücher über Geometrie und Graphentheorie zulegen. Einige Grundlagen findest du auch im Netz, wenn du z.b. nach Pathfinding googelst.

Bye, TGGC Deine Unterstützung wird gebraucht!

Sgt. Nukem

Viele posten dann immer: A* !

nuclearspider

also ich hab jetzt mal gagoogelt.
und das hier gefunden: http://www.policyalmanac.org/games/aStarTutorial.htm
aber irgendwie scheint das recht kompliziert zu sein und es wird dort nicht anhand von quellcode erklärt.

kennt ihr was besseres???

otze

besser als A*? nicht wirklich

TGGC

Sgt. Nukem schrieb:

Viele posten dann immer: A* !

Ohne zu wissen, was genau das ist...

Bye, TGGC Deine Unterstützung wird gebraucht!

Sgt. Nukem

TGGC schrieb:

Sgt. Nukem schrieb:

Viele posten dann immer: A* !

Ohne zu wissen, was genau das ist...

Darauf wollte ich hinaus...

Deutschland sucht den A-Star...

DocJunioR

Was mich immer irritiert ist folgendes :

Ich habe ein Raster mit 2 zu erreichenden Punkten und ein hindernis :

*********************
*                   *
*           B       *
*                   *
*     xxxx          *
*        x          *
*    A              *
*                   *
*********************

wenn ich nun von Punkt A in sämtliche nachbarn in denen nichts steht eine - hmm mindestens 3 rein schreibe. Dann in sämtliche leeren Nachbarn der Teile eine 2 und dann eine 1, anschließend geht das wieder bei 3 los :

*********************
*22222222132        *
*33333332132B       *
*3111113213332      *
*31222xxxx1132      *
*31233321x2132      *
*3123A32132132      *
*3123332132132      *
*********************

und zwar angefangen im Urzeigersinn bei 12 Uhr bis ich auf Punk B treffe.

anschließend suche ich genauso, nur zahlenmäßig anders herum die Nachbarn ab.
In diesem Falle wäre ich be einer 2 auf mein B gestoßen, ergo würde ich entgegen des Urzeigersinn nach einer 3 als Nachbarn suchen, dann nach einer 1 und dann eine2, etc:

*********************
*                   *
*           B       *
*           3       *
*     xxxx 1        *
*        x2         *
*    A3213          *
*                   *
*********************

Den Algorithmus nennt man Lee und er funktioniert sdeit je her.. für sämtliche Platinenlayoutprogramme... beidseitig
Hab irgendwo so nen Ding rumzuliegen. War eigenltich nur zu faul, ein Layoutprogramm dafür zu schreiben ^^

Hab ich doch vergessen, zu schreiben, was mich irritiert..

Wo ist der Unterschied zu A* ? Die beiden Algorithmen sind sich doch schonmal ziemlich ähnlich, oder nicht ?

Nein, sind sie nicht. Aber die allzu offensichtlichen Unterschiede kannst du wirklich auf eigene Faust herausfinden.

DocJunioR

Hmm.. Im Gegensatz zu Lee werden beim A* Knotenpunkte vergeben, über die Gegangen wird. Hierdurch ist die Wegekarte nicht so fein gerastert, wie die Spielkarte.. Weiterhin wird die Welle nicht rückwärts gezählt, sondern vorwärts.. Ansonsten ist A* nichts weiter als ne Adaption des Lee..

Das stimmt aber nicht wirklich.

Wie fein das Raster ist, hat mit A* nichts zu tun. A* ist ein abstrakter Algorithmus zum Lösen von beliebigen Problemen (beliebtes Beispiel: Schiebepuzzles), die bestimmte Eigenschaften aufweisen.
Außerdem hast du bei diesem Lee (den ich gar nicht kenne) wohl offensichtlich auch Knotenpunkte, die selben kannst du für den A* verwenden, außer du hast ein besseres System.

Der Hauptunterschied besteht immer noch darin, dass A* mit einer heuristischen Funktion arbeitet, die den verbleibenden Aufwand schätzt.

Cpp_Junky

Das schlimme ist, das im Netz hunderte Algorithmen kursieren die alle vorgeben A* zu sein. Ich habe für meine A* Implementierung folgendes Tutorial durchgeackert: http://www.gamedev.net/reference/articles/article2003.asp
Da ist alles ganz gut erklärt.
Momentan versuche ich noch "Binary Heaps" zu verwenden (Im Grunde genommen eine Art Quick-Sort-Insertion-Sort Mutation zum Sortieren und schnellen Auffinden der Open-List Elemente).

DocJunioR

hmm..
Das ist natürlich möglich.
Das Tutorial das ich gelesen habe, war mehr auf das Pathfinding ausgerichtet, als auf die entsprechende heuristische Suchmethode. Dementsprechend muss ich wohl meine Aussage (nach meinem Verständnis) insofern abändern, als dass A* nicht der Pathfinding-Algorithmus ist, sondern ein Aufsatz zur Optimierung eines Problems, im Pathfinding-Falle auf einen Lee ..

Werd mich aber mal genauer informieren - obwohl ich's bereuen werde, da mich solch eine Problematik im Moment nicht wirklich tangiert..

TGGC

A* kann beliebige Kantengewichte und Lee nicht.

@Cpp_Junky: Ich denk Fibonacci Heaps sind am effizientesten für Dijkstra und Konsorten?

Bye, TGGC (Dem beste BdT)

Cpp_Junky

@TGGC: Effizient ist es allemal. Wo ich früher durch die halbe Open-List suchen musste, muss ich jetzt vielleicht noch 3-4 vergleiche machen, dann weiss ich welches der nächstbeste Wegpunkt ist.

DocJunioR

TGGC schrieb:

A* kann beliebige Kantengewichte und Lee nicht.

Definiere "Kantengewichte"

Er meint verschiedene Kosten zum nächsten Wegknoten. Beispielsweise kann man, so wie ich, ein freies System haben, wo die Knoten nicht in einem Gitter liegen, sondern lediglich die Hindernisse umgeben. Dabei ist natürlich der Weg von einem Knoten zum nächsten nicht jedesmal der gleiche.
Oder man kann die Bewegung auf verschiedenen Terrainarten teurer machen.
Damit kann man z.B. einer Stealth-Einheit beibringen, sich möglichst im Schatten zu bewegen.
Oder natürlich, Sümpfe zu vermeiden, wenn in der Nähe auch ein Weg um den Sumpf herum führt.

</vermutung>

TGGC

In einem Graphen G = (V,E), wir die reele Zahl c(e), die der Kante e element E zugeordnet ist, Kantengewicht oder Bewertung genannt.

Hinweis: Optimizer hat recht.

Bye, TGGC (Der Held lebt!)