Edit: This is an old thread for the project that would eventually become the Advanced Turn Based Tile Toolkit on the marketplace. This is the last version where I used A instead of Dijkstra’s algorithm. This version is quite inefficient compared to later iterations, but might be of interest to people wanting to understand how A can be done through blueprints. This version is from when the pathfinding was at its most complex. Shortly after I made this version I started simplifying the algorithms, since this was overkill for what I needed.**
I’ve finally completed my A* pathfinding system in blueprint… sort of. I’ve included a download link below, but I recommend reading the rest of the post before downloading. For those who didn’t see my previous thread from a few weeks back, it can be found here. Vacationing and moving into a new apartment meant I couldn’t continue working on it until this week, but now it’s mostly done. It’s now a whole lot more efficient than it was before, but there are some remaining issues. I’m posting this in the Community Content, Tools and Tutorials sub forum, since my old thread was moved here, though this post is just as much a personal plea for help on this blueprint as it will be useful for other people.
As mentioned in the previous thread, this is the first proper blueprint I ever made, and I started working on it right after watching the basic UE4 blueprint video tutorials. This might have been a foolish move, but it’s been a stimulating challenge. Since I’ve been learning while making the blueprint it is certainly less efficient, readable and pretty than it could be, but I’ve tried to fix it up as well as I could before posting it here.
Worth noting is that the algorithm isn’t entirely complete. I do not re-check nodes to see if a new path is a better solution after a node has already been checked once (added to the open list). This would make many paths sub-optimal if movement costs were different for diagonal and straight movement. When both movement costs are the same, all the paths seem to be optimal. I spent some time today (hours) trying to implement this last piece of the algorithm, but I’ve given up for the moment (though I feel I’m close). I am in any case planning to make a game where movement costs are the same in all directions, so this doesn’t matter that much for me personally, though it does annoy me a bit that the algorithm is incomplete.
Another problem to be aware of is that the projects doesn’t work when launched or packaged, only when player in the editor (with the Play button). It launches just fine, but the start and end points do not appear. If anyone can help me identify what goes wrong during Launch I’ll be grateful. Because of this I have not included a packaged executable, but only the project folder. Just put the contents of the .zip in your own project folder, and it should hopefully work. I’ve stripped away everything i deemed unnecessary from the project folder, so it’s oly about 20 Mb.
The blueprint (pictured below) is pretty huge, but I’ve tried to organize it as best I could, and I have added some comments throughout. Please tell me if you see ways in which th blueprint can be organized in a cleaner way. If you want to understand how the pathfinding is done, you should know how A* works before delving into the blueprint. I recommend reading this introduction by Patrick Lester. The entire pathfinding blueprint is contained within the tileSpawner2 blueprint.
The project can be toggled in play mode to allow/dsallow diagonal movement and diagonal movement across walls. I have also included a slow motion mode that visualizes the search process.
The system uses a lot of loops, and large paths have caused crashes in previous versions of the project because of runaway loops, but this version seems stable. Please tell me if the blueprint crashes on your computer, as I’ve only tried it out on my quite powerful desktop computer so far.
I hope my project will be useful to other developers. Please comment if you have any questions, or have suggestions for how to improve any and all aspects of the project.
Planned features:
- Binary heap search for candidate nodes
- Hexagonal grids
- Movable actors following the path
- Nodes with higher movement costs
- Simple AI for moving to and preferring/avoiding certain nodes