footprints and moving smoke effects?

youtube.com/watch?v=Khfp6gm6 … ure=relmfu

0:58 - footprints
How to do that? I have some ideas but they will be too slow and some of them wont work on uneven terrain.

Next is the smoke effect, which starts at 2:41. I have asked this before. Im wondering if you can have individual particles relative to the world, not the particle system. Some use billboards, but this is a faster approach.