The wide availability of 3D-printers makes possible the simple creation of tactile maps for individuals with blindness. However, to be useful, these maps have to be designed using feedback from the future users. In this study, we worked with fifteen individuals with blindness to develop an optimized encoding system for 3D-printed tactile maps for building interiors. Based on their requests, we focused on the development of maps with information about safety routes and emergency exits. Additionally, users identified a set of important physical objects to be encoded on the map. After that, multiple encodings were evaluated individually and when integrated in maps. This resulted in a set of optimal encodings that was most positively perceived by all participants.