As extracted from game files.

https://gist.github.com/jbzdarkid/440ef052bfed0c6b0145f1717cf4cb1f

For those who aren't super coding-savvy, here's the critical lines: var chance = Math.random() * (150 - risk); if (chance <= _root.btlChance && _root.btlChance != 0 && GameData.steps >= 30 || _root.forceBattle)

Every step you take adds to "risk", and to GameData.steps. The game counts 30 steps (on any square), which are always safe -- and aside from that, it increments "risk" every time a battle could occur, and doesn't. Therefore, it's possible to "use up" the 30 safe steps, even if your risk is still 0. btlChance varies per region, lower meaning fewer encounters. Here's the list of values & the average encounter rate:

Battle chance 1: 89.5 steps per fight

Fire Temple Hub Battle chance 2: 69.33 steps per fight Goznor Sewer Level 1, Sandflow Caves - Gate room, Green Switch, King Cuthbert, Sun Temple, Water Temple Battle chance 3: 59.25 steps per fight Aeropolis Slums, Astral Tunnel, Canonia Woods, Catacombs, Crimson Peak, Crystal Cave, Dark Temple, Dreamcave, Dreamshrine, Dreamwood, Eastern Glens, Fire Temple 2 and challenge rooms, Gem Mine, Lake Qur, Lake Qur Underwater, Lifewood, Moric's Battleship Level 1, Sandflow Caves - Blue Switch, Soothwood, Tainted Grotto, Trilobite Cave Battle chance 4: 53.2 steps per fight Fire Temple Antechamber, Goznor Sewer Level 2, Miasmal Citadel, Sandflow Caves - Gizmometer, Passage to Miasmal Citadel, Passage to Sun Temple, Saul's Dungeon Battle chance 5: 49.17 steps per fight Earth Temple, Lost Monastery, Social Fox's Tomb Battle chance 8: 42.44 steps per fight Dreamwood - Pixie Spring, Gem Mine Underwater Battle chance 10: 40 steps per fight Dragon's Lair