TransWikia.com

Finding all possible paths from one hexagon to another

Game Development Asked by Vitozz_RDX on December 25, 2021

I got a hexagonal grid (cube coords)

enter image description here

In hex (0,0,0) there is a soldier and in another (distance == 4 hexes) a target:

enter image description here

i need to find all possible pathes from soldier hex to a target :

1)Length of path should be no more then 6 hexes

2)Not including those which returning to already visited tiles

3)Including those that are longer than the shortest possible path .

Though i need to solve it on javascript, but even pseudocode or just some thougths would be helpful

Thank you !

3 Answers

I did this :

function search(from,to,i) {

if(i == 1){
    if (isHexNear(from,to) || JSON.stringify(from) == JSON.stringify(to)){
        return [[from, to]]
    }
    return []
}

let all_paths = []

let neighbors = nearestHexesArr(from)
neighbors.push(from)


for (let node of neighbors) {

    let neighbor_all_paths = search(node,to,i-1)
    for( let path of neighbor_all_paths){
        all_paths.push([from, node].concat(path))
    }
}

return all_paths
}

Though it got some issues (resulting paths got duplicate hexes) , still after some cleaning of result it works.

isHexNear(from,to) and nearestHexesArr(from) are helper functions not hard to create.

Algorithm used is here: search Algo answer

Answered by Vitozz_RDX on December 25, 2021

This reminds me of a problem I did on Google Foobar recently. It's dynamic programming. Basically first compute every path where you can get to the destination in exactly 1 move (from any tile location). Then compute every path that you can get to the destination in exactly 2 moves (this is done by computing every path that can reach a tile in the previous step in 1 move) that do not reuse nodes. Keep on doing this recursively until you reach the max distance, in this case 6. Then your result is all possible paths that start at the start node with distance 6 or less.

Here's some psuedocode:

public List<List<Tile>> getAllPaths(Tile origin, Tile destination, int maxDistance) {
    List<List<Tile>>[] allPaths = new List<List<Tile>>[maxDistance]();
    
    // Add everything adjacent to destination
    allPaths[0] = new List<List<Tile>>();
    for (int i = 0; i < destination.edgeNeighbours.Count; i++) {
        List<Tile> newPath = new List<Tile>();
        newPath.Add(destination.edgeNeighbours[i]);
        allPaths[i].Add(newPath);
    }
    
    // Compute paths recursively
    for (int distanceMinusOne = 1; distanceMinusOne < maxDistance; distanceMinusOne++) {
        for (int subPath = 0; subPath < allPaths[distanceMinusOne - 1].Count; subPath++) {
            for (int nextTile = 0; nextTile < allPaths[distanceMinusOne - 1][subPath][0].edgeNeighbours.Count; nextTile++) {            
                
                // Check for duplicate tiles.
                if (allPaths[distanceMinusOne - 1][subPath].Contains(allPaths[distanceMinusOne - 1][subPath][nextTile])) {
                    break;
                }
                
                List<Tile> newPath = new List<Tile>();
                newPath.Add(allPaths[distanceMinusOne - 1][subPath][0].edgeNeighbours[nextTile]);
                newPath.AddAll(allPaths[distanceMinusOne - 1][subPath]);
                allPaths[distanceMinusOne].Add(newPath);
            }
        }
    }
    
    // Get all the paths
    List<List<Tile>> finalPaths = new List<List<Tile>>();
    for (int distanceMinusOne = 0; distanceMinusOne < allPaths.Count; distanceMinusOne++) {
        for (int path = 0; path < allPaths[distanceMinusOne].Count; path++) {
            if (allPaths[distanceMinusOne][path][0] == origin) {
                finalPaths.Add(allPaths[distanceMinusOne][path]);
            }
        }
    }
    
    return finalPaths;
}

Answered by andrew zuo on December 25, 2021

Some pseudo brute force that just goes into all direction and stops on either length > 6 or repeated field

function searchPath(x, y, z, gamefield, pathlength, pathtaken) {
 if (tile[x, y, z] == destination) {
  solutions.add(pathtaken);
 } else
 if (pathlength < 6) {
  if (gamefield[x, y, z] = false) {
   gamefield[x, y, z] = true;
   pathtaken.add(tile[x, y, z]);
   searchPath(x + 1, y - 1, z, gamefield, pathlength + 1, pathtaken);
   searchPath(x - 1, y + 1, z, gamefield, pathlength + 1, pathtaken);
   searchPath(x, y + 1, z - 1, gamefield, pathlength + 1, pathtaken);
   searchPath(x, y - 1, z + 1, gamefield, pathlength + 1, pathtaken);
   searchPath(x - 1, y, z + 1, gamefield, pathlength + 1, pathtaken);
   searchPath(x + 1, y, z - 1, gamefield, pathlength + 1, pathtaken);  
  }
 }
}

A simple recursion that does not care about bounds. x, y z are the coordinates and hold your current position, gamefield is an array of bools that hold if you visited the place already, pathlength how many fields you walked and pathtaken is a list of tiles you walked. Make sure that they get their own instance of the passed parameters.

Answered by Zibelas on December 25, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP