Programmera spel i C++ för nybörjare/Länkad lista 1

Från Wikibooks
Hoppa till navigering Hoppa till sök


Länkad lista[redigera]

Koden inspirerad av artikel: http://www.gamedev.se/artiklar/media/lankadelistor/lankadelistor.pdf


Att ha en lista som:

class fiender[100];

fungerar bra i de flesta enklare spel, men en dag kommer du att komma till den situationen när du behöver kunna stoppa in obegränsat med motståndare i en lista. Det finns några inbyggda klasser i STL biblioteket (array, deck osv.) men om du inte vill använda det kan du använda det som kallas för en ”länkad lista”.


Anta att du har ett spel där det skall komma ut obegränsat med sälar du skall skjuta ihjäl, som i spelet "seal hunter". Hur skall du då gå tillväga? Först måste du använda dig av en klass. Vi kan för enkelhetens skull kalla den "seal", vilket är "säl" på engelska. Ett förslag kan vara:

class seal 
{
public:
//Konstruktordeklaration, definition utanför klassdeklarationen
seal (int  hastighet, char sort, double spelare_x, double spelare_y);//startvärden
//Destruktion
~seal(){};

int  hastighet; //Hur snabb är den
double spelare_x; // var är den i sidled i programmet
double spelare_y; //var är den i höjdled i programmet
char sort; // säl, sjölejon, valross osv.
sf::Sprite sprite;

};//

//Konstruktionsdeklaration-------------------------------------------------------------------------
seal::seal (int  ut_hastighet, char ut_sort, double ut_spelare_x, double ut_spelare_y)
{
        hastighet=ut_hastighet;
        sort=ut_sort;
        spelare_x=ut_spelare_x;
        spelare_y=ut_spelare_y;
}/slut på class-deklaration

Det fungerar väl som en bra klass för sälfiender, eller hur? Anta nu att vi skall skapa säl, på säl, på säl, på säl...... du förstår tanken. Då måste vi kunna lägga in dem i en kö som kan växa obehindrat. Inte nog med det, vi måste kunna hitta en speciell säl i kön. Hur gör man det? Grundidén är följande:

  • Första sälen i kön vet att ingen står framför.
  • Sista sälen i kön vet att ingen står bakom
  • Alla andra sälar i kön vet att en säl står framför- och bakom dem, dessutom vilka sälar som står alldeles framför- och bakom dem.

Så om man går igenom kön vet man vilken säl som står först. I den sälens class-deklaration finns en länk till sälen bakom. Den sälen har i sin tur en länk till den säl som står framför den (i det här fallet den säl som står först i ledet) och även den säl som står bakom (om det inte råkar vara den sista sälen i kön, men det händer bara om kön enbart består av två sälar). För att underlätta hur det fungerar använder vi inte en sälklass först, utan en enkel struct.


Skapa enkel struct-lista[redigera]

Enklast möjliga struct ser ut så här:

struct sNode
{
int ID; //En identifierare för platsen
sNode *Next; //En pekare till den som står bakom i kön
sNode *Previous; //En pekare till den som står bakom i kön
};


Dessutom behöver vi ange de två pekarna som globala variabler (för enkelhetens skull):

sNode *Head = 0;
sNode *Tail = 0;


Koden blir:

#include "stdafx.h"

struct sNode //Allt är public så struct blir bäst 
{
int ID; //En identifierare för just den här figuren i kön
sNode *Next; //En pekare till den som står framför i kön
sNode *Previous; //En pekare till den som står bakom i kön
};

//Pekare till första- och sista elementet i den länkade listan
sNode *Head = 0; //Först i kön, global variabel
sNode *Tail = 0; //Sist i kön, global variabel

int _tmain(int argc, _TCHAR* argv[])
{
	return 0; 
}


Befolka listan[redigera]

Hur gör man för att lägga in något längst fram, eller längst bak i listan? Så här kan funktionerna för detta se ut:

