I ordered a cheap external EEPROM, i think for now i will settle for just storing critical coordinates, instead of the whole matrix
A particular method to keep in mind (if most of the area you are mapping is considered "empty") is the concept of "sparse arrays":
There are tons of techniques out there to "pack" what seems to be an amazing amount of data into a very small space - two of the best areas to learn about these techniques are from the game programming and demo coder worlds (especially those demos optimized for very small memory footprints; you would be floored by what can be done in 256 bytes).
Also, a review of certain "large" computer games from the 1970s and 1980s might be beneficial; many of these games (especially the larger scope turn-based and real-time strategy games) used fairly interesting techniques to pack their "worlds" (analogous to your maps) in small areas (aka, floppies) - granted, floppies have more space than you have available (most generally), but the techniques could be helpful.
