C#: A* i C#

Velena · 6. november 2008

Har en skoleoppgave gående, hvor jeg skal implementere A* i C#. Har brukt denne artikkelen som utgangspunkt for koden:A*. Er litt usikker på om jeg har gjort dette riktig, og vil gjerne at noen ser over den før jeg leverer den.

using System;
using System.Drawing;
using System.Collections.Generic;
using System.Text;

namespace AStar2
{
class AMethod
{
 /// <summary>
 /// Returns the shortest path between two squares in a given grid, if a valid one exists. Otherwise returns null.
 /// </summary>
 /// <param name="startPos">The starting position from which to search</param>
 /// <param name="endPos">The goal of the search</param>
 /// <param name="grid">The network which contains startPos and endPos</param>
 /// <param name="unwalkables">Rectangle array containing the squares which cannot be used in the path</param>
 /// <param name="rootOfA">Value representing the height/width of each square</param>
 /// <param name="gridFactorX">The number of squares in the grid on the X-axis</param>
 /// <param name="gridFactorY">The number of squares in the grid on the Y-axis</param>
 /// <param name="straightCost">One of two values indicating how to prioritze between straight and diagonal movement</param>
 /// <param name="diagonalCost">One of two values indicating how to prioritze between straight and diagonal movement</param>
 /// <param name="SpecialCostRects">Rectangle array containing all squares that should have a diffrent priority from the norm</param>
 /// <param name="specialCost">Int array indicating how to prioritze the special squares</param>

