Chasing game in C [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

I'm stuck with a quite complex problem:

On an MxN field containing a chicken, an eagle and a yard, the chicken tries to escape the eagle (by entering the yard), and the eagle tries to catch the chicken. The chicken escapes when reaches inside the yard, and the eagle catches the chicken when it's in the same position as the chicken. In a single step, the eagle can move one or two small squares, and the chicken can move a single square in any direction. The program should display a message saying if the chicken can win. It should compute the moves, and, at each step, it should write in the output file the current configuration of the field, and it should also visually represent it on the screen. The dimensions of the field, position of the chicken and of the eagle, and also of the yard, are given in a file.

I've solved the part with creating the field (a matrix), but I can't figure it out how to solve this. Perhaps backtracking would be an idea, but it's very complicated, and I can't handle it. I think I should find a way to find out the distance between the chicken and the yard, also between the eagle and the yard, and work somehow with that. It has to be in C. Any suggestion, idea is welcomed! Thank you in advance!

Answer 1

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.