Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# stephanh42/hexutil.py

Last active Nov 22, 2019
Utility functions for hex grids, in Python 3.
 """ Utility functions for hex grids. """ from math import sqrt from heapq import heappush, heappop import numpy import numpy.random neighbours = numpy.array(((2, 0), (1, 1), (-1, 1), (-2, 0), (-1, -1), (1, -1))) def _tiled_range(lo, hi, tile_size): return (lo // tile_size, (hi + tile_size - 1) // tile_size) def _make_range(x, width, bloat, grid_size): return _tiled_range(x + grid_size - 1 - bloat, x + width + bloat, grid_size) def distance(pos): """Distance of (x, y) from the origin on the hex grid, i.e. the number of setps which are needed to reach (x, y) from (0, 0). """ pos = numpy.abs(pos) x = pos[...,0] y = pos[...,1] return y + numpy.maximum(0, (x - y) // 2) _point_type = [("x", numpy.int), ("y", numpy.int)] def make_index_array(ar): ar = numpy.ascontiguousarray(ar).view(dtype=_point_type) shape = ar.shape[:-1] ar, inv = numpy.unique(ar, return_inverse=True) return (ar.view(numpy.int).reshape((-1, 2)), inv.reshape(shape)) class HexGrid: """Represents the dimensions of a hex grid as painted on the screen. The hex grid is assumed to be aligned horizontally, like so: / \ / \ / \ | | | | \ / \ / \ / The center of hex (0, 0) is assumed to be on pixel (0, 0). The hexgrid is determined by width and height, which are the screen coordinates of the upper-right corner of the central hex. To have equilateral hexes, width:height should be √3 : 1. If you only pass in width to the constructor, the height is computed to be an integer as close as possible to width / √3 . """ _factor = sqrt(1.0/3.0) _corners = numpy.array(((1, 1), (0, 2), (-1, 1), (-1, -1), (0, -2), (1, -1))) def __init__(self, width, height=None): if height is None: height = round(width * self._factor) self.width = width self.height = height self.size = numpy.array((width, height)) self.polygon = self._corners * self.size self.center_at = numpy.array((width, 3 * height)).__mul__ def __repr__(self): return "HexGrid(%d, %d)" % (self.width, self.height) def hexes_in_rectangle(self, x, y, width, height): x_lo, x_hi = _make_range(x, width, self.width, self.width) y_lo, y_hi = _make_range(y, height, 2*self.height, 3*self.height) xs = numpy.arange(x_lo, x_hi, dtype=numpy.uint8)[:,numpy.newaxis] ys = ~numpy.arange(y_lo, y_hi, dtype=numpy.uint8)[numpy.newaxis,:] numpy.bitwise_and(xs, 1, xs) numpy.bitwise_and(ys, 1, ys) sum = numpy.bitwise_xor(xs, ys) return numpy.transpose(numpy.nonzero(sum)) + (x_lo, y_lo) def center_at(self, pos): return (self.width * x, 3 * self.height * y) def polygon_at(self, pos): return self.center_at(pos)[..., numpy.newaxis,:] + self.polygon def cairo_surface(self): import cairo surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, 2*self.width, 6*self.height) cr = cairo.Context(surface) for poly in self.polygon_at(self.hexes_in_rectangle(0, 0, surface.get_width(), surface.get_height())): cr.move_to(*poly) for point in poly[1:]: cr.line_to(*point) cr.close_path() cr.stroke() return surface def hex_at_coordinate(self, x, y): width = self.width height = self.height x0 = x // width δx = x % width y0 = y // (3 * height) δy = y % (3 * height) if (x0 + y0) % 2 == 0: if width * δy < height * (2 * width - δx): return (x0, y0) else: return (x0 + 1, y0 + 1) elif width * δy < height * (width + δx): return (x0 + 1, y0) else: return (x0, y0 + 1) class HexPathFinder: """A* path-finding on the hex grid. All positions are represented as tuples of (x, y) - coordinates. Important data attributes: found -- True if path-finding is complete and we found a path done -- True if path-finding is complete: we either found a path or know there isn't one path -- The path, as a tuple of positions from start to destination (including both). Empty tuple if found is False. """ found = False done = False path = () def __init__(self, start, destination, passable, cost=lambda pos: 1): """Create a new HexPathFinder object. start -- Starting position for path finding. destination -- Destination position for path finding. passable -- Function of one position, returning True if we can move through this hex. cost -- cost function for moving through a hex. Should return a value ≥ 1. By default all costs are 1. """ self.start = start self.destination = destination self.passable = passable self.cost = cost self.closedset = set() self.openset = [(self._heuristic(start), 0, start, ())] def _heuristic(self, position): return distance(numpy.asarray(position) - self.destination) def _compute_path(self, path): result = [] while path: pos, path = path result.append(pos) return result[::-1] def run_n(self, n): """Run at most n path-finding steps. This method does a bounded amount of work, and is therefore useful if pathfinding must be interleaved with interactive behaviour or may be interrupted. """ openset = self.openset closedset = self.closedset passable = self.passable cost = self.cost destination = self.destination heuristic = self._heuristic for i in range(n): if not openset: self.done = True return h, cur_cost, pos, path = heappop(openset) if pos in closedset: continue new_path = (pos, path) if pos == destination: self.path = self._compute_path(new_path) self.found = self.done = True del openset[:] return closedset.add(pos) for new_pos in neighbours + pos: new_pos = tuple(new_pos) if (not passable(new_pos)) or (new_pos in closedset): continue new_cost = cur_cost + cost(new_pos) new_h = new_cost + heuristic(new_pos) heappush(openset, (new_h, new_cost, new_pos, new_path)) def run(self): """Run path-finding until done, that is, we either found a path or know there isn't one. """ while not self.done: self.run_n(100) def rotate_left(x, y): """Given a hex coordinate (x, y) return the coordinate of hex when rotated 60° around the origin. """ return ((x - 3 * y) >> 1, (x + y) >> 1) class _FovTree: _corners = ((0, -2), (1, -1), (1, 1), (0, 2)) _neighbours = ((1, -1), (2, 0), (1, 1)) _cached_successors = None def __init__(self, x, y, angle1, angle2): self.x = x self.y = y self.angle1 = angle1 self.angle2 = angle2 self.distance = 0.5 * sqrt(x*x + 3*y*y) self.points = self.make_points() def run(self, transparent, visible, direction, x0, y0, max_distance): if self.distance <= max_distance: δx, δy = self.points[direction] point = (x0 + δx, y0 + δy) visible.add(point) if transparent(point): for successor in self.successors(): successor.run(transparent, visible, direction, x0, y0, max_distance) def make_points(self): x = self.x y = self.y result = [] for i in range(6): result.append((x, y)) x, y = rotate_left(x, y) return tuple(result) def get_angle(self, corner): cx, cy = corner return (3*self.y + cy)/float(self.x + cx) def successors(self): _cached_successors = self._cached_successors if _cached_successors is None: _cached_successors = [] angles = [self.get_angle(c) for c in self._corners] for i in range(3): c1 = max(self.angle1, angles[i]) c2 = min(self.angle2, angles[i+1]) if c1 < c2: dx, dy = self._neighbours[i] _cached_successors.append(_FovTree(self.x + dx, self.y + dy, c1, c2)) self._cached_successors = _cached_successors = tuple(_cached_successors) return _cached_successors _fovtree = _FovTree(2, 0, -1.0, 1.0) def run_fov(transparent, max_distance, origin=(0, 0), visible=None): """Compute field-of-view on the hex grid. transparent -- function accepting a (x, y)-tuple and returning True is the hex is transparent (open) max_distance -- maximum distance that we can see origin -- (x, y)-tuple indicating the location of the viewer visible -- a set of (x,y)-tuples which will be updated with the visible locations and returned This function returns a set of (x,y)-tuples which are visible. Not that the origin is always added, even if transparent woudl return False for it. By passing in an existing set as "visible", multiple viewers can re-use the same set. """ if visible is None: visible = set() visible.add(origin) x0, y0 = origin for direction in range(6): _fovtree.run(transparent, visible, direction, x0, y0, max_distance) return visible def random_walk(N, origin=(0, 0)): """Return a set of (x,y)-tuples representing a random walk starting from origin.""" result = numpy.add.accumulate(neighbours[numpy.random.randint(0, 6, N)]) result += origin result = set(map(tuple, result)) result.add(origin) return result
to join this conversation on GitHub. Already have an account? Sign in to comment