(Disclaimer: I’m no expert on UE4’s navigation system, but I have written a few navigation algorithms from scratch for other projects, so I hope I can help shed light on the matter.)
I’m pretty sure your issue isn’t being caused by UE4 lacking some implementation of A* (or similar algorithms). What’s happening is UE4’s navigation system (specifically, the UNavigationSystemV1 class, if I understand you correctly) is calculating a navigation path and then optimizing that path by removing unnecessary points along the way between the starting position and the goal position. In other words, this behavior is designed to reduce the navigation path down to as few nodes (think of these as ‘waypoints’) as possible. In many cases, the result will be a straight line at an arbitrary angle — which works great for a lot of games, but isn’t necessarily what you want in a game constrained to a tile system, like yours.
Furthermore (hang in there), I believe UE4’s navigation system is built upon using navigation meshes, which are like simplified polygon meshes representing the reachable and unreachable areas of your level. This is relevant in your case because nav meshes don’t always contain polygons of the same size or shape because these polygons need to conform to the layout of the level they represent. (Being able to take on different shapes is sort of what makes polygons useful in the first place, right?)
Tile-based levels, on the other hand, are — pretty much by definition — made up of uniform-size and uniform-shape pieces. A totally different situation than your typical FPS level, for example.
Now to the point: your game may need a custom navigation system. The idea would be to supply a pathfinding algorithm (such as A*) with a collection of all your level’s tiles (in pathfinding talk, this collection is called the ‘graph’) and therefore have the algorithm create a solution that obeys the movement constraints of your tile system. (This is where the movement costs you asked about come in, using heuristics like Manhattan distance or similar; Wikipedia and other resources have great explanations of how that stuff works.) Then, depending on what kind of results you want, you can choose whether to ‘optimize’ the output by removing points along the solution path that you deem unnecessary. In either case, you can produce a pathfinding solution that strictly adheres to the tile-based system that you have in mind.
Of course, creating a custom navigation system is a bit of work. Luckily, if you do decide to go this route, there are a lot of resources online that are great at teaching the subject and showing plenty of examples. So it’s not as difficult as one might think.
I hope this helps explain things a little. (And I hope my lack of expertise with UE4’s built-in navigation system doesn’t end up making me look stupid!)
In any case, good luck!
