Inledning

A*, eller A-stjärna, är en algoritm för att hitta bästa vägen. Som många vet så är ju bästa vägen på en karta den så kallade fågelvägen från punkt A till punkt B. Problemet är att det kan finnas hinder mellan punkt A och B. Det kan också vara som så att det finns terräng som tar längre tid att korsa än annan terräng, t.ex. borde det vara skillnad på asfalterad väg och träskmarker.

För att hitta en optimal väg, oavsett om det är för fiender eller spelare, så måste vi komma fram till något bättre än endast fågelvägen. Vi kommer i denna artikel att gå igenom A* och förklara hur algoritmen fungerar

I bilden ovan så har vi en karta med hinder. Vi ska gå från punkt A (grön) till punkt B (röd). Den snabbaste och enkla vägen (röd linje) går ej att gå. Vi måste hitta en framkomlig väg till målet (grön linje).

Karta och data

För att beräkna en bästa väg så måste det finnas en karta. I ett enkelt scenario så har vi en 2D-karta uppbyggd av så kallade "tiles" (plattor). Plattorna kan antingen vara väg eller vägg, dvs. antingen kan vi gå på dem eller inte.

För att beräkna bästa vägen behöver vi en datarepresentation av något som vi kallar "nod" så vi skapar en klass Node för detta. En nod är en koordinat tagen från vår karta fast med lite mer information. Vi kikar på klassen.

namespace AStarLogic
{
    public class Node
    {
        public readonly int X;
        public readonly int Y;

        public int G { get; set; }
        public int H { get; set; }
        public int F { get; set; }
        public int Sx { get; set; }
        public int Sy { get; set; }
        public MapType Type { get; set; }
        public bool IsVisited { get; set; }
        public int Time { get; set; }

        public Node(int x, int y, int sx, int sy, int g, int h) 
        {
            X = x;
            Y = y;
            Sx = sx;
            Sy = sy;
            G = g;
            H = h;
            F = g + h;
        }
    }
}

Det är främst datan vi ska förstå i denna klass. X, Y är koordinaten på kartan för noden. G, H, F är beräknad data som beräknas i A* algoritmen. G är kostnaden att komma till denna nod, dvs. hur lång tid har det tagit att komma hit.

Vad kostar det då att gå från ett enda steg?

Det beror på vilken modell vi använder. Vi tänker oss att en förflyttning i vertikal eller horisontell led kostar 10 poäng. Diagonal förflyttning kostar 14p. Anledningen till detta är att du helt enkelt rör dig längre med ett steg diagonalt då du både rör dig 1 steg i sidled och 1 steg vertikalt. Talet 14 kommer från beräkning av diagonalen med Pythagoras sats, 10*10 + 10*10 = 200. Roten ur 200 = roten ur 2 * 10. Alltså en faktor roten ur 2 längre vilket vi avrundar till 1.4.

Här kan vi då göra modellen av kartan lite mer avancerad och låta kostnaden för förflyttning bero på underlaget. I vårt exempel gör vi inte detta utan låter all förflyttning i grunden kosta lika mycket men ändå kompensera för diagonal förflyttning.

H är ett så kallat heuristiskt värde. Ett finare ord för ett uppskattat värde som kan se som en tumregel men är likväl ett ofullständigt värde. Den uppskattning vi beräknar H till är avståndet vi har kvar till målet. Här använder vi inte fågelvägen som beräkning utan använder något som kallas för Manhattangeometri. Med "Manhattanavståndet" så beräknar vi avståndet utan att tillåta diagonal förflyttning. Enkelt sett kan vi se det som antal förflyttningar i sidled + antalet vertikala förflyttningar summerat. Därefter multiplicerat med 10.

	private int Distance(int x1, int y1, int x2, int y2)
	{
		//Beräknar så kallade Manhattan-avståndet
		var x = Math.Abs(x1 - x2);
		var y = Math.Abs(y1 - y2);
		return (x + y) * 10;
	}

Vilket heuristik vi använder kommer att påverka hur A* presterar. Vi har valt att använda Manhattangeometri, dels för att det är en vanlig implementation men också för att man slipper en massa kostsamma beräkningar.

