Dark Bit Factory & Gravity

PROGRAMMING => C / C++ /C# => Topic started by: disruptr on December 23, 2011

Title: [C#] A* algorithm implementation question
Post by: disruptr on December 23, 2011

Hi guys! I'm a newbie who's trying to get to grips with C#.

 I'm hoping it's okay for me to ask this question of you folks. It might not be because it's for a little game in my case, rather than a demo, but I guess it's more generic/universal in its possible applications than that? I dunno. If it's not okay to ask here, I'll just have to shuffle off sheepishly, won't I? :)


To the question:

I want to write a pathfinder function that gets the shortest path on a grid of nodes, or "cells" in this case.

I tried following the pseudo-code for A* that I found on wikipedia, but something's lacking in my understanding of it, as it's not working. I don't know if I'm not supposed to use List<T> for the open and closed sets or what, but it's being wierd.

The "cells" are hexes, but I don't think that's relevant to the problem: my HexDistance function (which returns a value of 1 between each hex, ie 2 adjacent hexes have a hexdistance of 1, if there's one between them they have a hexdistance of 2 etc.) is working okay.

Um...how best to explain...

Well, my code for the pathfinder so far is this. I know it's ugly and confused and I suspect very inefficient, I'm a beginner :p

PathNode is a struct that holds a position, f_score, g_score and h_score, with the constructor asking for the position.

Code: [Select]

               private void CalculatePath(Cell first, Cell goal)
        {

            List<AStarNode> openset = new List<AStarNode>();
            List<AStarNode> closedset = new List<AStarNode>();
            List<AStarNode> came_from = new List<AStarNode>();
            List<AStarNode> neighbourNodes = new List<AStarNode>();

            AStarNode firstNode = new AStarNode(GetZAxis(first.hexCoord));
            AStarNode goalNode = new AStarNode(GetZAxis(goal.hexCoord));

            firstNode.f_score = HexDistance(goalNode.position, firstNode.position);

            openset.Add(firstNode);

            int tentative_g_score = 0;

            while (openset.Count > 0)
            {

                IEnumerable<AStarNode> query = openset.OrderBy(node => node.f_score);

                AStarNode X = query.First();

                openset.Remove(X);
                closedset.Add(X);

                if (X.position == goalNode.position)
                {

                    openset.Clear();

                    foreach (AStarNode node in came_from)
                    {
                        //colour cell green
                        cells[(int)MathHelper.Clamp(node.position.X, 0, 9), (int)MathHelper.Clamp((node.position.Y + (node.position.X / 2)), 0, 9)].whichTex(4);
                    }

                    continue;
                }

                neighbourNodes = FindNeighbourNodes(X);

                foreach (AStarNode thisNode in neighbourNodes)
                {
                    AStarNode Y = thisNode;

                    tentative_g_score = X.g_score + 1;

                    if(!(openset.Contains(thisNode)) && !(closedset.Contains(thisNode)))
                    {
                        Y.g_score = X.g_score + 1;
                        Y.h_score = HexDistance(goalNode.position, thisNode.position);
                        Y.f_score = thisNode.g_score + thisNode.h_score;
                        came_from.Add(X);
                        openset.Add(Y);
                    }
                    else if (tentative_g_score < thisNode.g_score)
                    {
                        Y.g_score = X.g_score + 1;
                        Y.h_score = HexDistance(goalNode.position, thisNode.position);
                        Y.f_score = thisNode.g_score + thisNode.h_score;
                        came_from.Add(X);
                    }
                    neighbourNodes.Remove(X);
                }

                neighbourNodes.Clear();

            }

        }

        private List<PathNode> FindNeighbourNodes(PathNode thisNode)
        {
            List<PathNode> thisList = new List<PathNode>();
            Vector3 adjacent;

            adjacent = new Vector3(thisNode.position.X - 1, thisNode.position.Y + 1, thisNode.position.Z);
            thisList.Add(new PathNode(adjacent));

            adjacent = new Vector3(thisNode.position.X + 1, thisNode.position.Y - 1, thisNode.position.Z);
            thisList.Add(new PathNode(adjacent));

            adjacent = new Vector3(thisNode.position.X, thisNode.position.Y - 1, thisNode.position.Z + 1);
            thisList.Add(new PathNode(adjacent));

            adjacent = new Vector3(thisNode.position.X, thisNode.position.Y + 1, thisNode.position.Z - 1);
            thisList.Add(new PathNode(adjacent));

            adjacent = new Vector3(thisNode.position.X + 1, thisNode.position.Y, thisNode.position.Z - 1);
            thisList.Add(new PathNode(adjacent));

            adjacent = new Vector3(thisNode.position.X - 1, thisNode.position.Y, thisNode.position.Z + 1);
            thisList.Add(new PathNode(adjacent));

            return thisList;
        }

So, on a scale from 1 to facepalm, how stupid am I being?

Thanks for reading.


EDIT UPDATE: So, I changed the code above a bit , it does find a path now along any of the axes (X, Y or Z, treating the hexes as 2D projections of cubes), but when it tries to go off an axis it messes up a bit and finds not so much a path as several parallel paths...)

EDIT2: Okay, I get it, what it's doing is finding ALL available shortest paths and displaying them all at once. I'm not sure how to distinguish between individual paths.

Title: Re: [C#] A* algorithm implementation question
Post by: rain_storm on December 26, 2011

I found this tutorial (http://www.policyalmanac.org/games/aStarTutorial.htm) very useful when I was looking into A* a few years back. It would probably be best to get the function working for square cells before scaling it up to hexagons.

I think there should be a return or a break instead of continue in this if statement

Code: [Select]

if (X.position == goalNode.position)


Code: [Select]

while (NumOpenNodes > 0) {
    if (current node is the target node) break;
    find the node with the lowest cost and add it to the closed list
    for (each of its neighbours that is open and walkable) {
        if (NeighbourNode has no parent) {
            make the low cost node the parent of the neighbour node
        } else if (This path is superior to the previous parent path) {
            make the low cost node the parent of the neighbour node
        }
    }
}