I'm late to the party, I guess.
I have done some studying of how the RNG in this game works.
It seems that, in addition to the normal RNG used in battles that is similar to Ruby/Sapphire/Emerald, there is a second RNG used only to determine wild encounters.
The normal RNG ("RNG 1", address 0x3005000 for U version, 0x3004FA0 for J version), if you remember, uses the formula:
val <- val*0x41C64E6D + 0x6073
The second RNG ("RNG 2", address 0x20386D0 for U version, 0x203861C for J version), uses this formula:
val <- val*0x41C64E6D + 0x3039
In addition, RNG 2 only ever advances if you step in grass/cave/water. This verifies pretty much what everyone is saying about encounters.
RNG 2 is seeded in a strange way. This occurs right after the Charizard screen clears in the intro. First, RNG 1 is seeded with the 16-bit entropy address 0x4000104. Then RNG 1 is advanced twice. Then the top half of RNG 1 is used to seed RNG 2, which is thereafter used in the game.
Note that RNG 1 is seeded again at the naming screen, so the first seeding of RNG 1 is only used to seed RNG 2, and nothing else.
I can't really clarify the entropy address (it is very sensitive to timing and even moving around the naming screen), so it may have to come down to trial and error. What I do know is that, from running some C++ programs, I found that there are a few RNG 1 seeds that generate RNG 2 seeds with as few as 3 encounters within 74 advances of RNG 2. (I pulled the number 74 from an estimated minimum number of advances before you reach Pewter City and get Repel.)
There are some things that delay the advancing of RNG 2, but it seems only to be the first 6 grassy steps after a battle or when entering a new area. By the way, the encounter rate in grass is 21.5%. If top half of RNG 2 mod 1600 is less than 344, you get an encounter.
I used the debugger
VBA-SDL-H to help with my analysis. It wasn't too hard for me; just
- find RNG 1 and 2's addresses,
- construct a scenario, with help of Lua scripts to analyze, where their behavior is interesting,
- reconstruct the scenario in official VBA (because savestates are compatible with VBA-SDL-H),
- set a read/write breakpoint on them in VBA-SDL-H, and
- disassemble away.
Of course, having a lot of context helps. I don't have to examine all the opcodes to do a verification; I just need a clue to the likely formulas. Once I have that, the analysis takes care of itself.