Skip to main content
Share Your Experience: Take the 2024 Developer Survey
11 votes
Accepted

Efficient Algorithm for the boundary of a set of tiles

Finding an algorithm is usually best done with a data structure that makes the algorithm easy. In this case, your territory. The territory should be an unordered (O(1) hash) set of borders and ...
Yakk's user avatar
  • 371
11 votes
Accepted

How can I create a six sided tillable perlin noise image?

I don't recommend using the "increase the dimensions and orbit in a cylinder" trick here. It has several disadvantages: More expensive to compute: Perlin noise needs to select and ...
DMGregory's user avatar
  • 135k
9 votes
Accepted

Are there definitive, unambiguous terms for hexagon tile orientations?

While I don't know of any truly official convention for classifying these, in the mathematical sense, I'll take Anko's advice and write up what I do know... Amit Patel (Red Blob Games) wrote what I'd ...
DMGregory's user avatar
  • 135k
9 votes

Efficient Algorithm for the boundary of a set of tiles

If you need to find edges of holes in the middle of your territory too, then your linear in the area of the territory bound is the best we can do. Any tile on the interior could potentially be a hole ...
DMGregory's user avatar
  • 135k
7 votes

Efficient Algorithm for the boundary of a set of tiles

Notice: Whether or not a tile is on the boundary only depends on it and its neighbors. Because of that: It is easy to run this query lazily. For instance: You do not need to search for the boundary ...
Theraot's user avatar
  • 27k
7 votes
Accepted

How do I sort edge tiles for a hex grid in order to draw a border?

The usual approach here is to pretend like you're solving a maze blindfolded: keep your left hand in contact with the wall, and follow its contours until you reach the exit (or in this case, until you ...
DMGregory's user avatar
  • 135k
7 votes

Elegantly transition from 4-grid to 6-grid and back

This is most intuitive way that I can think of.
Shadows In Rain's user avatar
6 votes
Accepted

Finding all hexagonal grid coordinates inside cover arc

I prefer to do hex-cell coordinate math in what Amit calls cubical coordinates on your linked page. For the rest of this answer, (X, Y, Z) will refer to cubical coordinates. Basically, for any of ...
Jimmy's user avatar
  • 9,019
6 votes
Accepted

Find a encircliement in Hexagonal grid (optimization issue)

1. Optimize Needlessly Slow Operations Your basic approach should work well on small to medium maps, it's just that the way you've chosen to implement it is unnecessarily slow: You search the same ...
DMGregory's user avatar
  • 135k
5 votes

How to efficiently (no pointers) store hex grid with shared edges and vertices?

Assuming you have Hex objects stored in a 2d array, just make each Hex own some of its edges and vertices. For example, have each hex own the edges with arrows pointing to them as well as the two ...
Max's user avatar
  • 151
5 votes

How do I sort edge tiles for a hex grid in order to draw a border?

I see you already have an answer to your question, but I'm going to add another answer for anyone who's trying to solve a simpler variant of the question. Civilization puts borders between hex tiles ...
amitp's user avatar
  • 6,046
4 votes
Accepted

What is the easiest way to move towards and along the edge on a hex grid?

I think it'll be easier to solve this if you move one step at a time instead of one-or-two. For each location on the map there's a single direction to move in. Let's calculate that direction. First ...
amitp's user avatar
  • 6,046
4 votes

Creating a hexagonal wraparound map

Here's a demo of a wraparound hexagonal map. Use the QWEASD keys to move around: ...
Aadit M Shah's user avatar
4 votes
Accepted

Creating a hexagonal wraparound map

Here's a simple method which does not become more complex as the map grows in radius: Keep a list of the center coordinates of your main map (0, 0, 0), and its 6 shifted copies. After a move that ...
DMGregory's user avatar
  • 135k
3 votes
Accepted

How do I calculate hex coordinates from a ring and index?

