Some slick work has produced a functioning GPS device on the Nintendo DS using Google Maps. The author has yet to release the code (only "after a few things are cleaned up a bit"), so you'll have to be patient. In the meantime, be sure to pick up the GBA Movie Player (and Compact Flash card), as it's used to store the program and map data. We'll keep you posted.
[Thanks, retro]

