Categories
Reversing

Animal Crossing’s Perfect Town

Nintendo’s Animal Crossing series allows humans in 2020 to dive into a fictional world and experience wild, unattainable realities like going outside regularly and interacting with other beings. So naturally, I’ve been leaving it idle in the background during quarantine and hopping in every time I have a moment to spare.

In these games, there’s a goal that you can strive for to create the perfect town, as judged by the wishing well in the town. Creating the perfect town involves removing weeds, making sure there are enough trees, making sure there aren’t too many trees, cleaning up garbage, and possibly spicing up the place with flowers? But I’ve never seen a good reference for how this is actually evaluated; just vague GameFAQs articles from 2003 that suggest there may be a scoring system.

What follows is only a half-filtered live blog of my thought process while trying to reverse engineer this mechanic.

Where To Begin

So let’s dive in. Dolphin’s debugger is pretty legit, so let’s start by searching for the strings that the wishing well gives you as an evaluation. I downloaded an old save of a “near-perfect” town, and loaded it once with the modern date so that it’s overrun by weeds (since it was uploaded nearly a decade ago), and another state loaded in its time when things were still wonderful in the world. This should give us two separate strings to search for and the ability to crawl the stack upwards and see where the string is decided.

Luckily, both strings were pretty easily found in memory while on screen because they were in a mostly-ASCII format (with some leading special characters). They seem to get copied from elsewhere to the point that they’re actually read from by this loop at 0x803c0a20:

mtctr r0 # Move size of string to counter register
cmpwi r0, 0
ble- done # Predict no branch, string is non-empty
loop:
lbz r0, 0 (r4) # Read byte from address at r4
addi r4, r4, 1 # Move r4 up
stb r0, 0 (r3) # Write byte to address at r3
addi r3, r3, 1 # Move r3 up
bdnz+ loop # Decrement, branch if non-zero, predict branch
done:

So now before we go tracking down where r4 is calculated from, let’s do a quick experiment. Get the value at r4, and see if that address even contains the string at the beginning of this function. In my run, it was 0x81298364, and loading state and checking out that address at the start we see…

.....What errand
 have you at....
..the wishing we

So no, it’s not loaded yet; it’s still showing the prompt. So let’s track down which function call brings it in there by stepping through while watching the memory.

bl 0x8009aed0 # Nope, not this.
...
bl 0x803ac5c8 # Still nope.
...
rlwinm r3, r4, 0, 0, 26
addi r0, r5, 31
sub r31, r4, r3
addi r4, r28, 32
add r0, r31, r0
rlwinm r5, r0, 0, 0, 26
bl 0x80006c74 # Boom, it changed.

Hol’ Up

Actually, before we dive too deep and follow where the actual string copy takes place… maybe we should realign our target here. Loading up the “too many weeds” save file and prompting the wishing well, we hit this same block of code, so let’s compare the register values that gets set before this function call and see if perhaps which string to show has already been decided here.

# Too many weeds
r0 = 0xfe
r3 = 0xb4d9a0
r4 = 0x81298360
r5 = 0xe0
r31 = 0x12

# Town is mostly okay
r0 = 0xf8
r3 = 0xb4dac0
r4 = 0x81298360
r5 = 0xe0
r31 = 0x4

So r0, r3, and r31 are different and seem like ripe candidates for a string table offset/size or something along those lines. At the risk of crashing the emulator, let’s try and change them in the good case to the values used in the bad case.

Good town showing the bad town string; getting somewhere.

So the state of the town has already been decided at this point. Repeating this register-inspection as we go up the stack, we note that the calls to 0x803c0998 differ in the value of register r4, and we soon find out that 0x2c49 gives us good text and 0x2c47 gives us bad text. Just out of curiosity, can we assume that 0x2c48 is some intermediate state of disrepair?

Close, it’s the coveted perfect town string!