First, let's define a standard ordering of basis vectors to use. These are the offsets to each of the six hexes in the closest ring around our center, in clockwise order from top-left. ...
DMGregory's user avatar
  • 135k
3 votes

Moving a continue condition into the for loop produced something NOT logically equivalent?

The condition part of the for-loop tells the loop when to stop looping. This is different from the continue statement that just ...
bornander's user avatar
  • 4,491
3 votes
Accepted

How to orient a hexagonal tile on a geodesic sphere (Goldberg polyhedron)?

As I mentioned above, there won't be a perfect solution here, because the hexagons that make up a Goldberg polyhedron tend to be irregular and non-congruent with each other. From one part of the ...
DMGregory's user avatar
  • 135k
2 votes

Get ring of tiles in hexagon grid

I have found this article to be a very good reference for hexagonal grid algorithms, and its section on "Distances" provides a method for determining the number of steps between two tiles. If you ...
KPM's user avatar
  • 161
2 votes

Showing range on hexagonal grid

In case anyone needs it, here's the C# implementation of Patel's algorithm: ...
Allan Haugsted's user avatar
2 votes

Inconsistent movement / line-of-sight around obstacles on a hexagonal grid

The mistake in this post was treating any red line that crosses a hex as being equal. Those red lines are not all the same length in the Euclidean space of the player's screen (ignoring the grid). If ...
DMGregory's user avatar
  • 135k
2 votes

How can I detect hex edges and corners for Catan map?

I recommend reading this blog. Assuming you know the middle point coordinate and the width of every hexagon, from the linked blog you can easily calculate corner points. It is essential to know ...
Cedric Martens's user avatar
2 votes
Accepted

Moving a continue condition into the for loop produced something NOT logically equivalent?

The difference is that continue only skips forward one step and the condition ends the whole loop. To me it seems like the issue is, that you try to fit both the starting point and the end point into ...
mmmd's user avatar
  • 131
2 votes

Place hexagons together

Just fixed by doing the X coordinate with $x = $hexagon->ver + $i * $hexagon->size * 1.5; Looks beautiful now.
Enrique Benitez's user avatar
2 votes

Subdivided Icosahedron Hex/Pent grid efficient rendering?

First question that comes to mind: does the hex-planet change a lot during gameplay? If the planet is mostly static, and just the inhabitants on it move around a lot, I would definitely not render the ...
Bram's user avatar
  • 3,719
2 votes
Accepted

Get range of hexagon based on specified center

Found a better way to do by moving a cursor N times. ...
Enrique Benitez's user avatar
2 votes
Accepted

How to convert game object world position to hex grid cell coordinates?

Maybe this useful and complete article may help you : https://www.redblobgames.com/grids/hexagons/ There's 4 different possibilities for implementing an hexagrid. Depending on your "offset ...
Fabrice Bernard's user avatar
2 votes

How to orient a hexagonal tile on a geodesic sphere (Goldberg polyhedron)?

Updated: to show my final result. This answer is actually my implementation of the answer provided by @DMGregory above. For the most part, I found that answer worked very well, so I thought it ...
PKCLsoft's user avatar
  • 225
2 votes
Accepted

How can I seamlessly animate textures across tiles like in Civilization 6?

I don't know how Civ6 does it. But this is how I would do it: A height map is generated based on the tile information; this could be a simple version (a tile could be represented by 1 pixel in that ...
Felsir's user avatar
  • 4,067
2 votes

Efficient Algorithm for the boundary of a set of tiles

Move your area up one tile, then up-right, then down right, etc.. Afterwards remove the original area. Merging all six sets should be O(n), sorting O(n.log(n)), set difference O(n). If the original ...
tommsch's user avatar
  • 121
2 votes
Accepted

Calculate size of hexagonal map libgdx

The height of each individual hexagon is 84px including shadow but the shadow only matters for the last row. So we need to know the size without shadows. I believe the height of the hexagon without ...
amitp's user avatar
  • 6,046

Only top scored, non community-wiki answers of a minimum length are eligible