Trying to create A* pathfinding in blueprint as my first UE4 project probably wasn’t that good of an idea, but after days of work I finally have an implementation that works, even though it is currently very inefficient. I have some very limited programming experience, and have tried to create A* pathfinding before in C# for Unity. I read a lot of articles on pathfinding, and felt that I had a firm grasp of the concepts, but implementing it in C# seemed like an insurmountable task. I tried again in blueprint, without much hope for success, but blueprint turned out to be vastly more intuitive than it seemed at first look, and also surprisingly versatile and powerful.
I intend to share the entire Unreal project with this forum, but I’ll have to clean it up and add a few more comments first. I hope other people will find it useful, and that I can get input on ways to improve the pathfinding. As mentioned it is currently very inefficient. I have a lot of ideas of how to improve it, and I wonder how far I’ll be able to push it. Whenever people compare blueprints and C++ it is often mentioned that C++ should be used for the heavy lifting, and blueprint for the simpler stuff. Pathfinding is definitely up there with things that take a lot of computing power, and I suspect A* in blueprint will never be efficient enough for some projects. However, if you are making something turn based with a limited grid size, as I am, I think it might work. Currently the game crashes on paths longer than about 15-20 nodes, but I’m sure I can improve it significantly. This is more of a proof of concept and a starting point.
Below are pictures of my huge, poorly organised blueprint, as well as a path generated with a slowed down version of the pathfinding (that doesn’t crash the game for longer paths)
Any comments and ideas are welcome. Please ask if you have any questions about my A* implementation. As mentioned I intend to upload the project for anyone to peruse when I’ve tidied it up a bit.
Thank you! I almost gave up several times while making it, but I’m glad I kept trying. Something that surprised me when working With blueprint was that things often worked when I expected it not to, and often on the first try. I could come up with an idea, quickly throw together a few nodes, and it would just work. It’s the Complete opposite of my experiences With C#, where things often didn’t work even though the code looked seemingly good. One of the greatest benefits of visual scripting is making syntax errors a thing of the past.
Awesome! If I can help you test and improve your script I surely will!
That has been my experience as well. I think I spent something like 5-10 hours on my biome generator before I could even test it once, and it worked like a charm the first try!
Even when I get stuck and I am on the verge of banging my head on the wall, I come up with a fix and everything is great. My with experience scripting was almost the exact opposite.
Blueprint is nothing short of awesome as far as I am concerned and I await every update for even more awesomeness!
Thanks, Zeus! And thanks for the advice you gave as I was making it. Your map-gen blueprint was what convinced me of the power of bluprints in the first place. I’m sure your input will continue to be useful as i work to improve the algorithm.
I have an implementation of this in Blueprint as well, and I’m currently seeing if I’m permitted to release my project to the community. I’d love to see how we differed in implementation.
I’m with here, Blueprints are awesome and fit the way I think. I haven’t hit a problem with Blueprints that a bit of cleverness hasn’t been able to fix. Well, except the really annoying “Run Away Loop” counter being so tiny!
Thanks ! Could the “run away loop” counter be one of the reasons why my pathfinding crashes so easily? How long paths can you make in your implementation before it crashes? My A* is currently the simplest form possible, with a complete search through the closed list every time I check for the best node to select. I’m thinking of implementing a binary heap to speed things up. Have you tried different methods and found some that work better? I’d love to see what you have made, and find out how it compares to my own solution, and I really hope you are allowed to share it. In any case, you’ll be able to do so with my implementation. I’m currently in the process of moving into a new apartment, so I won’t be able to share my blueprint until probably late next week.
If you are hitting the loop limit your output log should tell you directly, though maybe it crashes before it can. If my map size causes me to hit the limit, when I hit play it won’t open and I see a message in the output log talking about the iteration limit being 1000000.
This awesome Monokkel! I’ve created a A* Pathing of my own I plan to release once I get time to clean it up as well. Its going to be so interesting to see what you came up with your solution. I also feel mine is inefficient and can be beefed up. But thats half the fun! I’ll post a link here once I release mine!
Ok, I’ll have to check what errors I am getting when I get the UE-PC set up again. Do you know if there is any way to find out what parts of a blueprint that’s causing the most slowdown? Other than trial and error by removing parts of the blueprin, I mean.
Thanks! As you know I was following your thread, and seeing you close to the finish line gave me an extra push to get my own method finished. Can’t wait to see your version!
There is probably some fancy tool in the debug menu that might help you out but I haven’t played around with them much so I am not sure. Actually I want to say you can flag nodes for some kind of debug tracking… I may have to look into that again.
What I have, is a few nodes at the beginning and the end of my generator that count the seconds(or milliseconds as it were). So as soon as the generator starts, it starts the clock, and when it ends it prints the time. So right now it prints about .399 seconds to generate the map, and I can make changes and see the difference in the generation time. I could probably print the time at steps throughout the generator to see how long each piece is taking, though right now it is small enough that I don’t care.
You could probably do something similar. Keep time from the start of the game, then print before and after you call the path generation function. Then you make some changes and see how they affect the generation time.
Hey, it’s my old thread risen from the dead! This was how my project looked more than half a year ago, and I’ve come pretty far since then. It’s really fun to look at this again, and even more so in that it reappeared on the same day my newest iteration hit the marketplace Trello Boards
Back then I was happy that I could get the pathfinding to find a path of seven nodes without crashing, while my new system can find every path to every node in a 40*40 grid in less than a millisecond. If you want to follow the progress of the blueprint I’ve since made three threads, in order here (same as Thommie linked to), here and here (from today ).
Like Thommie said, the first one includes a download link to the old version of the project. I’m not entirely sure I can recommend it anymore, as it is unneccessarily complicated, slow and poorly commented, but by all means take a look! If you’re sufficiently interested in this sort of thing that you would like to buy it, my newest blueprint will be on the marketplace in about a month (provided I get enough votes. Please vote here if you’re interested).
Feel free to ask my anything you want about creating grid based pathfinding in blueprint, as I’ve become pretty proficient at it these last months.
Again, thanks for resurrecting the thread. Perfect timing
).