The Path Most Followed

Well, I have just spent the better part of the last week working on a custom EQS generator that creates a cone-shaped graph of points and then uses the A* algorithm to plot a path through the graph. Having virtually no experience in this field of programming I had no right to hope that I could produce anything of any value, but thanks to Red Blob Games excellent articles on this I was able to implement this in Unreal.

To say that this was challenging (for me, at least) is an understatement of massive proportions. While I am an experienced C++ programmer, this field of programming is very demanding. I am very happy with the results that I was able to achieve from studying the code examples and explanations on Red Blob Games site. If you have any interest in how pathfinding works in games or other applications, you owe it to yourself to read every word on their site.

My implementation uses a cone as the shape of the graph to generate the initial points for the graph. Next comes the line traces to find all of the blocking volumes that may have points generating within them. These need to be marked as ‘wall’ points for the A* algorithm to plot a path around them. There is also terrain costing that can be implemented, so that path generation can take the type of terrain into account while plotting through the graph. While this hasn’t been implemented in my generator yet, there is a cost function that is already being called. It just returns a value of 1 for every point in the graph, but later a data table can be added to allow for different terrain types to cost different amounts. This will require some rewriting of the code because at the moment the generator isn’t doing any line traces to the landscape underneath each graph point to find the material at that location. This approach may not be possible for a variety if reasons, especially considering Unreal’s landscape material architecture, but even if that is the case, there is always a way to do something if your really determined.

Having a generator that will create paths that avoid blocking volumes is crucial, because I had written another EQS generator that would create its points along a straight line from Suzy to the target. It is crude, but effective in some instances…except where it sends Suzy running through the ocean. Obviously, this isn’t ideal. In the image for this post, you can see the EQS generator has created a short path for Suzy to follow. This image doesn’t show off what the generator can really do, but does show it in action. Just as an aside, the image also shows off the new female mannequin that Epic has given the community. The hair groom was a quick job in Blender to test out export settings to finally get a groom out of Blender. The tutorial is by Marvel Master and does what it claims to.

It has taken a lot of work to create this EQS generator, and while it isn’t perfect, it works very well and allows Suzy to run from one side of the test Island all the way to the other. I don’t know how far it is in-game, but it has to be at least a kilometer and is likely more. This generator isn’t just a great asset to this project, but it is now a permanent tool in our toolkit, and I have no doubt that the time spent creating it will be paid back ten-fold in the future. Hard work pays off.

Leave a Reply

Your email address will not be published. Required fields are marked *