When entering the tile of a tribal hut, it rolls a result and if the result is agreed, you get the prize. For example, if a scout, a game without barbs or 8 tiles away from your capital, you can't get barbs. If the first dice roll gives barbs, then it rerolls until a result fulfills the condition. And it goes on until 10 rolls, then if the result is not acceptable (like XP points on workers, settlers or city culture spread), it gives the incredibly rare result: "nothing", which was noted in the past game CivIII, but in Civ4, it just vanishes. Depending of the conditions, one may skew the tribal hut results, but it is rarely worth it because, in the end, it's all random. Nonetheless, here is a small list of possible conditions to bias the results:
1) No XP for workers, settlers and culture expansion
2) No techs before settling capital (unless playing K-mod)
3) No "friendly tribe healing your unit" if your unit isn't damaged more than 60% of its health.
4) No barbs for scouts, huts 8 tiles or less away from capital or "No Barbs" games.
5) No warriors or XP before the 10th turn (whatever the gamespeed). It was done for MP fairness.
6) Free settlers or workers below Prince diff.
That is all. Now, regarding a correct pathfinding to find huts, note that huts are hardcoded to never be distributed in less than three tiles of separation. Therefore, it is possible to make a optimal pathfinding to get as much huts in the fastest time while leaving unfogged regions. Only problem with hut system allowed is it confronts the basic need of complete exploration to plop your first cities with the best resources around. And that needs complete exploration of surroundings without leaving a single tile uncovered lest to miss a capital resource. Optimal "search and destroy" hut quest compromises this.
La fin.