[Unity3D Hex Map Game Dev] 25: A* (A-Star) Pathfinding on Hex Segments
Hello Unity fans, and welcome back to my hex map game development series. In the last two videos, which you can look out for in the top-right, we took control of the segments of our hexes, and managed to get our units walking smoothly on a path consisting of any arrangement of segments or way points. But the waypoints still had to be set by hand. Today, we will adapt our path finding algorithm to be based on segments rather than hexes.
Part0 (Introduction): • [Unity3D Hex Map Game Dev] 0: Introduction...
Part1 (Hexes to Water): • [Unity3D Hex Map Game Dev] 1: Hexes to Water
Part2 (Features and Textures): • [Unity3D Hex Map Game Dev] 2: Features, Te...
Part3 (Units, Visibility): • [Unity3D Hex Map Game Dev] 3: Units, Pathf...
Part4 (Random Maps): • [Unity3D Hex Map Game Dev] 4: Creating Ran...
Part5 (Post Processing): • [Unity3D Hex Map Game Dev] 5: Post Process...
Part6 (Resource Gathering): • [Unity3D Hex Map Game Dev] 6: Automated Re...
Part7 (Spinning Selector): • [Unity3D Hex Map Game Dev] 7: Spinning Obj...
Part8 (Preparing for Resources): • [Unity3D Hex Map Game Dev] 8: Preparing fo...
Part9(How Much Wood?): • [Unity3D Hex Map Game Dev] 9: How Much Woo...
Part10(Dynamic Trees): • [Unity3D Hex Map Game Dev] 10: Dynamic Trees
Part11(Meet The Meeples): • [Unity3D Hex Map Game Dev] 11: Meet The Me...
Part12(Harvesting Wood): • [Unity3D Hex Map Game Dev] 12: Harvesting ...
Part13(Harvesting Stone): • [Unity3D Hex Map Game Dev] 13: Harvesting ...
Part14(Walking Around Wallls): • [Unity3D Hex Map Game Dev] 14: Stop Walkin...
Part15(Multiple Unit Types): • [Unity3D Hex Map Game Dev] 15: Preparing f...
Part16(Manipulate Terrain): • [Unity3D Hex Map Game Dev] 16: Manipulate ...
Part17(ResourceBuilding Upgrades): • [Unity3D Hex Map Game Dev] 17: Resource Bu...
Part18(Camera Fly-through): • [Unity3D Hex Map Game Dev] 18: Camera Fly ...
Part19(Animated UI): • [Unity3D Hex Map Game Dev] 19: Animated Us...
Part20(Automated Farming): • [Unity3D Hex Map Game Dev] 20: Automated R...
Part21(UI Anchors, Buttons, ToolTip): • [Unity3D Hex Map Game Dev] 21: UI Anchors,...
Part22(Linking Graphics, Mechanics, UI): • [Unity3D Hex Map Game Dev] 22: Linking Gra...
Part23(Segmenting Hexes): • [Unity3D Hex Map Game Dev] 23: Segmenting ...
Part24(Smooth Irregular Movement): • [Unity3D Hex Map Game Dev] 24: Smooth Irre...
Way back in Part 3 of this series we started off with breadth-first search, then considered various ways of improving the algorithm, until we ended up with a properly optimized A* search algorithm that applied some intelligence to the decisions of which hexes to visit and which to skip. This left us with an algorithm that could guarantee finding the shortest path through a map containing both impassable obstacles and variable movement cost. Feel free to revisit that episode to review the basics before we adapt our algorithm for segments.
The basic change in the algorithm from hexes to segments was actually remarkably quick and easy. For the hexes version, all that the algorithm really required to find a path from one hex to another, was for each hex on the map to know who all its neighboring hexes were, and what the movement cost between each possible set of hexes are, if it could indeed be traversed. Making sure the rules catered for all eventualities could be a bit tricky, and there was also the search heuristic as absolute lowest possible move cost between hexes, but it actually requires very little information to work.
For the segments version, the algorithm works exactly the same way. All I needed to do was make sure the data structures applicable to the search algorithm of the segments mirrored that of the hexes, and assign new values to the distance parameters and rules. Previously, I called this class HexInternalLocation, but I changed it to the more appropriate HexSegment. I needed to add a reference to its parent hex, so we could find a reference to other segments in this way. I’m also storing its position, since that will be used a lot now. Then follows the pathfinding variables. PathFrom will be used to store the previous segment in the path, SearchPhase and NextWithSamePriority are used to decide which segments should be entering and exiting the search frontier, and Distance and SearchHeuristic is added together to determine the SearchPriority of the segment.
The search algorithm itself is quite simple, really. It starts off with some initialization and starting the search frontier at the starting segment. Then, as long as there are promising segments still to visit, and the shortest path to the target segment hasn’t been found yet, it loops through the neighbors of the currently visited segment. For each neighbor it tests whether the hex may be passed, and what the move cost between the two segments are, adding it to the current accumulated move cost. The search frontier and minimum distances are updated, and the next segment in the queue is visited, until the shortest path to the target segment is found.