Support hexagonal cells in `GridMap`

[BSChad]

This adds support for hexagonal grids in the GridMap node with the same offset and layout semantics as TileMap.

This is a rebase of the latest master for https://github.com/godotengine/godot/pull/59842. There was minimal editing outside of updating to the proper 4.2+ API, and using the new naming convention introduced in master. (IE: world_to_map and map_to_world to local_to_map and map_to_local).

Performed functional testing with a hex MeshLibrary.

Closes https://github.com/godotengine/godot-proposals/issues/4337. Based on discussion, it wouldn't be too hard to remove the Layout and Offset Axis options, though they seem to work just fine.

[BSChad]

Fixed argument prefix issues and added some out of range checks for properties. I had, apparently, forgotten to force push the changes to the function names to change world_to_map to local_to_map. Pushed those as well.

[BSChad]

Fixed a case of a function modifying the argument in draw_plane, instead storing calculated axis' in a new local.

[AThousandShips]

You have more whitespace issues, you can run clang locally to fix these, see here

[BSChad]

I was looking for the clang-format doc! Saw it once and then couldn't find it again, thanks @AThousandShips. Ran clang-format on the four files and added documentation.

[berkeleynerd]

Hoping this is supported in 4.3!

[AThousandShips]

@berkeleynerd Please don't bump without contributing significant new information. Use the :+1: reaction button on the first post instead.

[gulagkulak]

I'm really looking forward to this feature. Any chance of getting it merged?

[BSChad]

I'm really looking forward to this feature. Any chance of getting it merged?

I think we're just waiting for a review (perhaps another rebase) and then enough people to show that this is a use-case they want to use in their shipping game!

I plan to release my game on a custom build of the engine because I need this feature. Would love to join back up with a major version on trunk if it gets merged!

[nikoladigi]

I am waiting for this, for my board game project! Currently developing logic in 2d tilemap, but want it to be in 3D. Great Work!

I have build it, but I have noticed a small issue, that hex tiles are not scaled properly

It can be fixed, by setting z size to 1.1 in editor. There are plenty of use cases and potential games that can be made with this feature.

edit: @BSChad One suggestion to consider in order for this to be "proper" hex implementation is to add an option to chose between "Flat-Topped" and Pointy-Topped Hex

[BSChad]

I am waiting for this, for my board game project! Currently developing logic in 2d tilemap, but want it to be in 3D. Great Work!

I have build it, but I have noticed a small issue, that hex tiles are not scaled properly

It can be fixed, by setting z size to 1.1 in editor. There are plenty of use cases and potential games that can be made with this feature.

Interesting. I'll have to recheck the original math here from octetdev. Hopefully something simple.

edit: @BSChad One suggestion to consider in order for this to be "proper" hex implementation is to add an option to chose between "Flat-Topped" and Pointy-Topped Hex

Isn't that what the Offset Axis is? You can choose between Horizontal and Vertical.

[IkutiDev]

Looks great! Would love it to be merged in not too distant future.

But I have found 1 possible bug. When changing cell size in gridmap from 1:1:1, placing the tiles with the mouse has issues. It's like there is an offset and the place where the tile is placed is in another tile.

I have checked this on 4.2.1 stable and everything works correctly there when changing size to 2:1:2 or 3:1:3. This issue also happens on this branch no matter if shape is hexagon or square, so it would cause the issue to happen to the old grid maps as well.

[BSChad]

It can be fixed, by setting z size to 1.1 in editor. There are plenty of use cases and potential games that can be made with this feature.

I was just double checking all of the math here on this, but isn't that theoretically correct? Since the tiles are not actually square when laid out, if you have the points on top it would actually be longer in the z axis while the x axis would be slightly shorter. (The Inner Radius would be measured to the corners, so you can imagine a straight line from the center to the middle of a side would be shorter, right?)

This uses the same placement math in those axes as the 2d TileMap hex implementation. Is it the same way for tilemap?

[BSChad]

Looks great! Would love it to be merged in not too distant future.

But I have found 1 possible bug. When changing cell size in gridmap from 1:1:1, placing the tiles with the mouse has issues. It's like there is an offset and the place where the tile is placed is in another tile.