	public static List<Rectangle> ShortestPath (Rectangle startPos, Rectangle endPos, List<Rectangle> grid, List<Rectangle> unwalkables,int rootOfA, int gridFactorX,int gridFactorY,int straightCost,int diagonalCost,List<Rectangle>SpecialCostRects,int[] specialCost)
	{
		// Declarations
		bool onClosedList = false;

		int[] gScore = new int[1000];
		int[] hScore = new int[1000];
		int[] fScore = new int[1000];
		int currCost = 0;

		Rectangle currSquare = startPos;
		Rectangle adjSquare = new Rectangle();

		List<Rectangle> openList = new List<Rectangle>();
		List<Rectangle> closedList = new List<Rectangle>();
		List<Rectangle> parents = new List<Rectangle>();

		List<Rectangle> pathSquares = new List<Rectangle>();

		// iinitialisèr openList, f,g,og hScore, med startPos sine verdier
		openList.Add(startPos);
		fScore[grid.IndexOf(startPos)] = 0;
		gScore[grid.IndexOf(startPos)] = 0;
		hScore[grid.IndexOf(startPos)] = 0;

		while (openList.Count != 0 && !onClosedList)// While løkke som vil fortsette til den finner en sti, eller til det ikke finnes flere alternativ
		{
			foreach (Rectangle square in openList)
			{
				if (fScore[grid.IndexOf(square)] < fScore[grid.IndexOf(currSquare)])
					currSquare = square;
			}

			// Legg currSquare over i closedList
			openList.Remove(currSquare);
			closedList.Add(currSquare);

			for (int i = 0; i < 8; i++)// For løkke som ser etter alternativ, og legger dem i openList
			{
				switch (i)
				{
					case 0:
						adjSquare = grid[grid.IndexOf(currSquare) - 1];					//N
						currCost = straightCost;
						if (SpecialCostRects.Contains(adjSquare))
							currCost += specialCost[SpecialCostRects.IndexOf(adjSquare)];
						break;
					case 1:
						adjSquare = grid[grid.IndexOf(currSquare) + 1];					//S
						currCost = straightCost;
						if (SpecialCostRects.Contains(adjSquare))
							currCost += specialCost[SpecialCostRects.IndexOf(adjSquare)];
						break;
					case 2:
						adjSquare = grid[grid.IndexOf(currSquare) + gridFactorY];		  //E
						currCost = straightCost;
						if (SpecialCostRects.Contains(adjSquare))
							currCost += specialCost[SpecialCostRects.IndexOf(adjSquare)];
						break;
					case 3:
						adjSquare = grid[grid.IndexOf(currSquare) - gridFactorY];		  //W
						currCost = straightCost;
						if (SpecialCostRects.Contains(adjSquare))
							currCost += specialCost[SpecialCostRects.IndexOf(adjSquare)];
						break;
					case 4:
						adjSquare = grid[grid.IndexOf(currSquare) + gridFactorY + 1];	 //SE
						currCost = diagonalCost;
						if (SpecialCostRects.Contains(adjSquare))
							currCost += specialCost[SpecialCostRects.IndexOf(adjSquare)];
						break;
					case 5:
						adjSquare = grid[grid.IndexOf(currSquare) - gridFactorY + 1];	 //SW
						currCost = diagonalCost;
						if (SpecialCostRects.Contains(adjSquare))
							currCost += specialCost[SpecialCostRects.IndexOf(adjSquare)];
						break;
					case 6:
						adjSquare = grid[grid.IndexOf(currSquare) + gridFactorY - 1];	 //NE
						currCost = diagonalCost;
						if (SpecialCostRects.Contains(adjSquare))
							currCost += specialCost[SpecialCostRects.IndexOf(adjSquare)];
						break;
					case 7:
						adjSquare = grid[grid.IndexOf(currSquare) - gridFactorY - 1];	 //NW
						currCost = diagonalCost;
						if (SpecialCostRects.Contains(adjSquare))
							currCost += specialCost[SpecialCostRects.IndexOf(adjSquare)];
						break;
				}

				if (!unwalkables.Contains(adjSquare) && !closedList.Contains(adjSquare))
				{

					if (!openList.Contains(adjSquare))
					{
						openList.Add(adjSquare);
						parents[grid.IndexOf(adjSquare)] = currSquare;

						// Calculate f g og h value
						if (adjSquare.X > endPos.X)// h value calculation start 
						{
							if (adjSquare.Y > endPos.Y)
								hScore[grid.IndexOf(adjSquare)] = ((adjSquare.Y - endPos.Y) /rootOfA) + ((adjSquare.X - endPos.X) / rootOfA);
							else
								hScore[grid.IndexOf(adjSquare)] = ((endPos.Y - currSquare.Y) / rootOfA) + ((adjSquare.X - endPos.X) / rootOfA);
						}
						else
						{
							if (currSquare.Y > endPos.Y)
								hScore[grid.IndexOf(adjSquare)] = ((currSquare.Y - endPos.Y) / rootOfA) + ((-endPos.X - currSquare.X) / rootOfA);
							else
								hScore[grid.IndexOf(adjSquare)] = ((endPos.Y - currSquare.Y) / rootOfA) + ((endPos.X - currSquare.X) / rootOfA);
						}// h value calculation end

						gScore[grid.IndexOf(adjSquare)] = gScore[grid.IndexOf(currSquare)] + currCost;// g value calculation
						fScore[grid.IndexOf(adjSquare)] = gScore[grid.IndexOf(adjSquare)] + hScore[grid.IndexOf(adjSquare)];//f value calculation
					}
					else// Hvis kvadratet allerede finnes i openList
					{
						if (gScore[grid.IndexOf(adjSquare)] < gScore[grid.IndexOf(currSquare)])// Hvis kvadratet er et bedre alternativ enn currSquare
						{//[b]Er spesiellt usikker på dette, virker rett i forhold til beskrivelsen i artikkelen, men ikke ifølge mitt hode.[/b]
							parents[grid.IndexOf(adjSquare)] = currSquare;
							gScore[grid.IndexOf(adjSquare)] = gScore[grid.IndexOf(parents[grid.IndexOf(currSquare)])]+currCost;
							fScore[grid.IndexOf(currSquare)] = gScore[grid.IndexOf(currSquare)] + hScore[grid.IndexOf(currSquare)];
						}
					}
				}
			}
			if (closedList.Contains(endPos))
				onClosedList = true;
		}
		if (onClosedList)// Fant et alternativ
		{
		  currSquare = endPos;
		  while(!pathSquares.Contains(startPos))// while løkke som reverserer stien og legger den i pathSquares
		  {
			pathSquares.Add(grid.IndexOf(currSquare)); 
			currSquare = parents[grid.IndexOf(currSquare)];
		  }  return pathSquares;
		}
		else
			return null;// Ingen sti funnet, funksjonen returnerer null.
	}
}
}

