1

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)

Community
  • 1
  • 1
Jesse Purdy
  • 13
  • 3
  • You can overcome the negative coordinates problem easily by adding a constant to all coordinate values to shift them into the non-negative realm. Treating the problem as a two dimensional grid would seem like a pretty straightforward way to do, even if you do have to convert some coordinates here or there. – Will A May 08 '11 at 23:30
  • a nice coordinate system could be "ring number","cell number" where ring number goes up from the center hexagon, and cell number is starting at a point and working clockwise (or counterclockwise, does not really matter). the number of cells in each "ring" is 2n*(2n-1)/2, where n is the 1 indexed number of rings. not sure how to really do A* in this system, but i dont think its that hard either, and there are no wasted cells. it is also easy to determine adjacency. – soandos May 08 '11 at 23:38

2 Answers2

2

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.)

Aasmund Eldhuset
  • 37,289
  • 4
  • 68
  • 81
0

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

Martin Booth
  • 8,485
  • 31
  • 31
  • Hey at first glance this looks like a perfect solution.. I still need to work out some quirks but for now this is my accepted answer :) Thanks a lot. I'll be sure to let you (anybody reading) know if it really works as intended when fully integrated. If it does work perfectly then I feel pretty dumb for not thinking about it since it's so simple :P – Jesse Purdy May 09 '11 at 01:03
  • Let me know if you need any more detail, this is how I've implemented A* before so I'm pretty sure it can be made to work. Cheers! – Martin Booth May 09 '11 at 01:18