Okay, let’s wipe our breakpoints from the string copy since we know the computation happens outside of here. Repeating the pattern up the stack, we eventually find that the string table index is written in lwz r4, 0x0444 (r30) so let’s reload the good town, and set a memory breakpoint on where that evaluates to at 0x812982cc.

Interestingly, the first hit on that address is 0x803c00ac writing 0x2c45 (which is close, but not exact) instead of the value we expect. Continuing to the next one, we see the exact same instruction writing the expected value of 0x2c49. Curiosity strikes again, what string is 0x2c45?

It actually loads that string first in both the good and bad towns, so I guess it defaults to “you need more trees” before actually counting them? Let’s actually take this moment to compare the call stacks in the good and bad cases.

# Mostly good town
[ LR = 0x805bad48 ]
[ addr = 0x805bb244 ]
[ addr = 0x8037528c ]
[ addr = 0x8062aa18 ]
[ addr = 0x8062ab30 ]

# Weeded town
[ LR = 0x805bad48 ]
[ addr = 0x805bb244 ]
[ addr = 0x8037528c ]
[ addr = 0x8062aa18 ]
[ addr = 0x8062ab30 ]

Seems identical to me, so sadly no “this call is for good town, this call for bad town” just yet. Let’s keep climbing the stack until we stop seeing our table string offset values as the main argument being passed so we can properly discern when it’s computed.

Hitting the Callstack Ceiling

Okay, we’re at a tricky spot where we’re now stepping through functions that are called for other purposes other than this one, so we need to find the “earliest unique breakpoint” for this value getting computed and written. We do this by just hamfisting a bunch of breakpoints that come earlier than our last known one and at last, we come upon our possible first eureka moment: 0x805bad34 gets called in the good case but not the bad case. Looking around this method we can see some assembly I’ve labeled after figuring it out:

b prepare_print # We land here in bad case, skip past
almost_good:
lwz r0, 0x10 (sp) # We land on this in good case
li r29, 4
subfic r31, r0, 11342 # 0x2c49 gets loaded into r31
prepare_print:
mr r3, r30
mr r4, r31
bl 0x803c00ac

Unfortunately, “stepping out” just brings us to a generic “branch to control register address” call which is used for a bunch of other code, so we can’t set a breakpoint there; we’re just going to spam some more breakpoints above this area until we find the function entry point.

First common point I’ve found is at 0x805bac94 where we have:

cmpwi r31, 4
beq- almost_good

And as you can probably guess, almost good town takes the branch, bad town doesn’t. Just for fun, let’s try different values of r31 at this point.

Seems that we’ve missed the mark for perfect town at this point, so that check may have happened earlier since values 2-5 all give “it’s fine”. Let’s try go earlier:

lwz r0, 0x10 (sp)
cmpwi r0, 6
bne- evaluation_start # The start of the comparisons above
cmpwi r3, 0
beq- evaluation_start

So here and a few times after this, we have branches to our “what’s wrong” evaluation, and there seem to be at least 5 values that it checks. Let’s try and hack all of these branches to be skipped.

Over-Perfection

I almost didn’t recognize that first string, because we’ve skipped past “your town is perfect now” to the full “you’ve maintained the perfect town for X days” one, so we’ve definitely got all the way to the finish line. Because each of the fail checks branch to the same location, it’s probably easier to reverse engineer where the value of 3 meaning “too many weeds” comes from.

Acre Inspection

I came across a block of code at 0x803a1c44 that I see being called multiple times during this evaluation… could this be a loop that checks all acres? We find the loop variable at r23 and it goes up to and including, you (maybe) guessed it, 29, the last tile index in our 5 by 6 grid of 30 acres.

Now may be a good point to start getting some values that we can recognize so that we can figure out where different checks/sums are done. I’ve found some a point in this loop at 0x803a1d48 where we have register values for A-1 such as: 0x26, 0x18, and 0x9. Removing 3 weeds, 2 flowers, and 1 tree from A-1, these values change to 0x23, 0x16, and 0x8, which maps these out pretty directly as r0 = weeds, r3 = flowers, and r4 trees. Looking a little further down we see:

