Advertisement

A* Code in C#

Started by March 29, 2005 04:10 AM
6 comments, last by Zodiak 19 years, 8 months ago
Hello! Could anybody please post a link or just give me C# code for the A* algorithm? I'd really appreciate that. Thanks!
I'd definetly say that a glass is half-empty!
It should be almost identical to the C++ code. Check the Articles area and search for A* Pathfinding, you'll find tons of examples.
Advertisement

Hi,

I created a simple A* explorer in C# not too long ago. I created a class 'Area', which contained all kinds of 'Node' s.


These are the most important parts of the algorithm:

public void solveWithAStar() 	{		if (start.X == -1 || end.X == -1) return;		clearNodes();		getPath();			}	private void getPath() 	{				Point currentPoint = new Point();		Point newPoint = new Point();		int lowestIndex = 0;		int lowestValue = 0;		int val;		bool done = false;		openList.Clear();		closedList.Clear();		openList.Add(start);		while (!done) 		{			// get smallest F-value here			lowestIndex = 0;			currentPoint = (Point)openList[lowestIndex];			lowestValue = areaNode[currentPoint.X, currentPoint.Y].f;			for (int i = 0; i < openList.Count - 1; i++) 			{					currentPoint = (Point)openList;				val = areaNode[currentPoint.X, currentPoint.Y].f;				if (val < lowestValue) 				{					lowestIndex = i;					lowestValue = val;				}			}						currentPoint = (Point)openList[lowestIndex];			openList.Remove(currentPoint);			closedList.Add(currentPoint);					// checking and adding new points to move to			// adding LEFT adjacent square			newPoint.X = currentPoint.X - 1;			newPoint.Y = currentPoint.Y;				if (checkNode(newPoint, currentPoint)) processNode(currentPoint, newPoint);					// adding RIGHT adjacent square			newPoint.X = currentPoint.X + 1;			newPoint.Y = currentPoint.Y;			if (checkNode(newPoint, currentPoint)) processNode(currentPoint, newPoint);			// adding UP adjacent square			newPoint.X = currentPoint.X;			newPoint.Y = currentPoint.Y + 1;			if (checkNode(newPoint, currentPoint)) processNode(currentPoint, newPoint);			// adding DOWN adjacent square			newPoint.X = currentPoint.X;			newPoint.Y = currentPoint.Y - 1;			if (checkNode(newPoint, currentPoint)) processNode(currentPoint, newPoint);			// adding DOWN-LEFT adjacent square			newPoint.X = currentPoint.X - 1;			newPoint.Y = currentPoint.Y - 1;			if (checkNode(newPoint, currentPoint)) processNode(currentPoint, newPoint);					// adding DOWN-RIGHT adjacent square			newPoint.X = currentPoint.X + 1;			newPoint.Y = currentPoint.Y - 1;			if (checkNode(newPoint, currentPoint)) processNode(currentPoint, newPoint);					// adding UP-LEFT adjacent square			newPoint.X = currentPoint.X - 1;			newPoint.Y = currentPoint.Y + 1;			if (checkNode(newPoint, currentPoint)) processNode(currentPoint, newPoint);					// adding UP-RIGHT adjacent square			newPoint.X = currentPoint.X + 1;			newPoint.Y = currentPoint.Y + 1;			if (checkNode(newPoint, currentPoint)) processNode(currentPoint, newPoint);			if (openList.Count == 0) done = true;			if (openList.Contains(end)) done = true;		}		if (openList.Count == 0) return;				// path has been found		currentPoint = areaNode[end.X, end.Y].parent;		while (currentPoint != start) 		{			areaNode[currentPoint.X, currentPoint.Y].isPath = true;			currentPoint = areaNode[currentPoint.X, currentPoint.Y].parent;		}					}	private bool checkNode(Point p, Point oldPoint) 	{				// is this node walkable?		if (p.X < 0) return false;		if (p.Y < 0) return false;		if (p.X > (areaSize - 1)) return false;		if (p.Y > (areaSize - 1)) return false;				if (areaNode[p.X, p.Y].type			== Node.nodeType.ntWall) return false;		if (areaNode[oldPoint.X, p.Y].type	== Node.nodeType.ntWall) return false;		if (areaNode[p.X, oldPoint.Y].type	== Node.nodeType.ntWall) return false;				// is this square already in closed list?		if (closedList.Contains(p)) return false;		// node is valid		return true;	}	private void processNode(Point currentp, Point newp) 	{		// this is a valid node to move to,		int gScore, hScore;				// distance to get to the new point		int distance = Math.Abs(currentp.X - newp.X) + 					   Math.Abs(currentp.Y - newp.Y);				if (distance == 2)		// this is a diagonal move			distance = diagonalMove;		else					// this is a straight move			distance = straightMove;		gScore = areaNode[currentp.X, currentp.Y].g + distance;		hScore = Math.Abs(end.X - newp.X) * straightMove +				 Math.Abs(end.Y - newp.Y) * straightMove;				// check if this node is already on the open list		if (openList.Contains(newp)) 		{			if (gScore < areaNode[newp.X, newp.Y].g) 			{				areaNode[newp.X, newp.Y].parent = currentp;				areaNode[newp.X, newp.Y].g = gScore;				areaNode[newp.X, newp.Y].calculateF();			}			return;		}		// estimate for distance to end		// set parent and calculate cost		areaNode[newp.X, newp.Y].parent = currentp;		areaNode[newp.X, newp.Y].g = gScore;		areaNode[newp.X, newp.Y].h = hScore;					// here we calculate F = G + H		areaNode[newp.X, newp.Y].calculateF();			// finally add the new point to the open list		openList.Add(newp);		}


Hope this helps a bit,

Edo
Edo
Oh, this is great! Thanks a lot!
I'd definetly say that a glass is half-empty!
Quote: Original post by wyrd
It should be almost identical to the C++ code. Check the Articles area and search for A* Pathfinding, you'll find tons of examples.


Yes, but then he'd actually have to *finish* his homehork himself. Oh the horror!
Could someone please post the code for an MMORPG? Please make sure it's original and puts Doom3 graphics to shame. Appreciate it.
Advertisement
try here
http://www.thecodeproject.com/csharp/

there are some A* examples here in C#
Ok, thanks you all guys! Thanks a lot! Really, I mean it :) This is the bestest :) forum ever!
I'd definetly say that a glass is half-empty!

This topic is closed to new replies.

Advertisement