I am not sure exactly how AI following the player works, but to me it seems that they try to find the most direct way to the player.
I would suggest instead to have a pheromone kind of pathfinding. Where the player occasionally drops and invisible object when walking, which the bots pathfind to one after another.
This would mean the bots would follow the players path a little closer in case they are a bit slow again. This also might help with the water problem, where if you swim through a body of water the ai sometimes will walk around the water instead of following your swimming path.