# How to intercept someone moving in a 2-dimensional grid world?

Suppose you have a discrete 2D grid where each point represents a person, for example $\mathbf{d} = (x_d, y_d)$. Each person can only move exactly one square up, left, right or down (or stay put) per tick of the clock. Let's say that $\mathbf{d}$'s velocity is $(c_x, c_y)$, which means that on average after $t$ ticks he will end up to point $\mathbf{e} = (x_e, y_e)$, which lies $t \cdot c_x$ squares left or right on the $x$-axis and $t \cdot c_y$ squares up or down on the $y$-axis. Therefore,

$$x_e = x_d + c_x \cdot t$$ $$y_e = y_d + c_y \cdot t$$

Let another person, $\mathbf{o}$, who is chasing after $\mathbf{d}$ and knowing his velocity tries to intercept him. He has to calculate the point $\mathbf{e}$ where $\mathbf{d}$ will end up after $t$ moves and then follow the shortest path of length $t$ there. Since no diagonal moves are allowed, $t = |x_e-x_o| + |y_e-y_o|$.

So, to find $\mathbf{e}$ we end up with a system with two equations and two unknowns, like so:

$$x_e = x_d + c_x \cdot (|x_e-x_o| + |y_e-y_o|)$$ $$y_e = y_d + c_y \cdot (|x_e-x_o| + |y_e-y_o|)$$

Is this whole reasoning correct or am I missing something? If so, how is this system solved?

Additional details: We have four predators $\mathbf{o_i}$ which are chasing after a single prey $\mathbf{d}$. To capture the prey, they need to surround it from all directions, ie up, down, left and right. The predators' movement can be defined as we like, except for the usual constraint, that each predator can move up to one square and diagonal moves are not allowed. The prey moves randomly, with $p=0.2$ to conduct any of its available move (up, down, left, right, stay still). However, if its path is blocked from one side by a predator, then it will never move towards that square. I'm not sure of the details but I assume "the dice" are thrown again and again until a non-obstructed move is selected.

Motivation for the question above: The point is that after some but not all the predators have reached their position beside the prey to use our knowledge of the prey's behaviour to predict its movement so that the remaining predators can move towards where it will be in the future, not where it is right now. Hence, I said "on average" above instead of saying all this.

Full disclosure: I'm working on a homework assignment for the pursuit domain (multiagent systems). This question is part of my latest approach which involves herding the prey. The previous approached involved surrounding it without getting too close and then moving in for the kill.

-
'Each person can only move exactly one square up, left, right or down (or stay put) per tick of the clock': my interpretation is that at each tick, one only can move to on direction of up/left/right/down?..is that true? –  newbie Sep 30 '11 at 12:20
@newbie Yes, every person can pick at most one direction and move at most one square in that direction. –  Naurgul Sep 30 '11 at 12:30

I can't say much about the first part of the question, "Is this whole reasoning correct?", since you haven't explained what you mean by "on average", so the details of $\mathbf d$'s motion that lead to this average behaviour (e.g. randomized or systematically rounded) are unknown.
Regarding the second part of the question, "how is this system solved?", you can make a case distinction into four cases according to $x_e\lessgtr x_o$ and $y_e\lessgtr y_o$ to get rid of the absolute values, and then check which of the four solutions you get is/are consistent. The solutions will generally not be integers, which brings us back to the average/rounding problem.
Thanks, I was kinda hoping for an easier method though. Oh well. By the way, I updated the question to include some details of $d$'s motion to help motivate the question and help you make sense of what I'm trying to achieve. –  Naurgul Sep 30 '11 at 13:26