add r20, r20, r4
add r19, r19, r3
addi r29, r29, 512
add r18, r18, r0

So it seems like we do some overall counting and in the end, this unkempt town has 1529 weeds, 277 flowers, and 246 trees… that seems a little crazy to me, but let’s not immediately discredit these numbers and compare against the good town: 10 weeds, 278 flowers, 247 trees. Seems to line up for the most part (I probably ran over a flower). Hacking the weed total to 0 doesn’t change the fact that it complains about them, so it must be used elsewhere.

Tracking down the memory changes, we find a loop check at 0x803a17e4 that seems to compare each tile’s type as an integer with a certain range:

cmplwi r3, 8
blt- 0x803a1804
cmplwi r3, 10
bgt- 0x803a1804
lwz r3, 0 (r24)
addi r0, r3, 1
stw r0, 0 (r24) # Add 1 to the number of weeds

Seems to accept a range of values here for a weed, 8-10. Perhaps dead trees count as weeds? Following where we’re reading those type integers from, we come upon the actual memory representation of the acre, A-1 starting at 0x81279ba8. If we edit, then leave and re-enter the acre:

So it’s a safe assumption that the leading 0x08 is a flower class and then the digit afterwards is an extra specifier. Let’s see what our 8-10 weed values represent now by placing them one after another:

Of course, ya dingus, there are three variations of weeds! Brilliant! Some more fun:

Begone fence! No, you can’t walk onto/past the tracks still, sadly.

Anyway, getting back on track. Hacking the overall weed count didn’t seem to change what the well says we have to work on, but let’s try and see where the per-acre counts are read. Once it’s gone through each tile, we see at 0x803a1980:

sub r0, r0, r4 # r0 = weeds - flowers
stw r0, 0 (r24)

Interesting, so we’ve already revealed that it seems to factor in flower count versus weed count, not just a raw weed count.

Thresholds

Immediately following this computation, we seem to be running through a gauntlet of checks and it’s a little difficult to figure out exactly what they all are. At a certain point, however, one of these checks does the following:

li r0, 5
srawi r5, r4, 31
rlwinm r3, r0, 1, 31, 31
subc r0, r4, r0
adde r3, r5, r3

Here, r4 contains our weeds - flowers value and r3 ends up as 1 in the bad case and 0 in the good one. This is a fun little assembly exercise if you want to try wrap your head around PowerPC, but long story short, it’s just a r3 = weeds - flowers < 5 check, so first mechanic has been reversed here; you can merely overpower the number of weeds with flowers (caveat coming later).

This was the 3rd or 4th check in the chain, so let’s try and circle back and see what the others were. The first check seems to just always return success, the second one at 0x803a19a8 is a little more interesting. r4 seems to come in as the number of trees in the acre and:

lis r5, 0x8065
rlwinm r4, r3, 1, 31, 31
lbz r0, 0x35a0 (r5)
srawi r5, r0, 31
subc r0, r0, r3
adde r3, r5, r4

The value loaded from 0x806535a0 is 8, so this is a similarly roundabout way of checking that the number of trees is more than 8. Next one, coming in again with r3 being the number of trees:

lis r4, 0x8065
srawi r5, r3, 31
addi r4, r4, 13728
lbz r0, 0x0003 (r4)
rlwinm r4, r0, 1, 31, 31
subc r0, r3, r0
adde r3, r5, r4

The value read from 0x806535a3 is 0x11, which, as you may have guessed, is our upper limit for trees (must be less than 17). Next is the weed check, and… after that, we’re done! Just as a matter of science, let’s try and check if we can trigger each of these checks to fail for A-1 in our mostly good town state.

So that about covers all the bases as far as the “what is amiss” checks, but there’s two important pieces missing: where is the check for garbage and why is this town just okay and not perfect?

