Hex distance

[waterst]

I have a hex grid with xy coordinates and am trying to find the shortest hop distance between to hexagons. Is there a way to edit the basic distance formula to do this? or is there more I'll need to do? Thanks

[Magos]

Just a guess. You could build a graph, where the nodes are the hexagons and each node points to 6 other nodes, then use a breadth search (is that the correct name? It's the opposite of a depth search) to find the closest way between two nodes (hexagons).

[waterst]

a breadth search? a couple questions for that. 1 - what is it? 2 - would I actually need to create the grid in memory, or would the x,y coordinates be enough? thanks

[Magos]

I can't say for sure, since I have no experience in hex grids.

Here is an explanation of the breadth-first search algorithm:
http://marina.fortunecity.com/nelson/457/search.html

(If the info is not enough, do a search on google for more)

[Imperito]

You you could use the excessively OO apporach, make each hexagon an independant object with pointers to it's six neighbors, and then send a broadcast ping message, that would remember the series of nodes it had passed through on its way, and once it hit a target node it would backtrack along the message path until it got home, and the distance would be a factor of the number of hops of the shourtest route...

[quzah]

Basicly you create a double linked list, except that instead of two links, you have six. (As per the previous replies.)

struct hex
{
    struct hex *dir[6];
    int used;
    int start;
    int end;
};

Then, you basicly tag one node as start, and one as end. On your way down the path, you mark the node as used. Then whenever you can't move any more, you backtrack, or once you've reached the end, you unmark all of your nodes and try another way. It's really up to you at that point.

Recursion works nicely for this. You also basicly can build a list of directions for your path with something ending up like:

14621364261362136

You could basicly just return this as a string, and just use strlen to compare path lengths. (That's the benifit of using an array of pointers rather than six individual ones--although you could make a lookup function or table and end up with the same thing, the array just is easier.)

Quzah.

[Magos]

The advantage of the breadth-first algorithm is that the first path you find to the other node is the shortest, so no comparing is needed.

[waterst]

Well, i found a simple solution, but it isn't 100% correct, works about half of the time, here it is:

int dist = 0;

while((x1 != x2) || (y1 != y2))
{
if(x1 > x2) x1 = x1 - 1;
if(x1 < x2) x1 = x1 + 1;
if(y1 > y2) y1 = y1 -1;
if(y1 < y2) y1 = y2 + 1;
dist++;
}

again I say, it works, but not great, i'll probably experiment around with breadth first searches to make it 100% correct
thanks all.