Playing tag in a taxicab geometry

Question

Let's say we have two players on a taxicab geometry. One is a prey and runs in a certain pattern( e.g ULDRU) where U is up, L is left, D is down, R is right. Another is the chaser. It is guaranteed that they never start on the same position and they both move on each turn.

I have to apologize in advance as what I am gonna show you might involve computer science but essentially this should be combinatorial game. I have devised an algorithm for the chaser to predict where the prey will be after a certain amount of turns. When turns equal distance, that would mean that the prey is within range of the number of turns. Thus, allowing the chaser to move there within those amount of turns.

For each turn in the patterns

  1.Calculate the distance between players
  2.if number of turns = distance then "number of turns is minimum"
  3.if pattern is completed then redo the pattern
  4.do 'prey's movement' per the pattern, each turn at a time (distance is going to be updated)

** This is a loop because it only stops when line 2 is satisfied while line 3 keeps the loop going**

E.g: The prey moves in an L shaped pattern "DDDR". Per the pattern, the prey's movement will be "DDDRDDDRDD...". For each turn, we calculate the distance. If the distance, between the chaser and any points the prey is on per its pattern, happens to equal the number of movement made( turns), then the chaser can start moving to that point when the game starts. Since the amount of turns made are equal for both chaser and prey. The two will end up in the same position, allowing the prey to be caught. (Added for clarification)

However, for a starting position in which the other player is never caught, then this will go on infinitely. Thus, it leads me to my question.

Is there a way to determine if the one being chased never gets caught given that the chaser knows the pattern and the location of his opponent?

Answer 1

Suppose the chaser has a way to catch the prey. Among all such methods, there must be at least one with a minimal length. The chaser will catch the prey at a particular point on a particular turn. To reach the point from their starting position, the chaser will have to move right some number $h$ times ($h < 0$ if they move left) and up some number $v$ times ($v < 0$ if they move down). However, it doesn't matter in what order the chaser makes these $h+v$ moves. As long as their path has $h$ right moves total and $v$ up moves total, they will arrive at the correct point on the correct turn. Since the path moves the chaser $|h|$ units horizontally and $|v|$ units vertically, the distance between chaser's starting point and the interception point is $|h| + |v|$, as you've found experimentally.

If the prey's pattern backtracks - that is, includes both $R$ and $L$ moves, or includes both $U$ and $D$ moves - then chaser can always catch them, no matter the starting positions. If we call each repetition of the pattern a round, at the end of each round, the prey's position will be offset from its position at the start of the round by the same amounts $x$ horizontally and $y$ vertically. But because of the backtracks, $|x| + |y|$ will be less than the number of turns $r$ in a round. If the chaser is only concerned with capture, not least time, they can guarantee it by starting each round by moving $x$ units right and $y$ units up, parallelling the prey's progress through the round, then use the extra turns in the round to move towards the prey's round end-point. Every round the distance between the chaser and prey will decrease by $r - |x| - |y|$. Eventually, this will allow the distance to drop to zero (provided the chaser is allowed to sit still for some turns if they arrive early). This algorithm is not efficient, but it guarantees that a path to victory must exist.

Now suppose the prey does not backtrack. There three possibilities:

• If the prey's round movements $x$ and $y$ are both directed away from the chaser's position, the chaser cannot ever catch the prey. The best they can do is also move $x$ horizontally and $y$ vertically each round, leaving them no closer than when the round started. If they choose any other path, their distance from the prey increases instead of decreasing.
• If the prey moves towards the chaser both horizontally and vertically, then the chaser can always win. They need only move to the line of the prey's round-wise movement and wait for them to approach, and under these circumstances, they can always arrive at the line before the prey gets by.
• Finally, the prey may be approaching the chaser horizontally, but moving away vertically, or vice versa. For simplicity of description, I'll assume the prey is moving right and/or up, and the chaser is to the right and below the prey, but the other cases are all similar.

Suppose the chaser has an intercept, moving $h$ units right and $v$ units up (so $h \le 0$ and $v \ge 0$). As I already mentioned, it doesn't matter in which order the chaser makes these movements, so have them do all the up moves first, then the left moves. At the point where the chaser turns left, they must now be level with or above the prey vertically. If they were still below the prey, then the horizontal travel would not catch it, since the prey never moves down. But the chaser started below the prey. So at some point while the chaser was moving vertically, they caught up with the prey in that direction.

On the other hand, if the chaser does not know if they have an intercept, and just starts traveling up (in general, the direction where the prey is moving away from them), if they ever pull level with the prey in that direction while the prey is still to their left, then they will have an intercept. Once they've pulled level with the prey, they can change tactics, moving up only on turns where the prey moves up, and moving left towards the prey on turns where the prey moves right. Assuming the chaser can just wait if the prey will move to their current cell on the next turn, an intercept is assured.

However, if the chaser's vertical run does not level with the prey until after the prey has passed the chaser horizontally, the chaser cannot catch the prey. They have fallen into the first case above, where the prey is now moving away from the chaser in both directions.

From this you should be able to figure out a simple algorithm to determine if the chaser can catch the prey. But it is late and I have to work tomorrow. I'll try to finish it tomorrow night.