Procedural Object Avoidance

I have a “infinite” procedural terrain, how can I have AI that avoids gameobjects and walks around them to get to the target?

I can’t use NavMesh, because it can’t bake at runtime.

I am not sure if I can use A* because it seems to work with either predefined paths or a grid system which can’t fit an infinite terrain. (I am not sure if it has some way to do this)

If you could give me any suggestions on what would work fine for my game(Minecraft type just without voxels)

If you know you’re obstacles can be avoided by going either way around them, as in they are single blocks of obstacleness, then you could have your enemy walk in your direction and if there becomes an obstacle a certain distance in front then move parallel until the enemy ca ‘see’ you again.

Alternatively, I think the best bet would be to update you navigation grid proceduaral as you update your terrain or whatever!