In the newly released Pokémon GO, one of the major activities of the game is to catch wild Pokémon. These Pokémon are shown in the "nearby" list and their "rough distance" (RD) to you can be 0, 1, 2, or 3 footprints. If they are further than 3 footprints away, they disappear from the nearby list. So a Pokémon cannot appear with 4 or more footprints.
Although Niantic Labs has not released a concrete definition of what the footprints mean, I'll define them as follows. An RD of $x \in \{0,1,2,3\}$ means the Pokémon in question is in the circular band enclosed by two circles of radius $x$ and $x-1$, closed on the outer circumference and open on the inner circumference. E.g., if the number of footprints is 3, then the Pokémon's actual distance from you (at the origin of the Cartesian plane) is in $[3,2[$.
What is the best way to triangulate the position of a Pokémon?
One of the ambiguities of this question is the fact that "footprints" is undefined in terms of metres. It is said that one footprint is roughly 100 metres, but I can't confirm it. So, it is not true to say that walking 300 metres in any direction will affect the footprints, as 3 footprints may be much larger than 300 metres.
Given a Pokémon at an unknown point $(x,y)$ with RD $r$ footprints, pick a random direction and observe if the RD decreases or stays the same. If it does not and instead increases, stop (call this point $A$). Go in the opposite direction (do an about-face) and continue walking.
Stop when the $RD$ increases again. Call this point $B$. Go to the midpoint of $A$ and $B$. Choose a direction perpendicular to your original line. Continue in that direction until you reach the Pokémon (RD becomes zero), or, if it increases, turn around and head in the opposite direction, continuing past the midpoint of $A$ and $B$.
Discussion:
Will this method always find the Pokémon? I believe it will, because we have symmetry in the RD. I.e., if the Pokémon is 3 footprints from you, you are 3 footprints from it. So we can view your path as a line intersecting the circular bands of the Pokémon's $RD$. Since the line segment between $A$ and $B$ defines a chord on the Pokémon's $RD$ (circular bands), a line perpendicular to $AB$ intersecting the midpoint of $A$ and $B$ will pass through the centre of the circle (the Pokémon's position).
In the worst case, you would walk in all four directions. In the best case, you would've picked the direction the Pokémon is in and found them without backtracking.
Is there a better way to do this? I imagine something involving spirals may be better, but I'm not sure.
Here's a picture that should help. Basically, you walk around until you find a boundary where the number of foot prints changes. The most efficient way to do that is to walk in one direction. When you reach the boundary, mark your point, then walk in a tight circle around the point. Pay attentention to the number of paw prints. There will be two points where the number of paw prints changes, mark them. You now have three points equidistant from your Pokémon.
Triangulate and Go Catch Em All!