void AddFront(sNode *NewNode)
{//Börja lägga in längst fram
if (Head == 0 && Tail == 0) // listan är tom
 {
 Head = NewNode; //Den är både Head och Tail samtidigt
 Tail = NewNode; //-"-
 }
else // listan är inte tom
 {
 NewNode->Next = Head; //Vi kopplar ihop det gamla  huvudet och den nya noden som vi sätter in i listan
 Head->Previous = NewNode; //Vi puttar tillbaka Head/huvudet ett snäpp
 Head = NewNode; //Det nya huvudet blir den nya noden.
 }
}//slut på att lägga in längst fram
void AddBack(sNode *NewNode) //Lägg in längst bak i kön
{ //Börja lägga in längst bak
if (Head == 0 && Tail == 0) // listan är tom
 {
 Head = NewNode; //Den är både Head och Tail samtidigt
 Tail = NewNode; //-"-
 }
else // listan är inte tom
 {
 NewNode->Previous = Tail; //Vi kopplar ihop den gamla svansen/Tail och den nya noden som vi sätter in i listan
 Tail->Next = NewNode; //Vi säger att next=från föregående nod är den här noden
 Tail = NewNode; //Den nya svansen/Tail blir den nya noden.
 }
} //slut på att lägga in längst bak

Hitta en spelare[redigera]

Då kan vi slänga in en spelare i fronten eller i slutet på kön. Men hur hittar vi en speciell spelare i kön?

bool SearchList(int ID)
{ //Börja söka
 sNode *Temp = Head; //Börja vid huvudet, först i kön
 while (Temp != 0)//Så länge dety finns spelare i kön
   {
   if (Temp->ID == ID) //Om vi hittar det eftersökta ID?
   return true; //Sann om den hittas
   Temp = Temp->Next; //Gå till nästa i kön
   }
 return false; //False om ingen hittats
} //sluta söka

Komplett kod:-----------------------------------------------------------

#include "stdafx.h"

struct sNode //Allt är public så struct blir bäst
{
int ID; //En identifierare för just den här figuren i kön
sNode *Next; //En pekare till den som står framför i kön
sNode *Previous; //En pekare till den som står bakom i kön
};

//Pekare till första- och sista elementet i den länkade listan
sNode *Head = 0; //Först i kön, global variabel
sNode *Tail = 0; //Sist i kön, global variabel

void AddFront(sNode *NewNode); //Lägg in längst fram i kön
void AddBack(sNode *NewNode); //Lägg in längst bak i kön
bool SearchList(int ID); //Sök en speciell spelare

int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

void AddFront(sNode *NewNode)
{//Börja lägga in längst fram
if (Head == 0 && Tail == 0) // listan är tom
 {
 Head = NewNode; //Den är både Head och Tail samtidigt
 Tail = NewNode; //-"-
 }
else // listan är inte tom
 {
 NewNode->Next = Head; //Vi kopplar ihop det gamla  huvudet och den nya noden som vi sätter in i listan
 Head->Previous = NewNode; //Vi puttar tillbaka Head/huvudet ett snäpp
 Head = NewNode; //Det nya huvudet blir den nya noden.
 }
}//slut på att lägga in längst fram

void AddBack(sNode *NewNode) //Lägg in längst bak i kön
{ //Börja lägga in längst bak
if (Head == 0 && Tail == 0) // listan är tom
  {
 Head = NewNode; //Den är både Head och Tail samtidigt
 Tail = NewNode; //-"-
 }
else // listan är inte tom
 {
 NewNode->Previous = Tail; //Vi kopplar ihop den gamla svansen/Tail och den nya noden som vi sätter in i listan
 Tail->Next = NewNode; //Vi säger att next=från föregående nod är den här noden
 Tail = NewNode; //Den nya svansen/Tail blir den nya noden.
 }
} //slut på att lägga in längst bak

bool SearchList(int ID)
{ //Börja söka
 sNode *Temp = Head; //Börja vid huvudet, först i kön
 while (Temp != 0)//Så länge det finns spelare i kön
   {
   if (Temp->ID == ID) //Om vi hittar det eftersökta ID?
   return true; //Sann om den hittas
   Temp = Temp->Next; //Gå till nästa i kön
   }
 return false; //False om ingen hittats
} //sluta söka


Med sälklassen[redigera]

Observera nu att vi lagt in det som tidigare fanns i struct under public i klassen, så att man kommer åt det. ID är utlagt så att det kan tilldelas samtidigt som sälen skapas, medan head och tail läggs in i konstruktionen så att de alltid är 0/NULL vid skapandet.

