AnswerBun.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!

Related Questions

Best way to save game data in Unity

1  Asked on February 28, 2021 by tair-galili

   

Unity – Sprite vertices in 3D world

1  Asked on February 24, 2021 by muckington

   

How to represent a modular FSM for AI using ECS?

2  Asked on February 22, 2021 by christian-ivicevic

       

get access to Transform of a Clone in Unity

1  Asked on February 21, 2021 by amin007

   

Box2d on authoritative server for Unity client

0  Asked on February 19, 2021 by antonio-agustin

         

How to Send Voice over Unity Networking – UNET

1  Asked on February 12, 2021 by muhammad-faizan-khan

         

Mathf.Clamp not Working Properly

1  Asked on February 3, 2021 by shubhendra-chaddha

   

SetTrigger Only Works In Start and Not OnTriggerEnter

1  Asked on February 3, 2021 by kit-k

       

How do I detect image clicks in Dark GDK?

1  Asked on February 2, 2021 by bobman

   

FIx color banding in unity

0  Asked on February 1, 2021

 

OnMouseOver not registering collisions

3  Asked on January 29, 2021 by hyperific

   

Call native code from Unity iOS build error

1  Asked on January 29, 2021 by atlantis

   

Ask a Question

Get help from others!

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir