Implementing A* on a triangular/hexagonal Grid with negative Coordinates

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 arr开发者_C百科ay) 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)

---

Even though the indices of an array begin at 0, your program doesn't need to conceptually treat the arrays that way. For instance, if you always add e.g. 3 to your indices before using them to look up in an array, you effectively have an array where the indices begin at 3. In order to simplify working with arrays in this way, you could create a class called e.g. ArbitraryBaseArray that wraps an array and a number that specifies the desired base index.

Then, you could create a HexGrid class that contains an array of ArbitraryBaseArray, each with their own base index (depending on how the left edge of your hex area looks). The class could have an indexer that lets you look up a specific element based on two hex coordinates. It could also have a static method which, given a coordinate in the hex grid, returns an array with the six neighbouring coordinates; this method could be used by A*. (Note that while the illustration in the question you linked to uses three coordinates for each hex tile, two coordinates are sufficient.)

---

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