I have checked this on 4.2.1 stable and everything works correctly there when changing size to 2:1:2 or 3:1:3. This issue also happens on this branch no matter if shape is hexagon or square, so it would cause the issue to happen to the old grid maps as well.

I found and fixed an issue where there would be a phantom offset when changing the tile size to be larger. The placement code uses almost a straight copy of the tile_set.cpp code but wasn't accounting for the hex grid's center / offset property.

[dmlary]

I was excited to try this PR out, so I pulled and built it. I encountered an issue where the y-rotation shortcut S is not taking into account that we're using hexes not squares. As a result, the tile is being rotated 90 degrees instead of 60. See attached video.

https://github.com/godotengine/godot/assets/857742/926b6f4a-febf-45a2-aed6-f4a1d802f874

[dmlary]

The drag & fill gizmo is also not aligning correctly to the initial click, but the filled area does match the dragged region. Not sure if it's directly related to the changes in this PR. I will say that it happens both for hex and square gridmaps.

hex drag & fill:

https://github.com/godotengine/godot/assets/857742/3865c0ce-3044-4e42-8845-28e13d3ff091

square drag & fill:

https://github.com/godotengine/godot/assets/857742/17087ab8-fa31-4886-8695-ec1fda19614a

[dmlary]

I was excited to try this PR out, so I pulled and built it. I encountered an issue where the y-rotation shortcut S is not taking into account that we're using hexes not squares. As a result, the tile is being rotated 90 degrees instead of 60.

I took a stab at fixing this issue, and it doesn't appear to be a simple fix. Even if we correctly calculate the rotation amount based on the cell shape, the cursor is still rotated in 90 degree increments.

modules/gridmap/editor/grid_map_editor_plugin.cpp
@@ -94,16 +95,18 @@ void GridMapEditor::_menu_option(int p_option) {
 		} break;
 		case MENU_OPTION_CURSOR_ROTATE_Y: {
 			Basis r;
+			float rotation = node->get_cell_shape() == GridMap::CELL_SHAPE_SQUARE ? (Math_PI / 2.0) : (Math_PI / 3.0);
+
 			if (input_action == INPUT_PASTE) {
 				r = node->get_basis_with_orthogonal_index(paste_indicator.orientation);
-				r.rotate(Vector3(0, 1, 0), -Math_PI / 2.0);
+				r.rotate(Vector3(0, 1, 0), -rotation);
 				paste_indicator.orientation = node->get_orthogonal_index_from_basis(r);
 				_update_paste_indicator();
 				break;
 			}
 
 			r = node->get_basis_with_orthogonal_index(cursor_rot);
-			r.rotate(Vector3(0, 1, 0), -Math_PI / 2.0);
+			r.rotate(Vector3(0, 1, 0), -rotation);
 			cursor_rot = node->get_orthogonal_index_from_basis(r);
 			_update_cursor_transform();
 		} break;

I dug into the cursor code, and it looks like the deeper issue is that the GridMap has a set of hard coded basis' to represent the 24 possible orientations of a cube: https://github.com/godotengine/godot/blob/cff016d6dd2aa3345c1e6bcc0c49477c40488f97/modules/gridmap/grid_map.cpp#L436-L461

The cursor rotation works by getting the cursor orientation (an index into that Basis array), looking up the Basis (GridMap::get_basis_with_orthogonal_index()), rotating that Basis by some amount, then looking up the nearest Basis in that array and returning a new orientation index (GridMap::get_orthogonal_index_from_basis()).

There are no Basis' added for hexagon shapes in this PR. We need those, along with changes to GridMap::get_basis_with_orthogonal_index() and GridMap::get_orthogonal_index_from_basis() to support rotating hex tiles.

I can figure out what those hex basis' should be if you need a hand.

[dmlary]

Alright, I apparently can't stop playing with this. GridMap with hexes is very fun and exactly what I need, so I figured out a solution to the tile rotation problem. I forked this pr and added my commits on top. In this commit tile rotation works. We can do 60 degrees around the y-axis, and 180 around x & z. A lot more details in the commit message.

https://github.com/dmlary/godot/commit/1b9448d2d13f265a00e240d24642572611af8839

[dmlary]