Koden er ment å gi samme resultat som den forfatteren til artikkelen bruker, hvis den ikke gjør dette, vil jeg gjerne vite hva som er galt.Btw, prøvde å utheve en kommentar som jeg synes var vesentlig, men dette gikk ikke. Går det ann å bruke fet skrift i kodebokser? Takk på forhånd =).

Endret 7. november 2008 av Velena

Manfred · 6. november 2008

Hva er egentlig spørsmålet?

Velena · 7. november 2008

Ville bare vite om jeg hadde gjort det riktig. Driver og tester det selv nå, og har støtt på et aldri så lite problem:

List<Rectangle> someArray = new List<Rectangle>();
Rectangle someRect = new Rectangle(80,80,20,20);
someArray[10] = someRect;

Koden over ser ikke ut til å fungere, må jeg legge til en verdi for alle indexene opp til 10 for at jeg skal kunne legge en verdi i den indexen?

Edit: Har prøvd å omgå problemet ved å legge null verdier i alle indexene før jeg setter de riktige verdiene:

// count er antall kvadrater lagret i grid
public static void assign(int[] someInt, int count)
	{
		for (int i = 0; i < count; i++)
		{
			someInt[i] = 0;
		}
	}
// Har en slik for List<Rectangle> også

Men koden gir fremdeles et indexOutOfRange unntak, denne gang ved int arrayen.

Endret 7. november 2008 av Velena

GeirGrusom · 7. november 2008

Jeg lurer litt på hvor hodet ditt var når du laget den for/switch løkka :hmm:

Manfred · 7. november 2008

Jeg lurer litt på hvor hodet ditt var når du laget den for/switch løkka

Haha, det var en interessant, og utrolig unyttig del

Velena · 7. november 2008

Javel? Så det som en god nok måte å løse problemet >.>. Mener dere at jeg kunne gjort det enklere?

Edit: Fant noen slurvefeil i koden. Har rettet dem, så nå kjører den ihvertfall.Problemet nå er at det virker som koden er veldig ressurs krevende.

Edit 2: Var vist ikke det at den var ressurs-krevende, men at currSquare ikke oppdateres riktig, noe som resulterer i en evig loop.

Endret 7. november 2008 av Velena

alfred97 · 7. november 2008

Javel? Så det som en god nok måte å løse problemet >.>. Mener dere at jeg kunne gjort det enklere?

Hvis du ser etter en gang til, så er jeg helt sikker på at du også ser hva vi syntes var så festlig med den for/switch-konstruksjonen din.

Manfred · 7. november 2008

Vi ønsker gjerne at du kan forklare den for-switch saken din Og hva i all verden som var tanken bak

Velena · 9. november 2008