#include "stdafx.h"

class seal 
{
public:
//Konstruktordeklaration, definition utanför klassdeklarationen
seal (int  hastighet, char sort, double spelare_x, double spelare_y, int ID);//startvärden
//Destruktion
~seal(){};

int ID; //En identifierare för just den här figuren i kön
seal *Next; //En pekare till den som står framför i kön
seal *Previous; //En pekare till den som står bakom i kön

int  hastighet; //Hur snabb är den
double spelare_x; // var är den i sidled i programmet
double spelare_y; //var är den i höjdled i programmet
char sort; // säl, sjölejon, valross osv.
//sf::Sprite sprite;

};//

//Konstruktionsdeklaration-------------------------------------------------------------------------
seal::seal (int  ut_hastighet, char ut_sort, double ut_spelare_x, double ut_spelare_y, int ut_ID) 
{
	 ID = ut_ID;
	seal *Next = 0;
     seal *Previous = 0;
        hastighet=ut_hastighet;
        sort=ut_sort;
        spelare_x=ut_spelare_x;
        spelare_y=ut_spelare_y;

}//slut på class-deklaration



//Pekare till första- och sista elementet i den länkade listan
seal *Head = 0; //Först i kön, global variabel
seal *Tail = 0; //Sist i kön, global variabel

void AddFront(seal *NewNode); //Lägg in längst fram i kön
void AddBack(seal *NewNode); //Lägg in längst bak i kön
bool SearchList(int ID); //Sök en speciell spelare

int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

void AddFront(seal *NewNode)
{//Börja lägga in längst fram
if (Head == 0 && Tail == 0) // listan är tom
 {
 Head = NewNode; //Den är både Head och Tail samtidigt
 Tail = NewNode; //-"-
 }
else // listan är inte tom
 {
 NewNode->Next = Head; //Vi kopplar ihop det gamla  huvudet och den nya noden som vi sätter in i listan
 Head->Previous = NewNode; //Vi puttar tillbaka Head/huvudet ett snäpp
 Head = NewNode; //Det nya huvudet blir den nya noden.
 }
}//slut på att lägga in längst fram

void AddBack(seal *NewNode) //Lägg in längst bak i kön
{ //Börja lägga in längst bak
if (Head == 0 && Tail == 0) // listan är tom
 {
 Head = NewNode; //Den är både Head och Tail samtidigt
 Tail = NewNode; //-"-
 }
else // listan är inte tom
 {
 NewNode->Previous = Tail; //Vi kopplar ihop den gamla svansen/Tail och den nya noden som vi sätter in i listan
 Tail->Next = NewNode; //Vi säger att next=från föregående nod är den här noden
 Tail = NewNode; //Den nya svansen/Tail blir den nya noden.
 }
} //slut på att lägga in längst bak

bool SearchList(int ID)
{ //Börja söka
 seal *Temp = Head; //Börja vid huvudet, först i kön
 while (Temp != 0)//Så länge dety finns spelare i kön
   {
   if (Temp->ID == ID) //Om vi hittar det eftersökta ID?
   return true; //Sann om den hittas
   Temp = Temp->Next; //Gå till nästa i kön
   }
 return false; //False om ingen hittats
} //sluta söka


Skapa sälar[redigera]

Hur går det då till att skapa säg fem sälar?

// deklarera några noder
seal *seal1 = new seal(50,'S', 10, 10, 1);
//namn, hastighet, sort, x-koordinat, y-koordinat, ID
	seal *seal2 = new seal(50,'S', 10, 42, 2);
      seal *seal3 = new seal(50,'S', 10, 74, 3);
      seal *seal4 = new seal(50,'S', 10, 106, 4);
      seal *seal5 = new seal(50,'S', 10, 138, 5);

Så placeras de dessutom ut längs vänsterkanten ovanför varandra. Nu är sälarna skapade, men de finns inte i någon lista ännu. Sedan kommer det där att lägga in dem i kön:

//Lägger in sälarna i kön, från baksidan.
AddBack(seal1);
AddBack(seal2);
AddBack(seal3);
AddBack(seal4);
AddBack(seal5);

Anta nu att man söker efter en speciell säl i listan, då tar vi till funktionen för att söka upp den. Anta att vi söker efter just säl 2:

