67

To summarize and elaborate upon what has been said in other answers and in comments, triangles, squares and hexagons are the only mathematically possible regular tilings aka regular tessellations of the Euclidean plane. So yeah, this sucks. Triangles are completely useless here, squares suck because you can't move diagonally without having a somewhat ...


29

The author of HyperRogue here. HyperRogue actually uses a tesselation made of hexagons and heptagons, here is the reason why this particular tesselation has been chosen, instead of only octagons or heptagons, for example: Hyperbolic geometry in Hyperbolic Rogue Basically, the octagons are too big. Also some consequences of using hyperbolic geometry in a ...


16

No. √3 is an irrational number, and by definition an irrational number can not be used as a ratio between two natural numbers (integers) such as pixel counts. However, there is no rule that says you have to use ideal hexagons in your game tiles. If you approximate it closely and avoid any miscalculations that may result, which you should be able to do ...


12

There are many hex coordinate systems. The “offset” approaches are nice for storing a rectangular map but the hex algorithms tend to be trickier. In my hex grid guide (which I believe you've already found), your coordinate system is called “even-r”, except you're labeling them r,q instead of q,r. You can convert pixel locations to hex coordinates with these ...


11

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 elements. Whenever you add an element to the territory, you iterate over adjacent tiles and see if they should be a border tile; in this case, they are a border ...


11

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 interpolate \$d^2\$ gradient vectors per evaluation, so going from 2 dimensions to 5 means doing 8x more work. More distortion: by evaluating it on a membrane in higher-...


9

There are two ways to handle this problem, in my opinion. Use a better coordinate system. You can make the math much easier on yourself if you're clever about how you number the hexes. Amit Patel has the definitive reference on hexagonal grids. You'll want to look for axial coordinates on that page. Borrow code from someone who has already solved it. I ...


9

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 consider the definitive guide to using hexagonal grids in games. This guide uses the nomenclature: flat topped pointy topped So while it's not super ...


9

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 that we need to count, so we need to look at every tile in the area bounded by the territory's outline at least once to be sure we've found all the holes. But ...


7

As long as your movement space isn't Euclidean and things can block an entire grid space, you'll have this problem. If you want people to not "play the grid" you're probably going to have to not use a grid.


7

I'd consider a Square-based grid as a "base" type of tiles in any game. Such grid is simple to imagine and moves over this grid are simple to understand. It's also very simple to implement "under the hood". Those are few reasons why even the Chess game uses it :). Additionally, this grid helps you make "regular" levels, because Vertical and Horizontal are ...


7

As Vector57 noted, the problem is you are using the wrong coordinate system. The algorithm described is meant to be used with cube coordinates, which have x, y and z components: This may not be obvious from the algorithm's pseudocode, but that's because it's a simplification of this: var results = [] for each -N ≤ dx ≤ N: for each -N ≤ dy ≤ N: ...


7

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 on the whole map, only on what is visible. It is easy to run this query in parallel. In fact, I could image some shader code that does this. And if you need it ...


7

This is most intuitive way that I can think of.


6

I think Michael Kristofik's answer is correct, especially for mentioning Amit Patel's website, but I wanted to share my novice approach to Hex grids. This code was taken from a project that I lost interest in and abandoned written in JavaScript, but the mouse position to hex tile worked great. I used * this GameDev article * for my references. From that ...


6

The logic is simple: your contour is the set of all the edges that separate border tiles from non-border tiles. You can code the following: for each boundary tile for each edge if edge is shared with a hex tile that is NOT in the boundary tile list mark as contour edge render all contour edges Note that if you want the contour to ...


6

(I don't have enough reputation to comment) The answer here is that the distances are wrong. A is closer than B. To convince yourself, compare A and the reflection of B w.r.t. the player, so I don't think there is an issue here. Hex grids are tricky in a lot of ways.


5

All three uniform 2D grids can be stored in a rectangular grid, you just have to scale and shear it to fit the one you're aiming for. To know what regions you need to load just transform the viewport extents to the data's coordinate system.


5

Can't comment yet, so I'll give answer short answer. From my experience, square tiles are a little simpler to implement. If you are using e.g. a two-dimensional array, tile position is array index multiplied with tile size (at least that's what it boils down to). Finding neighboring tiles is as simple as adding one to the index (and maybe wrapping the value ...


5

Thanks for a fascinating puzzle! Yes, it looks like we can do better than a conversion through cartesian coordinates of hexagon centers. It can be done entirely with integer math, though I've included a rational in a matrix below to keep the notation concise. You're right that both the encoding and decoding processes require loops. Fortunately, because SHM ...


5

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 vertices between those edges: __ / \ <3 \__/ <2 ^ 1 We only store three edges and two vertices, so where do the others come from? Well, continuing ...


4

Amit Patel has provided an excellent resource for getting ranges on his site. In the article, he uses the following algorithm for collecting hex tiles within a range: for each -N ≤ Δx ≤ N: for each max(-N, -Δx-N) ≤ Δy ≤ min(N, -Δx+N): Δz = -Δx-Δy results.append(H.add(Cube(Δx, Δy, Δz))) This creates bounds aligned with the hex grid: ...


4

Pieter Geerkens (who is here on stackexchange) has a C# library for hexagons.


4

I actually found a solution without hex math. As I've mentioned in the question each cell saves it own center coords, by calculating the nearest hex center to the pixel coords I can determine the corresponding hex cell with pixel precision (or very close to it). I don't think it is the best way to do it since I have to iterate to each cell and I can see how ...


4

You can just apply A*( A-star ). Compared to a uniform square grid the only difference is the way you collect the adjacent tiles ( aka your hexagons ). Each tile should have a table of booleans representing the bridges corresponding to their direction like so //Depending on your hexagon order enum Direction{ NORTH, NORTH_EAST, SOUTH_EAST, ...


4

Just in case anyone is interested: Lets assume sqrt(3) is rational: Therefore, there must be two integral numbers a and b such that a/b = sqrt(3) We assume these numbers are coprime, if they have a common factor, we divide by it producing a coprime pair, a and b We know that (a/b)^2 = 3 and therefore a^2 = 3 * b^2. 3 * b^2 is devisible by 3 as b^2 is ...


4

So upon further inspection your problem actually has nothing to do with coordinate system conversions. This could have been made more clear by not naming your axial coordinates X and Y but rather Q and R. The problem you're actually having is bad loop conditions. The original code sample produces delta q's and r's which you try to convert, in your for loops, ...


4

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 observation: if you're using the 3-valued “cube” coordinates, the largest coordinate tells you which of the six “wedges” you're in. Here's a diagram showing the ...


4

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 sphere to another they distort in different ways. In general there's no rotation that will align a regular source hexagon with a given tile perfectly. But, there ...


4

The condition part of the for-loop tells the loop when to stop looping. This is different from the continue statement that just skips the rest of the current step and moves on to the next. Consider the following loop; for(i = 0; i < 10; i += 1) { if (i % 2 == 0) continue; // Skip even indices // Do stuff } If you were to extract the ...


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