Gjerne det manfred:

       public static List<Rectangle> ShortestPath (Rectangle startPos, Rectangle endPos,
List<Rectangle> grid, List<Rectangle> unwalkables,int rootOfA, int gridFactorX,int 
gridFactorY,int straightCost,int diagonalCost,List<Rectangle>SpecialCostRects,
int[] specialCost)
       {

           bool onClosedList = false;

           int[] gScore = new int[1600];
           int[] hScore = new int[1600];
           int[] fScore = new int[1600];
           int currCost = 0;

           Rectangle currSquare = startPos;
           Rectangle adjSquare = new Rectangle();

           List<Rectangle> openList = new List<Rectangle>();
           List<Rectangle> closedList = new List<Rectangle>();
           List<Rectangle> parents = new List<Rectangle>();

           List<Rectangle> pathSquares = new List<Rectangle>();


           openList.Add(startPos);



           assign(parents, grid.Count);
           assign(gScore, grid.Count);
           assign(hScore, grid.Count);
           assign(fScore, grid.Count);

           fScore[grid.IndexOf(startPos)] = 0;
           gScore[grid.IndexOf(startPos)] = 0;
           hScore[grid.IndexOf(startPos)] = 0;


           while (openList.Count != 0 && !onClosedList)
           {
               foreach (Rectangle square in openList)
               {
                   if (fScore[grid.IndexOf(square)] <= fScore[grid.IndexOf(currSquare)])
                       currSquare = square;

               }


               // Switch currSquare from openList to closedList
               openList.Remove(currSquare);
               closedList.Add(currSquare);

               for (int i = 0; i < 8; i++)
               {
                   switch (i)
                   {
                       case 0:
                           adjSquare = grid[grid.IndexOf(currSquare) - 1];                    
                           currCost = straightCost;
                           if (SpecialCostRects.Contains(adjSquare))
                               currCost += specialCost[specialCostRects.IndexOf(adjSquare)];
                           break;
                       case 1:
                           adjSquare = grid[grid.IndexOf(currSquare) + 1];                    
                           currCost = straightCost;
                           if (SpecialCostRects.Contains(adjSquare))
                               currCost += specialCost[specialCostRects.IndexOf(adjSquare)];
                           break;
                       case 2:
                           adjSquare = grid[grid.IndexOf(currSquare) + gridFactorY];          
                           currCost = straightCost;
                           if (SpecialCostRects.Contains(adjSquare))
                               currCost += specialCost[specialCostRects.IndexOf(adjSquare)];
                           break;
                       case 3:
                           adjSquare = grid[grid.IndexOf(currSquare) - gridFactorY];          
                           currCost = straightCost;
                           if (SpecialCostRects.Contains(adjSquare))
                               currCost += specialCost[specialCostRects.IndexOf(adjSquare)];
                           break;
                       case 4:
                           adjSquare = grid[grid.IndexOf(currSquare) + gridFactorY + 1];     
                           currCost = diagonalCost;
                           if (SpecialCostRects.Contains(adjSquare))
                               currCost += specialCost[specialCostRects.IndexOf(adjSquare)];
                           break;
                       case 5:
                           adjSquare = grid[grid.IndexOf(currSquare) - gridFactorY + 1];     
                           currCost = diagonalCost;
                           if (SpecialCostRects.Contains(adjSquare))
                               currCost += specialCost[specialCostRects.IndexOf(adjSquare)];
                           break;
                       case 6:
                           adjSquare = grid[grid.IndexOf(currSquare) + gridFactorY - 1];     
                           currCost = diagonalCost;
                           if (SpecialCostRects.Contains(adjSquare))
                               currCost += specialCost[specialCostRects.IndexOf(adjSquare)];
                           break;
                       case 7:
                           adjSquare = grid[grid.IndexOf(currSquare) - gridFactorY - 1];     
                           currCost = diagonalCost;
                           if (SpecialCostRects.Contains(adjSquare))
                               currCost += specialCost[specialCostRects.IndexOf(adjSquare)];
                           break;
                   }

                   if (!unwalkables.Contains(adjSquare) && !closedList.Contains(adjSquare))
                   {
                       if (!openList.Contains(adjSquare))
                       {

                           openList.Add(adjSquare);
                           parents[grid.IndexOf(adjSquare)] = currSquare;


                           if (adjSquare.X > endPos.X)
                           {
                               if (adjSquare.Y > endPos.Y)
                                   hScore[grid.IndexOf(adjSquare)] = (((adjSquare.Y - endPos.Y) /rootOfA) + ((adjSquare.X - endPos.X) / rootOfA))*straightCost;
                               else
                                   hScore[grid.IndexOf(adjSquare)] = (((endPos.Y - adjSquare.Y) / rootOfA) + ((adjSquare.X - endPos.X) / rootOfA))*straightCost;
                           }
                           else
                           {
                               if (adjSquare.Y > endPos.Y)
                                   hScore[grid.IndexOf(adjSquare)] = (((adjSquare.Y - endPos.Y) / rootOfA) + ((endPos.X - adjSquare.X) / rootOfA))*straightCost;
                               else
                                   hScore[grid.IndexOf(adjSquare)] = (((endPos.Y - adjSquare.Y) / rootOfA) + ((endPos.X - adjSquare.X) / rootOfA))*straightCost;
                           }

                           gScore[grid.IndexOf(adjSquare)] = gScore[grid.IndexOf(currSquare)] + currCost;
                           fScore[grid.IndexOf(adjSquare)] = gScore[grid.IndexOf(adjSquare)] + hScore[grid.IndexOf(adjSquare)];


                       }
                       else
                       {
                           if (gScore[grid.IndexOf(adjSquare)] < gScore[grid.IndexOf(currSquare)])
                           {
                               parents[grid.IndexOf(adjSquare)] = parents[grid.IndexOf(currSquare)];
                               gScore[grid.IndexOf(adjSquare)] = gScore[grid.IndexOf(parents[grid.IndexOf(adjSquare)])]+currCost;
                               fScore[grid.IndexOf(adjSquare)] = gScore[grid.IndexOf(adjSquare)] + hScore[grid.IndexOf(adjSquare)];
                           }
                       }

                   }
                   if (i == 7)
                   {
                       if (openList.Count != 0)
                           currSquare = openList[0];
                   }
               }
               if (closedList.Contains(endPos))
                   onClosedList = true;
           }
           if (onClosedList)
           {
             currSquare = endPos;
             while(!pathSquares.Contains(startPos))
             {
               pathSquares.Add(grid[grid.IndexOf(currSquare)]); 
               currSquare = parents[grid.IndexOf(currSquare)];
             }  return pathSquares;
           }
           else
               return null;
       }
       public static void assign(List<Rectangle> rect, int count)
       {
           for (int i = 0; i < count; i++)
           {
               rect.Add(new Rectangle(0, 0, 0, 0));
           }
       }
       public static void assign(int[] someInt, int count)
       {
           for (int i = 0; i < count; i++)
           {
               someInt[i] = 0;
           }
       }

