Dr. Mario virus placement

Thread in 'Research & Development' started by IoannesPaulus, 3 Aug 2012.

  1. Hi,

    Does anybody know the algorithm behind the virus placement at the beginning of every level of Dr. Mario? I'm interested in the NES version and the SNES "Tetris and Dr. Mario" version.
    The patent only mentions random number data, and I'm not into disassembling and understanding ROM assemblies.
    This is what I know. The grid (bottle) size in these versions is 8 x 13.
    On each level there are (level_num+1) x 4 viruses. In the NES version the maximum number of viruses is 84 (21 x 4), the SNES version goes up to 96 (24 x 4).

    The pattern we get at the end of virus generation has one quite visible attribute: there are no second neighbors (neither horizontally nor vertically) of the same color (i.e. you never see this: V?V - where Vs are identical color viruses and ? is a cell of any kind /empty or occupied/).
    When filling the grid with viruses - drawing them at least - you can see the viruses being placed so that the three colors take turns. The first color is randomly selected (let's say red) and then the sequence is red, yellow, blue, red, yellow, ... During placement the algorithm never "gets into trouble", there is always a legal empty cell to place the next color.
    If you implement a dumb algorithm that rotates through the colors and always places the next color randomly to a position that is legal (cell is empty and does not have second neighbors of the current color) then the algorithm may "get in trouble" - as mentioned above -, and cannot place the required amount of viruses.
    This means that there is a placement "strategy" that guarantees that the required amount can be placed.
    As I saw the pattern that emerges during population of the bottle looks like there are "holes" left out which are filled from the edges.

    Of course the contents of the bottle may not be generated in the order of the viruses appearing, but I suspect it is. If it is not then the generation must also guarantee that there are nearly the same number of all colors (exactly the same if the virus count for the current level is divisible by three).

    I'm quite interested in this topic, so any extra information is well appreciated.

    Cheers
     
    Last edited: 3 Aug 2012
  2. Amnesia

    Amnesia Piece of Cake

    if no one here can give you a reply, I have 2 people in my facebook friend list who seem to be crazy at Dr Mario. Maybe they will be able to help you.
     
  3. I don't know. All my knowledge is either about strategy or tactics, or in the form of muscle memory. Patrick has been studying and taking notes(mostly about what causes freezes, I guess, but maybe other things of interest too), so maybe he'd be able to offer something.
     
  4. Kitaru: should we do some disassembly funtimes?
     
  5. Yes, I think so.
     
  6. Looks like the patent does have some hints as to how the algorithm works, and might be helpful while disassembling; go to page 22, top of column 12 of patent 5,265,888 to see the relevant randomizer part. It looks like the game might use a predefined table of numbers to generate the viruses and uses the same table for piece generation. Page 9, Fig. 6 might be the most important, as it might be something of a guide to disassembling the ROM.
     
  7. nightmareci: I also had similar thoughts :)

    Zircean and Kitaru: if you can get the info by disassembling, you're the best! :D
     
  8. Amnesia: nem gondoltam, hogy a Dr. Mario téma épp egy másik magyart szólaltat meg először ;)
     
  9. I managed to find the necessary information to find out how the randomizer works, but I'm a bit in over my head with figuring out the randomizer's workings. I've attached my notes that will help a more experienced individual find out how the code works; the main thing I found is where the code writes viruses into the bottle, which will eventually lead to the randomizer code. I also found information about how the code generates capsules.

    I myself am interested in how the randomizer works, as I'd like to use the information in a clone; there are just so few Dr. Mario clones, probably due to the randomizer problem.

    I haven't analyzed any versions other than the NES one.
     

    Attached Files:

  10. Cool. I also started the whole investigation because I created a clone for Symbian S60 several years ago and this was the hardest part back then and I never managed to figure it out. :)
     
    Last edited: 31 Aug 2012
  11. Amnesia

    Amnesia Piece of Cake

    Ha ha ha..Magyar emberek mindenhely vannak !
    De sajnos, nem magyar, francia vagyok, dolgozok Szentes 3 éve.

    EDIT : Hol laksz ?
     
    Last edited: 22 Aug 2012
  12. Hát vicces, de egészen egy héttel ezelőttig Pesten laktam. Most pedig Olaszországba, Bariba költöztem (még épp lakást keresünk barátnőmmel).
     
  13. Amnesia

    Amnesia Piece of Cake

    I dont think we can keep talking in hungarian, some moderators could tell us something...I am glad that today I can get the meaning without jumping on google translator anymore (I hope)...But just roughly, and because I know my initial question :

    You have been living in Peste, now you are in Italy, at Bari where you are searching a flat for you and your girlfriend.

    :$
     
  14. Yes, sorry about that, moderators. :)
     
  15. I found the randomizer code and have figured out a bit of how it works. I've also rewritten the randomizer in C code. A few notes:
    • The algorithm to insert a virus fails in some situations. It's okay though, the function usually only fails 1-2 times at most, but usually succeeds first try. The algorithm first randomly selects a position in the bottle to insert, searches left-to-right top-to-bottom for an empty position from the starting position if the starting position was filled, then fails if the search for an empty position goes outside the bottle in the lower right corner.
    • For the randomly selected position to add a virus, it will only place a new virus there if it's not the case that all three virus colors surround that position two columns/rows away. So, visually, this would be a "dead cell" (term coined by pineapple), with the '*' the candidate cell and the '-' characters can be anything:
      Code:
      --Y--
      -----
      R-*-B
      -----
      -----
      This would not be a dead cell, because the candidate is only surrounded by two colors, not all three:
      Code:
      --B--
      -----
      R-*-R
      -----
      --B--

    See the attached archive for C code of the algorithm, and an assembly listing containing the function that inserts a virus into the bottle heavily commented. Also, some informational text files are included that describe how I got to the code that inserts into the bottle.

    I plan on looking at how vitamin randomization works too, but I haven't gotten there yet. And I *might* look at the SNES version's code some day, but I'm not yet ready for that project.
     

    Attached Files:

  16. I've improved the C code now and added a simple Makefile for Linux and Mac OS X developers. I've also added an assembly listing of sub_B771, which is a simple RNG function that is part of the original 6502 code that generates a virus. Lastly, I verified the code is precisely equivalent to the 6502 code, and it generates the same bottle contents for a given seed. To test the code works for a specific seed, do the following:
    1. Load up Dr. Mario in a NES emulator with debugging features. FCEUX is a good one, and I even use the Windows version under Wine, and it works great; the Linux/Mac version lacks the debugger.
    2. Set a breakpoint at $9CFF. $9CFF is the location where the virus generation function starts.
    3. Choose virus level 20 and any speed; virus level affects the randomizer, but speed does not. The code has provisions for speed to affect the randomizer, but it was coded such that selecting any speed gets the same results as any other speed choice. The reason for choosing virus level 20 is the bottle program is hard-coded with that level, but if you modify the code you can change the level and use the same level when running the bottle program.
    4. Start the game. The breakpoint should be hit pretty quickly after pressing start; leave the debugger stopped where it hit the breakpoint, don't let it continue.
    5. Pull up a memory view (the "Hex editor" in FCEUX's Debug menu) and look at the bytes at addresses $17 and $18; run the bottle program with the contents of bytes $17 and $18 as arguments, i.e. if $17 = $C6 and $18 = $8F, then run the bottle program as "./bottle c6 8f" (or use uppercase C6 8F, it doesn't matter).
    6. Remove the breakpoint you added in step 2., then let the code run so you can see the full contents of the bottle.
    7. Pause the emulator somehow (the Pause key on your keyboard in FCEUX) and examine the virus contents of the bottle, checking that it matches up with the output of the bottle program.
    There's also a test script (test.sh) that, once the bottle program is compiled, can be used to test if the program generates the correct contents for seed $17 = $C6 and $18 = $8F.
     

    Attached Files:

  17. Hi,

    Awesome, you're the best! :)
    I haven't had time to run through the code yet, but I definitely will have a go in the upcoming weeks.

    I read through your posts. You say: "The reason for choosing virus level 20 is the bottle program is hard-coded with that level". You mean the original one? Then how does it accomplish to generate viruses for lower levels (e.g. the lower levels have smaller virus height in the bottle)?
     
  18. Zaphod77

    Zaphod77 Resident Misinformer

    It's known that you cannot manipulate the piece sequence after the game starts.

    I strongly suspect that all 9 possible combinations are equally likely. (RB and BR are different, even though you can flip them around). you get two chances per piece to get your desired color, and dual colors being more common than single color helps with constructing combos.
     
  19. I believe he is referring to his bottle program in its current state.
     
  20. Ok, thanks. That makes sense, just wanted to clarify.
     

Share This Page