HexKit - C# tools for hex grids, including pathfinding and field of view.

Hey folks! I've been working on this for entirely too long, and today I finished implementing my feature list. There's still a round of double-check testing, documentation, and the actual submission process to go through, but it seems like a good time to drop by and say hello.

HexKit is a script asset, consisting of two main parts. The first half, HexCoord, is MIT-licensed and available on GitHub. It represents a two-axis integer coordinate system (based on Amit Patel's excellent reference) and handles the geometry of the hexagons and the grid, including conversion to/from Unity position coordinates, as well as a polar coordinate system.

HexKit proper is a static class providing a number of utility functions, including:

• Pure integer line drawing (Bresenham), including "supercover" lines appropriate for raycasting.
• Field-of-view enumeration using real-space arcs.
• Movement range enumeration, known-target pathfinding (A*), and unknown-target pathfinding (Dijkstra).
• Several simpler spacial enumerations such as range fill, range overlap, rectangle fill, and ring.
• Procedural hexagon mesh creation, "solid" (4-tri) and "border" (12-tri).

Linq fans rejoice! Except for pathfinding, all of the spacial operations return IEnumerable and calculate their yields one hex at a time. (Path functions return true or false depending on whether a path is found, with the path itself returned as an array via an out argument.) No assumptions are made about your map data: move-range, pathing and FOV take function arguments to determine whether a hex is obstructed and/or what it costs to move through, and the unknown-target pathing also uses a function argument to determine whether it's found a target.

That's the quick-and-dirty. Yes, I'm hideously bad at presentation. If anyone's interested in this, I'm actually hoping for some questions... answering them will help me fill in the gaps in the brief description, and avoid vague points in the real documentation.

Also, a question for anyone experienced with submitting script assets: I'm uncertain exactly how I should handle input sanitization. The submission guidelines say I should never throw a null reference exception, but is a deliberate null argument exception okay? Do I need to explicitly guard against integer overflows due to someone thinking Int32.MaxValue is an appropriate fill range for an area not centered at [0,0], or is it enough to warn about that in the docs? Etc.

 

I can not help you on submitting assets but you can count me in as a customer when this hits the store.

 

Based on some questions I was asked via PM, here are a few more bits of info:

Movement and pathfinding calculations have two modes: boolean and integer. Boolean mode is optimized for monotonous grids, where every cell is either an obstacle or is passable. Though this can be trivially simulated with the integer calculation, it's about 13% faster as a dedicated function.

Integer mode assigns a movement cost to each cell transition. The cost function takes both the hex you're leaving and the one you're entering, allowing non-uniform and non-symmetrical costs (e.g. cell A -> B costs 1, cell B -> A costs 5). If your costs are uniform on entry (e.g. entering cell X always costs 3), there's an optional argument to specify that which speeds things up a bit.

Pathfinding is inherently unbounded -- it searches until it finds a target or runs out of search cells. Movement range enumeration takes a maximum path cost (range allowance), with an option for "permissive" calculation wherein a cell can always be entered if there is >0 range allowance remaining, even if its entry cost is higher than the actual allowance.

For consistent behavior and to eliminate potential infinite loops in both operations, a movement cost of zero (actually <1) is special-cased to indicate an impassible barrier. To simulate "free" movement, multiply regular movement costs by a constant larger than your map size, then assign the "free" cells a cost of 1.

The return type for all movement and pathing operations is a path node object which contains the coordinate, as well as the direction it was entered from and the total path cost to that point. This should make it easy to present things like multi-turn movement breakdowns, color-coding movement range by distance, etc.

 

I'll be submitting to the Asset Store this weekend. I'm not sure how long the review process normally takes, but it should be live pretty soon! To whet your appetite, here's the documentation (pdf).

 

Submitted to the store! Another teaser, hands-on this time: below is the control script for the usage example, and this download is the compiled scene, demonstrating basic pathfinding and field-of-view.

Code (csharp):

1. using UnityEngine;
2. using System.Collections.Generic;
3. using Settworks.Hexagons;
4.  
5. public class HexKitExampleSceneControl : MonoBehaviour {
6.     public GameObject solid;
7.     public GameObject open;
8.  
9.     GameObject cursor;
10.     HexCoord mpos;
11.     bool clear;
12.  
13.     HexCoord origin;
14.  
15.     HexCoord target;
16.     HashSet<HexCoord> blockers;
17.  
18.     HexCoord minBounds;
19.     HexCoord maxBounds;
20.     Dictionary<HexCoord, Renderer> borders;
21.     Dictionary<HexCoord, Renderer> cells;
22.  
23.     bool FOV;
24.  
25.  
26.     void Start() {
27.         // Find viewport boundaries in QR space.
28.         // Subtracting 3 units guarantees the boundary is outside the screen.
29.         minBounds = HexCoord.AtPosition(camera.ScreenToWorldPoint(Vector2.zero) - (Vector3.one * 3));
30.         maxBounds = HexCoord.origin - minBounds;
31.  
32.         // Construct the grid out of borders and backgrounds.
33.         // These objects never move, so all we need to store are their Renderer components for color changes.
34.         borders = new Dictionary<HexCoord, Renderer>();     // Grid outline.
35.         cells = new Dictionary<HexCoord, Renderer>();       // Cell backgrounds.
36.         foreach (HexCoord hex in HexKit.WithinRect(minBounds, maxBounds)) {
37.             // This could be done without the temporary object, but it helps clarify what's happening.
38.             GameObject o = GameObject.Instantiate(open, hex.Position(), Quaternion.identity) as GameObject;
39.             borders.Add(hex, o.renderer);
40.             o = GameObject.Instantiate(solid, (Vector3)hex.Position() + Vector3.forward, Quaternion.identity) as GameObject;
41.             cells.Add(hex, o.renderer);
42.         }
43.  
44.         // The cursor is a smaller outline, so it doesn't obscure anything.
45.         // This will move around, so we need the GameObject itself.
46.         cursor = GameObject.Instantiate(open, HexCoord.origin.Position(), Quaternion.identity) as GameObject;
47.         cursor.transform.localScale = new Vector3(0.9375f, 0.9375f);
48.  
49.         // There are initially no blockers.
50.         blockers = new HashSet<HexCoord>();
51.  
52.         // Everything's ready. Render the initial scene.
53.         UpdateGrid();
54.     }
55.  
56.  
57.     // Update performs input handling, then conditionally updates the screen with UpdateGrid()
58.     void Update() {
59.         // Handle cursor position. Store old position, we'll check it a couple of times.
60.         HexCoord mposWas = mpos;
61.         // Mouse position in pixels -> world position -> HexCoord position.
62.         mpos = HexCoord.AtPosition(camera.ScreenToWorldPoint(Input.mousePosition));
63.         // We set the screen boundary in Start(). Make sure the mouse is inside it.
64.         // This is done in QR space because there will be partial hexes at the real screen border.
65.         if (mpos.IsWithinRectangle(minBounds, maxBounds))
66.             cursor.transform.position = mpos.Position();
67.         else mpos = mposWas;    // Mouse is somehow outside of screen, keep old position.
68.  
69.         bool changed = mpos != mposWas;     // Later, we'll only update if changed==true.
70.  
71.         // Escape clears all blockers.
72.         if (Input.GetKeyDown(KeyCode.Escape)) {
73.             changed = true;
74.             blockers.Clear();
75.         }
76.         // Tab switches between FOV and pathfinding modes.
77.         if (Input.GetKeyDown(KeyCode.Tab)) {
78.             changed = true;
79.             FOV = !FOV;
80.         }
81.  
82.         // In FOV mode, target is not used. In path mode, move it with right mouse button.
83.         if (target != mpos  (FOV? false: Input.GetMouseButton(1))) {
84.             changed = true;
85.             target = mpos;
86.         }
87.         // In FOV mode, move origin with right mouse button. In path mode, move it with space.
88.         if (origin != mpos  (FOV? Input.GetMouseButton(1): Input.GetKey(KeyCode.Space))) {
89.             changed = true;
90.             origin = mpos;
91.         }
92.         // In either mode, place/remove blockers with left mouse button.
93.         if (Input.GetMouseButtonDown(0))
94.             // At time of click, check the current cell.
95.             // If it's a blocker, we're clearing; otherwise setting.
96.             clear = (blockers.Contains(mpos));
97.         if (Input.GetMouseButton(0)) {
98.             // If the block state is the same as the clear state, it will wind up flipped.
99.             if (blockers.Contains(mpos) == clear)
100.                 changed = true;
101.             // We don't care what the previous state was here, only what it should be.
102.             if (clear)
103.                 blockers.Remove(mpos);
104.             else
105.                 blockers.Add(mpos);
106.         }
107.  
108.         // Input is taken care of. Update the screen if necessary.
109.         if (changed) UpdateGrid();
110.  
111.         // Note: Alt-F4 handling is built in.
112.     }
113.  
114.  
115.     // This function is used exclusively as an argument to HexKit functions in UpdateHexes()
116.     bool IsBlocked(HexCoord hex) {
117.         return !hex.IsWithinRectangle(minBounds, maxBounds) || blockers.Contains(hex);
118.     }
119.  
120.  
121.     // Heavy lifting happens here. If grid status has changed, find new path/FOV and update display.
122.     void UpdateGrid() {
123.         HashSet<HexCoord> lit;  // "Lit" hexes are the path from origin to target, or the visible area for FOV.
124.         if (FOV) {
125.             // Radiate returns IEnumerable<HexCoord>, which HashSet can use for initialization.
126.             lit = new HashSet<HexCoord>(
127.                 HexKit.Radiate(origin, minBounds.AxialLength() * 2, IsBlocked)
128.                 );
129.         }
130.         else {
131.             // Path returns HexPathNodes instead of HexCoords, and does so through an out argument.
132.             lit = new HashSet<HexCoord>();  // Initialize empty.
133.             HexPathNode[] nodes;    // For the out argument.
134.             // If there is no path, this evaluates false and lit stays empty.
135.             if (HexKit.Path(out nodes, origin, target, IsBlocked)) {
136.                 // Iterate the nodes, and add their HexCoord locations to lit.
137.                 foreach (HexPathNode node in nodes) {
138.                     lit.Add(node.Location);
139.                 }
140.             }
141.         }
142.  
143.         // Iterate border objects, setting colors by status.
144.         foreach (HexCoord hex in borders.Keys) {
145.             if (hex == target  !FOV)    // Ignore target in FOV mode.
146.                 borders[hex].material.color = Color.red;
147.             else if (lit.Contains(hex))
148.                 borders[hex].material.color = Color.yellow;
149.             else
150.                 borders[hex].material.color = new Color(0.125f, 0.125f, 0.125f);    // Dim gray.
151.         }
152.  
153.         // Same for cell backgrounds.
154.         foreach (HexCoord hex in cells.Keys) {
155.             if (hex == origin)
156.                 cells[hex].material.color = Color.green;
157.             else if (blockers.Contains(hex))
158.                 cells[hex].material.color = Color.magenta;
159.             else
160.                 cells[hex].material.color = Color.black;
161.         }
162.     }
163.  
164.  
165.     void OnGUI() {
166.         GUILayout.Label("RMB: move " + (FOV? "origin" : "target") + (FOV? "" : "\t\tSpace: move origin") +
167.                         "\nLMB: place or clear obstacles" +
168.                         "\nEsc: clear all obstacles" +
169.                         "\nTab: switch to " + (FOV? "pathfinding" : "field of view") +
170.                         "\nAlt-F4: Quit");
171.     }
172. }

 

First submission was declined due to concerns with documentation and organization. I wasn't entirely clear on the documentation issue, so I went back through and tried to give everything the ELI5 treatment. Re-submitted, fingers crossed! Here is the updated documentation (same URL, you may need to reload).

Meanwhile, I've got the website ready to go. Here is the page describing HexKit, and here are the forums. The example scene linked above is now available through a web player, here.

 

I just picked up HexKit. I'm checking out all the features now. The HexKit.Path sounds like pure gold.

 

Is this dead?