The beauty is that you need *no* map to start with. Just a way to sense your coordinates (GPS or dead reckoning, or any combination of the two should work well.) and obstacles that can not be traversed.
In a fairly sparse environment a LOS Bug algorithm would work slightly faster but D* with localization is pretty good for teaching your robot how to go from any where in the house, to your refrigerator and back, and never have an exactly accurate map. And the D* algorithm won't have any problems with local minimums (known as wells) like a P-field might. Although it does need tweaking to make it work in an inexact environment, so I'm trying reading about a subsumption architecture that combines D* with a P-fieldesque approach for object avoidance.
slow going....ug....