Apple Search

This homework is going to be a bit different. We are going to build a bit of computer NPC! Imagine if you could play two player snake, but didn't need to wait for a friend?

A computer NPC needs behaviors associated with it, and it uses the current state of the system to determine what behavior it should follow. People try to call it AI, but it's really not intelligence, it's really just a set of instructions to follow (like any other program). But doing this, we can simulate intelligence, so that it seems like the computer player is really a person.

The task

Your task is, given a current game board, which has a set of apples, figure out the one which is closest. This should be the one your NPC should head for next.

Note that sometimes the closest apple isn't the most ideal, but this is one strategy that should work for a simple NPC. The apple also might not be accessible, based on where the snake's body currently is, or where it might be as you move around. But we can ignore such restrictions and start with this simple task.

For this, we are going to somewhat forget our current code, so we don't have to deal with all the drawing, networking, and complex structure. We are going to have simple inputs, and simple outputs.

Starting code

Create a new D project called applesearch, and put in the following code:

import std.stdio;
import std.math;

struct Apple {
    int x;
    int y;
}

struct GameState {
    int x; // snake head x coordinate
    int y; // snake head y coordinate
    Apple[] apples;
}

Apple targetApple(GameState state) {
   // your code here
}

void main() {
   GameState state = GameState(0, 0, [Apple(5, 5), Apple(7, 2)]);
   Apple result = targetApple(state);
   writeln("I should go for the apple ", result);
}

You should fill in the function called targetApple so that it returns the apple to target. The distance between the snake and an apple is how many squares it has to go before it will reach the apple. If two apples are the same distance, pick the one which comes first in the array.

In the above test case, the closest apple is at coordinate (7, 2), because it will take 9 moves to reach it, whereas the apple at (5, 5) will take 10 moves.

Check out the image below, which shows a path to the closest apple in green, and a path to the furthest apple in purple. Note that these are not necessarily the only path that can be taken! If you count the squares, you will see it's 9 moves to get to the green one, and 10 moves to get to the purple.

You may wonder why there is an import of std.math. That is for the function abs which stands for absolute value. This function returns a positive number which represents the magnitude of the number. For example abs(5) == 5; abs(-5) == 5;. This will help you calculate the closest apple.

To give you a hint, it's not important what exact path the snake takes, what is important is that it only moves towards the apple. That is, there's no reason for it to move away from the apple.

More tests

Once you get that one working, you can try out some of these other tests. Each test helps determine whether your code is written correctly. If your code provides the correct answer, you can be more sure that you wrote your code correctly. This kind of testing is called unit testing. A unit test uses a created test with a known answer, and executes the function being tested on that input, and verifies that the test is correct. All coordinates are in (x, y) format.

Case 1:
Snake: (3, 4)
Apples: (7, 9), (1, 5), (8, 7)
Answer: (1, 5)

Case 2:
Snake: (8, 9)
Apples: (1, 3), (10, 0), (4, 6)
Answer: (4, 6)

Case 3:
Snake: (15, 4)
Apples: (12, 8), (18, 19), (17, 7)
Answer: (12, 8)

When you have your targetApple function complete, post it to the homework discord channel, and we can compare solutions

Next Class

In the next class, in addition to upgrading the network play, I'll set up an NPC to play against me, and I'll implement some simple rules:

It should go after the closest apple
It should turn if it is about to hit a wall or other snake piece

With those simple rules, I'd be surprised if it lasts long, but maybe we can talk about how the NPC can improve during the class.