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.

  • 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 8 '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 9 '18 at 6:10

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.

| improve this answer | |
  • IMHO path-finding is overkill here, it is effectively BFS, no need to get fancy. – wondra Mar 9 '18 at 6: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 9 '18 at 8:00

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

| improve this answer | |
  • BFS does not deliver the cells in the given number of steps which are reachable by a smaller number of steps. – Doc Brown Mar 9 '18 at 7:59
  • @DocBrown don't discard the results for each depth. – Pete Kirkham Mar 9 '18 at 16:03

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.