if (SearchList(seal->ID))
cout << "Node2 hittades!\n";
else
cout << "Node2 hittades inte.\n";



Komplett fungerande kod:[redigera]

#include "stdafx.h"
#include <iostream>


class seal 
{
public:
//Konstruktordeklaration, definition utanför klassdeklarationen
seal (int  hastighet, char sort, double spelare_x, double spelare_y, int ID);//startvärden
//Destruktion
~seal(){};

int ID; //En identifierare för just den här figuren i kön
seal *Next; //En pekare till den som står framför i kön
seal *Previous; //En pekare till den som står bakom i kön

int  hastighet; //Hur snabb är den
double spelare_x; // var är den i sidled i programmet
double spelare_y; //var är den i höjdled i programmet
char sort; // säl, sjölejon, valross osv.
//sf::Sprite sprite;

};//

//Konstruktionsdeklaration-------------------------------------------------------------------------
seal::seal (int  ut_hastighet, char ut_sort, double ut_spelare_x, double ut_spelare_y, int ut_ID)
{
	     ID = ut_ID;
		 seal *Next = 0;
		 seal *Previous = 0;
        hastighet=ut_hastighet;
        sort=ut_sort;
        spelare_x=ut_spelare_x;
        spelare_y=ut_spelare_y;
}//slut på class-deklaration



//Pekare till första- och sista elementet i den länkade listan
seal *Head = 0; //Först i kön, global variabel
seal *Tail = 0; //Sist i kön, global variabel

void AddFront(seal *NewNode); //Lägg in längst fram i kön
void AddBack(seal *NewNode); //Lägg in längst bak i kön
bool SearchList(int ID); //Sök en speciell spelare

int _tmain(int argc, _TCHAR* argv[])
{
	seal *seal1 = new seal(50,'S', 10, 10, 1);
//namn, hastighet, sort, x-koordinat, y-koordinat, ID
	seal *seal2 = new seal(50,'S', 10, 42, 2);
   seal *seal3 = new seal(50,'S', 10, 74, 3);
   seal *seal4 = new seal(50,'S', 10, 106, 4);
   seal *seal5 = new seal(50,'S', 10, 138, 5);


//Lägger in sälarna i listan
AddBack(seal1);
AddBack(seal2);
AddBack(seal3);
AddBack(seal4);
AddBack(seal5);

if (SearchList(2))
std::cout << "Node2 hittades!\n";
else
std::cout << "Node2 hittades inte.\n";

	return 0;
}

void AddFront(seal *NewNode)
{//Börja lägga in längst fram
if (Head == 0 && Tail == 0) // listan är tom
 {
 Head = NewNode; //Den är både Head och Tail samtidigt
 Tail = NewNode; //-"-
 }
else // listan är inte tom
 {
 NewNode->Next = Head; //Vi kopplar ihop det gamla  huvudet och den nya noden som vi sätter in i listan
 Head->Previous = NewNode; //Vi puttar tillbaka Head/huvudet ett snäpp
 Head = NewNode; //Det nya huvudet blir den nya noden.
 }
}//slut på att lägga in längst fram

void AddBack(seal *NewNode) //Lägg in längst bak i kön
{ //Börja lägga in längst bak
if (Head == 0 && Tail == 0) // listan är tom
 {
 Head = NewNode; //Den är både Head och Tail samtidigt
 Tail = NewNode; //-"-
 }
else // listan är inte tom
 {
 NewNode->Previous = Tail; //Vi kopplar ihop den gamla svansen/Tail och den nya noden som vi sätter in i listan
 Tail->Next = NewNode; //Vi säger att next=från föregående nod är den här noden
 Tail = NewNode; //Den nya svansen/Tail blir den nya noden.
 }
} //slut på att lägga in längst bak

bool SearchList(int ID)
{ //Börja söka
 seal *Temp = Head; //Börja vid huvudet, först i kön
 while (Temp != 0)//Så länge dety finns spelare i kön
   {
   if (Temp->ID == ID) //Om vi hittar det eftersökta ID?
   return true; //Sann om den hittas
   Temp = Temp->Next; //Gå till nästa i kön
   }
 return false; //False om ingen hittats
} //sluta söka