Sign in to follow this  
Zodiak

A* Code in C#

Recommended Posts


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[i];
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this