Debugging the game using Altirra (an excellent Atari 8bit emulator) I was able to find where the lives are stored, player and enemy positions, but most importantly, I found the memory location where the displayed room was stored.
This opened the possibility to modify rooms, so I planned a PoC (Proof of concept): Would I be able to modify a pair of rooms from the game and even play?
In a few weeks (March 2018) I was able to do it (in a very unpractical way), but I prove it was possible!
The next months I dedicated my scarce free time trying to understand how the rooms, enemies, and items were defined in memory, and how some memory locations stored relevant information that needed to be loaded in order to display correctly the room, enemies, and items. Once I understood the coded mechanics, I made my own room load, item load and enemy load routines (very different from the original ones by the way).
Now, I needed to insert my new code to the game, and the newly designed rooms (which I made initially with AtariMapMaker from MatoSimi), but the original Montezuma executable is only 16kb (this was a space restriction made back when the game was programmed in 1984, to make it fit in a 16kb cartridge), so I expanded the file to 32kb, leaving me with 16kb to store my code and the newly designed rooms. This was done by compressing the rooms (each room is 1000 bytes uncompressed, that is 40 tiles width by 25 tiles height)
Once I finished including this new code and rooms (may 2018), I released a demo version I named "Montezuma Again! (demo version)", which included only 13 new rooms, all of which where stored inside the executable file.
Then I continue designing and including more rooms (eventually up to 100 per pyramid), so I turned my eyes into AtariMapMaker and remembered that MatoSimi has posted the source code of this software. I contacted him asking for permission to use his code as part of a Montezuma Map Maker, and he accepted. Since then, I installed Visual Studio and analyzed the code. Also, I programmed some classes to represent the pyramid, it's rooms, enemies, items and their position.
Once I understood most of the code of MatoSimi, I started programming what I call MonteMaker, a mapmaker for Montezuma that allows fast designing of rooms, items, and enemy positioning. It also creates the XEX file automatically, all in a graphic way. This helped me a lot to design and test the other 59 rooms, for a total of 72 that Montezuma Again! Final version 1.0 has (released September 2018). Why 72 and not 100? Only space. I made too many intricate rooms, that compressed poorly, so the space for more rooms inside the XEX was insufficient.
The next step from now on is to continue improving MonteMaker and make more pyramids (easier ones) and release MonteMaker and more romhacks of this great game.