Programmera spel i C++ för nybörjare/Länkad lista 1
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