Path finding on hex maps and alternative routes

By | September 28, 2017

Hex grids are useful for any number of reasons but if you’ve ever used them yourself you no doubt know of they have some interesting properties too.

Looking at the very simple 4 hex “map” you can see two routes A and B

They are both equally valid taking the same number of steps and additionally they are both exactly the same distance from start to goal.

 

Especially with regards to path finding algorithms like A* its common practice to select the top item off a list or heap that is maintained in some kind of “score” order.

While this leads to perfectly valid paths, given the same start and destination you will always get exactly the same path even if there are multiple paths of the same cost / length.

Initial thoughts lead me to believe that the top of a selection list could have multiple ties (even more than two) however thinking about it (and looking at the first illustration above) you only need to check the top two

As there are likely to be multiple places along a path where this might happen, this can often lead to a wide range of paths, again all of them valid and of equal length.

 mapNode_t* current = openList->head->data;
 if (openList->head->next!=NULL) {
   mapNode_t* nn = openList->head->next->data;
   if (current->G+current->H == nn->G+nn->H ) {
     if (rand()/(float)RAND_MAX > 0.5) {
       current = nn;
     }
   }
 }

The example code is trivial if there are two or more items in the list and they have the same total cost then randomly use either the top of the list or the next item.

This is a case of a simple little tweak to an algorithm that isn’t always obvious, till you see it and then its trivial.¬† Its simple enhancements like this that when added together can make all the difference whatever type of software you’re creating…

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *