qHexWalker

Table of Contents

• Overview
• Key Features
• Architecture
• Module Structure
  • Core Module
  • Models Module
• Algorithms
  • Bidirectional A* Search
  • Maze Generation (Prim's Algorithm)
• Threading Model
• Building
  • Requirements
  • Build Commands
  • Build Documentation
• Dependencies
• License

Overview

qHexWalker is a Qt 6 desktop application that combines Uber's H3 hexagonal indexing system with MapLibre maps to provide interactive pathfinding and maze visualization on hexagonal grids.

Key Features

• H3 Hexagonal Grid Visualization - Display hierarchical hexagonal cells at resolutions 3-15
• Bidirectional A* Pathfinding - Fast pathfinding with hierarchical resolution refinement
• Procedural Maze Generation - Generate perfect mazes using Prim's algorithm on hex grids
• Multi-Waypoint Routing - Plan routes through multiple destinations
• Real-time Visualization - Watch the algorithm explore cells during search

Architecture

The application follows a layered architecture:

Module Structure

Core Module

The core module contains application initialization and configuration:

Class	Description
Application	QGuiApplication subclass with app metadata
EntryPoint	UI initialization orchestrator
MapProvider	Map style and source management

Models Module

The models module implements data models and algorithms:

Class	Description
H3Model	QAbstractListModel for hexagonal cells
H3TargetsModel	QAbstractListModel for waypoints
H3Cell	Data model for a single H3 cell
H3Target	Data model for a waypoint target
H3Worker	Threading wrapper for async operations
H3AStar	Bidirectional A* pathfinding algorithm
H3MazeGenerator	Maze generation using Prim's algorithm
H3MazeAdapter	Async wrapper for maze generation

Algorithms

Bidirectional A* Search

The H3AStar class implements bidirectional A* with hierarchical resolution refinement:

// Example usage
H3AStar astar;
astar.setBlockedCells(mazeWalls);
auto path = astar.findShortestPath(startCell, endCell);

Algorithm steps:

1. Coarse search at Resolution 3 - Find approximate path on coarse grid
2. Bidirectional expansion - Search from both start and goal simultaneously
3. Path refinement - Refine path to target resolution

Complexity: O(b^(d/2)) instead of O(b^d) for standard A*

Maze Generation (Prim's Algorithm)

The H3MazeGenerator class creates perfect mazes on hexagonal grids:

// Example usage
H3MazeGenerator generator;
auto result = generator.generateMazeWithEntrances(centerCell, radius);
// result.walls - set of wall cells
// result.entrance - maze entrance
// result.exit - maze exit

Algorithm steps:

1. Create room grid with 2-cell spacing
2. Initialize with random room
3. Add walls to frontier
4. Connect rooms through walls
5. Repeat until all rooms connected

Threading Model

The application uses a worker thread for pathfinding to keep UI responsive:

Building

Requirements

• CMake >= 3.19
• C++20 compiler (GCC 10+, Clang 12+, MSVC 2022+)
• Qt 6.5+ (QuickControls2, Sql, Positioning)
• vcpkg with packages: h3, spdlog, gtest, benchmark
• MapLibre Native Qt

Build Commands

cmake -S . -B build \
  -DCMAKE_TOOLCHAIN_FILE=<vcpkg>/scripts/buildsystems/vcpkg.cmake \
  -DCMAKE_PREFIX_PATH="<Qt6>;<MapLibre>"
 
cmake --build build -j

Build Documentation

cd /path/to/qHexWalker
doxygen Doxyfile
# Documentation generated in docs/html/

Dependencies

Library	Version	Purpose
Qt 6	6.5+	UI framework
H3	4.4.0+	Hexagonal indexing
MapLibre Native Qt	Latest	Map rendering
spdlog	1.16.0+	Logging
GTest	1.17.0+	Unit testing
Google Benchmark	1.9.4+	Performance testing

License

MIT License - See LICENSE file for details.

---

Author

qHexWalker Development Team

Version

0.0.1

Date

2025