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
23 from typing import NamedTuple
25 from model.python.point import Point
26 from model.python.geo_location import GeoLocation
30 def __init__(self, q: int, r: int, s: int):
31 if round(q + r + s) != 0:
32 raise ValueError("The sum of q, r, and s must be 0.")
37 def __str__(self) -> str:
38 return f"q: {self.q}, r: {self.r}, s: {self.s}"
41 def hex_add(a: Hex, b: Hex) -> Hex:
42 return Hex(a.q + b.q, a.r + b.r, a.s + b.s)
45 def hex_subtract(a: Hex, b: Hex) -> Hex:
46 return Hex(a.q - b.q, a.r - b.r, a.s - b.s)
49 def hex_scale(a: Hex, k: int) -> Hex:
50 return Hex(a.q * k, a.r * k, a.s * k)
53 def hex_rotate_left(a) -> Hex:
54 return Hex(-a.s, -a.q, -a.r)
57 def hex_rotate_right(a) -> Hex:
58 return Hex(-a.r, -a.s, -a.q)
61 hex_directions: list[Hex] = [
71 def hex_direction(direction: int) -> Hex:
72 return hex_directions[direction]
75 def hex_neighbor(hex: Hex, direction: int) -> Hex:
76 return hex_add(hex, hex_direction(direction))
79 hex_diagonals: list[Hex] = [
89 def hex_diagonal_neighbor(hex: Hex, direction: int) -> Hex:
90 return hex_add(hex, hex_diagonals[direction])
93 def hex_length(hex: Hex) -> int:
94 return (abs(hex.q) + abs(hex.r) + abs(hex.s)) // 2
97 def hex_distance(a: Hex, b: Hex) -> int:
98 return hex_length(hex_subtract(a, b))
101 def hex_round(hex: Hex) -> Hex:
102 qi = int(round(hex.q))
103 ri = int(round(hex.r))
104 si = int(round(hex.s))
105 q_diff = abs(qi - hex.q)
106 r_diff = abs(ri - hex.r)
107 s_diff = abs(si - hex.s)
108 if q_diff > r_diff and q_diff > s_diff:
115 return Hex(qi, ri, si)
118 def hex_lerp(a: Hex, b: Hex, t: int) -> Hex: # linearly interpolation
120 a.q * (1.0 - t) + b.q * t, a.r * (1.0 - t) + b.r * t, a.s * (1.0 - t) + b.s * t
124 def hex_linedraw(a: Hex, b: Hex) -> list[hex]:
125 N = hex_distance(a, b)
126 a_nudge = Hex(a.q + 1e-06, a.r + 1e-06, a.s - 2e-06)
127 b_nudge = Hex(b.q + 1e-06, b.r + 1e-06, b.s - 2e-06)
128 results: list[hex] = []
129 step = 1.0 / max(N, 1)
130 for i in range(0, N + 1):
131 results.append(hex_round(hex_lerp(a_nudge, b_nudge, step * i)))
135 OffsetCoord = collections.namedtuple("OffsetCoord", ["col", "row"])
141 def qoffset_from_cube(offset: int, hex: Hex) -> OffsetCoord:
143 row = hex.r + (hex.q + offset * (hex.q & 1)) // 2
144 if offset != EVEN and offset != ODD:
145 raise ValueError("offset must be EVEN (+1) or ODD (-1)")
146 return OffsetCoord(col, row)
149 def qoffset_to_cube(offset: int, hex: Hex) -> Hex:
151 r = hex.row - (hex.col + offset * (hex.col & 1)) // 2
153 if offset != EVEN and offset != ODD:
154 raise ValueError("offset must be EVEN (+1) or ODD (-1)")
158 def roffset_from_cube(offset: int, hex: Hex) -> OffsetCoord:
159 col = hex.q + (hex.r + offset * (hex.r & 1)) // 2
161 if offset != EVEN and offset != ODD:
162 raise ValueError("offset must be EVEN (+1) or ODD (-1)")
163 return OffsetCoord(col, row)
166 def roffset_to_cube(offset: int, hex: Hex) -> Hex:
167 q = hex.col - (hex.row + offset * (hex.row & 1)) // 2
170 if offset != EVEN and offset != ODD:
171 raise ValueError("offset must be EVEN (+1) or ODD (-1)")
175 DoubledCoord = collections.namedtuple("DoubledCoord", ["col", "row"])
178 def qdoubled_from_cube(hex: Hex):
180 row = 2 * hex.r + hex.q
181 return DoubledCoord(col, row)
184 def qdoubled_to_cube(hex: Hex) -> Hex:
186 r = (hex.row - hex.col) // 2
191 def rdoubled_from_cube(hex: Hex) -> DoubledCoord:
192 col = 2 * hex.q + hex.r
194 return DoubledCoord(col, row)
197 def rdoubled_to_cube(hex: Hex):
198 q = (hex.col - hex.row) // 2
204 Orientation = collections.namedtuple(
205 "Orientation", ["f0", "f1", "f2", "f3", "b0", "b1", "b2", "b3", "start_angle"]
209 # Layout = collections.namedtuple("Layout", ["orientation", "size", "origin"])
210 class Layout(NamedTuple):
211 orientation: Orientation
216 layout_pointy: Orientation = Orientation(
218 math.sqrt(3.0) / 2.0,
221 math.sqrt(3.0) / 3.0,
227 layout_flat: Orientation = Orientation(
230 math.sqrt(3.0) / 2.0,
235 math.sqrt(3.0) / 3.0,
240 def hex_to_pixel(layout: Layout, hex: Hex) -> Point:
241 M = layout.orientation
243 origin = layout.origin
244 x = (M.f0 * hex.q + M.f1 * hex.r) * size.x
245 y = (M.f2 * hex.q + M.f3 * hex.r) * size.y
246 return Point(x + origin.x, y + origin.y)
249 def pixel_to_hex(layout: Layout, p: Point) -> Hex:
250 M = layout.orientation
252 origin = layout.origin
253 pt = Point((p.x - origin.x) / size.x, (p.y - origin.y) / size.y)
254 q = M.b0 * pt.x + M.b1 * pt.y
255 r = M.b2 * pt.x + M.b3 * pt.y
256 return Hex(q, r, -q - r)
259 def hex_corner_offset(layout: Layout, corner: int) -> Point:
260 M = layout.orientation
262 angle = 2.0 * math.pi * (M.start_angle - corner) / 6.0
263 return Point(size.x * math.cos(angle), size.y * math.sin(angle))
266 def polygon_corners(layout: Layout, hex: Hex) -> list[Point]:
267 corners: list[Point] = []
268 center = hex_to_pixel(layout, hex)
269 for i in range(0, 6):
270 offset = hex_corner_offset(layout, i)
271 corners.append(Point(center.x + offset.x, center.y + offset.y))
275 def hex_to_geo_location(
276 layout: Layout, hex: Hex, reference: GeoLocation
278 hexPoint: Point = hex_to_pixel(layout, hex)
279 return GeoLocation(reference).point_to_geo_location(hexPoint)
286 print("FAIL {0}".format(name))
289 def equal_hex(name, a, b):
290 if not (a.q == b.q and a.s == b.s and a.r == b.r):
294 def equal_offsetcoord(name, a, b):
295 if not (a.col == b.col and a.row == b.row):
299 def equal_doubledcoord(name, a, b):
300 if not (a.col == b.col and a.row == b.row):
304 def equal_int(name, a, b):
309 def equal_hex_array(name, a, b):
310 equal_int(name, len(a), len(b))
311 for i in range(0, len(a)):
312 equal_hex(name, a[i], b[i])
315 def test_hex_arithmetic():
316 equal_hex("hex_add", Hex(4, -10, 6), hex_add(Hex(1, -3, 2), Hex(3, -7, 4)))
318 "hex_subtract", Hex(-2, 4, -2), hex_subtract(Hex(1, -3, 2), Hex(3, -7, 4))
322 def test_hex_direction():
323 equal_hex("hex_direction", Hex(0, -1, 1), hex_direction(2))
326 def test_hex_neighbor():
327 equal_hex("hex_neighbor", Hex(1, -3, 2), hex_neighbor(Hex(1, -2, 1), 2))
330 def test_hex_diagonal():
331 equal_hex("hex_diagonal", Hex(-1, -1, 2), hex_diagonal_neighbor(Hex(1, -2, 1), 3))
334 def test_hex_distance():
335 equal_int("hex_distance", 7, hex_distance(Hex(3, -7, 4), Hex(0, 0, 0)))
338 def test_hex_rotate_right():
339 equal_hex("hex_rotate_right", hex_rotate_right(Hex(1, -3, 2)), Hex(3, -2, -1))
342 def test_hex_rotate_left():
343 equal_hex("hex_rotate_left", hex_rotate_left(Hex(1, -3, 2)), Hex(-2, -1, 3))
346 def test_hex_round():
347 a = Hex(0.0, 0.0, 0.0)
348 b = Hex(1.0, -1.0, 0.0)
349 c = Hex(0.0, -1.0, 1.0)
353 hex_round(hex_lerp(Hex(0.0, 0.0, 0.0), Hex(10.0, -20.0, 10.0), 0.5)),
355 equal_hex("hex_round 2", hex_round(a), hex_round(hex_lerp(a, b, 0.499)))
356 equal_hex("hex_round 3", hex_round(b), hex_round(hex_lerp(a, b, 0.501)))
362 a.q * 0.4 + b.q * 0.3 + c.q * 0.3,
363 a.r * 0.4 + b.r * 0.3 + c.r * 0.3,
364 a.s * 0.4 + b.s * 0.3 + c.s * 0.3,
373 a.q * 0.3 + b.q * 0.3 + c.q * 0.4,
374 a.r * 0.3 + b.r * 0.3 + c.r * 0.4,
375 a.s * 0.3 + b.s * 0.3 + c.s * 0.4,
381 def test_hex_linedraw():
392 hex_linedraw(Hex(0, 0, 0), Hex(1, -5, 4)),
398 flat = Layout(layout_flat, Point(10.0, 15.0), Point(35.0, 71.0))
399 equal_hex("layout", h, hex_round(pixel_to_hex(flat, hex_to_pixel(flat, h))))
400 pointy = Layout(layout_pointy, Point(10.0, 15.0), Point(35.0, 71.0))
401 equal_hex("layout", h, hex_round(pixel_to_hex(pointy, hex_to_pixel(pointy, h))))
404 def test_offset_roundtrip():
406 b = OffsetCoord(1, -3)
408 "conversion_roundtrip even-q",
410 qoffset_to_cube(EVEN, qoffset_from_cube(EVEN, a)),
413 "conversion_roundtrip even-q",
415 qoffset_from_cube(EVEN, qoffset_to_cube(EVEN, b)),
418 "conversion_roundtrip odd-q", a, qoffset_to_cube(ODD, qoffset_from_cube(ODD, a))
421 "conversion_roundtrip odd-q", b, qoffset_from_cube(ODD, qoffset_to_cube(ODD, b))
424 "conversion_roundtrip even-r",
426 roffset_to_cube(EVEN, roffset_from_cube(EVEN, a)),
429 "conversion_roundtrip even-r",
431 roffset_from_cube(EVEN, roffset_to_cube(EVEN, b)),
434 "conversion_roundtrip odd-r", a, roffset_to_cube(ODD, roffset_from_cube(ODD, a))
437 "conversion_roundtrip odd-r", b, roffset_from_cube(ODD, roffset_to_cube(ODD, b))
441 def test_offset_from_cube():
443 "offset_from_cube even-q",
445 qoffset_from_cube(EVEN, Hex(1, 2, -3)),
448 "offset_from_cube odd-q",
450 qoffset_from_cube(ODD, Hex(1, 2, -3)),
454 def test_offset_to_cube():
456 "offset_to_cube even-", Hex(1, 2, -3), qoffset_to_cube(EVEN, OffsetCoord(1, 3))
459 "offset_to_cube odd-q", Hex(1, 2, -3), qoffset_to_cube(ODD, OffsetCoord(1, 2))
463 def test_doubled_roundtrip():
465 b = DoubledCoord(1, -3)
467 "conversion_roundtrip doubled-q", a, qdoubled_to_cube(qdoubled_from_cube(a))
470 "conversion_roundtrip doubled-q", b, qdoubled_from_cube(qdoubled_to_cube(b))
473 "conversion_roundtrip doubled-r", a, rdoubled_to_cube(rdoubled_from_cube(a))
476 "conversion_roundtrip doubled-r", b, rdoubled_from_cube(rdoubled_to_cube(b))
480 def test_doubled_from_cube():
482 "doubled_from_cube doubled-q",
484 qdoubled_from_cube(Hex(1, 2, -3)),
487 "doubled_from_cube doubled-r",
489 rdoubled_from_cube(Hex(1, 2, -3)),
493 def test_doubled_to_cube():
495 "doubled_to_cube doubled-q", Hex(1, 2, -3), qdoubled_to_cube(DoubledCoord(1, 5))
498 "doubled_to_cube doubled-r", Hex(1, 2, -3), rdoubled_to_cube(DoubledCoord(4, 2))
503 test_hex_arithmetic()
508 test_hex_rotate_right()
509 test_hex_rotate_left()
513 test_offset_roundtrip()
514 test_offset_from_cube()
515 test_offset_to_cube()
516 test_doubled_roundtrip()
517 test_doubled_from_cube()
518 test_doubled_to_cube()
519 print("test finished")
522 if __name__ == "__main__":