My A* Pathfinding blueprint or: How Not to Build a Blueprint

[Monokkel]

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

DOWNLOAD LINK

[Zeustiak]

Nice timing! I just worked out Axial Coordinates for my generator so I am not too far away from being able to implement some A*.

Unfortunately I won’t have much time in the near future to do much testing, but maybe next week. Busy this weekend and then after next week I will be away working for 2 weeks.

Looking at your blueprint reminds me of my river generator, which I now realize uses some rough approximation of A*, just with a tile cost system that has different objectives.

I will try to pop in an help as much as I can. Let me know if you need anything specific regarding hex maps!

[Monokkel]

Thats great news! Using axial coordinates is probably the optimal solution for hex grids, so it’s good to see that it’s relatively straightforward to implement.

You have your share of experience with massive interconnected blueprints, so you know how it is to work for ages on something, but not being able to test it properly until you’re done. Quite nervewracking, but awesome when it works.

[Zeustiak]

Yeah super easy to put together once I placed everything in the spreadsheet so I could visualize how to store it.

I love it when dozens of hours of work pays off by magically working the first try. I wonder if I would have a similar experience if I had UE4 10 years ago. I am not sure I had the same attention to detail back then.

I verified my coordinates are all indexed properly so now I am going to start crafting new neighbor check functions.

How does A* account for the boundaries of the map? Do you set limits or do you just let it hit non-existent array indexes?

[Monokkel]

@Zeustiak;114787

How does A* account for the boundaries of the map? Do you set limits or do you just let it hit non-existent array indexes?

When I check the neighbors of a tile I see if the current tile is on one of the border tiles of the map. If it is, I simply do not check the neighbor on the other side of that border. I’m uncertain if this is the most efficient solution, or if I should simply populate all the border tiles with walls so I can just use my regular methods of checking for walls. I’m planning to check this out using timers. Just download the blueprint if you want to see exactly how I solved it. It’s at the bottom left of the blueprint (the one marked “Check if tiles are out of bounds” in the picture).

[PeterLNewton]

, this is amazing! I tried out everything and it was all stable. I checked out the blueprint and that’s wild man! Your setup is way different than of mine own. This is great work, well organized too. I like how you have options to cross corners or not. You’ve done a lot.

Peter

[Monokkel]

Thanks, SilentX! Great to hear that it’s stable on your computer as well. Hearing that your blueprint is so different makes me more excited to see how you have solved it. That’s the reason I didn’t want to look at your solution before completing my own. I’m surprised that you think that it’s well organized, as it’s still quite chaotic, but then again it’s hard to make such a complex blueprint not look a bit tangled. Can’t wait to see your tutorial!

[Zeustiak]

Just had a chance to download and try out your path generator. Looks pretty good!

If I have time tonight I will delve through the path generating portion of the blueprint.

I will say though that you could probably make use of functions and custom events, though I would understand if you are leaving everything on the board so you can keep it straight in your head.

@;114815

When I check the neighbors of a tile I see if the current tile is on one of the border tiles of the map. If it is, I simply do not check the neighbor on the other side of that border. I’m uncertain if this is the most efficient solution, or if I should simply populate all the border tiles with walls so I can just use my regular methods of checking for walls. I’m planning to check this out using timers. Just download the blueprint if you want to see exactly how I solved it. It’s at the bottom left of the blueprint (the one marked “Check if tiles are out of bounds” in the picture).

The problem with checking the border on a hex map is that you still run into the offset hex problem. Look at the hexes at the bottom of the 2 rightmost columns on a hex map. Both are on the very bottom technically, but when doing an edge check you have to treat them both differently. The 0/0 tile can not check any south direction. The tile to its left is only restricted from checking directly south but still has tiles to the SE and SW.

Here is one way I might handle this. Create 2 arrays, one each for the north and south edges. Fill these arrays with coordinates for tiles just outside of the map area. Whenever neighbor checking north, you see if the north edge array contains the coordinates and if not, then you branch out of the loop. For me, this could mean searching an array that has upwards of 200-300 members in each edge array. I am not sure how quick such an action would be, so maybe this isn’t the most ideal solution.

Alternatively, you could take the X of the column and based on that information do some math to figure out what the off-limit tile coordinate would be for either edge. So for each direction you do a small bit of math to determine if the neighbor tile is off limits and if so you branch out. That is probably the more efficient method.

