1 # Copyright 2023 highstreet technologies GmbH
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # inspired by http://www.redblobgames.com/grids/hexagons/
19 from __future__ import division
20 from __future__ import print_function
24 Point = collections.namedtuple("Point", ["x", "y"])
26 _Hex = collections.namedtuple("Hex", ["q", "r", "s"])
30 assert not (round(q + r + s) != 0), "q + r + s must be 0"
35 return Hex(a.q + b.q, a.r + b.r, a.s + b.s)
38 def hex_subtract(a, b):
39 return Hex(a.q - b.q, a.r - b.r, a.s - b.s)
43 return Hex(a.q * k, a.r * k, a.s * k)
46 def hex_rotate_left(a):
47 return Hex(-a.s, -a.q, -a.r)
50 def hex_rotate_right(a):
51 return Hex(-a.r, -a.s, -a.q)
64 def hex_direction(direction):
65 return hex_directions[direction]
68 def hex_neighbor(hex, direction):
69 return hex_add(hex, hex_direction(direction))
82 def hex_diagonal_neighbor(hex, direction):
83 return hex_add(hex, hex_diagonals[direction])
87 return (abs(hex.q) + abs(hex.r) + abs(hex.s)) // 2
90 def hex_distance(a, b):
91 return hex_length(hex_subtract(a, b))
98 q_diff = abs(qi - h.q)
99 r_diff = abs(ri - h.r)
100 s_diff = abs(si - h.s)
101 if q_diff > r_diff and q_diff > s_diff:
108 return Hex(qi, ri, si)
111 def hex_lerp(a, b, t):
113 a.q * (1.0 - t) + b.q * t, a.r * (1.0 - t) + b.r * t, a.s * (1.0 - t) + b.s * t
117 def hex_linedraw(a, b):
118 N = hex_distance(a, b)
119 a_nudge = Hex(a.q + 1e-06, a.r + 1e-06, a.s - 2e-06)
120 b_nudge = Hex(b.q + 1e-06, b.r + 1e-06, b.s - 2e-06)
122 step = 1.0 / max(N, 1)
123 for i in range(0, N + 1):
124 results.append(hex_round(hex_lerp(a_nudge, b_nudge, step * i)))
128 OffsetCoord = collections.namedtuple("OffsetCoord", ["col", "row"])
134 def qoffset_from_cube(offset, h):
136 row = h.r + (h.q + offset * (h.q & 1)) // 2
137 if offset != EVEN and offset != ODD:
138 raise ValueError("offset must be EVEN (+1) or ODD (-1)")
139 return OffsetCoord(col, row)
142 def qoffset_to_cube(offset, h):
144 r = h.row - (h.col + offset * (h.col & 1)) // 2
146 if offset != EVEN and offset != ODD:
147 raise ValueError("offset must be EVEN (+1) or ODD (-1)")
151 def roffset_from_cube(offset, h):
152 col = h.q + (h.r + offset * (h.r & 1)) // 2
154 if offset != EVEN and offset != ODD:
155 raise ValueError("offset must be EVEN (+1) or ODD (-1)")
156 return OffsetCoord(col, row)
159 def roffset_to_cube(offset, h):
160 q = h.col - (h.row + offset * (h.row & 1)) // 2
163 if offset != EVEN and offset != ODD:
164 raise ValueError("offset must be EVEN (+1) or ODD (-1)")
168 DoubledCoord = collections.namedtuple("DoubledCoord", ["col", "row"])
171 def qdoubled_from_cube(h):
174 return DoubledCoord(col, row)
177 def qdoubled_to_cube(h):
179 r = (h.row - h.col) // 2
184 def rdoubled_from_cube(h):
187 return DoubledCoord(col, row)
190 def rdoubled_to_cube(h):
191 q = (h.col - h.row) // 2
197 Orientation = collections.namedtuple(
198 "Orientation", ["f0", "f1", "f2", "f3", "b0", "b1", "b2", "b3", "start_angle"]
202 Layout = collections.namedtuple("Layout", ["orientation", "size", "origin"])
204 layout_pointy = Orientation(
206 math.sqrt(3.0) / 2.0,
209 math.sqrt(3.0) / 3.0,
215 layout_flat = Orientation(
218 math.sqrt(3.0) / 2.0,
223 math.sqrt(3.0) / 3.0,
228 def hex_to_pixel(layout, h):
229 M = layout.orientation
231 origin = layout.origin
232 x = (M.f0 * h.q + M.f1 * h.r) * size.x
233 y = (M.f2 * h.q + M.f3 * h.r) * size.y
234 return Point(x + origin.x, y + origin.y)
237 def pixel_to_hex(layout, p):
238 M = layout.orientation
240 origin = layout.origin
241 pt = Point((p.x - origin.x) / size.x, (p.y - origin.y) / size.y)
242 q = M.b0 * pt.x + M.b1 * pt.y
243 r = M.b2 * pt.x + M.b3 * pt.y
244 return Hex(q, r, -q - r)
247 def hex_corner_offset(layout, corner):
248 M = layout.orientation
250 angle = 2.0 * math.pi * (M.start_angle - corner) / 6.0
251 return Point(size.x * math.cos(angle), size.y * math.sin(angle))
254 def polygon_corners(layout, h):
256 center = hex_to_pixel(layout, h)
257 for i in range(0, 6):
258 offset = hex_corner_offset(layout, i)
259 corners.append(Point(center.x + offset.x, center.y + offset.y))
267 print("FAIL {0}".format(name))
270 def equal_hex(name, a, b):
271 if not (a.q == b.q and a.s == b.s and a.r == b.r):
275 def equal_offsetcoord(name, a, b):
276 if not (a.col == b.col and a.row == b.row):
280 def equal_doubledcoord(name, a, b):
281 if not (a.col == b.col and a.row == b.row):
285 def equal_int(name, a, b):
290 def equal_hex_array(name, a, b):
291 equal_int(name, len(a), len(b))
292 for i in range(0, len(a)):
293 equal_hex(name, a[i], b[i])
296 def test_hex_arithmetic():
297 equal_hex("hex_add", Hex(4, -10, 6), hex_add(Hex(1, -3, 2), Hex(3, -7, 4)))
299 "hex_subtract", Hex(-2, 4, -2), hex_subtract(Hex(1, -3, 2), Hex(3, -7, 4))
303 def test_hex_direction():
304 equal_hex("hex_direction", Hex(0, -1, 1), hex_direction(2))
307 def test_hex_neighbor():
308 equal_hex("hex_neighbor", Hex(1, -3, 2), hex_neighbor(Hex(1, -2, 1), 2))
311 def test_hex_diagonal():
312 equal_hex("hex_diagonal", Hex(-1, -1, 2), hex_diagonal_neighbor(Hex(1, -2, 1), 3))
315 def test_hex_distance():
316 equal_int("hex_distance", 7, hex_distance(Hex(3, -7, 4), Hex(0, 0, 0)))
319 def test_hex_rotate_right():
320 equal_hex("hex_rotate_right", hex_rotate_right(Hex(1, -3, 2)), Hex(3, -2, -1))
323 def test_hex_rotate_left():
324 equal_hex("hex_rotate_left", hex_rotate_left(Hex(1, -3, 2)), Hex(-2, -1, 3))
327 def test_hex_round():
328 a = Hex(0.0, 0.0, 0.0)
329 b = Hex(1.0, -1.0, 0.0)
330 c = Hex(0.0, -1.0, 1.0)
334 hex_round(hex_lerp(Hex(0.0, 0.0, 0.0), Hex(10.0, -20.0, 10.0), 0.5)),
336 equal_hex("hex_round 2", hex_round(a), hex_round(hex_lerp(a, b, 0.499)))
337 equal_hex("hex_round 3", hex_round(b), hex_round(hex_lerp(a, b, 0.501)))
343 a.q * 0.4 + b.q * 0.3 + c.q * 0.3,
344 a.r * 0.4 + b.r * 0.3 + c.r * 0.3,
345 a.s * 0.4 + b.s * 0.3 + c.s * 0.3,
354 a.q * 0.3 + b.q * 0.3 + c.q * 0.4,
355 a.r * 0.3 + b.r * 0.3 + c.r * 0.4,
356 a.s * 0.3 + b.s * 0.3 + c.s * 0.4,
362 def test_hex_linedraw():
373 hex_linedraw(Hex(0, 0, 0), Hex(1, -5, 4)),
379 flat = Layout(layout_flat, Point(10.0, 15.0), Point(35.0, 71.0))
380 equal_hex("layout", h, hex_round(pixel_to_hex(flat, hex_to_pixel(flat, h))))
381 pointy = Layout(layout_pointy, Point(10.0, 15.0), Point(35.0, 71.0))
382 equal_hex("layout", h, hex_round(pixel_to_hex(pointy, hex_to_pixel(pointy, h))))
385 def test_offset_roundtrip():
387 b = OffsetCoord(1, -3)
389 "conversion_roundtrip even-q",
391 qoffset_to_cube(EVEN, qoffset_from_cube(EVEN, a)),
394 "conversion_roundtrip even-q",
396 qoffset_from_cube(EVEN, qoffset_to_cube(EVEN, b)),
399 "conversion_roundtrip odd-q", a, qoffset_to_cube(ODD, qoffset_from_cube(ODD, a))
402 "conversion_roundtrip odd-q", b, qoffset_from_cube(ODD, qoffset_to_cube(ODD, b))
405 "conversion_roundtrip even-r",
407 roffset_to_cube(EVEN, roffset_from_cube(EVEN, a)),
410 "conversion_roundtrip even-r",
412 roffset_from_cube(EVEN, roffset_to_cube(EVEN, b)),
415 "conversion_roundtrip odd-r", a, roffset_to_cube(ODD, roffset_from_cube(ODD, a))
418 "conversion_roundtrip odd-r", b, roffset_from_cube(ODD, roffset_to_cube(ODD, b))
422 def test_offset_from_cube():
424 "offset_from_cube even-q",
426 qoffset_from_cube(EVEN, Hex(1, 2, -3)),
429 "offset_from_cube odd-q",
431 qoffset_from_cube(ODD, Hex(1, 2, -3)),
435 def test_offset_to_cube():
437 "offset_to_cube even-", Hex(1, 2, -3), qoffset_to_cube(EVEN, OffsetCoord(1, 3))
440 "offset_to_cube odd-q", Hex(1, 2, -3), qoffset_to_cube(ODD, OffsetCoord(1, 2))
444 def test_doubled_roundtrip():
446 b = DoubledCoord(1, -3)
448 "conversion_roundtrip doubled-q", a, qdoubled_to_cube(qdoubled_from_cube(a))
451 "conversion_roundtrip doubled-q", b, qdoubled_from_cube(qdoubled_to_cube(b))
454 "conversion_roundtrip doubled-r", a, rdoubled_to_cube(rdoubled_from_cube(a))
457 "conversion_roundtrip doubled-r", b, rdoubled_from_cube(rdoubled_to_cube(b))
461 def test_doubled_from_cube():
463 "doubled_from_cube doubled-q",
465 qdoubled_from_cube(Hex(1, 2, -3)),
468 "doubled_from_cube doubled-r",
470 rdoubled_from_cube(Hex(1, 2, -3)),
474 def test_doubled_to_cube():
476 "doubled_to_cube doubled-q", Hex(1, 2, -3), qdoubled_to_cube(DoubledCoord(1, 5))
479 "doubled_to_cube doubled-r", Hex(1, 2, -3), rdoubled_to_cube(DoubledCoord(4, 2))
484 test_hex_arithmetic()
489 test_hex_rotate_right()
490 test_hex_rotate_left()
494 test_offset_roundtrip()
495 test_offset_from_cube()
496 test_offset_to_cube()
497 test_doubled_roundtrip()
498 test_doubled_from_cube()
499 test_doubled_to_cube()
502 if __name__ == "__main__":