Ran into another issue with the PR. Threw together a small hex-based GridMap, and some code for hex cell picking using cursor raycasting. Right now GridMap.local_to_map() is returning a number of different Cell values for multiple points within a hex cell. This means we cannot accurately get the the cell index based on position.

For every point within a hex cell, GridMap.local_to_map() should return the exact same value. In the following video, I run the cursor around the top of a hex cell, showing that the X value of the cell returned by GridMap.local_to_map() is different in the lower right hand corner than the rest of the cell (2 in the lower right, 1 everywhere else). My guess is that the the cell's Z size isn't being taken into account, but I need to look deeper.

https://github.com/godotengine/godot/assets/857742/6509c67a-ced4-4d05-8924-e4dedc56baac

This is the code I'm using to do the raycast and cell lookup. I've dug through it a number of times, and the code works correctly with the square cell shape.

func _process(delta: float) -> void:

	var mouse_pos: Vector2 = get_viewport().get_mouse_position()
	raycast.target_position = project_local_ray_normal(mouse_pos) * 100.0
	raycast.force_raycast_update()

	if raycast.is_colliding():
			var collider = raycast.get_collider()
			if collider is GridMap:
				var collison_point = raycast.get_collision_point()
				var local = collider.to_local(collison_point)
				var cell = grid_map.local_to_map(local)
				var item = grid_map.get_cell_item(cell)
				label.text = "collision %s\nlocal %s\ncell %s\nitem %d" % [ collison_point, local, cell, item]
				label.position = collison_point
				label.position.y += 0.1

[BSChad]

Alright, I apparently can't stop playing with this. GridMap with hexes is very fun and exactly what I need, so I figured out a solution to the tile rotation problem. I forked this pr and added my commits on top. In this commit tile rotation works. We can do 60 degrees around the y-axis, and 180 around x & z. A lot more details in the commit message.

dmlary@1b9448d

Can pull this into my repo. Thanks for messing around with this. I'm super focused on a deadline for a client so I'm slower getting this feedback incorporated!

It's awesome to see folks digging into this. Hopefully enough to get it in a good spot and feel like a worthwhile merge into master!

Ran into another issue with the PR. Threw together a small hex-based GridMap, and some code for hex cell picking using cursor raycasting. Right now GridMap.local_to_map() is returning a number of different Cell values for multiple points within a hex cell. This means we cannot accurately get the the cell index based on position.

Whoa, love the way you visualized it! I had the log printing on a separate window and it was tedious! I haven't dug too deeply, but I think the main issue is that we're not getting the in_top_left_triangle / right triangle check passing.

// Compute the tile offset, and if we might the output for a neighbor top tile.
Vector2 in_cell_pos = Vector2(raw_pos.x - map_position.x, raw_pos.z - map_position.z);
bool in_top_left_triangle = (in_cell_pos - Vector2(0.5, 0.0)).cross(Vector2(-0.5, 1.0 / overlapping_ratio - 1)) <= 0;
bool in_top_right_triangle = (in_cell_pos - Vector2(0.5, 0.0)).cross(Vector2(0.5, 1.0 / overlapping_ratio - 1)) > 0;

For some reason while a tile_set with an oblong tile_size uses this same code and works correctly, for some reason this is still only detecting the square boundaries and not correctly offsetting the selecting if it's in the top left / top right overlap. It was off by more before I subtracted the offset from the incoming position, but it's still not quite right despite normalizing the input by dividing by the cell_size. You may try adding your in_cell_position here to that debug output to see what is happening.

I believe, if you look closely, what you're seeing in your video is that the cell is bouncing because it is thinking it is in the tiles below at first because the point is low enough that the broken topleft / topright parts that overlap are not being checked correctly and always defaulting to the lower tile.

[BSChad]

The drag & fill gizmo is also not aligning correctly to the initial click, but the filled area does match the dragged region. Not sure if it's directly related to the changes in this PR. I will say that it happens both for hex and square gridmaps.

hex drag & fill:

drag-and-fill-hex.mov square drag & fill:

drag-and-fill-square.mov

I bet this one is also because the offset is not being used. (Just looking at the diff.) Probably need to apply that at the end of the map_to_local.

