Jump to content
  • Advertisement
Sign in to follow this  
code_nerd

Using A* on hexagonal maps!?

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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
already).

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!!!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!