recognizing and dealing with 2 valid paths when walking a hex map

Question

I am writing a cost path script for use on hexagonal maps. Currently I am in the "learning how to walk" phase of development.

In general terms the code works. I can reliably get from A to B. However, consider the following map:

Both the sequence 0406 -> 0405 -> 0505 and 0406 -> 0506 -> 0505 are valid. I would like to traverse and output BOTH paths.

My code follows:

public function walkMap($origCol, $origRow, $destCol, $destRow) {
    $curRow = $origRow;
    $curCol = $origCol;
    while (($curRow != $destRow) || ($curCol != $destCol)) {
        $newRow = self::getNextMove($curRow,$destRow);
        if ($newRow == $curRow) {
            $curCol = self::getNextMove($curCol,$destCol);
        } else {
            $curRow = $newRow;
        }
    }
}

private function getNextMove($cur,$dest) {
    if ($cur < $dest) {
        ++$cur;
    } else if ($cur > $dest) {
        --$cur;
    }
    return $cur;
}

My desired result is a numeric array of step => hexCoord showing the path taken. But I'm not sure how to adopt the above working code to intelligently branch, and having done that, how best to shape the output data structure...

Thanks in advance.

Answer 1

I noticed that, at the moment, your path choice is simply "get to the right row, then get to the right column." I realize that you're still getting started, but you might want to think ahead about how you want to work cost into your paths and let that tell you about your data structure.

For example, you can use Dijkstra's algorithm to mark each point on your map with the least cost from that point to a given destination. Finding a path is then a matter of picking an origin and repeatedly moving to the neighboring hex with the least cost, building the path array that you want as you go. If there are two optimal paths at any point, you'll see that as a hex with two minimally-cheap neighbors -- you'd make a new copy of the path array for each and complete them independently. Taking that approach, you'd work with (and return) an array of path arrays.