[dmlary]

I believe, if you look closely, what you're seeing in your video is that the cell is bouncing because it is thinking it is in the tiles below at first because the point is low enough that the broken topleft / topright parts that overlap are not being checked correctly and always defaulting to the lower tile.

There is some of that bouncing, but that impacts the Cell's y coordinate in that video; it shouldn't be the cause of the change in x that happens independent of that y change.

I'll look deeper at the top_left/bottom_right code you included above for cell bounding boxes. At first glance, I'm curious if this is significantly more complicated than it needs to be. I need to dig deeper, but I think instead of treating this as standard (x, y, z) indexing (which it appears to be), the code needs to use axial coordinate system (https://www.redblobgames.com/grids/hexagons/#coordinates-axial), and adding the layer as the third value. This makes hex grid mapping (q, r, z) representing a mathematically specific hex region instead of mapping a cube coordinate (x, y, z) and adjusting overlaps by hand.

I'm going to dig deeper into this to see if my understanding is correct.

[dmlary]

Ok, the code is vastly simplified (with the exception of maths) when I remove all of the layout options and use the axial coordinate system along with the level for hex indexes. I've confirmed that changing the index scheme resolves the cell lookup problem, and added test cases in to confirm it without needing to build a test project.

One piece of functionality that was lost was the ability to have irregularly shaped hexagon cells. So longer on one side (not axis) than another. The math used for the axial coordinate system depends on the hexagons being regular (all sides of equal length). I don't think this is widely needed functionality.

I'm going to continue down this trimming path and remove the offset axis option also. I started adding the support for it back into my branch, and it started getting ugly. Keep in mind you can easily swap from pointy orientation to flat orientation by rotating the gridmap 30 degrees. I don't think this capability needs to be built directly into GridMap, and looking at past comments, this seems to be in line with past conversations.

I'll update when I get my branch cleaned up and pushed.

[dmlary]

Alright, those changes are in, and pushed to https://github.com/dmlary/godot/commit/6912c0b4759199aba24879846d6ff7a4e981cb5a

Those changes include unit tests to verify local_to_map() functions correctly for the corners and edges of the cells.

Here's a video of the test project showing local_to_map() working correctly for the boundaries of the hex cells. The y coordinate still jumps, but that's due to raycast rounding errors.

https://github.com/godotengine/godot/assets/857742/709e892e-d84d-4a58-88ae-6604af2ca88a

[dmlary]

One more push to support the Center-Y option. At this point things are working well both for top-down and fps usage with collider shapes. It's very fun to play with.

https://github.com/godotengine/godot/assets/857742/007545a1-968c-4bd5-b347-a936cc9ba3bc

The last few issues I've seen are:

• grid gets out of sync with editor level
• selection is still very broken

[dmlary]

Fixed the floor grid sync issue. It's pushed to my branch.

That said there's more work to be done in the grid area. With the code in this PR (without my changes), editing on the Z-axis causes tiles to be places in a zig-zag pattern, while editing on X-axis lines up. For both of these, the editor grid does not line up well with the cells.

Z-axis:

X-axis:

For editing levels, it makes sense to have a user-experience more like what we see in the X-axis. All cells line up flat side to flat side. We obviously cannot do this on the Z axis as the cells along this axis are not lined up face to face, but vertex to edge (see diagram below). We can however get an equivalent grid editing experience if we use two different diagonal axis instead of the Z axis. If we use the Q-axis (northwest to southeast), and the S-axis (northeast to southwest), we're able to draw contiguous lines of cells edge to edge. (Note, the R-axis in the diagram below is the X-axis; that's why the lettering jumps).

This would mean there are four axises we can edit hex-grids on: Y-axis (top-down), Q-axis (northwest-southeast), R-Axis/X-Axis (east-west), and s-axis (northeast-southwest).

I'm going to poke at this and see if I can:

• Fix the grid alignment for x-axis editing
• Add Q/R/S axis only available with hex mode

[BSChad]

@dmlary Looks awesome and these updates are exciting!

The only thing I worried about with axial co-ordinates is how well it'll play with the built-in path-finding and nav mesh systems that Godot provides.