The answer: A-3, along with other acres, seems to fail the “not enough trees” check and other checks, but it still says the town is “mostly okay” so this lines up with theories/guides I’ve read that suggest some tiles are exempt. Just as a test, I tried chopping down all trees in A-3 and it still said “mostly okay”.

We’ll come back to exempt acres later; for now, let’s crawl back up the stack and try to find where the values that the “how bad is it” checks get set.

Degrees of Perfection

The first check is at 0x805bac20 doing a comparison of a value on the stack at 0x812f9578 with 6. It gets set to 5 in our “mostly good town” at instruction address 0x803a2118. This ultimately happens shortly after our per-acre check, but not before another method runs with entry point 0x803a1e40. Let’s jump in there and see what it does with the 0xd that the good town passes it (the bad town passes a flat zero).

It first gets compared at 0x803a16ac with zero, then again at the same address with 2, and again with 4, 7, 12, 16 (at this point I started hacking the value so that it’d succeed just to see where this was going), and lastly with 255, which I assume we’re not supposed to go above. Let’s keep it above 16. My hunch at this point is that 0xd is the number of “perfect acres” we have and we need over 16 to have a perfect town. Let’s see what our value hacking did…

Why the tiered scoring system? Well, hacking smaller values there we get:

Well, those get really depressing. The lower ones are probably very unlikely to be seen since I’m guessing you have to fail only that many exempt acres, since non-exempt acres seem to complain more specifically. For now, let’s confirm that this 0xd value is indeed our “perfect” acre count; it seems likely given that the bad town reported 0, but let’s see where it gets set/incremented.

  1. r3 gets 0xd from r26 at 0x803a1de8.
  2. r26 gets set by adding r26 and r0 at 0x803a1d7c.
  3. r0 gets its value by dividing r25 in half at 0x803a1d6c.
  4. r26 has a value of 5 when it’s added to r0, so we get 0x8 + 0x5 = 0xd, as expected.

Let’s track down what r25and r26 represent before the final sum. r25 gets incremented at 0x803a1d30 so let’s see what conditions bring us there. For one, A-1 causes it to be incremented, so let’s step through the values there.

Some value gets loaded to r0 from the stack, but it’s zero for A-1. Perhaps garbage? We can circle back to this later.

Then our weeds - flowers difference gets loaded again and compared as less than 3, so it would seem that the threshold of 5 we had before is only for it to complain explicitly about weeds, whereas having 3 or 4 wouldn’t.

Another check follows, seemingly using the number of trees, and does another sliding scoring system by comparing whether it’s greater than 8, 11, 14, 17, and 255. This score is compared with 2 at 0x803a1d18, and if they’re equal, it increments r26, otherwise it increments r25.

Interestingly, something I didn’t catch before, but see now is that after the acre check fails, there’s a similar scoring call that merely checks an array of coordinates for exemption; it scores 1 if the tile is exempt and 0 otherwise. If it’s exempt, it does the same “stricter” scoring above to decide whether to add it to the perfect tile.

So ultimately this all pieces together as: an acre with a weed-flower difference less than 3, and between 12-14 trees scores a full point. An acre that has the correct weed-flower difference but not the perfect tree count scores half a point since r25 gets halved later before being added to r26.

Garbage?

One major final piece remains: is that zero-comparison we passed on before for garbage? At the start of each acre loop, we have an explicit write of zero to the address, and I never hit a write breakpoint on that address again, so it may never get changed. Where does garbage get checked, then? I caught a piece from fishing, laid it down in A-1, and duplicated it 6 times in memory.

Great, it seems to get detected here at 0x803a2098:

lbz r0, 0x1394 (r30)
cmplwi r0, 1
bne- 0x803a20d8
mr r3, r28
mr r4, r29
bl 0x803a1e70
cmpwi r3, 0

The first comparison seems to possibly be a flag for whether to bother to check for garbage (maybe as an optimization), since it’s r3 that contains the actual garbage amount. And indeed, 0x803a1e70 is a function that seems to just count garbage tiles (0x250f) and returns 7 for us. The comparison indicates it must be zero to pass.

