Trying to finish last part of A* Star in C#
March 11, 2009 09:22 PM
Okay, I have been working the past few days on creating the A* algorithm in C# console. So far everything seems to be working except for trying to find the final shortest path using the parent path. Its not that I cant get my code to find the path to work, its that I dont quite understand what the tutorial means about going backwards and following the pointing arrows. The tutorial is here:
http://www.policyalmanac.org/games/aStarTutorial.htm
The part im refering to is near the bottom about how to find the shortest path when your done reaching your goal. When I look at my parent list, it pretty much contains a linear path to the starting position, but there are a couple extra nodes/squares that are showing up as well. So I guess my parent pointer system is not working properly? Or is that how it always is and you have to write a proper algorithm to know which ones to ignore?
Ill post the code as well if you want to just plug it into console and run it. Its also pretty bulky Im sure, but I still consider myself new to C# :P
http://pastebin.com/m5cdec3ef
Anyway, just to recap, I want to know how to get the final/shortest path back to the start, or some tips on how to do it. :P
Also, here is a pic showing how I am basicly trying to repeat the tutorial with my program.
http://www.imagedump.com/index.cgi?pick=get&tp=546644
Thanks a ton for any help offered :)
132
March 12, 2009 01:54 AM
Hi
Try this one here:
http://www.ziggyware.com/readarticle.php?article_id=236
it has source and demo.
Basically those are the waypoints that you will traverse to, to get to your destination. So you backtrack, storing them into an array/vector and you use data that was stored for your units. Your units will use all those way points when they move.
A* always returns you a series of way points that you can use to move your units to get to their destination.
Try this one here:
http://www.ziggyware.com/readarticle.php?article_id=236
it has source and demo.
Quote:
its that I dont quite understand what the tutorial means about going backwards and following the pointing arrows
Basically those are the waypoints that you will traverse to, to get to your destination. So you backtrack, storing them into an array/vector and you use data that was stored for your units. Your units will use all those way points when they move.
A* always returns you a series of way points that you can use to move your units to get to their destination.
March 12, 2009 02:01 AM
Hmmmm, I havnt seen this demo before. Ill have to check it out. Thanks for the reply. :)
*Edit*
Well, his example is quite different from mine. This is gonna be tough :/ If anybody has any other suggestions along the way. Please feel free!
*Edit*
Well, his example is quite different from mine. This is gonna be tough :/ If anybody has any other suggestions along the way. Please feel free!
769
March 12, 2009 09:01 AM
Once you have reached the target, following the links back from the target to its previous node, and the link from that node to its previous, and so on, will give you the shortest path. If that is not working for you, make sure you are setting the previous node link correctly when you update the distance on a node already on the open list as well as when you open a new node.
For reference here is my quick lash-up of A* in C# for my game Abaria. It references several classes which aren't important here but hopefully the algorithm is clear so you can see what you may have missed. (Heh, I'd missed the updating of open nodes myself, I saw when looking over the code.)
The part which you are confused about, tracking back the path, is right at the end, and is literally as simple as following the parent pointers back, which is why I think your mistake must be in setting those pointers correctly.
(Yes I know this is an inefficient way of storing the lists, using an ordered list for the open nodes would work better.)
For reference here is my quick lash-up of A* in C# for my game Abaria. It references several classes which aren't important here but hopefully the algorithm is clear so you can see what you may have missed. (Heh, I'd missed the updating of open nodes myself, I saw when looking over the code.)
// A* pathfinder and other route finding utilities for icosahedral worldusing System;using System.Collections;using RedCorona.Geometry;namespace RedCorona.Net.Games.Abaria { public class Path { TileLocation start, end; World w; Abaria game; ArrayList open, closed, path; public class Node { public TileLocation Location; public int Cost, Heuristic, dCost; public Node Parent; public bool Closed = false; internal Node(TileLocation loc, TileLocation target, Node parent, int dcost, int worldsize){ Location = loc; Parent = parent; dCost = dcost; Cost = (parent == null ? 0 : parent.Cost) + dcost; Heuristic = (int)((Utils.TileVector(loc, worldsize) - Utils.TileVector(target, worldsize)).Magnitude); } } public ArrayList Route { get { return path; } } public Node this[int inx]{ get { return (Node)path[inx]; } } public int Length { get { return path.Count; } } public Path(Abaria g, World w, TileLocation start, TileLocation end){ game = g; this.start = start; this.end = end; this.w = w; } Node GetNode(TileLocation tl){ foreach(Node n in open) if(n.Location == tl) return n; foreach(Node n in closed) if(n.Location == tl) return n; return null; } public ArrayList Resolve(LandType[] terrain, NationInfo owner, ServerBrigade sb, int frame){ // Find a valid path // Start: open list contains start node bool[] validland = new bool[255]; // big so it doesn't get forgotten for(int i = 0; i < terrain.Length; i++) validland[(int)terrain] = true; int worldsize = w.Icosahedron.SideLength; // Make sure the end tile is somewhere we can move to! LandType type = w.GetTransientTileType(Utils.TileVector(end, worldsize), w.GetYearPhase(frame), worldsize); if(!validland[(int)type]) return null; // Initialise lists open = new ArrayList(); closed = new ArrayList(); Node n; open.Add(n = new Node(start, end, null, 0, worldsize)); int startdist = n.Heuristic; // Iterate until we find the end bool finished = false; while(!finished){ if(open.Count == 0) return null; // no path // Find best open node n = (Node)open[0]; foreach(Node n2 in open){ if((n2.Cost + n2.Heuristic) < (n.Cost + n.Heuristic)) n = n2; } // Close this node open.Remove(n); closed.Add(n); n.Closed = true; // Find adjacent nodes and add new ones to open list TileLocation[] adj = Utils.GetAdjacentTiles(n.Location, worldsize, true); for(int i = 0; i < adj.Length; i++){ Node n2 = GetNode(adj); if(n2 != null){ if((!n.Closed) && (n2.Cost < n.Cost + n2.dCost)){ n2.Cost = n.Cost + n2.dCost; n2.Parent = n; } continue; } type = w.GetTransientTileType(Utils.TileVector(adj, worldsize), w.GetYearPhase(frame), worldsize); if(!validland[ (int)type ]) continue; int cost = 1; TileInfo ti = game.GetTile(owner.World, adj); string answer = sb.TileIsValid(ti); if((sb != null) && (null != answer)) { Console.WriteLine("Invalid tile "+adj+": "+answer); continue; } n2 = new Node(adj, end, n, cost, worldsize); if(n2.Heuristic > startdist * 2) continue; open.Add(n2); if(adj == end){ finished = true; break; } } } // Now track back a path. Destination will be last node on open list Node nn = (Node)open[open.Count - 1]; path = new ArrayList(); while(nn != null) { path.Add(nn); nn = nn.Parent; } path.Reverse(); return path; } }}The part which you are confused about, tracking back the path, is right at the end, and is literally as simple as following the parent pointers back, which is why I think your mistake must be in setting those pointers correctly.
(Yes I know this is an inefficient way of storing the lists, using an ordered list for the open nodes would work better.)
March 12, 2009 10:22 AM
That makes sense :) Thanks for the help guys! Im gonna toy around with it some more and see what I come up with.
132
March 12, 2009 11:13 AM
Quote:
*Edit*
Well, his example is quite different from mine. This is gonna be tough :/ If anybody has any other suggestions along the way. Please feel free!
How is it different? it should be the same. A star is a star.
March 12, 2009 06:33 PM
Quote: Original post by mickeyrenQuote:
*Edit*
Well, his example is quite different from mine. This is gonna be tough :/ If anybody has any other suggestions along the way. Please feel free!
How is it different? it should be the same. A star is a star.
I meant the way he implemented it. I am still new to programming, so there are a few keywords and procedures Im not familiar with yet :P
192
March 12, 2009 06:57 PM
Might as well throw in my implementation I did during lunch at work last year (got bored, write a random map generator and A* to test if it was possible to make it from start to end point.. lunch-times get boring :p).
[Edited by - DensitY on March 12, 2009 10:57:45 PM]
// AStar Search node. public class CAStarNode : ICloneable { public int Index; // index of this Astar node, it'll match the tile index on the map, which will be y * width + x. public int ParentIndex; // Parent index, basically from which node did we travel to this existing node. -1 = starting node. // Redunant public int tX = 0; public int tY = 0; public float G; public float H; public float F; public CAStarNode() { } public void CalcCost(float g, float h) { G = g; H = h; F = G + h; } public object Clone() { return this.MemberwiseClone(); } } public class CAStarTilePathNode { public int X = 0; public int Y = 0; } public class CAStar { private CMap rMap = null; private List<CAStarNode> m_OpenList = new List<CAStarNode>(); private List<CAStarNode> m_ClosedList = new List<CAStarNode>(); public List<CAStarTilePathNode> m_FinalPath = new List<CAStarTilePathNode>(); // offset list. /* * 0 1 2 * 3 4 * 5 6 7 */ private Point[] m_OffsetList = { new Point(-1,-1), new Point(0, -1), new Point(1,-1), new Point(-1, 0), new Point(1,0), new Point(-1, 1), new Point(0, 1), new Point(1,1) }; // costings table. private int[] m_CostTable = { 14, 10, 14, 10, 10, 14, 10, 14 }; private CAStarNode m_StartNode = null; public CAStar(ref CMap map) { m_OpenList.Clear(); m_ClosedList.Clear(); rMap = map; } // Build index number private int BuildIndex(int x, int y) { return y * 40 + x; } // reverse index. private void BuildTileIndex(int index, ref int x, ref int y) { if(index < 0) index = 0; if(index > 40 * 40 -1) index = 40 * 40; y = index / 40; x = index - (y * 40); } private CAStarNode FindInAnyList(int index) { int i; CAStarNode node = null; for (i = 0; i < m_ClosedList.Count; i++) { if (m_ClosedList.Index == index) { node = m_ClosedList; break; } } for (i = 0; i < m_OpenList.Count; i++) { if (m_OpenList.Index == index) { node = m_OpenList; break; } } return node; } // Grab node with lowest F from openList index. private int SmallestOpenFNode() { float max = 999999999.0f; int retindex = -1; for(int i = 0; i < m_OpenList.Count;i++) { if(m_OpenList.F < max) { max = m_OpenList.F; retindex = i; } } return retindex; } private bool NodeInClosedList(int index) { bool isit = false; foreach (CAStarNode node in m_ClosedList) { if (node.Index == index) { isit = true; break; } } return isit; } private bool NodeInOpenList(int index) { bool isit = false; foreach (CAStarNode node in m_OpenList) { if (node.Index == index) { isit = true; break; } } return isit; } // Start Searching from starting tile to ending tile. // TODO: we need to show if we failed or not. public void SearchPath(int startX, int startY, int endX, int endY) { int EndIndex = BuildIndex(endX,endY); // Create our Starting node. m_StartNode = new CAStarNode(); m_StartNode.Index = BuildIndex(startX,startY); m_StartNode.tX = startX; m_StartNode.tY = startY; m_StartNode.F = 0.0f; // force lowest score, we want to start testing from here. // add to list m_OpenList.Add(m_StartNode); // Right, we need to search until the openlist is empty. // TODO: we should have a limit to stop stupidly long searchers while(m_OpenList.Count > 0) { int[] BlockList = new int[8]; int lowestOpen = -1; // Find node with smallest F value. lowestOpen = SmallestOpenFNode(); CAStarNode Opened = m_OpenList[lowestOpen].Clone() as CAStarNode; // we're done with this guy, lets remove the lowest, and add it to the closed list m_OpenList.RemoveAt(lowestOpen); m_ClosedList.Add(Opened); // Check if this is our goal node, if so move to it. and we're done really. if (Opened.Index == EndIndex) { CAStarTilePathNode tempPathNode = new CAStarTilePathNode(); List<CAStarTilePathNode> tempList = new List<CAStarTilePathNode>(); tempList.Clear(); m_FinalPath.Clear(); // Add first into temp list tempPathNode.X = Opened.tX; tempPathNode.Y = Opened.tY; tempList.Add(tempPathNode); // we've found our target!!! // do a reverse walk to build final path. CAStarNode ParentNode = FindInAnyList(Opened.ParentIndex); while (ParentNode != null) { tempPathNode = new CAStarTilePathNode(); tempPathNode.X = ParentNode.tX; tempPathNode.Y = ParentNode.tY; tempList.Add(tempPathNode); ParentNode = FindInAnyList(ParentNode.ParentIndex); } // just flip this around. for (int i = tempList.Count - 1; i > 0; i--) { m_FinalPath.Add(tempList); } return; } // Prep the block list. Handles blocking of diag edges for (int i = 0; i < 8; i++) { int testX = Opened.tX + m_OffsetList.X; int testY = Opened.tY + m_OffsetList.Y; if (testX < 0 || testY < 0 || testX >= 40 || testY >= 40) BlockList = 1; if (rMap.Tiles[testX, testY].TileIndex > 0 && rMap.Tiles[testX, testY].TileIndex != 2) { BlockList = 1; switch (i) { case 1: BlockList[0] = 1; BlockList[2] = 1; break; case 3: BlockList[0] = 1; BlockList[5] = 1; break; case 4: BlockList[2] = 1; BlockList[7] = 1; break; case 6: BlockList[5] = 1; BlockList[7] = 1; break; default: break; } } } // we need to walk through all steps around it, score it then move to it. // we'll walk around the 8 tiles around us. for (int i = 0; i < 8; i++) { int testX = Opened.tX + m_OffsetList.X; int testY = Opened.tY + m_OffsetList.Y; // check if we've blocked it if(BlockList == 1) continue; // test if node is in closed list. if (NodeInClosedList(BuildIndex(testX, testY)) != false) continue; CAStarNode NewNode = new CAStarNode(); NewNode.tX = testX; NewNode.tY = testY; NewNode.ParentIndex = Opened.Index; NewNode.Index = BuildIndex(testX, testY); float h,g; // h = guestimate distance, g = additive cost from start point. // Calculate move cost. g = Opened.G + m_CostTable; // guestimate distance. int dx = endX - testX; int dy = endY - testY; h = (float)Math.Sqrt((dx * dx) + (dy * dy)); // calculate F cost NewNode.CalcCost(g, h); // add to open node list. if(NodeInOpenList(NewNode.Index) != true) m_OpenList.Add(NewNode); } } } }[Edited by - DensitY on March 12, 2009 10:57:45 PM]
March 13, 2009 03:24 PM
Nice! Thanks DensitY, I will check yours out as well.
876
March 13, 2009 04:29 PM
A* in plain english.
You have a graph of nodes that you are pathing on. From it, you can ask what is adjacent to a given node, and how much would it cost to get there from here. You read from this during the A* algorithm, and your goal is to find the shortest path between one node on the graph (the start node) and another node on the graph (the end node).
In the algorithm itself:
You have two collections of nodes.
The first is the 'frontier'. The frontier contains your current cost for your best route of getting to the node, and the node you use to get there for that estimate.
The second is the 'interior'. The interior contains the current cost for your best route to a node, and the node that the best route used to get there.
You need to be able to add nodes to the interior cheaply, and look them up cheaply.
For the 'frontier' you need to be able to update a node's estimated cost cheaply, add a node, remove a node, and find the lowest cost node in it cheaply.
Start with the only node in the frontier being your start node, and the estimated cost being 0.
Repeat the following steps until you want to add the goal node to your interior. At that point, skip to the path construction part later on.
Take the cheapest estimated node out of the frontier. Call this your current node. If there is no nodes in the frontier, you cannot get to the destination from the source.
Move that node to the interior. Record it's cost as gospel.
For each node in the full map adjacent to your current node that isn't in the collection of interior nodes already, add it to the frontier with a new estimated cost (or if it is already in the frontier, update the cost of it in the frontier).
This is the end of the stuff you are suppposed to repeat.
Now, the estimated cost of a node ends up being the sum of the 'gospel' cost of the current node whose adjacent node you are adding, the cost to move from the current node to the frontier node, and the 'as the crow flies' distance between the adjacent node and the target node. It is important that the 'as the crow flies' cost never overestimates the cost of getting from a node to the destination node, or you can miss a shorter path.
Finally, how to construct the path. You stopped the algorithm just as you where about to insert the goal node into your 'interior' set. It was adjacent to some current node, which is now in the interior.
Your path, backwards, ends up being the goal node, then the current node, then the 'previous' node from the current node, etc -- until you eventually terminate with the 'start' node (who has no previous node).
...
Finally, note that you can run A* in parallel over multiple units all trying to get to one destination, to find the path from any one of the units that could reach the destination in the shortest period of time. Simply insert each unit's starting node (with an estimate based off of 'how the crow flies' costs for extra efficiency) into the list of frontier nodes.
The first strategy might be useful for "patrol and intercept" AI, where you have a collection of units that collectively intercept opponents over a given area.
You can similarly path to a collection of acceptable end locations by making the goal node a collection of nodes. When you are about to insert _any_ of the goal nodes into the interior, you have found a best path.
This second is useful for 'attack target with ranged weapon'. Instead of pathing to the target, path to the set of nodes from which you can attack the target.
...
Did I make any errors in my description of A*? I think there are some optimisations I might have missed in my English language description.
[Edited by - NotAYakk on March 14, 2009 12:29:58 PM]
You have a graph of nodes that you are pathing on. From it, you can ask what is adjacent to a given node, and how much would it cost to get there from here. You read from this during the A* algorithm, and your goal is to find the shortest path between one node on the graph (the start node) and another node on the graph (the end node).
In the algorithm itself:
You have two collections of nodes.
The first is the 'frontier'. The frontier contains your current cost for your best route of getting to the node, and the node you use to get there for that estimate.
The second is the 'interior'. The interior contains the current cost for your best route to a node, and the node that the best route used to get there.
You need to be able to add nodes to the interior cheaply, and look them up cheaply.
For the 'frontier' you need to be able to update a node's estimated cost cheaply, add a node, remove a node, and find the lowest cost node in it cheaply.
Start with the only node in the frontier being your start node, and the estimated cost being 0.
Repeat the following steps until you want to add the goal node to your interior. At that point, skip to the path construction part later on.
Take the cheapest estimated node out of the frontier. Call this your current node. If there is no nodes in the frontier, you cannot get to the destination from the source.
Move that node to the interior. Record it's cost as gospel.
For each node in the full map adjacent to your current node that isn't in the collection of interior nodes already, add it to the frontier with a new estimated cost (or if it is already in the frontier, update the cost of it in the frontier).
This is the end of the stuff you are suppposed to repeat.
Now, the estimated cost of a node ends up being the sum of the 'gospel' cost of the current node whose adjacent node you are adding, the cost to move from the current node to the frontier node, and the 'as the crow flies' distance between the adjacent node and the target node. It is important that the 'as the crow flies' cost never overestimates the cost of getting from a node to the destination node, or you can miss a shorter path.
Finally, how to construct the path. You stopped the algorithm just as you where about to insert the goal node into your 'interior' set. It was adjacent to some current node, which is now in the interior.
Your path, backwards, ends up being the goal node, then the current node, then the 'previous' node from the current node, etc -- until you eventually terminate with the 'start' node (who has no previous node).
...
Finally, note that you can run A* in parallel over multiple units all trying to get to one destination, to find the path from any one of the units that could reach the destination in the shortest period of time. Simply insert each unit's starting node (with an estimate based off of 'how the crow flies' costs for extra efficiency) into the list of frontier nodes.
The first strategy might be useful for "patrol and intercept" AI, where you have a collection of units that collectively intercept opponents over a given area.
You can similarly path to a collection of acceptable end locations by making the goal node a collection of nodes. When you are about to insert _any_ of the goal nodes into the interior, you have found a best path.
This second is useful for 'attack target with ranged weapon'. Instead of pathing to the target, path to the set of nodes from which you can attack the target.
...
Did I make any errors in my description of A*? I think there are some optimisations I might have missed in my English language description.
[Edited by - NotAYakk on March 14, 2009 12:29:58 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
