Inledning
Detta är en direkt fortsättning på del 1. Läs del 1 först!
Hitta en röd pixel
Vi ska som uppvärmning börja med att söka igenom ban-grafiken efter en röd pixel. Den röda pixeln har vi valt som startposition för skeppet. På så vis blir det väldigt enkelt att bygga banor eftersom vi bara behöver ett ritprogram. Vi skapar en ny metod i Game1.cs som tar emot en textur och ett pixelvärde samt som returnerar en vektor som beskriver var i bilden pixeln hittades.
protected Vector2 FindPixel(Texture2D texture, uint color)
{
//Kopiera pixeldata som uint
uint[] bits = new uint[texture.Width * texture.Height];
texture.GetData<uint>(bits);
for (int x = 0; x < level.Width; x++)
{
for (int y = 0; y < level.Height; y++)
{
//Har vi hittat det vi söker?
if (bits[x + y * texture.Width] == color)
return new Vector2(x, y);
}
}
//Om inget hittades
return Vector2.Zero;
}
I vår LoadContent kan vi nu positionera skeppet genom att använda metoden:
ship.Position = FindPixel(level, 0xFFFF0000) - new Vector2(0, ship_normal.Height / 2 + 5);
Pixeldatan är i 32-bitars format enligt ARGB, där A=alpha, R=röd, G=grön och B=blå. Varje nivå är mellan 0-255 som hexadecimalt motsvarar två siffror. En solid röd fär blir alltså 0xFFFF0000 hexadecimalt. Från pixlens position flyttar vi centrum av skeppet uppåt med en liten marginal.
Det hela bygger på att det bara finns en pixal i bilden som är #FFFF0000. Prova att det fungerar.
Hitta alla kantpixlar
Teori
Vi vill kunna kolla kollision mot bakgrundsbilden (banan) och mot skeppet hela tiden. Detta även då skeppet är roterat såklart. Under dessa förutsättningar så kommer inte enkla metoder som rektangel mot regtangel eller cirkel mot cirkel att fungera. Bakgrunden roterar ju ej så där kan vi använda en rektangel av data, men hur blir det med skeppet?
Vi skulle kunna rotera grafiken i skeppet och göra en vanlig pixel mot pixel test. I vårt fall hade de flesta datorer inte haft något problem med det. Hade vi däremot jobbat med ett spel med tusentals sprites på skärmen samtidigt så är det en dålig idé.
Tekniken vi ska använda är rätt enkel. Vi ska börja med att beräkna de pixlar av skeppet som är intressanta, nämligen kantpixlarna. Det är endast dessa som beskriver formen på vårt skepp. DE pixlar vi vill ha fram är de gulmarkerade i bilden nedan.
Vi kan göra en snabb beräkning på hur mycket vi tjänar på att göra detta. Spriten vi använder är 23 x 49 pixlar, dvs totalt 1127 pixlar. Det betyder 1127 rotationsberäkningar varje gång skeppet roterar samt 1127 per pixel test mot bakgrunden för att veta att vi inte kolliderar. Kantpixlarna är endast ca 110st.
Praktik
Vi behöver utöka klassen SpaceShip med lite fler saker. Kantpixlarna kommer vi att kalla "hull" efter engelskans skrov. Vi lägger till följande medlemmar:
bool _recalcHull = true;
List<Point> _hull;
Dictionary<Point, bool> _hullTransformed;
Variabeln _recalcHull ska indikera om vi behöver räkna om kantpixlarna. Detta kan vi nu utnyttja vår property Rotation genom att ändra den till:
public float Rotation
{
get { return _rotation; }
set { _rotation = value; _recalcHull = true; }
}
På så vis kommer vi att veta om skeppet har roterats av spelet.
Listan med punkter, _hull, kommer att innehålla alla kantpixlar.
Dictionaryn _hullTransformed kommer att hålla de aktuella kantpixlarna centrerade kring skeppets mittpunkt och såklart roterade efter skeppets rotation.
Det kan tyckas konstigt att vi använder en Dictionary för de transformerade kantpixlarna. Faktum är att vi kan lika gärna använda en List i vårt exempel. Vi ska bara var noga med att inte skapa om lagringsstrukturen varje gång för det sänker prestandan. Anledningen till en Dictionary är om vi i framtiden vill testa kollision mellan två roterande sprites. I så fall har vi redan kantpixelns position som ett index i dictionaryn och kan snabbt avgöra om den finns i en annan dictionary (annan sprite). På så vis minskas komplexiteten från att vara kvadratisk till att vara linjär, men det är ämne för en annan artikel.
Vi går direkt in på en metod som beräknar kantpixlarna som vi placerar i SpaceShip.cs den också.
private void FindHull()
{
_hull = new List<Point>();
//Läs in pixeldata från spriten
uint[] bits = new uint[_gfx.Width * _gfx.Height];
_gfx.GetData<uint>(bits);
for (int x = 0; x < _gfx.Width; x++)
{
for (int y = 0; y < _gfx.Height; y++)
{
//Ignorera genomskinliga pixlar
if ((bits[x + y * _gfx.Width] & 0xFF000000) >> 24 <= 20)
continue;
//Pixlar på kanten av texturen?
if (x == 0 || y == 0 || x == _gfx.Width - 1 || y == _gfx.Height - 1)
{
_hull.Add(new Point(x, y));
continue;
}
//Kant i spriten?
if (((bits[x + 1 + y * _gfx.Width] & 0xFF000000) >> 24 <= 20) ||
((bits[x - 1 + y * _gfx.Width] & 0xFF000000) >> 24 <= 20) ||
((bits[x + (y + 1) * _gfx.Width] & 0xFF000000) >> 24 <= 20) ||
((bits[x + (y - 1) * _gfx.Width] & 0xFF000000) >> 24 <= 20))
_hull.Add(new Point(x, y));
}
}
}
Vi ignorerar alla pixlar som är genomskinliga (värde på alpha under 20), de kan inte vara kantpixlar.
Befinner vi oss på kanten i spriten så är det ju en kantpixel, eller hur?
En kant "inne i" spriten kollar vi genom att försökra oss om att den har minst en granne som är genomskinlig. Denna koll kan vi riskfritt göra då vi raden ovanför tar hand om kanten på spriten. Alltså igen risk för IndexOutOfRangeException.
Nu återstår bara att kalla på metoden FindHull i konstruktorn för SpaceShip.
public SpaceShip(Texture2D ship_normal, Texture2D ship_acc)
{
this._gfx = ship_normal;
this._gfx_acc = ship_acc;
FindHull();
}
Okej, det var mycket jobb utan att vi ännu kan se något resultat. Tyvärr dröjer det lite till.
Rotera kantpixlarna
Teori
Varför sparar vi _hull? Kan vi inte bara använda _hullTransformed?
Det kommer alltid att bli avrundningfel vid rotationer. Om vi hela tiden roterade redan roterade pixlar så kommer avrundningfelen att byggas på och till slut blir det stora fel. Därför beräknar vi hela tiden från "original"-kantpixlarna.
Att rotera en vektor (x, y) med vinkel v i 2D följer formen:
- x_ny = x * cos(v) - y * sin(v)
- y_ny = y * cos(v) + x * sin(v)
Testa gärna formeln på rutat papper genom att rita ett koordinatsystem och en vektor från origo. Beräkna sedan en rotation på t.ex. 45 grader eller 90 grader och se var den nya vektorn hamnar.
En trevlig sak med formeln för rotation är att det, för en given vinkel, är samma cos(v) och sin(v) i beräkningen för alla pixlar.
Praktiken
Vi skapar en ny metod, UpdateHull i SpaceShip.cs
private void UpdateHull()
{
//Initiera med beräknad längd för ökad prestanda
_hullTransformed = new Dictionary<Point, bool>(_hull.Count);
//Beräkna rotationen
float cos = (float)Math.Cos(_rotation);
float sin = (float)Math.Sin(_rotation);
//Center för skeppet
int width =_gfx.Width / 2;
int height = _gfx.Height / 2;
foreach (Point p in _hull)
{
//Beräkna nytt x o y kring centrum
int newX = (int)((p.X - width) * cos - (p.Y - height) * sin);
int newY = (int)((p.Y - height) * cos + (p.X - width) * sin);
Point newP = new Point(newX, newY);
//Punkten kan redan finnas p.g.a avrundning
if (!_hullTransformed.ContainsKey(newP))
_hullTransformed.Add(newP, true);
}
_recalcHull = false;
}
Nu när vi kan rotera kantpixlarna så ska vi se till att det sker också. Vi ändrar i Update i SpaceShip.cs till:
public void Update(GameTime gameTime)
{
Rotation += _turnRate;
_position += _speed;
if (_recalcHull)
UpdateHull();
}
Observera att vi ändrar till Rotation för uppdatering av skeppets rotation. På så sätt vet vi om vi behöver beräkna om kantpixlarna längre ned i koden.
Okej, fortfarande inga synliga förändringar... lugn det kommer
Kollisionshantering
Teori för detektering
Eftersom vi nu har de roterade kantpixlarna färdiga så behöver vi gå igenom dem alla varje frame, lägga till skeppets position för att få en pixelkoordinat i banan. Ryms pixeln i banan (vi kan flyga utanför) så kollar vi helt enkelt vilken färg den överlappande pixeln har. Sen tidigare har vi sagt att svart (0xFF000000), grön (0xFF00FF00) och blå (0xFF0000FF) ska var de färger som vi kan kollidera mot.
Detta är den enkla biten.. det svåra är vad ska vi göra när vi kolliderar?
Teori för kollisionshantering
Detta inkluderar ändring av hastighet för skeppet, position samt även rotation beroende på hur vi kolliderar.
Vi börjar med att försöka förklara hur rotationen beräknas vid en kollision. Fundera på följande scenario.
Punkten för kollision samt centrum för skeppet kan användas för att beräkna en hävstång kring centrum. Ju närmre centrum vi kolliderar desto mindre hävstång kommer vi att få.
Vi tänker oss vidare att vi har en riktning på hastigheten när vi kolliderar. Beroende på dess riktning kommer vi att få medurs eller moturs rotation eller kanske t.o.m ingen rotation alls.
Inom linjär algerbra kan vi lösa detta genom en skalärprodukt mellan den roterade hävstångsvektorn och hastighetsvektor. En skalärprodukt är som störst när vektorerna är parallella. Är de däremot vinkelräta mot varandra så blir resultatet 0. Resultatet blir även negativ om den ena vektorn pekar mer än 90 grader från den andra vektorns riktning.
Om du verkligen vill förstå detta så rekommenderas att du använder rutade blad och ritar vektorer och dess skalärprodukt. En skalärprodukt mellan 2D-vektorerna a och b beräknas som a.X * b.X + a.Y * b.Y. Att förstå innebörden kan ta lite tid.
Sist men inte minst ska vi kolla på själva kollisionen mellan kantpixel och bakgrund. I bilden nedan syns skeppet förstorat. Vår fysiska modell bygger på cirklar. Den svarta cirkeln representerar skeppets tänkta sfär i det ögonblick det sker en kollision (denna kommer attt variera beroende på var på skeppet vi kolliderar). Den röda cirkel är en uppförstoring för att visa att den kolliderande punkten på bakgrunden också behandlas som en cirkel.
Tänk dig att du studsar en boll på en annan. Exakt så kommer kollisionen att fungera. Pilarna med de olika färgerna symboliserar krafter och beräkningar som kommer att göras i koden längre fram. Den viktigaste kraften är skeppets hastighet före kollisionen (grön) och dess hastighet efter kollisionen (röd). Trixandet med vektorerna handlar bara om att räkna fram den nya hastigheten. Skalärprodukten som vi har nämt tidigare kan även ses som en definition på resulterande arbete mellan två krafter.
Ett annat sätt att se på saken är att tänka sig ett plan mellan cirklarna och hur mycket av hastigheten som kan projiceras på planet och därmed beräkna "studsen" från planet. Nog om det matematiska, vi hade gärna länkat här till fler bra förklaringar av samma sak men tyvärr hittar vi inget pedagogiskt material...
Praktik
Vi går direkt på källkoden, vi ska nämligen skapa metoden CheckCollision i SpaceShip.cs och skapa variabeln _collision (bool).
public void CheckCollision(Texture2D level)
{
uint[] levelPixels = new uint[level.Width * level.Height];
level.GetData<uint>(levelPixels);
Dictionary<Point, bool>.Enumerator enumer = _hullTransformed.GetEnumerator();
//Eftersom vi kommer att gå igenom alla pixlar som kolliderar
//så behöver extra temporära variabler för att kunna räkna ut
//ett medelvärde längre fram
int num_found = 0;
Vector2 delta_pos = new Vector2();
float delta_angle = 0;
while (enumer.MoveNext())
{
//Beräkna pixelpositon för kantpixeln
Point p = enumer.Current.Key;
int x = p.X + (int)Position.X;
int y = p.Y + (int)Position.Y;
//Pixlar utanför banan ignoreras
if (x < 0 || y < 0 || x >= level.Width || y >= level.Height)
continue;
//Endast svarta, gröna och blåa pixlar kan vi kollidera mot
if ((levelPixels[x + y * level.Width] == 0xFF000000) ||
(levelPixels[x + y * level.Width] == 0xFF00FF00) ||
(levelPixels[x + y * level.Width] == 0xFF0000FF))
{
//Vektor från centrum (hävstång)
Vector2 c = new Vector2(Position.X - x, Position.Y - y);
//Roterad vektor 90 grader moturs
Vector2 h = new Vector2(-c.Y, c.X);
//Beräkna rotation (skalad skalärprodukt)
float rot = (h.X * Speed.X + h.Y * Speed.Y) / 600.0f;
delta_angle += rot;
//Flytta tillbaka skeppet vid första tecken på kollision
//för att förhindra att skeppet fastar
if(num_found == 0)
Position -= Speed;
//Vektor som pekar mot centrum för skeppet
//se artikelbild för bättre förklaring
Vector2 D = new Vector2(x - (Position.X), y - (Position.Y));
D.Normalize();
Vector2 V = Speed;
float length = Vector2.Dot(D, V);
Vector2 pl = length * D;
Vector2 np = V - pl;
//Flytta isär lite extra i riktning från kollisionen
delta_pos -= V.Length() * D;
//Beräkna dämpning beroende på pixelfärg
float dampening = 0.8f;
if ((levelPixels[x + y * level.Width] == 0xFF00FF00) ||
(levelPixels[x + y * level.Width] == 0xFF0000FF))
dampening = 0.4f;
//Ny hastighet
Speed = (-pl + np) * dampening;
num_found++;
}
}
_collision = num_found > 0;
//Beräkna medelvärdet för positions/rotations ändring samt rotationshastighet
//om vi har kolliderar
if (num_found > 0)
{
Position += delta_pos / num_found;
Rotation += delta_angle/ num_found;
TurnRate = delta_angle / num_found;
}
}
Vi kopierar ut data från bakgrundsbilden som vi sedan använder för att testa mot våra roterade kantpixlar (rad 26). Pixlar utanför banan ignoreras, vilket betyder att vi kan åka utanför om vi vill.
För att det ska bli en kollision måste vi träffa en helt svart, grön eller blå pixel. Vi har några variabler kallade delta_ som ska hjälpa oss att beräkna position och rotation efter kollisionen. Detta behövs då vi kan hamna i lägen att mer än en kantpixel på skeppet kolliderar samtidigt med banan. Att då bara göra beräkningar på en pixel kan bli lite konstigt. Därför går loop'en genom alla skeppets kantpixlar.
Skulle vi kolliderar så följer en rotationsberäkning för att eventuellt sätta skeppet i spinn, som vi diskuterat tidigare. Sedan flyttar vi tillbaka skeppet i den riktning vi kom ifrån för att flytta isär på skeppet och bakgrunden. Något som vi bara gör en gång, kontrollerat av num_found som håller kolla på antalet kolliderande kantpixlar. Nu följer sedan beräkningen för att få fram en ny hastighet efter kollisionen. Denna beräkning illustreras i bilden ovan.
Modellen och fysiken är inte perfekt så vi försöker få skeppet att "fastna" på kanterna så lite som möjligt genom att flytta skeppet lite extra (rad 52). Problemet med modellen är egentligen att varken skeppet eller banan kan ses som kolliderande cirklar.
För att göra det lättare att landa så inför vi en annan dämpning på landningsplatserna (0.4) istället för standard 0.8 mot banan.
Nu behöver vi även kalla på kollisionsberäkningen från Game1.cs. Vi tar med några dubletter av kodrader så du kan se ungefär var ändringen ska in.
ship.Accelerating = ks.IsKeyDown(Keys.W);
//Låt skeppet uppdatera sig
ship.Update(gameTime);
//Kolla kollision
ship.CheckCollision(level);
Allra sist ska vi även göra en liten ändring i SpaceShip.cs. Vi vill förhindra att spelaren kan rotera skeppet när det befinner sig i en kollision. Vi ändrar i Update.
public void Update(GameTime gameTime)
{
if(!_collision)
Rotation += _turnRate;
_position += _speed;
if (_recalcHull)
UpdateHull();
}
Avslutning
Nu är det äntligen dags att testa! Fick du inte ihop det så kolla källkoden längre ned.
I nästa del ska vi färdigställa allt med ljudeffekter, mätare, byte av banor etc etc. Tills dess, ha det bra!