1

I am currently developing a simple game in Unity.

I got a game board composed of hexagons. Let's say, the red dot is the player.

Game board

Now I want to show the user on which fields he can go, depending on the number he diced. The user should not be allowed to enter one hexagons multiple times in one move.

Is there any algorithm to solve this path problem? I've only found algorithms which asserted whether there is a connection between two nodes, but no algorithm to get all possible moves.

Lolo
  • 11
  • 1
  • 4
    Since you're saying the user can't re-enter a hex I presume you're only looking to light up possible final destinations when fully consuming the number rolled on the dice. Is this correct? – candied_orange Mar 08 '18 at 14:03
  • If you forget the hexagons and just think the corners as vertices and sides as edges of a graph, then you can apply some of the existing graph traversal algorithms. Once the path is found, you can do another pass to select some hexagons that have the path segments as sides. – S.D. Mar 09 '18 at 06:10

2 Answers2

1

Yes, in fact most algorithms that check whether there is a connection between two graph nodes also compute what the connection is. It's just a matter of not discarding the information that was used to make the yes/no judgement and instead returning it.

Path-finding algorithms are almost always recursive in nature: if the target node is adjacent, the answer is yes, otherwise check (via a self-call) whether it's adjacent to any of the adjacent ones, etc. Actually constructing the path just means returning a partial path on each call, which ultimately resolves to a complete path if the top-level call succeeds.

Kilian Foth
  • 107,706
  • 45
  • 295
  • 310
  • IMHO path-finding is overkill here, it is effectively BFS, no need to get fancy. – wondra Mar 09 '18 at 06:35
  • @wondra: BFS does not deliver the cells in the given number of steps which are reachable by a smaller number of steps. This answer, however, seems to miss that as well. – Doc Brown Mar 09 '18 at 08:00
1

The best resource for hex-grid algorithms I've ever read is this Red Blob Games article, and it has a whole section on movement range. It says:

If there are obstacles, the simplest thing to do is a distance-limited flood fill (breadth first search).

The exact implementation will depend on the coordinate system you've chosen to represent your hex grid, but essentially you'll find all the hexes that are one move away, then from that list you can find all the hexes that are two moves away, and so on...

Brad Buchanan
  • 151
  • 4