But what about acres like the dump? Surely garbage is allowed there and not included in this sum. Throwing some into my A-2 tile seems to match this theory, and then more information arises:

Dumping a single piece of garbage into C-2 didn’t produce the garbage complaint; it merely made it fail the “perfect acre” check, confirming that the branch we were curious about above was a garbage count. Adding more garbage, however, eventually had it produce the full complaint to go clean it up. This must be what that first flag was responsible for: perhaps it only enables garbage count checks when the amount dropped exceeds a certain amount, and then doesn’t get cleared until the count drops to zero. Let’s find out when it’s set.

lbz r0, 0x1394 (r30) # The same address as our garbage flag
cmplwi r0, 0
bne -0x803a2100

Eventually, this jumps to a function at 0x803a1ae8 with a bit that loops through all acres again, summing all garbage counts to r14 and then goes something like:

cmpwi r14, 5
...
blt- past_flag_set
...
li 0, 1
addis r3, r3, 2
li r26, 0
stb r0, 0x1394 (r3)
...
past_flag_set

So there’s a threshold for 5 pieces of garbage before it starts complaining, at which point you have to remove all the garbage in those acres. But why is the dump exempt, and are there any others? For one, it seems like the dump’s tiles get read explicitly before the actual “every acre” loop, so let’s step into that function at 0x805141d8.

It seems to load the exact coordinates of the dump and then compares each tile with a value of 0x583B; we’ll check what that value corresponds to later. The per-acre loop after has a comparison of the acre’s coordinates to values that sit on the stack:

lwz r0, 0x20 (sp)
cmpw r0, r28
bne- do_garbage_count
lwz r0, 0x24 (sp)
cmpw r0, r27
bne- do_garbage_count
addi r8, sp, 32
b skip_acre
do_garbage_count

Those coordinates in my case? Albert Einste– the garbage dump, at (2, 1). So indeed it appears the dump tile is a very specific exception to the garbage sum. With a caveat, of course:

Going back to that 0x583B value we saw the garbage dump loop checking for, I threw one down in A-1 and… it’s the actual visual garbage dump area. It seems to search for it so that it can note its coordinates down within the tile and compare garbage that it finds in that tile with those coordinates to determine if it’s inside or outside the actual dump area. Putting 2 pieces of garbage in the dump and 4 outside doesn’t trigger the check, but 5 outside does. Mystery solved.

How Long Though?

One thing that I could easily look up, but I figured we could just find in the code: how many days do you have to maintain perfection for, again? Let’s step back to that score = 6 check. The check for whether to give the axe is predicated based on town state being 6 and r3 being 1, which we see is set here at 0x803a1584:

li r3, 0
addi r4, r4, 25600
addis r4, r4, 2
lwz r0, 0xr180 (r4)
cmpwi r0, 15
bltlr-
li r3, 1
blr

There it is. 15 days.

Exemption

I lied, another main piece of the puzzle remains: which tiles are exempt from the strict complaint checks? The array used in the exemption scoring seems to suggest there are 5 in this town:

  1. (1, 3) which is C-1 which is the Wishing Well
  2. (5, 2) which is B-5 which is the River Pool
  3. (3, 1) which is A-3 which is the Train Station
  4. (3, 2) which is B-3 which is the Player Houses
  5. (5, 5) which is E-5 which is the Museum

However, stepping through the actual method that should index that array, the B-3 acre for the Houses does not return exemption for this town in the bad state. It seems there’s a value stored in r6 that dictates this, and it turns out it’s the index of the check that failed in the chain, i.e. the “issue” with the acre. Too few (index 1) or too many (index 2) trees is fine, too many weeds (index 3) is not. Just as a test, let’s fix the registers to return too many weeds in the Train Station in our otherwise good town:

There we go. All major mysteries solved! Onward to perfection, and sweet, sweet, sleep.

Leave a Reply

Your email address will not be published. Required fields are marked *