One other method would be to do the neighbor check in every circumstance, and then when you go to get that tile’s index it would come up empty since those coordinates don’t exist in your array. If you use a Find node on an array and nothing is found, what does the Find node return on the index? 0? That might not be ideal since 0 is normally an active index, but I suppose things could be re-engineered if that is the best way to handle things.

[Monokkel]

@Zeustiak;115004

I will say though that you could probably make use of functions and custom events, though I would understand if you are leaving everything on the board so you can keep it straight in your head.

Yeah, that’s probably a good idea, and I’ll look into it. THe only thing I’ve done so far is make three macros for certain parts of the blueprint that are repeated often.

@Zeustiak;115004

The problem with checking the border on a hex map is that you still run into the offset hex problem. Look at the hexes at the bottom of the 2 rightmost columns on a hex map. Both are on the very bottom technically, but when doing an edge check you have to treat them both differently. The 0/0 tile can not check any south direction. The tile to its left is only restricted from checking directly south but still has tiles to the SE and SW.

Here is one way I might handle this. Create 2 arrays, one each for the north and south edges. Fill these arrays with coordinates for tiles just outside of the map area. Whenever neighbor checking north, you see if the north edge array contains the coordinates and if not, then you branch out of the loop. For me, this could mean searching an array that has upwards of 200-300 members in each edge array. I am not sure how quick such an action would be, so maybe this isn’t the most ideal solution.

That’s basically the same as making the map array one node wider than you need and populating the edges with walls (invisible or otherwise), which works great in my system, and might be the method I’ll end up using. You should not do this by searching through an entire edge array for a certain value, which would be very slow. You should just have to find out what index in the array corresponds to the tile you want to check, and use the Get function instead of Find item (if this is what you meant). If you use Get I don’t think it really matters how big an array is.

@Zeustiak;115004

Alternatively, you could take the X of the column and based on that information do some math to figure out what the off-limit tile coordinate would be for either edge. So for each direction you do a small bit of math to determine if the neighbor tile is off limits and if so you branch out. That is probably the more efficient method.

That sounds good, and means you need a slightly smaller array than the solution above, which might be a good thing. The wall solution makes for a somewhat dimpler blueprint, though.

@Zeustiak;115004

One other method would be to do the neighbor check in every circumstance, and then when you go to get that tile’s index it would come up empty since those coordinates don’t exist in your array. If you use a Find node on an array and nothing is found, what does the Find node return on the index? 0? That might not be ideal since 0 is normally an active index, but I suppose things could be re-engineered if that is the best way to handle things.

I’m uncertain if this would work in my system. If I check for a tile that’s outside the bounds of the array, and try to convert it to an index, it would probably (in the case of the rightmost and leftmost tiles) wrap around to the other side and move one row up or down.

Do you have any clue as to why my project won’t work in Launch mode, by the way? Haven’t managed to solve it yet.

[Zeustiak]

Yeah this might be one of those blueprints where it is so complicated that I will only really get what is going on if I build it from the ground up myself…

@;115308

Yeah, that’s probably a good idea, and I’ll look into it. THe only thing I’ve done so far is make three macros for certain parts of the blueprint that are repeated often.

Here are some thoughts from looking at the monstrosity at the bottom of your graph:

I would start with creating a few variables labeled “Current Index”, “Current G”, “Current H”, “Current IsOutOfBounds?”, etc, and then setting them at the start of any large execution chain they are needed in. This will allow you to get rid of a lot of those lines running every which way and also give you a better idea of what is being input into a node since it has a named variable next to it instead of 10 pages away.

Turn your Get Wall Array + Branch into a function with your Current Index variable plugged into the Get. Same for Get Open List Bool + Branch.

All your Set Array Elem/BreakStruct/MakeStruct stuff at the end can be one function that has your Current Index/etc variables plugged in. You won’t even need 8 of them on the board, just 1 to take the place of all of them. Just make sure you have Set Current whatever variable appropriately hooked up coming out of each of those sequence outputs.