=D. Forslag til forbedring er selvsagt fortsatt velkomne.

Edit: Hvorfor ble kodeboksene så enormt brede? Prøvde å justere dem ved å dele noen av linjene i to, men det ser ikke ut til å ha hjulpet =/.

Endret 9. november 2008 av Velena

Manfred · 9. november 2008

Men hvorfor kjører du en for-løkke med en switch inni?? Hvorfor kan du ikke bare kjøre en og en av det du har inni de casene uten å måtte ha en for-løkke rundt??

Velena · 9. november 2008

Og hvordan skulle jeg gjøre dette? Ser fortsatt ikke hva du mener jeg kunne gjort annerledes.

Manfred · 9. november 2008

I stedet for

for(int i = 0; i < 3; i++)
{
 switch(i)
 {
case 0:
	func1();
	break;
case 1:
	func2();
	break;
case 2:
	func3();
	break;
 }
}

Så kan du liksom gjøre

func1();
func2();
func3();

Der vil jeg liksom si at det første eksempelet virkelig er waste.

Edit: typo

Endret 9. november 2008 av Manfred

Velena · 9. november 2008

Jeg blir jo fortsatt nødt til å hardkode det som er inne i casene, så lengdemessig blir det jo det samme. Har en følelse av at du har gått glipp av det at adjSquare brukes lengre ned i koden før verdien settes på nytt.

Manfred · 9. november 2008

...men likevel...

Interessant kodebit da, jeg har aldri noen sinne sett noe lignende. haha.

GeirGrusom · 9. november 2008

Men over til oppgaven: hvorfor lager du et arrayy av rectangle? er det ikke mer fornuftig å bruke et todimensjonalt array her?

Velena · 11. november 2008

Hva sikter du til GeirGrusom? Mener du at jeg burde lage en flerdimensjonal rectangle array istedet for å deklarere flere endimensjonale?

GeirGrusom · 11. november 2008

Ja nemlig. Og det er unødvendig å definere de som rectangle, fordi dette vil bli massiv dobbeltlagring. Størrelsen er jo lik for alle celler og posisjonen kan enkelt regnes ut ifra posisjonen i arrayet.

C#: A* i C#

Anbefalte innlegg

Lenke til kommentar

Videoannonse

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Opprett en konto eller logg inn for å kommentere

Opprett konto

Logg inn

Hvem er aktive 0 medlemmer