F är helt enkelt G + H och används för att avgöra vilken nod som hittills verkar bäst. Valet av variabelnamn kan tyckas dåliga. Faktum är att algoritmen i sitt ursprung har betecknat dessa data som G, H, F och det har blivit kotym.

Sx, Sy talar om från vilken annan position på kartan man kom ifrån för att hamna här. Kostnaden, G, beräknas alltså som G från "föregående" nod plus förflyttningen hit. Som vi tidigare diskuterade så beror kostnaden på om det var en diagonal förflyttning eller ej. Koden nedan reder ut problemet.

	private int MoveCost(int x1, int y1, int x2, int y2)
	{
		var dx = Math.Abs(x1 - x2);
		var dy = Math.Abs(y1 - y2);
		if ((dx + dy) == 2)
			return 14;
		if ((dx + dy) == 1)
			return 10;
		return 0;
	}

Resterande variabler, MapType, IsVisited, Time, används inte av A* egentligen. Vi använder dessa till som hjälp för att visualisera beräkningarna och den väg som ska visas.

Hjärtat i A*

Vi vill hitta en väg från punkt A (x1, y1) till punkt B (x2, y2).

I förväg har vi översatt kart-data till en struktur med noder som vi kallar MapData.

Algoritmen jobbar med två listor: En för "öppna" noder och en för "stängda" noder.

Den öppna listan är noder som måste undersökas innan vi med säkerhet kan säga att vi hittat den bästa vägen. Den stängda listan är noder som vi beräkningsmässigt är klara med och som vi inte vill återvända till igen.

Vi börjar med att lägga till en enda nod i listan för de öppna noderna. Denna nod är startpunkten (x1, y1). Kostnaden att komma hit är 0 och avståndet till målet är Manhattanavståndet. Vi håller också reda på om vi har nått målet eller ej med variabeln finished.

Algoritmen börjar med en loop som formuleras; "så länge vi inte är klara och vi har noder kvar att undersöka".

Vi tar sedan den bästa noden i listan över öppna noder och undersöker alla nodens nod-grannar om:

• Grannen ligger inom kartan, dvs. är en del av kartan.
• Grannen INTE är en vägg, dvs. vi måste kunna gå till noden.

Nod-grannarna undersöks sedan:

1) Om de redan finns i listan över stängda noder. Om så är fallet så uppdaterar vi den stängda noden om det visar sig att vi kunde nå den stängda noden snabbare via den "bästa" noden vi just nu undersöker.

2) Om de inte finns i den öppna listan så beräknar vi G, H och stoppar in dem i den öppna listan.

När alla nod-grannar har undersökt så läggs den hittills bästa noden i listan över stängda noder. Om den bästa noden var målet så är vi nu klara. Därefter tar vi bort den hittills bästa noden från den öppna listan.

Vi hoppas att detta låter begripligt och presenterar nu koden för algoritmen.

	private void MoveFromTo(int x1, int y1, int x2, int y2)
	{
		//Lägg till startpunkten i listan 
		_openNodes.Add(new Node(x1, y1, x1, y1, 0, Distance(x1, y1, x2, y2)));
		var finished = false;
		int time = 0;

		while (!finished && _openNodes.Count > 0)
		{
			var bestNode =  _openNodes.Aggregate((minNode, nextNode) => 
					minNode.F > nextNode.F ? nextNode : minNode);
			var sx = bestNode.X;
			var sy = bestNode.Y;

			//Lägg till punkter runt om och kollar så att de ligger inom kartans gränser
			for (var y = bestNode.Y - 1; y <= sy + 1 && y >= 0 && y < SizeY; y++)
			{
				for (var x = bestNode.X - 1; x <= sx + 1 && x >= 0 && x < SizeX; x++)
				{
					//Strunta i väggar
					if (MapData[y, x].Type == MapType.Wall)
						continue;

					//Finns noden redan i den bearbetade listan?
					var closedNode = _closeNodes.FirstOrDefault(n => n.X == x && n.Y == y);
					if (closedNode != null)
					{
						//Om noden finns och vi kunde ta oss hit till "bestNode" 
						//snabbare så uppdaterar vi besNode
						int tmpG = closedNode.G + MoveCost(sx, sy, x, y);
						if (tmpG < bestNode.G)
						{
							bestNode.Sx = closedNode.X;
							bestNode.Sy = closedNode.Y;
							bestNode.G = tmpG;
							bestNode.F = bestNode.G + bestNode.H;
						}
					}
					else if (!_openNodes.Any(n => n.X == x && n.Y == y))
					{
						//Om noden inte finns varken i open- eller closelistan så lägger vi 
						//till den med uppdaterad info
						MapData[y, x] = new Node(x, y, sx, sy, bestNode.G + MoveCost(x, y, sx, sy),
							Distance(x, y, x2, y2)) {IsVisited = true, Time = time++};
						_openNodes.Add(MapData[y, x]);
								
					}
				}
			}

			//Flytta över punkten till den stängda listan
			_closeNodes.Add(bestNode);

			//Var detta målet?
			if (bestNode.H == 0)
				finished = true;

			//Ta bort den från den öppna listan
			_openNodes.Remove(bestNode);
		}
	}

