Over the last month, my focus has been on a pathfinding algorithms.
For The final assessment of the year at University, we were tasked with a project of our choice.
My peers choose to work on a variety of interesting ideas and mechanics, and it was exciting to see everyone exploring new programming ideas and methods.
I decided I wanted to learn more about pathfinding, for a couple reasons, one of which being that I have a deep and burning passion for point and click adventure games and have always wanted to know how the walk boxes and movement systems work in those games, the other reason being that I have an interest in video game AI and smooth and natural looking pathfinding is extremely imperative for good game AI.
So, where do I start?
Well, I started reading as much info as I could about the different types of pathfinding commonly used and what their best use cases are, very quickly it became very apparent that, like most things in programming, there are many many different approaches to pathfinding and many many different ways to implement the same algorithms.
So I decided to go with a classic, the “Hello world!” of pathfinding if you will, A*.
A* is relatively simple and effective, it’s not entirely the most efficient but it’s not bad overall.
Now I’m not going to try and explain how A* works, there are much better explanations out there on the web, all you need to know is that my take on it cuts the world up into a grid of “nodes” which hold some values that the A* can use to compare nodes to each other to determine if a node is closer or further away from the destination, I’ll show you the summary I have written up the top of my node class.
It also contains a bool that determines if that node is “walkable”, which determines if it can be used in the path or not, if it’s not the algorithm will ignore that node and build the path around it, hence that actual pathfinding part.
From here it’s as easy as finding the start node, in this case being the player’s position, and the end node, which is a position in the world collected on mouse click (ignoring the Y axis),
then the A* does its thing and compares all the nodes between the start and end node and finds the nodes with the lowest overall cost (f cost), and places them in a list (I’ll talk about lists another time) which then makes up the path.
here’s and example of the grid
The algorithm checks the layer mask of objects and if they are solid it will turn the nodes that the object occupies to “unwalkable”, turning it red and unable to be used in the path.
Ok I’ve rambled enough, I’ll bore you with more details soon.
Thanks for reading!