[Unity3D Hex Map Game Dev] 42: Path Finding Functionality Visual Deep Dive
Hello Unity fans and welcome back to my game development series. In today’s video we’re going to do something a little different. A few of the previous videos have considered path finding and a unit’s movement on the chosen path. These were more about the technical aspects of the path finding algorithm itself, and how to make sure the unit’s movement between the nodes of the path works well, taking into account possible collisions with other units. However, there’s another important aspect of this topic which we haven’t spent a lot of time on: How we design the implementation of this functionality into our game, it’s mechanics and the different kinds of tasks our units, buildings, UI and even AI need to be able to perform. A large part of the practical application of path finding has to do with things like finding areas that would be suitable for certain buildings or actions, rather than just finding a path from point A to point B. Today, we’ll consider how to achieve this functionality using the foundation of our path finding algorithm, but increasing the complexity step by step to end up with very useful and optimised mechanics based on path finding. Since we’d like to take a step back from the technical aspects and code in this video, we’ll be considering the ideas visually with in-game scenarios. Let’s get going.
➤ Subreddit: / world_turtles
➤ Patreon: / recogmission
Music Credits:
Acoustic Breeze, Small Guitar by Bensound.com
A Robust Crew by Darren Curtis
Room For Two from YouTube Library
Exploration by Random Mind
Although our path finding actually utilises the segments of the hexes, we’ll be considering the ideas visually, and working with hexes as the base nodes. There’s no need to complicate the visuals and the ideas can easily be transferred to segments. At its very core, our pathfinding has a starting point, a destination and a collection of connected nodes through which travel can take place. Each node has one or more next-door neighbours, which count as the next potential steps on the path. Now, for a featureless, monotone map like this, it’s quite easy for the algorithm to find the best path. At this point the distance between each pair of hexes is used as the cost to minimise, and the algorithm will quickly find the optimal path as the path with the smallest number of hexes to visit. There you go – you’ve got your first game. You can slap some adds onto it, run off to the game store page, dump it into the play-for-free pile, hope someone finds it pressed into an obscure little corner and you get 10 million add views. Or you could work on it a bit more.
We need some features on our map to make things interesting. These can come in a variety of forms for a variety of different applications in the game, but in terms of pathfinding, the main impact they have is that they take some of the potential nodes out of contention when finding a path. You may not be able to scale a cliff, or cross a river. But it also does not have to be all or nothing. Certain features could only slow you down, or increase the cost of travel to and from that node, but still allow you through. For example, wading through marshland or snow, or even something as simple as walking slower when encountering an uphill slope. These can usually be handled by the combination of an access flag and some kind of cost calculation, which replaces the simple distance measure used previously. So, you can’t scale a cliff, but walking up and down a small hill may be better than going around it. Then again, if the hill becomes too steep, walking around becomes less costly again. And in terms of rivers, a bridge could unblock the path again, while roads in general could reduce the cost of the path.
This is a lot more interesting already, and you may even earn a few ad views from it, but it’s still only finding a path from point A to point B, both specified upfront. A lot of functionality in the game requires exactly this, but we need to be able to do a lot more. Let’s see why…
At this stage we are able to tell our algorithm to find a path from our woodcutter to this specific tree. It has to know where the unit starts from, and it needs to know the location of the specific tree. But once that tree has been cut down, do we have to manually select the next tree? This will be tedious. How about giving the path finder an order like “find a path from this unit to the closest tree”? Now, only one of the locations is specified, and the destination is open-ended. So, where previously, the algorithm picked most promising potential next steps by considering the distance between each hex and the target hex, it now has no idea in which direction the closest tree would ultimately turn out to be. At the start, it has no idea in which direction to aim. So, what should it do?