How to use A* for animals walking on a procedural generated mesh?

Hey, this is just a theoretical question based on my project setup:
I use the procedural generation code by sebastian lague. This creates a mesh with high und low points. After this, vegetation such as trees and stones are spawned. Then i want animals to move with A* pathfinding randomly around the map.
How do i approach this at best? Since this is all dynamically generated it would make sense to use the grid from the infinite world example but i could not figure out if this only works with meshes having a straight floor. This would be perfect if the animals could just move around like this.
A Recast Graph could also be an option since 3 dim meshes are no problem but i really dont know how to face this properly. I tried to solve this problem with unitys navmesh but this took way to long to bake, so A* here we go!
How would you solve this problem?