Also, pure functions are going to make your life much easier. Pretty much make them for everything. Make a Pure Function for each of your neighbor node index checks that happens at the start of the monstrosity at the bottom of the graph. Make one for Grid Size X times Grid Size Y, and the other 2 above that. Then make pure functions with those pure functions inside that output your bounds bools. Turn your IndexToVector and Manhattan macros into Pure Functions. Anything in your graph that is more than 3 nodes and only has non-execution outputs such as “Is End Index?”, “Is Less than 500 Index?”, your whole transform bit for the Path Instance transform, etc should be turned into a Pure Function.

The best part about pure functions is they practically comment themselves so you just glance at them and know what it is they are doing for you. Of course, the reduced clutter frees your brain up to focus on the important parts of the execution chain as well.

@;115308

That’s basically the same as making the map array one node wider than you need and populating the edges with walls (invisible or otherwise), which works great in my system, and might be the method I’ll end up using. You should not do this by searching through an entire edge array for a certain value, which would be very slow. You should just have to find out what index in the array corresponds to the tile you want to check, and use the Get function instead of Find item (if this is what you meant). If you use Get I don’t think it really matters how big an array is.

That sounds good, and means you need a slightly smaller array than the solution above, which might be a good thing. The wall solution makes for a somewhat dimpler blueprint, though.

Yeah though I don’t think I want to fatten my arrays with a wall around the outside. I think doing a small amount of math for each lookup should work just fine.

@;115308

I’m uncertain if this would work in my system. If I check for a tile that’s outside the bounds of the array, and try to convert it to an index, it would probably (in the case of the rightmost and leftmost tiles) wrap around to the other side and move one row up or down.

Yeah, I have been thinking of pathfinding in terms of my whole map, but you may just want a smaller box that doesn’t search the whole map for a short path. In that case, you may be doing math on every run anyway so doing a pole check would be par for the course. So you could do a path check with a bounding box set to small, and if that doesn’t work, it redoes it with a larger bounding box to look for further paths? Could be a good way to optimize it. Maybe you could even get the height in tiles of an obstruction such as a known wall and set the box height to match.

@;115308

Do you have any clue as to why my project won’t work in Launch mode, by the way? Haven’t managed to solve it yet.

You mean standalone? I have never used it, but just tried it with your generator and it worked fine.

[Monokkel]

@Zeustiak;115355

Yeah this might be one of those blueprints where it is so complicated that I will only really get what is going on if I build it from the ground up myself…

That’s one of the big reasons I decided to make it myself. For the sort of games we are planning, A* is such an integral part of the game that it’s important to have a full understanding of how it works; and the best way to get there is to make it from the ground up. I hope you can still benefit from my blueprint when you start to make your own, and feel free to ask questions if you get stuck.

@Zeustiak;115355

I would start with creating a few variables labeled “Current Index”, “Current G”, “Current H”, “Current IsOutOfBounds?”, etc, and then setting them at the start of any large execution chain they are needed in. This will allow you to get rid of a lot of those lines running every which way and also give you a better idea of what is being input into a node since it has a named variable next to it instead of 10 pages away.

Turn your Get Wall Array + Branch into a function with your Current Index variable plugged into the Get. Same for Get Open List Bool + Branch.

All your Set Array Elem/BreakStruct/MakeStruct stuff at the end can be one function that has your Current Index/etc variables plugged in. You won’t even need 8 of them on the board, just 1 to take the place of all of them. Just make sure you have Set Current whatever variable appropriately hooked up coming out of each of those sequence outputs.

Also, pure functions are going to make your life much easier. Pretty much make them for everything. Make a Pure Function for each of your neighbor node index checks that happens at the start of the monstrosity at the bottom of the graph. Make one for Grid Size X times Grid Size Y, and the other 2 above that. Then make pure functions with those pure functions inside that output your bounds bools. Turn your IndexToVector and Manhattan macros into Pure Functions. Anything in your graph that is more than 3 nodes and only has non-execution outputs such as “Is End Index?”, “Is Less than 500 Index?”, your whole transform bit for the Path Instance transform, etc should be turned into a Pure Function.

that’s exactly the kind of input I was hoping for. I’ll be sure to look into all the solutions you mention. Thanks!

@Zeustiak;115355

Yeah though I don’t think I want to fatten my arrays with a wall around the outside. I think doing a small amount of math for each lookup should work just fine.

I suspect both solutions will be about equally effective, so I guess it’s more a matter of taste.

