Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Werbeanzeige

xXSlayerXx

Treue Seele

  • »xXSlayerXx« ist der Autor dieses Themas

Beiträge: 111

Beruf: Technischer Produktdesigner

  • Private Nachricht senden

1

16.04.2013, 18:47

[C++] Pacman Ansätze für Botprogrammierung

Hi Leute

ich programmiere momentan mein erstes Spiel.
Es handelt sich um Pacman.

Bisher lieft alles super und sogut wie ohne Hilfe von außerhalb.
Doch nun weiß ich schon seit einigen Tagen nichtmehr weiter.

Es geht nun nämlich um die Programmierung der Gegner.

Der Aktuelle status meines Projektes:

Man kann den Pacman steuern und auch die Punkte einsammeln. Wenn man über einen Taler kommt, so wird die gesamte Map dunkel rot und die Gegner leuchten Blau. Dieser Effekt wird durch Alphablending verstärkt.
Auch das teleportieren von der einen Seite der Map zu anderen funktioniert super.

Die Map wird aus einer Datei ausgelesen welche die änderung .pmm (PacManMap) besitzt. Momentan gibt es 5 Maps.
Hier mal ein Bild des aktuellen Stands:

(Link)


Die Texturen werde ich ganz am Ende der Programmierung nochmal überarbeiten. Erstmal soll das Spiel stehen.

Nun zu meinem Problem:
Wie bestimme ich, wo sich der Bot hinbewegt?
Was für ein Konzept benutzt man da? (Ich habe absolut keine Ahnung wie ich daran gehe.)

Villeicht kann mir jemand etwas darüber erzählen.
Ich möchte mir jetzt nicht extra ein Buch zu dem Thema kaufen, da ich noch mit 2 anderen parallel beschäftigt bin und das schon sehr viel Zeit in Anspruch nimmt.

Ich kann ja mal sagen, wie ich momentan dei Kollisionsabfrage vom Spieler gemacht habe. Villeicht ist ja auch der komplette aufbau verkehrt. :fie:

Also ich besitzte eine Klasse CMap, in welcher ich eine Struktur Names sMapData[8000] habe.
So ist es möglich 8000 Objekte auf dem Spielfeld zu haben. Muss man jedoch nicht.
die Strukut sMapData sieht wiefolgt aus:

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
struct sMapData
{
    public:
        tbVector3 Position;
        int ItemID;
        bool alive;

        //Konstruktor
        sMapData() {alive = true;}
};

Das ganze Funktioniert wie folgt:
mit hilfe von Position wird wie man sich schon denkt die Position des Models bestimmt.
ItemID gibt an, um was es sich genau Handelt (z.B.: Wall,Coint,Teleporter...).
Wenn alive auf FALSE steht, wird dieses Objekt nicht gerendert und auch nicht in der Kollisionsabfrage berücksichtigt.

Mithilfe dieser Werte führe ich nun meine Kollisionsabfrage durch.
Hier mal eine kleine Übersicht über das System:

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
void CGame::EventLoop()
{
    bool anyCoints = false;

    for (int i = 0; i <8000; i++)
    {
        if (Game.Map.MapItem[i].alive == true)
        {
            switch (Game.Map.MapItem[i].ItemID)
            {
                //Wall
            case 0:
                {
                    Game.Map.RenderWall(i);

                    //kollisionserkennung
                    if(Game.Pacman.Position.x < Game.Map.MapItem[i].Position.x + 1 && Game.Pacman.Position.x > Game.Map.MapItem[i].Position.x && Game.Pacman.Position.z > Game.Map.MapItem[i].Position.z - 0.8f && Game.Pacman.Position.z < Game.Map.MapItem[i].Position.z + 0.8f)
                    {
                        Game.Pacman.Position.x = Game.Map.MapItem[i].Position.x + 1;
                    }
                    if(Game.Pacman.Position.x > Game.Map.MapItem[i].Position.x - 1 && Game.Pacman.Position.x < Game.Map.MapItem[i].Position.x && Game.Pacman.Position.z > Game.Map.MapItem[i].Position.z - 0.8f && Game.Pacman.Position.z < Game.Map.MapItem[i].Position.z + 0.8f)
                    {
                        Game.Pacman.Position.x = Game.Map.MapItem[i].Position.x - 1;
                    }
                    if(Game.Pacman.Position.z > Game.Map.MapItem[i].Position.z - 1 && Game.Pacman.Position.z < Game.Map.MapItem[i].Position.z && Game.Pacman.Position.x > Game.Map.MapItem[i].Position.x - 0.8f && Game.Pacman.Position.x < Game.Map.MapItem[i].Position.x + 0.8f)
                    {
                        Game.Pacman.Position.z = Game.Map.MapItem[i].Position.z - 1;
                    }
                    if(Game.Pacman.Position.z < Game.Map.MapItem[i].Position.z + 1 && Game.Pacman.Position.z > Game.Map.MapItem[i].Position.z && Game.Pacman.Position.x > Game.Map.MapItem[i].Position.x - 0.8f && Game.Pacman.Position.x < Game.Map.MapItem[i].Position.x + 0.8f)
                    {
                        Game.Pacman.Position.z = Game.Map.MapItem[i].Position.z + 1;
                    }
                }break;
//Case 2: .....
            }
        }
        Game.Map.RenderGround(i);
    }
    //Wenn alle Coints weg sind, soll nach einer gewissen Zeit eine neue Map geöffnet werden.
    if(anyCoints == false)
    {
        RenderWinText();

        for (int Num=0; Num<Game.Map.NumEnemys; Num++)
        {
            Game.Enemy[Num].isAlive = false;
        }
        NewMapWaitTime -= g_fNumSecsPassed;
        if (NewMapWaitTime <= 0)
        {
            Game.Map.UnloadMap();
            char Map[64];
            Game.NumMap++;
            sprintf(Map, "Map%i",Game.NumMap);
            Game.Map.InitMap(Map);
            NewMapWaitTime = 10;
        }
    }
}


