Hey,

A* is great, it finds the closest path possible. But what could I do, to vary that path a little bit? E.g. don't always take the closest path possible, go 3rd or 4th closest path. Or just move little bit different path.

What do you guys suggest to make it look great?

I had the same idea. How big should that random be? Currently I see these cost values range from 2 to 80. What should I factor in random range?

Plug in some numbers and find out?

Indeed. Cost perturbations should be positive, to avoid any possible risk of getting negative costs, but it's the only real constraint: noise amounts greater than the cost difference between the actual best move and the second best one have no effect (the best move remains the best), but that difference is often zero.