Designing Maps and Pathfinding on a Hexagonal GridHexagonal grids (hex grids) are a powerful alternative to square grids for representing 2D maps in games, simulations, and spatial analysis. They offer advantages in movement symmetry, neighbor relationships, and aesthetic layout. This article covers hex grid basics, coordinate systems, map design, terrain and weighting, pathfinding algorithms adapted for hex grids, performance considerations, and practical tips for implementation.
Why choose a hexagonal grid?
- Equal distance to all six neighbors — unlike squares where diagonal moves differ from orthogonal ones, hexes make movement cost uniform in six directions.
- Natural-looking maps — hexes reduce alignment artifacts and often feel more organic for terrain and strategy games.
- Simplicity in neighbor enumeration — each cell has exactly six neighbors (barring edges), which simplifies many algorithms.
Hex representations and coordinate systems
Several coordinate systems are commonly used; choice affects simplicity of algorithms and arithmetic.
Offset coordinates (odd-q / even-q, odd-r / even-r)
Offset coordinates store grid positions as (col, row) with an offset every other column or row. They are convenient when working with 2D arrays (tile maps) and render easily.
Example odd-q (vertical columns shifted):
- Columns (q) are integers, rows ® are integers.
- For odd columns, row indices are offset by +0.5 tile height visually.
Advantages:
- Easy to store in conventional 2D arrays. Disadvantages:
- Neighbor calculation requires conditional logic depending on column/row parity.
Axial coordinates (q, r)
Axial coordinates reduce hex positions to two coordinates by projecting cube coordinates. They are a subset of cube coordinates and are often simpler than offset for many algorithms.
- Each hex is (q, r).
- Third cube coordinate can be derived: s = -q – r.
Advantages:
- Simpler neighbor arithmetic than offset.
- Good for range queries and drawing lines.
Cube coordinates (x, y, z)
Cube coordinates represent hexes as points in 3D integer coordinates constrained by x + y + z = 0. Useful for distance calculations and rotations.
- Each hex is (x, y, z) with x + y + z = 0.
- Distance between hexes: (|dx| + |dy| + |dz|) / 2.
Advantages:
- Symmetric, simplifies many operations (distance, interpolation, rotation). Disadvantages:
- Uses one extra coordinate (but small overhead).
Conversions between coordinate systems
Common conversions:
- Axial (q, r) <-> Cube (x, y, z): x = q, z = r, y = -x – z.
- Offset <-> Axial: formulas depend on chosen odd/even layout.
Implement conversions in utility functions to avoid bugs.
Map design considerations
Map shapes
- Rectangular (in offset coords) — simpler storage.
- Hex-shaped (radius-based) — common for strategy maps.
- Custom irregular polygons — for island or region shapes.
To generate a hex-shaped map of radius R in axial/cube coords:
- Include all hexes where max(|x|, |y|, |z|) ≤ R.
Terrain and passability
- Store terrain type and movement cost per cell.
- Use integer or float weights; normalize costs for pathfinding heuristics.
Layering and features
- Keep separate layers for terrain, objects, and units.
- Support multiple occupancy or stacking if needed (e.g., bridges, tunnels).
Rendering and visual considerations
- Choose pointy-top vs flat-top orientation depending on UI and movement direction preferences:
- Pointy-top: hexes have points up/down (commonly used with axial q/r).
- Flat-top: hexes have flat tops left/right.
- Precompute vertex positions for rendering and hit testing.
Neighbor enumeration
In axial coordinates, six neighbor directions are constant vectors. For pointy-top axial:
- directions = [(+1, 0), (+1, -1), (0, -1), (-1, 0), (-1, +1), (0, +1)]
Add these to a hex’s (q, r) to get neighbor coordinates. For offset grids, neighbor logic depends on parity—wrap that logic into a helper.
Distance and range queries
- Cube distance: distance(a, b) = (|ax-bx| + |ay-by| + |az-bz|) / 2.
- Axial distance uses same formula via conversion.
- Range of radius R: all hexes where distance(center, hex) ≤ R.
Range queries can be done by iterating q and r within bounds or by using cube loops.
Pathfinding on hex grids
Pathfinding on hex grids follows the same principles as on square grids but uses hex-specific neighbors and distance metrics.
A* on hex grids
A* is the most common algorithm. Key components:
- Graph nodes: hex cells.
- Edges: between neighboring hexes, with movement cost equal to destination cell cost or average.
- Heuristic: use hex distance (cube distance) multiplied by minimal movement cost.
Heuristic formula (admissible and consistent):
- h(a, b) = hex_distance(a, b) * min_move_cost
Using cube or axial distance preserves admissibility because it gives the minimum number of steps.
Example pseudocode
# Node is axial (q, r) open_set = priority_queue() g_score[start] = 0 f_score[start] = h(start, goal) open_set.push(start, f_score[start]) while open_set: current = open_set.pop() if current == goal: return reconstruct_path(came_from, current) for dir in directions: # six axial directions neighbor = current + dir if not in_bounds(neighbor) or not passable(neighbor): continue tentative_g = g_score[current] + cost_to_move(current, neighbor) if tentative_g < g_score.get(neighbor, inf): came_from[neighbor] = current g_score[neighbor] = tentative_g f_score[neighbor] = tentative_g + h(neighbor, goal) if neighbor not in open_set: open_set.push(neighbor, f_score[neighbor]) Movement cost details
- Uniform cost: default 1 per move.
- Terrain cost: weight based on terrain. Use normalized minimal weight for heuristic.
- Diagonal-equivalent moves: none on hexes — all neighbors are single-step.
Tie-breaking and path quality
- Tie-breaker on f or g can produce more direct-looking paths (prefer lower h or higher g).
- Smooth paths: consider post-processing (e.g., string-pulling, funnel algorithm adaptations) if unit movement requires straight smoothing.
Dealing with impassable or weighted edges
- Blocked hex: mark passable=false.
- One-way movement / directional costs: store edge-specific modifiers.
- Probabilistic costs: useful in AI planning, but treat carefully for deterministic pathfinding.
Performance considerations
- Use efficient open-set (binary heap, Fibonacci heap rarely needed).
- Keep g_score and f_score in hash maps keyed by coordinates; use integer keys for speed.
- Early exit when goal popped from open set.
- Use hierarchical pathfinding for large maps: coarse grid planning followed by local detailed A*.
- Precompute walkable regions or connected components to quickly rule out unreachable goals.
Special topics
Path smoothing on hex grids
Hex grids produce stair-stepped routes. For smoother motion:
- Interpolate in cube space to generate intermediate points and then snap to nearest hex.
- Use line-drawing (cube linear interpolation + rounding) for straight segments.
- Combine with steering behaviors for continuous movement.
Line-of-sight and visibility
- Cast rays using cube line drawing between centers and check blockers.
- For shadowcasting FOV, adapt existing algorithms using hex neighbor topology.
Multiple agents and crowding
- Consider flow-field pathfinding for many units toward a common goal — compute cost field once and let units follow vectors.
- Use local avoidance (reciprocal velocity obstacles, steering) combined with hex navigation for responsive crowd motion.
Implementation checklist
- Pick coordinate system (axial/cube recommended for algorithms).
- Implement conversion helpers and neighbor enumerators.
- Implement movement costs and passability checks.
- Implement A* with hex distance heuristic.
- Add map generation tools and rendering helpers (vertex positions, hit tests).
- Optimize: use efficient data structures, consider hierarchical or flow-field algorithms for scale.
- Add smoothing/steering for unit motion.
Practical examples & snippets
- Store hex as small struct/class with coordinates, terrain ID, cost, and passable flag.
- Precompute neighbor lists where static to avoid recalculating parity logic each step.
- Use integer packing for coordinates (e.g., 32-bit q and r) as hash keys.
Common pitfalls
- Using Euclidean distance as heuristic — Euclidean underestimates but is unnecessary; cube distance is exact for steps.
- Mixing coordinate systems without correct conversion — leads to subtle bugs.
- Not normalizing movement costs — can break heuristic admissibility.
Conclusion
Hexagonal grids provide elegant solutions for map design and pathfinding, combining uniform neighbor relationships with natural-looking layouts. Use axial or cube coordinates for algorithmic simplicity, apply A* with the hex distance heuristic, and consider hierarchical or flow-field methods for scale. With careful handling of terrain costs, neighbors, and smoothing, hex-based maps can support robust, efficient navigation for games and simulations.
Leave a Reply