(Personally, in my project, I'm not using the built-in nav mesh and simply using the AStar2D, so I can just use q & r, I think.)

[dmlary]

The only thing I worried about with axial co-ordinates is how well it'll play with the built-in path-finding and nav mesh systems that Godot provides.

I'll throw pathfinding and AStar3d scenes into my test project to confirm they work.

in my project [...] using the AStar2D, so I can just use q & r

In all honesty, regardless of the internal coordinate system used, GridMap should provide some mechanism for determining cell neighbors (among other things). As it stands in 4.2.2, every project that maps a GridMap to an AStar2D/AStar3D, or procedurally generates a level, they explicitly duplicate the internal coordinate system of the GridMap. That's a lot of code that already exists in GridMap, but isn't exposed.

The minimal change approach for this would be Vector3i GridMap.map_neighbor(Vector3i cell, GridMap::Direction neighbor_direction). Given one cell's coordinates, get the coordinates of a cell in the given direction, with GridMap::Direction being an enum.

What I'd rather see is GridMap returning a GridMap::CellIndex that provides the same methods as Vector3i, but adds the helper methods for neighbor traversal, distance calculation, etc. That way you can do things like:

# moving player in GridMap::Direction
var vector = ... # some axis input
var direction = grid_map.direction_from_vector(vector)
var dest = grid_map.local_to_map(position).neighbor(direction)
var contents = grid_map.cell_item(dest)

# Apply an AOE affect to all cells within 3 cells of the selected point
var center = grid_map.local_to_map(selected_point);
for cell in center.within_range(3):
    apply_affect(grid_map.map_to_local(cell))

This change probably does not fit in this PR as it touches gdscript (introducing a direction type), and affects the square GridMap implementation. But I will look at ways to allow users to navigate the coordinate system easily.

[dmlary]

Making progress on hex selection. I fixed the issue where selection on hex grids was significantly offset. Once that was working, I switched the selection style from one big cube to per-tile selection to be able to visualize where the selection box will fall along the Z axis. Still working on this to add the outlines to the cell mesh.

https://github.com/godotengine/godot/assets/857742/8c8b7ceb-095a-4a5d-917b-69081c8f81c6

[dmlary]

Duplicating a cell selection, with rotation is now working for hex cells.

https://github.com/godotengine/godot/assets/857742/ca8479a3-e32b-4fc5-9ed2-b7156f0f3a9f

Updates:

• GridMap: Add local_region_to_map() to get a TypedArray of cell indexes within given bounding box
• GridMap: Added cell_shape_changed signal to GridMap
• GridMapEditor: Update grid floor when cell shape changes
• GridMapEditor: Add cell shape mesh for hex tiles
• GridMapEditor: Update tile selection mesh when cell shape changes
• GridMapEditor: update fill selection for hex shaped cells
• GridMapEditor: update clear selection for hex shaped cells
• GridMapEditor: paste indicator working for hex shaped cells
• GridMapEditor: paste working for hex shaped cells

TODO:

• GridMapEditor: select after paste (Paste Selects option) results in non-pasted cells being selected on hex-shaped cells
  • Maybe change selection storage to contain a set of cell indices instead of an AABB
• GripMapEditor: Improve indicators around select & paste indicators
  • outline each cell? PRIMITIVE_LINES
    • don't see method on BoxMesh or CylinderMesh to get lines
    • don't wanna have to write the coords myself for each cell shape, but may be required
  • tried material changes, but nothing worked as well as an outline
• GridMapEditor: Add Q/R floor axis for hex-shaped cells
• GridMap: Add neighbor helpers
• GridMap: Add pathfinding demos in hex test project
  • AStar3d based
  • Navmesh based

I did run across a bug in the existing implementation (4.2.2, without this PR) where if the tile mesh uses points with y < 0, the mesh will clip through the floor. This is because the paste indicator is using the mesh directly, and not taking into account any MeshInstance transform that may have been bundled up with the tile. I'm leaving it for now because I don't really know how to find that data.

[dmlary]

Pushed Q/R/S axis editing: https://github.com/dmlary/godot/tree/hexgrid

https://github.com/godotengine/godot/assets/857742/484dc061-63fb-4159-87a5-7cb8dbf7aea1