@Zeustiak;115355

Yeah, I have been thinking of pathfinding in terms of my whole map, but you may just want a smaller box that doesn’t search the whole map for a short path. In that case, you may be doing math on every run anyway so doing a pole check would be par for the course. So you could do a path check with a bounding box set to small, and if that doesn’t work, it redoes it with a larger bounding box to look for further paths? Could be a good way to optimize it. Maybe you could even get the height in tiles of an obstruction such as a known wall and set the box height to match.

If I understand what you are suggesting correctly, I doubt that would help with optimizing the pathfinding. If you have searched within the small bounding box to no avail, it wouldn’t make sense to start again with a larger bounding box. In that case the best way would be to continue on the end of the path which was made inside the smaller bounding box, and then it becomes identical to starting with the larger bounding box in the first place. I don’t think searching a larger array is automatically slower than searching a smaller array. That just depends on the length of the eventual path and the placement of obstacles in the way.

@Zeustiak;115355

You mean standalone? I have never used it, but just tried it with your generator and it worked fine.

I meant either clicking the Launch button next to the Play button or packaging the project as an .exe and running it. When you say standalone, you mean packaging the project (file -> Package project)? Weird that it works for you and not for me. Thanks for checking it out.

[Zeustiak]

@;115477

That’s one of the big reasons I decided to make it myself. For the sort of games we are planning, A* is such an integral part of the game that it’s important to have a full understanding of how it works; and the best way to get there is to make it from the ground up. I hope you can still benefit from my blueprint when you start to make your own, and feel free to ask questions if you get stuck.

Oh I am sure it will help quite a bit!

@;115477

If I understand what you are suggesting correctly, I doubt that would help with optimizing the pathfinding. If you have searched within the small bounding box to no avail, it wouldn’t make sense to start again with a larger bounding box. In that case the best way would be to continue on the end of the path which was made inside the smaller bounding box, and then it becomes identical to starting with the larger bounding box in the first place. I don’t think searching a larger array is automatically slower than searching a smaller array. That just depends on the length of the eventual path and the placement of obstacles in the way.

I think I see what you are saying. I think I had some A* animation I saw stuck in my head where it checks all the tiles in the map.

@;115477

I meant either clicking the Launch button next to the Play button or packaging the project as an .exe and running it. When you say standalone, you mean packaging the project (file -> Package project)? Weird that it works for you and not for me. Thanks for checking it out.

Ok, I was just using the dropdown next to play that says standalone.

I went into the level viewport that has the launch button and launch was greyed out. I clicked the dropdown to play it on my PC and it just hung there. So I opened the output log and it was dropping about 10-20 of these a second:

LogPlayLevel:Display: AStarPathfinding02: [2014.08.10-22.57.47:714][997]LogPrimitiveComponent:Warning: Trying to move static component ‘CapsuleComponent /Temp/Autosaves/Game/Maps/UEDPCMinimal_Default.Minimal_Default:PersistentLevel.TileCharacter_C_1.CollisionCylinder’ after initializationLogPrimitiveComponent:Warning: Trying to move static component ‘CapsuleComponent /Temp/Autosaves/Game/Maps/UEDPCMinimal_Default.Minimal_Default:PersistentLevel.TileCharacter_C_1.CollisionCylinder’ after initialization

[Monokkel]

@Zeustiak;115545

Ok, I was just using the dropdown next to play that says standalone.

I went into the level viewport that has the launch button and launch was greyed out. I clicked the dropdown to play it on my PC and it just hung there. So I opened the output log and it was dropping about 10-20 of these a second:

Hmm, strange. I’ll have to look into this some more. Thanks for the input!

[Monokkel]

After toiling for hours, I’ve now managed to change the open list in my pathfinding algorithm to a binary heap! Getting it to work properly was almost as big of a challenge as making the rest of the algorithm, but I work a lot quicker now that I’ve become more proficient with blueprints. Using a binary heap list has greatly improved the speed of the algorithm. With the old system the pathfinding would hit the loop limit after searching an entire array of 4545 (2025) nodes. Using a binary heap the loop limit is first reached if I increase the grid to 8484 (7056) nodes. This should be more than enough for my purposes.

