Public Group

# Using A* on hexagonal maps!?

This topic is 5156 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi folks, i am trying to get A* working on my HexWarGame (pic: http://www.nux-acid.org/hexfeld.gif) I found an implementation for C# (i am using C# and GDI+) but i can't figure out how to define my "node" that it is a hexagon, instead of just to single coordinates. Here is the article: http://www.codeproject.com/csharp/CSharpPathfind.asp Another one for C# i found: http://www.codeproject.com/csharp/graphs_astar.asp Second, i don't get this "arc" thing, where you have to define a list of neighbours or so... how to do that in my case? Can anybody help me (best with an example) how i could implement A* with the hexagons on my map? Many thanks for your time! EDIT: I edited the tutorial link, i posted the wrong at first. The correct links are now in place. http://www.codeproject.com/csharp/CSharpPathfind.asp http://www.codeproject.com/csharp/graphs_astar.asp

##### Share on other sites
I find that the simplest way to handle maps is to have each hex, square, tile, region, whatever, have pointers to all of its neighbors. You're probably storing all of your hexs in a vector of vectors, or an array of arrays. Once all of your hex objects are created you loop through them all and link the pointers up.

##### Share on other sites
like Glak said your node will definately need to have pointers to all of its neighbors. Then you should probably store the A* specific information (given/total cost - heuristic weights, etc..) This will help in determining what path to use when your adding up your A* heuristics. If you've never worked with A* before, maybe you should try a grid implementation before moving to a Hex implementation.

-moe.ron

##### Share on other sites
thanks for the answers, but i still don't get any further :(
Since now i could figure out all things i need for my game,
but this pathfinding thing really makes me nervous...
(is this a big part or am i just to n00b?)

Still my problem:
I have seen a few c# implementations, but they all use
nodes that have (int x int y) values, so a 2-D grid if
i am right.

In the same code the map is displayed like this:

static int[,] Mapdata = 		{			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1,-1, 1, 1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1,-1, 1, 1, 1},			{ 1, 1, 1,-1,-1,-1, 1, 1,-1,-1 ,-1, 1,-1, 1, 1, 1},			{ 1, 1, 1, 1, 1,-1, 1, 1, 1, 1 ,-1, 1,-1, 1, 1, 1},			{ 1, 1, 1, 1, 1,-1, 1, 1, 1, 1 ,-1, 1,-1, 1, 1, 1},			{ 1, 1, 1, 1, 1,-1, 1, 1, 1, 1 ,-1, 1,-1, 1, 1, 1},			{ 1, 1, 1, 1, 1,-1, 1, 1, 1, 1 ,-1, 1,-1,-1, 1, 1},			{ 1, 1, 1, 1, 1,-1, 1, 1, 1, 1 ,-1, 1, 1,-1, 1, 1},			{ 1,-1,-1,-1,-1,-1, 1,-1,-1,-1 ,-1, 1, 1,-1, 1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 1, 1, 1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1,-1 , 1, 1, 1, 1,-1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1,-1 , 1, 1, 1, 1,-1, 1},			{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 ,-1,-1,-1,-1,-1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 1, 1, 1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 1, 1, 1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 1, 1, 1, 1}		};

My first plan was the following:
If a hexagon is clicked, "convert" this hexagon from my Hexagons[AllFields]
array (if a hexagon is clicked i get "Field 2" for example) to a value like
[0,0] which belongs to a map like the above (however thats going to work).
This would be fine, because i don't need to touch the Astar code in
any way.. just converting my hexgrid to a map which is used there already.

