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.
Cheers,
–mieszko