0
\$\begingroup\$

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 !

\$\endgroup\$
  • \$\begingroup\$ What do you mean with "all possible paths"? Should this really include all paths including those which waste moves by returning to already visited tiles or paths which are longer than the shortest possible path? \$\endgroup\$ – Philipp Jul 24 at 9:05
  • \$\begingroup\$ Not including those which returning to already visited tiles , but for the second part - yes, those that are longer than the shortest possible path must be included. Thank you for correction ! \$\endgroup\$ – Vitozz_RDX Jul 24 at 9:16
  • \$\begingroup\$ @Philipp , i saw your answer , but then you deleted it . Is it possible to recover it ? \$\endgroup\$ – Vitozz_RDX Jul 24 at 19:24
  • \$\begingroup\$ It wouldn't help you, because it was incorrect. \$\endgroup\$ – Philipp Jul 24 at 21:12
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can improve the efficiency of this if needed (say for large maps with higher max limits). First, compute the length of the shortest path from your destination to each cell. If you have obstacles this can be done with BFS; if not, you can quickly compute it as a "hexagon radius" on demand. If during your backtracking search your remaining move budget ever exactly meets the shortest path length to this cell, you can immediately find all valid completions of the path by following this distance field downhill. If it exceeds it, you can immediately abort, cutting out fruitless meanders. \$\endgroup\$ – DMGregory Jul 24 at 13:39
  • \$\begingroup\$ please , correct me if i'm wrong - searchPath(x + 1, y, z) is a mistake (for example hex 0,0,0 becomes (1,0,0) it can't be so in cube coordinates) \$\endgroup\$ – Vitozz_RDX Jul 24 at 18:17
  • \$\begingroup\$ I tried your proposal and it didn't work for me \$\endgroup\$ – Vitozz_RDX Jul 24 at 19:18
  • 1
    \$\begingroup\$ "didn't work" is never enough information to diagnose and fix a problem, @Vitozz_RDX. You're more likely to get useful fixes if you concretely describe a test case, the expected result, and how the observed result differs from the expectation. \$\endgroup\$ – DMGregory Jul 24 at 21:04
  • \$\begingroup\$ @DMGregory i agree with you . I can't put my code here , so i'll create a link to fiddle later . Quite possible that i just write it not correctly but the output i get is an array of length 3 with arrays of length 32 correspondingly . And i expected a bunch of arrays length 6 ( maximum ) \$\endgroup\$ – Vitozz_RDX Jul 24 at 21:12
0
\$\begingroup\$

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;
}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.