Following the apparent tradition of of using this question as the basis of new questions I too have a problem I am looking to solve as elegantly as possible:
I have implemented a hexagonal map as such:
(Wanted to insert image here.. but I'm not allowed due to being new... Please see above link)
But am now wondering how to (elegantly) implement A* for this type of map with these types of coordinates. I have experience with using A* on typical squared grids (cartesian grids I think?) and the way I handle it there seems incompatible with this coordinate system.
Typically I would generate a 2D array of bytes. The indices of the array would correspond to a grid coordinate and the value at said index would give the 'weight' of that node. (0 being impassible and higher numbers 'weighing' more then lower numbers).
Example:
sbyte[,] pathGrid = new sbyte[5, 5]
{
{0,0,1,0,0},
{9,5,1,3,0},
{9,5,1,3,0},
{9,5,1,3,0},
{0,0,1,0,0}
};
Where the 0's would be impassible, the 1's would be easily traversable, and higher numbers would 'cost' more to traverse. (sorry about formatting.. I'm a stack overflow newb :P ) This array would be generated based on the composition of my map and then fed into my path finding algorithm which would in turn spit out a list of nodes (the path) or return null if no path was found.
However, using this type of grid, that isn't possible (at least at first glance) due to negative coordinates (which obviously do not work in an array) and the fact that the grid doesn't follow the same rules as a 'typical' grid.
There are ways to solve this using my A* method I think but they are all rather sloppy (converting grid coordinates and using empty nodes) and I was wondering if anybody has thought of a way to do this elegantly.
Thanks for reading in any case :) (Btw I am doing this in C#/.net for what it's worth)
You could store your coordinates in a dictionary:
var nodes = new Dictionary<Point, Vector[]>;
This way you're not limited to positive coordinates, and you're also not limited on the number of paths from each node