# 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)

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

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 !

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]();

allPaths[0] = new List<List<Tile>>();
for (int i = 0; i < destination.edgeNeighbours.Count; i++) {
List<Tile> newPath = new List<Tile>();
}

// 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>();
}
}
}

// 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) {
}
}
}

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) {
} else
if (pathlength < 6) {
if (gamefield[x, y, z] = false) {
gamefield[x, y, z] = true;
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

## Related Questions

### Calculate hockey puck bouncing off rubber bumper

0  Asked on March 5, 2021 by jinxy

### Trying to understand 3D transforms by making an aircraft control script. How would you implement 3D transforms correctly in this example?

1  Asked on March 2, 2021 by pocketonion

### Best way to save game data in Unity

1  Asked on February 28, 2021 by tair-galili

### How do I fix missing anti-aliasing in the Unity scene view and game?

0  Asked on February 27, 2021 by pale_rider

### Unity – Sprite vertices in 3D world

1  Asked on February 24, 2021 by muckington

### Should UI systems update naively with events and data from outside, or should they be coupled to some game state/singleton to know to change itself?

1  Asked on February 22, 2021 by yookakim

### How to represent a modular FSM for AI using ECS?

2  Asked on February 22, 2021 by christian-ivicevic

1  Asked on February 21, 2021 by amin007

### Box2d on authoritative server for Unity client

0  Asked on February 19, 2021 by antonio-agustin

### UE4 C++ – Add generated source code folders to Visual Studio solution?

1  Asked on February 12, 2021 by json-brody

### How to prevent a sprite to move in an angle that will lead to collision

1  Asked on February 4, 2021 by user3150201

### 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

### How to copy morphs from one SkeletalMesh to another in UE4?

0  Asked on January 29, 2021

### Call native code from Unity iOS build error

1  Asked on January 29, 2021 by atlantis

### Unity – Smooth player input direction when changing camera

1  Asked on January 24, 2021 by herewego