Add pathfinding support for hexagonal tilemaps to AStarGrid2D

[airs1991]

Describe the project you are working on

Turn-based strategy game similar to Civilization

Describe the problem or limitation you are having in your project

I'm trying to use astargrid2d as a built-in tilemap pathfinding scheme, which is more convenient than astar2d, but cannot support hexagonal tilemaps.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Currently astargrid2d does not return correct paths in hexagon based tilemaps. It is hoped that after improvement, the hexagonal tilemap can directly select the hexagon through CellShape to get a native matching pathfinding system.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Support for hexagons by updating the built-in _compute_cost, _estimate_cost methods and CellShape enumeration.

If this enhancement will not be used often, can it be worked around with a few lines of script?

It can be solved by using astar2d instead of astargrid2d, but it is more troublesome. Pathfinding based on tilemap coordinates should be more performant.

Is there a reason why this should be core and not an add-on in the asset library?

As a built-in function, hexagonal tilemap should match the corresponding astargrid2d.

[Calinou]

• Related to https://github.com/godotengine/godot-proposals/issues/4337.

[markshumarov]

I also faced this problem. AStarGrid2D doesn't work properly with hex-gid obstackles. I guess it is because it doesn't have cell_shape for hexes.

https://github.com/godotengine/godot-proposals/assets/66621386/d8af8ce9-b692-45e2-b626-dd45673cf3aa