Instead of starting from really scratch I started with precompiled maps from this website:
There are many others providing the same service and similar outputs. Another famous source for maps is this website: http://wiki.openstreetmap.org/wiki/User:Computerteddy
Here you get a lot of precompiled tiles and also some final maps for upload to GPS-device.
What do we get?
When downloading a map from the first website, you get an installer for windows. But in fact it's just a self-extracting zip file and you can also open the exe with 7zip.
So unpack it into a folder of your choice.
There you have the map data!
PS: I chose the map of south africa because it is quite small and processing very fast, you can do this with any map and any tiles.