Laatst bijgewerkt:
dinsdag 15 april 2014
Nieuws — Lesstof — Pengo — Projecten — Console API — Links
Pengo © 2002-2003, Joost Ronkes Agerbeek
(adem in, fffffffff) (adem uit, shhhhhhhh) Zzzzzennnnnn.
O pardon, ben je er al. Ik was me even mentaal aan het voorbereiden op deze les. We gaan kunstmatige intelligentie programmeren en daar moet je volledig ontspannen voor zijn. Het is namelijk een hele klus.
Klaar? Oké, daar gaan we dan. Laat ik maar met het slechte nieuws beginnen: onze vijanden worden niet echt slim. Dus dit is een moeilijke les, met lastige code en ingewikkelde abstracte ideeën en aan het eind zijn ons vijanden niets eens slim? Inderdaad. Deal with it. Hé, volgens mij heb ik ineens veel minder lezers. ;-)
Een goede AI schrijven is ontzettend moeilijk, zelfs voor een simpel spel als Pengo. (AI is de afkorting van artificial intelligence wat Engels is voor kunstmatige intelligentie.) De vijand moet de kortste route zoeken naar de speler. Daarbij moet hij de blokken ontwijken en zorgen dat hij niet gedood kan worden. Vervolgens moet hij inschatten waar de speler heen zal lopen zodat hij meteen die kant op kan. En dan moet hij eigenlijk ook nog samenwerken met de andere vijanden.
Onze vijand neemt niet de kortste route, houd geen rekening met het feit dat de speler beweegt en werkt al even slecht samen met andere vijanden als leerlingen die een project uitvoeren (jeetje, heb ik dat echt opgeschreven? :-P). Maar... hij ontwijkt wel alle blokken.
Heb je er al zin in? :-)
Voordat we de AI gaan programmeren, zal ik proberen uit te leggen hoe het algoritme werkt. Het is de bedoeling dat jij het probeert te begrijpen. :-P Ik laat op dit moment nog een aantal details weg, maar die vullen we wel in als we de code gaan schrijven.
Voor ik het vergeet, een algoritme is een stap-voor-stap-procedure voor het oplossen van een bepaald probleem. (Er schiet mij ineens een vraag te binnen voor de eerstvolgende toets. ;-)) In ons geval beschrijft het algoritme dus de stappen die we moeten nemen om te bepalen in welke richting de vijand loopt.
Het doel van de vijand is om tegen de speler aan te lopen. Net als een speler kan een vijand naar boven, naar beneden naar links of naar rechts lopen. We moeten dus voor elke stap bepalen welke van deze vier richtingen hij op moet. In onderstaande afbeelding zie je dit idee getekend.
In afbeelding 1 moet de vijand naar rechtsonder lopen om Pengo te pakken te krijgen. Hij kan niet diagonaal lopen, dus hij moet eerst naar rechts en dan naar beneden of andersom. De volgorde is in dit geval niet van belang.
Als de vijand op één lijn staat met Pengo, is het een duidelijke zaak. In afbeelding 2 moet de vijand naar rechts.
'Hé, dat is een makkie. En je had gezegd dat het zo moeilijk zou zijn. Nou, ik merk er niets van.' Oké, je hebt erom gevraagd.
In de praktijk staan er allerlei blokken tussen de vijand en de speler in. De vijand mag niet door deze blokken heen lopen en heeft ook niet de mogelijkheid om ze weg te schoppen. Hij zal dus een weg moet zoeken naar Pengo waarbij hij de blokken ontwijkt. Dat is voor jou misschien niet zo'n grote opgave, maar om dat om te zetten in een computeralgoritme is een heel karwei. Als je me niet gelooft (maar waarom zou je dat niet doen), probeer het dan maar eens. (Zelf aan het werk? Nee, nee, ik geloof je.)
De kortste weg zoeken van de vijand naar de speler is een lastige opgave waar je recursie voor nodig hebt. (Het kan me niet schelen dat je wilt weten wat recursie is, ik heb geen zin om het je uit te leggen.) Wij zijn allang blij als we een route kunnen vinden van de vijand naar de speler. (Ja, jij bent dan ook blij.)
In afbeelding 3 zie je dat er op de weg van de vijand naar de speler een blok staat. In eerste instantie doen we alsof de blokken er niet zijn. We laten de vijand net zo lang richting Pengo lopen tot hij niet meer verder kan. Zodra we bij een blok zijn, veranderen we de looprichting van de vijand. In afbeelding 4 kun je dit zien. De vijand begint naar beneden te lopen. Zodra hij in het vakje komt dat met een 1 gemarkeerd is, kan hij niet verder naar beneden en loopt hij naar rechts.
Het kan voorkomen dat de vijand op een punt terecht komt waar hij niet meer rechtstreeks naar de speler kan lopen. Dit kun je zien in afbeelding 5.
De vijand begint naar rechts te lopen en komt dan aan in vak 1. Daar kan hij niet verder naar rechts. Hij zou nu naar beneden moeten lopen, maar ook dat gaat niet meer. We kunnen de vijand nu wel stil laten staan, maar dan komt hij nooit bij Pengo terecht. Hij zal dus een stap weg moeten doen van de speler.
Stel dat we de speler nu naar links bewegen. De eerstvolgende stap is dan een stap naar rechts. En dan weer een stap naar links. En dan weer een stap naar rechts. We moeten voorkomen dat de vijand op deze manier begint te ijsberen. (Ha, ha. Pinguïn... ijsberen. Heb je 'm, heb je 'm! Laat maar.) Daarom onthouden we waar de vijand vandaan komt. Als het even kan, laten we hem geen stap terug doen. In afbeelding 5 loopt de vijand vanaf vak 1 dus naar boven. Soms kun je natuurlijk niet anders dan teruglopen, zoals in afbeelding 6.
Vijanden mogen dan slechts kunstmatig intelligent zijn, ze zijn niet suïcidaal. Daarom zullen ze nooit op één lijn gaan staan met de speler als er slechts één blok tussenzit. In afbeelding 7 zal de vijand dus nooit op vakje 1, 2 of 3 gaan staan. Vakjes 4 en 5 zijn wel veilig.
Om te voorkomen dat meerdere vijanden dezelfde route lopen en je ze dus makkelijk tegelijk kunt doodschoppen (klinkt gezellig), mogen vijanden nooit op hetzelfde vakje staan. Voor een vijand is een andere vijand dus net een blok.
Het wordt tijd om weer aan het programmeren te gaan. Laten we maar makkelijk beginnen.
We zullen regelmatig moeten controleren of de vijand in een bepaalde richting kan lopen. Een richting is geblokkeerd als er een blok staat of als er een vijand staat. IsEnemy en IsBlock zijn relatief trage functies, dus we willen zien niet voortdurend aanroepen. Daarom maken we voor elke richting een variabele aan waarin we opslaan of deze geblokkeerd is.
/**
* Verplaats een vijand één positie.
*
* @param enemy de vijand die verplaatst moet worden
*/
void MoveEnemy(Enemy& enemy)
{
// bepaal of looprichtingen geblokkeerd zijn
bool myIsLeftBlocked = IsBlock(enemy.X - 1, enemy.Y) ||
IsEnemy(enemy.X - 1, enemy.Y);
bool myIsRightBlocked = IsBlock(enemy.X + 1, enemy.Y) ||
IsEnemy(enemy.X + 1, enemy.Y);
bool myIsUpBlocked = IsBlock(enemy.X, enemy.Y - 1) ||
IsEnemy(enemy.X, enemy.Y - 1);
bool myIsDownBlocked = IsBlock(enemy.X, enemy.Y + 1) ||
IsEnemy(enemy.X, enemy.Y + 1);
}
De makkelijkste situatie is degene die je in afbeelding 8 ziet. De vijand kan niet bewegen, dus we hoeven ook de richting niet te bepalen; we stoppen de functie gewoon.
// zijn alle richtingen geblokkeerd?
if (myIsLeftBlocked && myIsRightBlocked && myIsUpBlocked &&
myIsDownBlocked)
{
// ja, vijand beweegt niet
return;
}
Als de situatie is zoals in afbeelding 9, dan is het ook vrij makkelijk om te bepalen wat we moeten doen. (Als je dat niet inziet, dan ben je zelf hard toe aan een nieuw algoritme. :-P)
// staat de speler links?
if (((enemy.X - 1) == GlobalLevel.Player.X) &&
(enemy.Y == GlobalLevel.Player.Y))
{
// ja, beweeg naar links
enemy.X--;
// speler is dood
GlobalLevel.Player.IsDead = true;
return;
}
// staat de speler rechts?
if (((enemy.X + 1) == GlobalLevel.Player.X) &&
(enemy.Y == GlobalLevel.Player.Y))
{
// ja, beweeg naar rechts
enemy.X++;
// speler is dood
GlobalLevel.Player.IsDead = true;
return;
}
// staat de speler boven?
if ((enemy.X == GlobalLevel.Player.X) &&
((enemy.Y - 1) == GlobalLevel.Player.Y))
{
// ja, beweeg naar boven
enemy.Y--;
// speler is dood
GlobalLevel.Player.IsDead = true;
return;
}
// staat de speler onder?
if ((enemy.X == GlobalLevel.Player.X) &&
((enemy.Y + 1) == GlobalLevel.Player.Y))
{
// ja, beweeg naar beneden
enemy.Y++;
// speler is dood
GlobalLevel.Player.IsDead = true;
return;
}
Je kunt je code testen door vlak langs een vijand te lopen. Ongeveer 1 op de 2 keer (afhankelijke van de delay die je voor de speler en de vijanden hebt ingesteld) pakt de vijand je dan.
De derde simpele situatie zie je in afbeelding 10. De vijand kan maar één kant op.
// kan de vijand alleen maar naar links?
if (myIsRightBlocked && myIsUpBlocked && myIsDownBlocked &&
!myIsLeftBlocked)
{
// ja, verplaats 'm naar links
enemy.X--;
return;
}
// kan de vijand alleen maar naar rechts?
if (myIsLeftBlocked && myIsUpBlocked && myIsDownBlocked &&
!myIsRightBlocked)
{
// ja, verplaats 'm naar rechts
enemy.X++;
return;
}
// kan de vijand alleen maar naar boven?
if (myIsLeftBlocked && myIsRightBlocked && myIsDownBlocked &&
!myIsUpBlocked)
{
// ja, verplaats 'm naar boven
enemy.Y--;
return;
}
// kan de vijand alleen maar naar beneden?
if (myIsLeftBlocked && myIsRightBlocked && myIsUpBlocked &&
!myIsDownBlocked)
{
// ja, verplaats 'm naar beneden
enemy.Y++;
return;
}
De makkelijkste manier om te voorkomen dat de vijand naar een positie loopt waar de speler hem kan doodschoppen, is zulke posities blokkeren. Dat doen we door rekening te houden met deze zelfmoordposities bij het bepalen van myIsLeftBlocked, myIsRightBlocked, myIsUpBlocked en myIsDownBlocked. We hebben dan wel een functie nodig die van elke positie kan bepalen of het een zelfmoordpositie is.
/**
* Bepaalt van de opgegeven positie of het een zelfmoordpositie is. Een positie
* is een zelfmoordpositie als hij op één lijn ligt met de speler en er tussen
* de positie en de speler één blok staat.
*
* @param x de x-coördinaat van de positie
* @param y de y-coördinaat van de positie
*
* @return true als de opgegeven positie een zelfmoordpositie is, anders false
*/
bool IsSuicidePosition(int x, int y)
{
// is de positie op één verticale lijn met de speler?
if (GlobalLevel.Player.X == x)
{
// ja, bepaal of speler boven of onder positie staat
int myUpperY, myLowerY;
// staat de speler boven de positie?
if (GlobalLevel.Player.Y < y)
{
// ja, onthoud
myUpperY = GlobalLevel.Player.Y;
myLowerY = y;
}
else
{
// nee, onthoud
myUpperY = y;
myLowerY = GlobalLevel.Player.Y;
}
// doorloop alle plaatsen tussen positie en speler en tel blokken
int myNumberOfBlocks = 0;
for (int i = myUpperY; i < myLowerY; i++)
{
// is dit een blok?
if (IsBlock(x, i))
{
// ja, verhoog aantal blokken
myNumberOfBlocks++;
}
}
// staat er precies één blok tussen positie en speler?
if (myNumberOfBlocks == 1)
{
// ja, dit is een zelfmoordpositie
return true;
}
}
// is de positie op één horizontale lijn met de speler?
if (GlobalLevel.Player.Y == y)
{
// ja, bepaal of speler links of rechts van positie staat
int myLeftX, myRightX;
// staat de speler links van de positie?
if (GlobalLevel.Player.X < x)
{
// ja, onthoud
myLeftX = GlobalLevel.Player.X;
myRightX = x;
}
else
{
// nee, onthoud
myLeftX = x;
myRightX = GlobalLevel.Player.X;
}
// doorloop alle plaatsen tussen positie en speler en tel blokken
int myNumberOfBlocks = 0;
for (int i = myLeftX; i < myRightX; i++)
{
// is dit een blok?
if (IsBlock(i, y))
{
// ja, verhoog aantal blokken
myNumberOfBlocks++;
}
}
// staat er precies één blok tussen positie en speler?
if (myNumberOfBlocks == 1)
{
// ja, dit is een zelfmoordpositie
return true;
}
}
// positie is geen zelfmoordpositie
return false;
}
Deze code doet feitelijk twee keer hetzelfde: één keer als de positie op een horizontale lijn staat met de speler en één keer als de positie op een verticale lijn staat met de speler. Omdat we een for-lus van de kleinste waarde naar de grootste waarde moeten doorlopne, moeten we bepalen wat de kleinste waarde is en wat de grootste waarde is (het lijkt wel logisch). Als we dat eenmaal weten, doorlopen we alle plaatsen tussen de opgegeven positie en de speler en we tellen het aantal blokken dat we tegenkomen. Alleen als er één blok tussen de speler en de opgegeven positie staat, gaat het om een zelfmoordpositie (zie afbeelding 7).
Opmerking 1: de functie IsSuicidePosition controleert niet of we misschien de positie hebben opgegeven waar de speler staat. Toch gaat het goed als je de positie van de speler opgeeft (IsSuicidePosition geeft dan false terug). Ik laat het als oefening voor de lezer om te controleren dat dit inderdaad zo is. :-P
Opmerking 2: Er zijn (minstens :-s) twee situaties waarin de functie IsSuicidePosition een verkeerd resultaat oplevert. De eerste kom je tegen wanneer je coördinaten opgeeft die buiten het veld liggen (hierdoor crasht Pengo). Dit moet je dus gewoon niet doen. De tweede situatie is als je een positie opgeeft die èn links ligt van Pengo èn een blok bevat. In dat geval telt IsSuicidePosition een blok teveel. Echter, omdat de vijand op die positie toch niet kan staan, is dat geen probleem. Ik laat het wederom als oefening voor de lezer om na te gaan waarom dit zo is. :-)
Waar hadden we deze functie ook al weer voor nodig? O ja, we zouden myIsLeftBlocked, myIsRightBlocked, myIsUpBlocked en myIsDownBlocked aanpassen. Deze variabelen moeten nu ook true zijn als ze naar een zelfmoordpositie verwijzen. Een kleine aanpassing dus.
// bepaal of looprichtingen geblokkeerd zijn bool myIsLeftBlocked = IsBlock(enemy.X - 1, enemy.Y) || IsEnemy(enemy.X - 1, enemy.Y) || IsSuicidePosition(enemy.X - 1, enemy.Y); bool myIsRightBlocked = IsBlock(enemy.X + 1, enemy.Y) || IsEnemy(enemy.X + 1, enemy.Y) || IsSuicidePosition(enemy.X + 1, enemy.Y); bool myIsUpBlocked = IsBlock(enemy.X, enemy.Y - 1) || IsEnemy(enemy.X, enemy.Y - 1) || IsSuicidePosition(enemy.X, enemy.Y - 1); bool myIsDownBlocked = IsBlock(enemy.X, enemy.Y + 1) || IsEnemy(enemy.X, enemy.Y + 1) || IsSuicidePosition(enemy.X, enemy.Y + 1);
Om zo snel mogelijk bij de speler te komen, loopt de vijand een zo kort mogelijke route. Dus als de speler linksonder de vijand staat, loop de vijand eerst naar links en dan naar beneden (of andersom). Dat betekent dat we in onze code moeten controleren waar de speler staat ten opzichte van de vijand en naar aanleiding daarvan een richting moeten kiezen.
Voor de duidelijkheid, deze code komt dus in MoveEnemy te staan onder de code die we tot nu toe hebben. Zo, dat zou me weer heel wat vragen moeten schelen. (In ieder geval van degenen die deze tekst ook echt lezen.)
// moet de vijand naar links?
if (GlobalLevel.Player.X < enemy.X)
{
// ja, kan dat?
if (!myIsLeftBlocked)
{
// ja, doe maar dan
enemy.X--;
return;
}
}
// moet de vijand naar boven?
if (GlobalLevel.Player.Y < enemy.Y)
{
// ja, kan dat?
if (!myIsUpBlocked)
{
// ja, doe maar dan
enemy.Y--;
return;
}
}
// moet de vijand naar rechts?
if (GlobalLevel.Player.X > enemy.X)
{
// ja, kan dat?
if (!myIsRightBlocked)
{
// ja, doe maar dan
enemy.X++;
return;
}
}
// moet de vijand naar beneden?
if (GlobalLevel.Player.Y > enemy.Y)
{
// ja, kan dat?
if (!myIsDownBlocked)
{
// ja, doe maar dan
enemy.Y++;
return;
}
}
Zoals je ziet beweegt de vijand altijd in een vaste volgorde. Dus als de speler rechtsboven de vijand staat, gaat de vijand altijd eerst naar rechts en dan naar boven. Misschien niet de fraaiste oplossing, maar een stuk makkelijker dan wanneer we de richting willekeurig moeten laten bepalen.
'Mmm, opvallend dat hij afwijkt van de gebruikelijke volgorde van links, rechts, boven, beneden. Zou dat opzettelijk zijn?' Vast wel. 'Zou hij ons ook vertellen waarom of laat hij het weer als oefening voor de lezer?' Gna. :-P
Op dit punt in de code kunnen we het volgende met zekerheid zeggen: als de vijand nog niet heeft bewogen, dan is een directe route naar de speler toe niet mogelijk. Met andere woorden, we zullen een indirecte route moeten kiezen. Voor de duidelijkheid zal ik dit met een opmerking aangeven in de code.
We weten trouwens ook dat de vijand nog twee kanten op kan, anders had de vijand maar één mogelijke looprichting gehad en dan was hij daar al heen gelopen. Ja, ja, denk daar maar eens over na.
Het maakt eigenlijk niet zoveel uit in welke van de overgebleven richtingen de vijand loopt, dus laat we de eerste de beste vrije richting maar kiezen.
// OPMERKING: op dit punt weten we dat een directe route naar de speler
// niet mogelijk is
// kan de vijand naar links?
if (!myIsLeftBlocked)
{
// ja, doe maar dan
enemy.X--;
return;
}
// kan de vijand naar rechts?
if (!myIsRightBlocked)
{
// ja, doe maar dan
enemy.X++;
return;
}
// kan de vijand naar boven?
if (!myIsUpBlocked)
{
// ja, doe maar dan
enemy.Y--;
return;
}
// kan de vijand naar beneden?
if (!myIsDownBlocked)
{
// ja, doe maar dan
enemy.Y++;
return;
}
Ik ga even ingewikkeld doen. (Was het zo makkelijk tot nu toe dan?) Zodra de vijand in een situatie terecht komt waar hij niet de kortste route kan lopen, begint hij te ijsberen. Om dit te voorkomen moeten we onthouden waar de vijand als laatst geweest is en die kant niet meer oplopen. Echter, we hoeven alleen maar te onthouden waar de vijand vandaan komt als hij niet de kortste route neemt en we hoeven alleen maar te controleren waar de vijand vandaan komt (en waar hij dus niet heen mag) als hij wel de kortste route wil nemen. Ben je al duizelig?
Laten we bij het begin beginnen (zei hij aan het eind van één van de laatste lessen). Hoe houden we de vorige positie van de vijand bij? Voor elke vijand moeten we een vorige positie opslaan. Daarvoor moeten we dus de structure Enemy uitbreiden.
/**
* Een vijand.
*/
struct Enemy
{
/**
* De positie van de vijand.
*/
int X, Y;
/**
* De vorige positie van de vijand.
*/
int OldX, OldY;
/**
* Geeft aan of de vijand beweegt.
*/
bool IsMoving;
};
In MoveEnemy maken we van de oude positie gebruik om te bepalen uit welke richting de vijand komt. De volgende code komt helemaal bovenaan in de functie MoveEnemy te staan.
// bepaal uit welke richting de vijand komt
bool myCameFromLeft = false;
bool myCameFromRight = false;
bool myCameFromAbove = false;
bool myCameFromBelow = false;
// komt de vijand van links
if (enemy.OldX < enemy.X)
{
// ja
myCameFromLeft = true;
}
// komt de vijand van rechts
if (enemy.OldX > enemy.X)
{
// ja
myCameFromRight = true;
}
// komt de vijand van boven
if (enemy.OldY < enemy.Y)
{
// ja
myCameFromAbove = true;
}
// komt de vijand van beneden?
if (enemy.OldY > enemy.Y)
{
// ja
myCameFromBelow = true;
}
Nu we bepaalt hebben waar de vijand vandaan komt, kunnen we de oude positie overschrijven met de huidige coördinaten. Die geven straks de oude positie aan.
// onthoud oude positie van vijand enemy.OldX = enemy.X; enemy.OldY = enemy.Y;
Het wordt tijd dat we ook gebruik gaan maken van de informatie die we nu hebben. Bij de eerste paar controles hoeven we geen rekening te houden met de richting waar de vijand vandaan kwam. Immers, als de speler direct naast de vijand staat, dan moet de vijand de speler pakken, ongeacht waar hij vandaan komt. Evenzo, als de richting waaruit de vijand komt de enige mogelijke looprichting is, dan zal hij daar toch heen moeten gaan.
Pas in de code die daarna komt, houden we rekening met de looprichting van de vijand. Dit doen we door vanaf dat moment de richting waarvandaan de vijand komt aan te geven als geblokkeerd.
// blokkeer de richting waar de vijand vandaan komt myIsLeftBlocked = myIsLeftBlocked || myCameFromLeft; myIsRightBlocked = myIsRightBlocked || myCameFromRight; myIsUpBlocked = myIsUpBlocked || myCameFromAbove; myIsDownBlocked = myIsDownBlocked || myCameFromBelow;
Compileren, linken en... oeps, foutmeldinkje. Even oplossen. Zo. Compileren, linken en... weer een foutmelding. Even.. zo. Compileren, linken en... mmm.... Nu dan. Compileren, linken en... spelen maar. :-)
Dit is het! Pengo is af. Misschien dat je vindt dat er nog wat aanpassingen en uitbreidingen nodig zijn, maar ik heb je nu ver genoeg aan het handje gehouden.
Was dit het? Was dit echt de laatste les? Nee! ;-) Volgende keer gaan we het hele spel namelijk omzetten naar een Windows-applicatie. Yeah, baby!
Programmeren is leuk. :-D
Als je de bovenstaande code af hebt en je wilt Pengo graag uitbreiden, dan kun je de volgende features toevoegen.
De volgende bestanden horen bij deze les.
Laatst bijgewerkt:
dinsdag 15 april 2014