Das ist die Schleife, durch die alles gesteuert wird, was mit den Mapobjekten zu tun hat.

Villeicht kann ja mal jemand sagen, ob das völliger schwachsinn ist was ich da mache oder ob das soweit richtig ist.

So nun erstmal genug geschrieben^^

Mit freundlichem Gruß
xXSlayerXx
Bestes Zitat aus einem Quellcode :D

C-/C++-Quelltext

1
2
3
4
5
6
7
8
/** 
Once you are done trying to ‘optimize’ this routine, 
and have realized what a terrible mistake that was, 
please increment the following counter as a warning 
to the next guy: 

total_hours_wasted_here = 11 
*/

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »xXSlayerXx« (16.04.2013, 18:52)


TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

2

16.04.2013, 19:10

Falls du ein Originalgetreues Pacman machen willst, lies doch einfach mal nach, wie es dort ist.

xXSlayerXx

Treue Seele

  • »xXSlayerXx« ist der Autor dieses Themas

Beiträge: 111

Beruf: Technischer Produktdesigner

  • Private Nachricht senden

3

16.04.2013, 19:13

es geht mir weniger darum, wie sie sich letzendlich bewegen sollen.
Mich interessiert viel mehr der Programmiertechnische Hintergrund.

Ich habe bereits mehrere Artikel gelesen, in denen steht, wie diese Bots im echten Pacman programmiert wurden. Doch niergends steht, wie man soetwas umsetzt.
Bestes Zitat aus einem Quellcode :D

C-/C++-Quelltext

1
2
3
4
5
6
7
8
/** 
Once you are done trying to ‘optimize’ this routine, 
and have realized what a terrible mistake that was, 
please increment the following counter as a warning 
to the next guy: 

total_hours_wasted_here = 11 
*/

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

4

16.04.2013, 19:19

Da gibt es recht viele verschiedene Möglichkeiten die du hast, deine Gegner zu implementieren. Im original Spiel hat zum Beispiel jeder der 4 Gegner ein eigenes verhalten. Bei Wikipedia stehen ein paar Informationen dazu. Ansonsten kannst du sicherlich mit Google ein paar brauchbare Informationen dafür zusammen tragen. Ich erkläre einfach mal zwei Herangehensweisen für einen Gegner in Pacman. Dadurch hast du schon mal ein paar Ideen und kannst dir deine eigene KI ausdenken.
Möglichkeit1: Zufällige Bewegung für "blöden" Gegner. Hierbei könnte sich ein Gegner von Kreuzung zu Kreuzung auf der Map bewegen und dann zufällig eine der möglichen Richtungen wählen. Dafür würde ich die Map zusätzlich als Graph darstellen. Auch eine Tilemap kann als Graph angesehen werden. Dabei ist ein begehbares Tile ein Knoten. Eine Kante ist nur logisch vorhanden, da zwei benachbarte begehbare Tiles automatisch durch eine (implizite) Kante verbunden werden. Diese KI könnte auch so implementiert werden, dass sich der Gegner so lange in eine Richtung bewegt, bis er mit einer Wand kollidiert. Erst jetzt wird eine neue Richtung bestimmt. Diese beiden Varianten hängen vom Zufall ab. Da kann es sinnvoll sein, der entgegengesetzten Richtung eine kleinere Wahrscheinlichkeit zu geben. Dann pendeln Gegner weniger hin und her.
Möglichkeit2: Der Gegner kennt immer die Position vom Spieler und versucht diesen auf kürzestem Weg zu erreichen. Dabei brauchst du irgendeine Art von Wegfindung in deinem Spiel. Auch hier würde sich ein Graph anbieten, in welchem du dann zum Beispiel mit dem Algorithmus von Dijkstra oder der Erweiterung davon ( A* ) den gewünschten Weg bestimmen kannst. Hier bestimmst du einfach in jedem Schritt den kürzesten Weg. Jetzt kann sich der Gegner entlang dieses Weges bewegen. Das kann man natürlich noch verbessern. Der Weg könnte zum Beispiel nur alle paar Steps (Zeiteinheiten) aufgerufen werden. Möglicherweise wird der Algorithmus auch nur an Kreuzungen aufgerufen. Dadurch bewegt sich der Gegner quasi von Kreuzung zu Kreuzung.
Das sind zwei Möglichkeiten, welche recht simple KI darstellen. Wenn du dir zusätzlich noch die Ideen hinter der originalen KI anguckst, hast du schon mal ein paar Ideen. Wobei meine beiden Vorschläge von der originalen KI beeinflusst sind;)


