Hi, I’m working on a game prototype similar to XCOM: EU. At the moment, I’m working on the pathing for AI and player characters. I’ve already got a dynamic grid based movement setup working and have been using the default pathing algorithm that came with UE4. Since I’m spawning grids only around the mouse click, I’m showing the path from the actor location to the destination point using splines and ‘path to location’ node. However that’s when I hit a problem with navigation. I noticed that all my characters that are placed in the level before level start do not follow the shortest path during their first movement command. In fact, they usually take a step in some random direction based on the nav mesh cut around them, and then move towards the destination. Until I got the splines working, I didn’t give much attention to this as it was only happening during the first movement turn. You can see it here:
So after checking navigation I’ve realized that if my character’s collision affects the nav mesh, it creates a hole in the nav mesh around their initial position. But once they’ve move out of that region, there still is a hole in the same place and nothing near their new position. As a result, now no one can move to this starting location and there is no pathing around this character’s current location.
If I have the player characters to not influence the nav mesh, they move correctly. But whenever they have to path around the other characters, they just bump in to them. I’d like to know if there is any way to tackle this internally in UE4, or if I would have to go and implement some custom A* algorithm for pathing.
By default UE4’s Navigation System does not take characters into consideration when finding paths and the only way to achieve that out of the box is to have characters affect navmesh generation - like you did. However, you also need to enable runtime navmesh generation to have navmesh react to characters’ location changes (this can be done vis Project Settings in the Editor). In an XCom-like game I’d suggest controlling this behavior dynamically, meaning enabling character’s navmesh collision when he’s stationary, and disabling when on the move (otherwise constant navmesh regeneration is messing with his pathfollowing).
The “random step” behavior you’re experiencing is a result of character-generated holes in the navmesh. Navigation paths found for characters are bound to the navmesh, so the first path point is not at character’s feet, rather at a point on navmesh closes to the feet. This could be easily addressed by disabling navmesh collision for “current” character so that he doesn’t have a hole under his feet when looking for a path. Alternative solutions are not possible without code changes, but exposing this functionality is on my list of things to do.
Hi Mieszko, I had tried the run time generation for navmesh. That helped to move the character generated holes along with the character. But as you said, that was also causing the characters to move erratically. So I turned it off. You’re referring to the “SetCanAffectNavigationGeneration” function right? I’ll try that out and let you know.
And thanks for explaining the pathing relation to the navmesh. I was wondering why it was moving that way. There also seems to be an issue with shortest path in my case. If you check out the first picture above, player 1 going behind player 2 seems to be the shortest path. However it’s taking the longer path in front of player 1 to reach the destination. But if I reduce the ‘CellSize’ from 19 to 10 and ‘AgentRadius’ from 35 to 20, it’s able to correctly find the path. But even at that radius, since the navmesh hole is bigger than the size of a movement grid that I’m using, it might create a similar issue in the future. I could probably take care of that by reducing the agent radius and cell size until it’s smaller than a single movement grid. So I wanted to know how well the overall performance scales with increasing the navmesh details. As you see, I’m using a very simple map for now. With more meshes, it’s obviously going to get complex. So I just want to get your opinion on whether it’s feasible on the long run.
Hey, I’ve tried out turning on/off ‘SetCanAffectNavigationGeneration’ along with runtime rebuild. Now, the navigation is working fine. Thanks a lot man.
Regarding pathfinding we use a regular A* algorithm for finding paths on the navmesh. It does find the shortest path, with couple of caveats related to implementation details. In practice the “shortestness” of a path depends to a degree on underlying navmesh structure, how the navmesh in given area is triangulated. Another thing influencing the perceived shortestness of a path is that we’re not calculating the string-pulled path. The shortest path is found in navigation graph build with navmesh polygons, and the string pulling is just a postprocess step after the path is found.
What it all means in practice is that the higher the resolution of the navmesh (the smaller the size of a voxel) the better quality of the paths found. Higher resolution navmeshes are of course more time consuming to generate. Since you need navmesh generation performance as well you need to find a satisfying balance yourself.
One more thing you might want to play around with is RecastNavMesh.HeuristicScale. This influences how important the “direct distance” is for the A* algorithm. Setting values over 1 results in the algorithms preferring to go straight towards the goal. Counterintuitively this is not always what you need since it may result in worse performance (when direct path does not exist) but could help in finding the shortest-shortest paths. This is just an experience-based hunch
Cool, i don’t think I’ll need to change HeuristicScale for now. I’ll increase the navmesh resolution when needed and see how it scales as I add more details to the level. I don’t see much performance drop for now with the increased resolution. Unlike most Turn Based games, I do not want to restrict movement along the grid centers and diagonals. All that matters to me is the starting point, end point and a seemingly shortest path. So I’ll try to stick with the unreal navigation as much as possible. Thanks.
hi,MieszkoZ:
i understand your answer, but how could we get a better result as the moving character can block others except himself(without random step)??