BUT, on a second thought it may be impossible to display the shifted
hexagons (they aren't all in a row like squares as you can imagin and
see on http://nux-acid.org/hexfeld.gif) in a 2-D grid like the
"static int[,] Mapdata = ..." from above, which is not shifted (and i
can't imagin any way to do this).

So, my question for know, can i convert my hexmap to a "static int[,] Mapdata"
like the one above or is this impossible due to the shifting as i think?

If it is impossible (what i think it is) i just don't get it how
to create a node and arch whith hexagons, i would really appreciate
any help with this problem and the code below (the implementation i
am working on right now).
My hexagons are all stored in an 2-D Point[][] array, so i can access
every single Point if i know which field was clicked (and i do that

So if my fist thought wont't work, how to get AStar work with
my Point[][] stored hexfields!?

The File: Astar.cs
using System;using System.Collections ;namespace ArchitectureI{		public class Map	{				static int[,] Mapdata = 		{			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1,-1, 1, 1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1,-1, 1, 1, 1},			{ 1, 1, 1,-1,-1,-1, 1, 1,-1,-1 ,-1, 1,-1, 1, 1, 1},			{ 1, 1, 1, 1, 1,-1, 1, 1, 1, 1 ,-1, 1,-1, 1, 1, 1},			{ 1, 1, 1, 1, 1,-1, 1, 1, 1, 1 ,-1, 1,-1, 1, 1, 1},			{ 1, 1, 1, 1, 1,-1, 1, 1, 1, 1 ,-1, 1,-1, 1, 1, 1},			{ 1, 1, 1, 1, 1,-1, 1, 1, 1, 1 ,-1, 1,-1,-1, 1, 1},			{ 1, 1, 1, 1, 1,-1, 1, 1, 1, 1 ,-1, 1, 1,-1, 1, 1},			{ 1,-1,-1,-1,-1,-1, 1,-1,-1,-1 ,-1, 1, 1,-1, 1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 1, 1, 1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1,-1 , 1, 1, 1, 1,-1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1,-1 , 1, 1, 1, 1,-1, 1},			{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 ,-1,-1,-1,-1,-1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 1, 1, 1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 1, 1, 1, 1},			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 1, 1, 1, 1}		};		public Map()		{		}						public static int  getMap(int x,int y)		{			int yMax =Mapdata.GetUpperBound (0);			int xMax =Mapdata.GetUpperBound (1);			if (x<0 ||  x>xMax)				return -1;			else if (y<0 || y>yMax)				return -1;			else				return Mapdata[y,x];		}		static public void PrintSolution(ArrayList solutionPathList)		{			int yMax =Mapdata.GetUpperBound (0);			int xMax =Mapdata.GetUpperBound (1);			for(int j=0;j<=yMax;j++) 			{				for(int i=0;i<=xMax;i++) 				{					bool solutionNode = false;					foreach(Node n in solutionPathList) 					{						Node tmp = new Node(null,null,0,i,j);												if(n.isMatch (tmp))						{							solutionNode = true;							break;						}					}					if(solutionNode)						Console.Write("o "); //solution path					else if(Map.getMap (i,j) == -1)						Console.Write("# "); //wall					else						Console.Write(". "); //road				}				Console.WriteLine("");			}		}		}	public class NodeComparer:IComparer	{		public NodeComparer()		{					}			public int Compare(object x, object y)		{			return ((Node)x).totalCost -  ((Node) y).totalCost ;		}	}	public class SortedCostNodeList	{		ArrayList _list;		NodeComparer _nodeComparer;		public int Count		{			get 			{				return _list.Count ;			}		}		public SortedCostNodeList()		{			_list = new ArrayList ();			_nodeComparer = new NodeComparer ();		}						public Node NodeAt (int i)		{			return (Node) _list;		}		public void RemoveAt (int i)		{			_list.RemoveAt (i);		}		public int IndexOf(Node n)		{			for (int i =0; i< _list.Count ;i++)			{				Node nodeInTheList = (Node) _list;				if (nodeInTheList.isMatch (n))					return i;			}			return -1;		}		public int push (Node n)		{			int k = _list.BinarySearch (n,_nodeComparer);						if (k==-1) // no element				_list.Insert (0,n);			else if (k<0) // find location by complement			{				k=~k;				_list.Insert (k,n);			}			else if (k>=0)			 	_list.Insert (k,n);									return k;		}		public Node pop()		{			Node r = (Node) _list[0];			_list.RemoveAt (0);			return r;		}	}		public class Node:IComparable 	{		public int totalCost		{			get 			{				return g+h;			}			set			{				totalCost = value;			}		}		public int g;		public int h;				public int x;		public int y;				private Node _goalNode;		public Node parentNode;		private int gCost;		public Node(Node parentNode, Node goalNode, int gCost,int x, int y)		{						this.parentNode = parentNode;			this._goalNode = goalNode;			this.gCost = gCost;			this.x=x;			this.y=y;			InitNode();		}			private void InitNode()		{			this.g = (parentNode!=null)? this.parentNode.g + gCost:gCost;			this.h = (_goalNode!=null)? (int) Euclidean_H():0;		}		private double Euclidean_H()		{			double xd = this.x - this._goalNode .x ;			double yd = this.y - this._goalNode .y ;			return Math.Sqrt((xd*xd) + (yd*yd));		}				public int CompareTo(object obj)		{						Node n = (Node) obj;			int cFactor = this.totalCost - n.totalCost ;			return cFactor;		}		public bool isMatch(Node n)		{			if (n!=null)				return (x==n.x && y==n.y);			else				return false;		}		public ArrayList GetSuccessors()		{			ArrayList successors = new ArrayList ();			for (int xd=-1;xd<=1;xd++)			{				for (int yd=-1;yd<=1;yd++)				{					if (Map.getMap (x+xd,y+yd) !=-1)					{						Node n = new Node (this,this._goalNode ,Map.getMap (x+xd,y+yd) ,x+xd,y+yd);						if (!n.isMatch (this.parentNode) && !n.isMatch (this))                            successors.Add (n);					}				}			}			return successors;		}	}}

The example code that calls the astar
ArrayList SolutionPathList = new ArrayList();			//Create a node containing the goal state node_goal			Node node_goal = new Node(null,null,1,15,15);						//Create a node containing the start state node_start			Node node_start = new Node(null,node_goal,1,0,0);						//Create OPEN and CLOSED list			SortedCostNodeList OPEN = new SortedCostNodeList ();			SortedCostNodeList CLOSED = new SortedCostNodeList ();									//Put node_start on the OPEN list			OPEN.push (node_start);			//while the OPEN list is not empty			while (OPEN.Count>0)			{				//Get the node off the open list 				//with the lowest f and call it node_current				Node node_current = OPEN.pop ();				//if node_current is the same state as node_goal we have found the solution;				//break from the while loop;				if (node_current.isMatch (node_goal))				{					node_goal.parentNode = node_current.parentNode ;					break;				}				//Generate each state node_successor that can come after node_current				ArrayList successors = node_current.GetSuccessors ();								//for each node_successor or node_current				foreach (Node node_successor in successors)				{					//Set the cost of node_successor to be the cost of node_current plus					//the cost to get to node_successor from node_current					//--> already set while we are getting successors					//find node_successor on the OPEN list					int oFound = OPEN.IndexOf (node_successor);										//if node_successor is on the OPEN list but the existing one is as good					//or better then discard this successor and continue					if (oFound>0)					{						Node existing_node = OPEN.NodeAt (oFound);						if (existing_node.CompareTo (node_current) <= 0)							continue;					}					//find node_successor on the CLOSED list					int cFound = CLOSED.IndexOf (node_successor);										//if node_successor is on the CLOSED list but the existing one is as good					//or better then discard this successor and continue;					if (cFound>0)					{						Node existing_node = CLOSED.NodeAt (cFound);						if (existing_node.CompareTo (node_current) <= 0 )							continue;					}					//Remove occurences of node_successor from OPEN and CLOSED					if (oFound!=-1)						OPEN.RemoveAt (oFound);					if (cFound!=-1)						CLOSED.RemoveAt (cFound);					//Set the parent of node_successor to node_current;					//--> already set while we are getting successors					//Set h to be the estimated distance to node_goal (Using heuristic function)					//--> already set while we are getting successors					//Add node_successor to the OPEN list					OPEN.push (node_successor);				}				//Add node_current to the CLOSED list				CLOSED.push (node_current);			}						//follow the parentNode from goal to start node			//to find solution			Node p = node_goal;			while(p != null) 			{				SolutionPathList.Insert(0,p);				p = p.parentNode ;			}			//display solution			//return(p);			Map.PrintSolution (SolutionPathList);			Console.ReadLine ();		}	}

I really don't get any further by myself, i read about 8 tutorials
by know, i know in theory how a* is supposed to work (open/closed list,
heuristics, start/end node,the f,g,h values,...), i just can't
implement it due to a lack of programming skills i think.

Many, many thanks^1000 for your help!!!

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 11
• 15
• 21
• 26
• 11