However, there appeared an unexpected issue when using the new method. Though all generated paths are still optimal, they often don’t look as good as in the old system. The new algorith doesn’t care if it’s moving in a straight line or zig-zagging towards the target, as long as the movement costs are the same. This will not be an issue if I use hexes or have higher costs for diagonal movement, but I’ll have to find a solution if I decide to keep a square tile layout with equal costs in all directions.

Examples of paths generated with the old and new algorithms are posted below. Please tell me if you have any ideas for how to make the new path look more like the old one, though I might have a few ideas already

[Monokkel]

I’ve managed to fix the wobbly paths when using binary heaps, and the process has been very enlightening. I’ve simply added a single boolean if-statement every loop, but this has caused the algorithm to hit the loop limit at a grid of 81*81 nodes (down from 84). It seems small additions can have big impacts on performance. This probably means that the possibilites for optimizing are much larger than I thought, and that I should try to be be more vigilant in keeping the blueprint as simple as possible

[Zeustiak]

How goes it?

[TechLord]

My A* Pathfinding blueprint or: How Not to Build a Blueprint

Doesn’t UE4 use a built-in A* for navigation?

[Zeustiak]

Probably, but that doesn’t mean it is ideal for all situations. Even the devs have developed separate A* functions for specific things like precise grid movement.

If they could expose more of the navigation mesh code to blueprint that would be pretty sweet.

[Monokkel]

@Zeustiak;138593

How goes it?

I’ve had a really busy schedule the last couple of weeks, so work on the blueprint has progressed a bit more slowly lately. I have made some significant additions, but these lie outside the pathfinding algorithm itself, and so I haven’t updated this thread, and was planning to start a new thread about making a turn based strategy system (With the a* algorithm as the base).

So far I’ve implemented Dijkstra’s algorithm for choosing and displaying all tiles a pawn can move to, depending on the speed attribute of the pawn. I’ve also created a system for selecting and moving pawns on the grid. I’m currently also working on an unrelated Project on the side, so I’ll probably keep making slower progress the next few weeks.

@TechLord;138738

Doesn’t UE4 use a built-in A* for navigation?

@Zeustiak;139548

Probably, but that doesn’t mean it is ideal for all situations. Even the devs have developed separate A* functions for specific things like precise grid movement.

If they could expose more of the navigation mesh code to blueprint that would be pretty sweet.

Indeed. If all you want is to find the shortest path to a node, the built in A* Works great (and a Whole lot faster than my implementation). However, for creating a grid based game I need access to information from many of the intermediary steps of the algorithm. For instance I need to be able to exactly match pathfinding nodes to the tiles in the game, to display which tiles are part of the path and to handle events that trigger when pawns enter or exit specific nodes on the path.

Nothing would make me happier than if I could access and tweak the in-built pathfinding through blueprints, but at the moment it seems I must make my own system to get the sort of control I need.

[Zeustiak]

@;143050

I’ve had a really busy schedule the last couple of weeks, so work on the blueprint has progressed a bit more slowly lately. I have made some significant additions, but these lie outside the pathfinding algorithm itself, and so I haven’t updated this thread, and was planning to start a new thread about making a turn based strategy system (With the a* algorithm as the base).

So far I’ve implemented Dijkstra’s algorithm for choosing and displaying all tiles a pawn can move to, depending on the speed attribute of the pawn. I’ve also created a system for selecting and moving pawns on the grid. I’m currently also working on an unrelated Project on the side, so I’ll probably keep making slower progress the next few weeks.

Yeah same here with being busy. Look forward to seeing your new thread. What kind of game exactly?

@;143050

Indeed. If all you want is to find the shortest path to a node, the built in A* Works great (and a Whole lot faster than my implementation). However, for creating a grid based game I need access to information from many of the intermediary steps of the algorithm. For instance I need to be able to exactly match pathfinding nodes to the tiles in the game, to display which tiles are part of the path and to handle events that trigger when pawns enter or exit specific nodes on the path.

Nothing would make me happier than if I could access and tweak the in-built pathfinding through blueprints, but at the moment it seems I must make my own system to get the sort of control I need.

Yeah I think I will make a request in the roadmap thread to expose more of the navigation mesh to blueprint with emphasis on Turn Based applications. What is currently exposed of the nav mesh is more for FPS/RTS/etc games.