edit: Wenn es dir eher um den Hintergrund geht. Bei meinem Beispielen stehen ja schon mal ein paar Dinge dazu dabei. Wenn du damit nicht richtig weiterkommst, dann guck dir vielleicht schon mal die Wegfindung an. Immer schön Schritt für Schritt arbeiten.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

xXSlayerXx

Treue Seele

  • »xXSlayerXx« ist der Autor dieses Themas

Beiträge: 111

Beruf: Technischer Produktdesigner

  • Private Nachricht senden

5

16.04.2013, 19:26

Ok das hört sich logisch an.
Doch wie finde ich anhand meiner Daten heraus, ob sich der Gegner gerade an einer Kreuzung befindet?
Das ist so momentan mein größtes Problem, welches mir auch am meisten Bauchschmerzen bereitet.
Bestes Zitat aus einem Quellcode :D

C-/C++-Quelltext

1
2
3
4
5
6
7
8
/** 
Once you are done trying to ‘optimize’ this routine, 
and have realized what a terrible mistake that was, 
please increment the following counter as a warning 
to the next guy: 

total_hours_wasted_here = 11 
*/

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

6

16.04.2013, 19:33

Ok das hört sich logisch an.
Doch wie finde ich anhand meiner Daten heraus, ob sich der Gegner gerade an einer Kreuzung befindet?
Das ist so momentan mein größtes Problem, welches mir auch am meisten Bauchschmerzen bereitet.

Du vergleichst die Position mit der Position einer Kreuzung.

xXSlayerXx

Treue Seele

  • »xXSlayerXx« ist der Autor dieses Themas

Beiträge: 111

Beruf: Technischer Produktdesigner

  • Private Nachricht senden

7

16.04.2013, 19:40

Mein Map Format besteht momentan aus:

X= WALL
W= MONSTERSPAWNGATE
P= TALER
F= FREE FIELD
C= COINT
S= PLAYERSPAWN

Soll ich das also erweitern, damit erkenntlich wird, ob es sich um eine Kreuzung handelt oder nicht?
Und dann nochmal erkenntlich, ob es so eine Kreuzung ist:
###
XXX
#X#
oder so eine:

#X#
XXX
#X#
?
Bestes Zitat aus einem Quellcode :D

C-/C++-Quelltext

1
2
3
4
5
6
7
8
/** 
Once you are done trying to ‘optimize’ this routine, 
and have realized what a terrible mistake that was, 
please increment the following counter as a warning 
to the next guy: 

total_hours_wasted_here = 11 
*/

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

8

16.04.2013, 19:46

Soll ich das also erweitern, damit erkenntlich wird, ob es sich um eine Kreuzung handelt oder nicht?
Wie du magst!

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

9

16.04.2013, 20:01

????

Du benutzt doch Tilemaps oder nicht? Bei mal ein Beispiel mit deiner Notation:

XFX
FFF
XFX

XXX
FFF
XFX

Das sind zwei Beispiele von den Kreuzungen von denen ich gesprochen habe. Es geht einfach um Positionen, an welchen dem Gegner/Spieler neue Möglichkeiten für die Bewegung gegeben werden. Es gibt also nicht mehr nur noch den Weg nach vorne und den Weg nach hinten sondern einen neuen. Im Prinzip können hier auch einfache Kurven interessant sein. Würdest du jetzt für jede Möglichkeit ein neues Zeichen benutzen, wäre das zwar möglich aber an sich doch unsinnig.
Du kannst doch einfach die benachbarten Tiles betrachten. Wenn diese begehbar sind, dann weißt du, dass du von deiner aktuellen Position zu diesem Tile gehen kannst. Das ist ja eigentlich das was du möchtest. Du guckst also die Tiles über, unter und neben deiner aktuellen Position an. Wenn diese begehbar sind, dann kannst du entsprechend reagieren.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

xXSlayerXx

Treue Seele

  • »xXSlayerXx« ist der Autor dieses Themas

Beiträge: 111

Beruf: Technischer Produktdesigner

  • Private Nachricht senden

10

16.04.2013, 20:04

ist es möglich, die struktur nach nach der Position zu durchsuchen, ohne einmal alle Objekte der Map durchzugehen und zu gucken, ob eines davon neben dem gegner ist?
Bestes Zitat aus einem Quellcode :D

C-/C++-Quelltext

1
2
3
4
5
6
7
8
/** 
Once you are done trying to ‘optimize’ this routine, 
and have realized what a terrible mistake that was, 
please increment the following counter as a warning 
to the next guy: 

total_hours_wasted_here = 11 
*/

Werbeanzeige