Navigation2d pathfinding with hex tilemap?

Question

Hi guys. I'm looking to implement pathfinding in a 2D strategy game using a hex tilemap.

I've been following the example from https://github.com/FEDE0D/godot-pathfinding2d-demo and it works fine for square tiles but I'm finding hexes more difficult to work with. I'm basically drawing the nav poly instance around each hex tile that I want traversable, but there are only 2 points generated by getsimplepath so I'm guessing the nav poly instances don't fit together properly.

Is there another way to do pathfinding with hex tilemaps, is there something I'm missing, maybe should I use the A star class instead?

Thanks.

Comments

Can you show a picture of what you get compared to what you want?

Do you imlply that the path you want should actually go through one of the 6 directions of a hex instead of crossing them? Because if that's the case, you may want a different pathfinder like the AStar one so that you can choose which waypoints to traverse (in any case that will require some scripting to get that constraint). Making your own pathfinder is also an option.

---

http://tinyimg.io/i/lHcvU9f.png

So I followed the example in the pathfinding2d demo linked in the question pretty closely, the only difference being I used hex tiles as opposed to squares. And the result I try to show in the image above with black arrows, is that the sprite literally only goes to the adjacent (horizontal) hex, one at a time. And there are only two points in the path, even when I want the sprite to go several hexes away (e.g. the red points I marked in the image).

And yes, I do want the path to go through one of the 6 directions of a hex. To be honest, I don't really know how navigation2d/navpolyinstance/getsimplepath works and wasn't sure if it would work with hexes in the same way it would work with squares in a tilemap. I think you're right it would probably be easier to script with AStar, I might give that a shot.

Answer 1

This guy made a hex pathfinder module for Godot 3.0
https://www.youtube.com/watch?v=rlKvOnQrxZg

Comments

Yup I ended up going with this and it wasn't too difficult to set up.

---

Hey hnuqweasd, I hope you still get this message!
What did you do? Did you try to use use the module with Godot 2.1 or Godot 3.0? Because that is still Alpha and not stable, also missing some things. How did your project turn out?

I am currently also trying to do a turn based hex strategy game, and the pathfinding is giving me a headache as well. ;)

---

I used the 2.1 branch of cefleet's hex module: https://github.com/cefleet/HexModule/tree/2.1.3_legacy

And the godot AStar module: http://docs.godotengine.org/en/stable/classes/class_astar.html

I used this video to learn how to use the AStar module https://www.youtube.com/watch?v=Hjn8bS4mW8A, and this video to learn how to use AStar with cefleet's hex module https://www.youtube.com/watch?v=wpzoCShnfbI, with the code here as a reference https://github.com/cefleet/GodotAstarTutorial

Answer 2

Supplemental: Here's a terrific resource that covers everything related to hex maps (different types of coordinate systems, A* search pathfinding with obstacles, and so on:

https://www.redblobgames.com/