[Solved] Chasing game in C [closed]

by


It is an interesting problem. Let’s go over the rules again. Players

  1. Chicken: takes shortest path to field (there could be multiple shortest paths) and away from eagle (maximise the distance between itself and eagle among shortest paths).
  2. Eagle: takes shortest path to chicken

To solve the problem we have to assume it is played in turns: first chicken then eagle and so on.
Game is over when :

  1. Eagle is on chicken.
  2. Chicken is on field.

Here is the trick for the distance:

Update

The distance you want is called Chebyshev distance. You can easily calculate it:

distance = max of(difference of corresponding coordinates between the two points)

For (1,1) and (2,3) distance = max(|1-2|,|2-3|) = 2

For (2,3) and (4,7) distance = 4

For (4,5,6) and (1,1,1) distance = 5

You can ignore the older answer if you want.

Old

distance = Manhattan distance - length of longest 45 deg diagonal

Manhattan distance is easy to understand. See its wiki. Take some examples :

    ---/F
    --/-|
    -/--|
    C---X

    manhattan distance = 7
    length of max diagonal = 3
    distance = 7-3 = 4

Another one

    ---/-F
    --/--|
    -/---|
    C----X

    distance = 8-3 = 5

Caveat: Remember there can be many shortest possible paths. For eg.

    ---F
    --/F
    -/-F
    C--F
    -\-F
    --\F
    ---F

Lots of places to go in 3 moves. Pick one which is farthest from eagle using distance calculator.
Also if distance between eagle and chicken is less than chicken and field at any time then eagle wins else chicken. Just simulate the moves and you will know.

2

solved Chasing game in C [closed]