På rad 10 använder vi Aggregate som en tjusig LINQ-metod för att hitta den bästa noden utan att sortera om listan. Ordningen för noderna är mycket viktig för att algoritmen ska fungera. Förklaringen till detta är tyvärr mycket avancerad, läs mer i avslutningen.

Ok men var är bästa vägen?

När algoritmen är klar så finns det ett spår utlagt i listan över stängda noder. Den sista noden i listan är där vi hamnade. Förhoppningsvis hittade vi till målet men det är inte alls säkert. Vi kan ha varit instängda på kartan! Vägen som vi tagit till målet måste vi nu spåra tillbaka via noderna i den stängda listan. Vi plockar egentligen inte ut bästa vägen i vårt exempel men metoden PlotRoute markerar den i datan.

	public void PlotRoute()
	{
		if (_startX == -1 || _startY == -1 || _goalX == -1 || _goalY == -1)
			return;

		var node = _closeNodes.Last();

		while (node.G != 0)
		{
			//Hitta föregående nod
			for (var i = 0; i < _closeNodes.Count; i++)
			{
				if (_closeNodes[i].X == node.Sx && _closeNodes[i].Y == node.Sy)
				{
					node = _closeNodes[i];
					break;
				}
			}
			if (node.G != 0)
				MapData[node.Y, node.X].Type = MapType.Route;
		}

		MapData[_startY, _startX].Type = MapType.Start;
		MapData[_goalY, _goalX].Type = MapType.Stop;
	}

Implementationen

Vi har valt att göra implementationen i 3 olika projekt. Ett klassbibliotek kallat AStarLogic som vi sedan använder oss av både i ett Console Application och ett Windows Game (XNA) projekt.

Alltså koden som du kan ladda hem går att köra på två olika sätt.

I XNA kan du bygga om kartan med vänster och höger musknapp genom att sätta eller ta bort väggar. Start sätts ut med knappen Q och målet med knappen E. Tryck sedan ENTER för att illustrera beräkningarna. Se videon nedan.

Kör du Console-varianten så blir det lite mer sparsamt men ändå en presentation.

Avslutning

Vill man fördjupa sig i olika bästa-vägen-algoritmer eller underöka hur A* prestera i olika varianter så rekommenderar vi fortsatt läsning från Stanford University om A*.

Komplexiteten för att beräkna bästa vägen är rätt hög. Du vill alltså inte göra detta för ofta med allt för stora kartor. Det finns en uppsjö av varianter på A* som förbättrar prestandan under olika speciella förutsättningar. Du kanske också måste beräkna om bästa vägen ibland då saker och ting rör sig på kartan. Det finns också en uppsjö av olika strategier för att beräkna om bästa vägen då vi har rörelse på kartan.

Tänk på att denna implementation som vi erbjuder är gjord delvis för att kunna presentera och illustrera beräkningarna grafiskt. En del saker i implementationen har alltså inte så mycket med just algoritmen att göra. Vi har ändå försökt hålla koden avskalad och begriplig.