Java snacktime bot

[Benny_1]

I'm new in java, so I'm not very good at it yet and my teacher has stumped me. We are supposed to make a bot for a game called snacktime, which is usually user controlled.

About Snacktime:

• There are a maximum of 16 snacks layed out randomly on 600x400 board.
• Each snack has a certain a mount of calories (aka energy). (The more energy you eat, the slower you get. Huh.)
• The more calories you have eaten, the slower you get.
• There is a 5 minute time limit.
• There is a limit of 100 moves.
• This distance you move on your turn is this: 10 / 2 ^ (energy / 1000)

My questions are:
What is the best algorithm to do this (I've come up with several so far)
I'm not sure how to even program this, we haven't had much practice with logic.

PS:

This is my first post, so please tell me if I've done something wrong or missed something.
Snacktime Link #1
Snacktime Link #2

[Traevel]

Not familiar with the game, but it sounds fun. If you're not feeling at home with java perhaps try a simple solution first, like heading towards the one with the highest calories. Once that works you can implement better solutions.

I noticed on the video that whenever a food item gets eaten a new one pops up randomly. There are some things that come to mind after watching, maybe they'll be of help.

Keep track of your opponent, where he is and how fast he is going. Which food items can you reach before he could. Perhaps there are clusters of food items, those would be favorable over a lone (distant) single item. But what if it's a close one, or the last one in the cluster. Maybe plan ahead as well, how will an item affect my speed, will the move limit be hit before I reach it. If my opponent is lower in energy than I am perhaps I should follow a different strategy than when he is higher. If he's higher he's also slower, perhaps I can steal some food items away from a cluster he's heading to.

I guess you can make it as complex as you'd like, but I'd still start simple and build from there. From what I saw you need to implement a move() method that has a list of items/players with their coords and energy. I'd start by making some helper methods that you'll need often. One that calculates the distance to a certain point for instance. Then make a simple implementation and watch it go, see if it's doing what it should: like go for the nearest item. Then slowly expand.

You could even go all AI on it. For instance you could assign weights to items and update their values on each turn based on a set of rules like the ones above; proximity to you, proximity to other food items, opponent speed/direction, your current speed/direction, the item you chose the previous turn, etc.

I don't think there's a best algorithm, there are lots of different approaches. Besides there are factors that are not in your control. Like the opponent or simply luck; that a good item will spawn near you at just the right moment. Perhaps your bot's behaviour will do badly against one opponent but good against a different one, that doesn't necessarily means the algorithm is bad/good.

[Benny_1]

Thanks a lot! I'm going with a simple algorithm my friend suggested to me. It's supposed to make the bot move to the farthest snack there is. (I'm skeptical however, just trying it out. Besides, I definetely need to implements a "cluseters finder" like you suggested.) I'm getting the hang of this I think. If have a methods to:

• Find the farthest snack
• Find how far I can move
• Find the distance inbetween me in the snack

But I'm stuck on the methods for how far I should move.
I'm making the methods calc_angle, step_x() and step_y. (The move method returns a new double array with the new x coordinate and the new y coordinate, so I was thinking I would return something like new double {oldPositionX + step_x, oldPositionY + step_y} I have no idea how to calculate the angle (in radians (I hate radians)). I might not even need the calc_angle method. I'm not sure where to start.

[Benny_1]

Also, at the moment we're only doing the programming with one bot and no opponents, but that will probably change by tomorrow's class. If it doesn't then I guess I won't have any time to program anything about the other player.

[Traevel]

There's not a lot of documentation on snacktime that I can find, but there are similar programs out there and a lot of helper methods like calculate heading/bearing of yourself and opponents are described, but I agree that you might not need the angle. The robot has no front or back so for all you care it shuffles sideways towards the snack. However, something that I know has tutorials for heading/bearing, speed, energy calculation, opponent tracking and so forth is Robocode so you might want to look there for inspiration as well.

For instance here is a discussion on point to point movement for Robocode.

And here would be an implementation of linear targeting, except you wouldn't be shooting at something but walking towards it.

If there is no opponent I can see why you would want to start with the farthest snack, but if new food items pop up you'll always end up travelling the furthest possible distance for the next snack. Unless you accidentaly bump into one I suppose. If you have the coordinates to the snack furthest away you could calculate a linear path towards those coords and adjust them based on the max length you can still travel (I'm guessing from your reply that the move() method won't adjust the coords to the max travel distance for you), then return them as new coords.

Perhaps this is of more help to you on that.

ps. Links seem to be acting a bit wonky in the preview I'm getting so I'll copy them here for you:

http://robocode.sourceforge.net/
http://old.robowiki.net/robowiki?Movement/CodeSnippetBasicGoTo
http://robowiki.net/wiki/Linear_Targeting
http://math.stackexchange.com/questions/409689/how-do-i-find-a-point-a-given-distance-from-another-point-along-a-line

[JamesCherrill]

This sounds like a cunning re-phrasing of the classic "Travelling Salesman Problem" with its O(n!) time for a brute force solution. There's a vast amount of info on the TSP, including more algorithms than you could shake a stick at. WikiPedia is yopur friend.

[JeffGrigg]

But I'm stuck on the methods for how far I should move.
... I have no idea how to calculate the angle (in radians (I hate radians)).
I might not even need the calc_angle method. I'm not sure where to start.

I would start by taking a close look at the API your program must use to communicate with the game engine that runs the simulation.

How far should you move?
Well, I don't see any penalty or cost to moving "too far." And the example video seems to show the "winning" bot moving as fast as it can all the time.
So I think the answer is always "move as far as you can."

Offhand, I don't think you need to calculate angles. (At least not for a simple bot.) It looks like, to move, you're expected to return the Point you want to move to. I don't know what happens if you attempt to move "too far." Maybe it only moves you as far as you can go. You should try it and see.

So (for a simple bot), I'm guessing you'd really only have to compute distances.

[Taywin]

After reading your assignment page, do you need to implement only the move() method? If so, it is not that difficult. By the way, ignore the video because it is simply to illustrate the concempt but it is not exactly the program is going to be.

What you need to do first in the move() method are to calculate the Euclidean distance (traveling distance) and traveling time from where the bot is for each of the snack location. Save all of whatever you computed for later use. The next part is your own AI implementation (to make a decision which one it should go to.

The simpliest AI is a naive approach. Pick one of the snack under any condition -- farthest snack location, closest location, highest energy, lowest energy, randomly select, randomly select with probability, etc. Each condition may yield higher result at the end depends on how snacks are located in the field. In your case, you may choose the farthest distance your robot can travel (but not guarantee the highest yield).

Improved approach. Do you know all your opponent locations before you issue the next move location? If not, naive method (with mix of random) would be suffice in this case. If you do know, then it would be more challenge. You may start off with shortest distance to observe what your opponents are doing. You should be able to make a guess of what your opponents' algorithm are this way. You could also assign certain probability value to determine whether or not you should try to steal the target snacks your opponent may try to get to. The meaning of "stealing" means your robot will get to the snack before your opponent (you should be able to guess opponent speeds because you know the location & snacks they consumed by looking at locations).

After all, it is a strategic game. To increase the chance of winning, you need to be able to make guesses of what your opponents are doing. You may have 50:50 chance or lower if you ignore them all.

[Benny_1]

Ok, I ditched the calc_angle method and there is now just the methods step_x and step_y. And it works, except for one flaw. Once it hits the snack my has_target variable continues to be false. Here is my code:

import edu.berkeley.shared.Snack;
import edu.berkeley.shared.Snacker;
import java.util.Map;
import edu.berkeley.shared.SnackerAgent;

public class My_Muncher implements SnackerAgent {
    double foo = 100.0;
    double[] position;
    double new_x;
    double new_y;
    double[] snacks_position;
    boolean has_target;
    double[] target;
    Snack snack_target;
    int snacker_id;
    Snacker snacker;

    @Override
    public double[] move(int snackerId, Map<Integer, Snack> snacks,
            Map<Integer, Snacker> snackers) {

        snacker = snackers.get(snackerId);
        foo = foo + 15; // will move you further right!
        position = snacker.get_position(); // passes your
        snacker_id = snacker.get_id();
                                                            // snackers position
                                                            // to variable
                                                            // "position"
        System.out.println("my muncher's position is " + position[0] + ", " + position[1] + "."); // prints
                                                                                                    // out
                                                                                                    // the
                                                                                                    // x
                                                                                                    // position
                                                                                                    // of
                                                                                                    // your
                                                                                                    // snacker

        // my target from the target method is..
        if(!has_target){
            target = calc_target(snackerId, snacks, snackers);
        }
        if(snack_target == null || position == target){
            has_target = false;
        }
        System.out.println("The farthest target is at " + target[0] + ", " + target[1] + ".");
        System.out.println("Theta is " + calc_angle(position, target));

        // try to approach your target somehow!

        return new double[] {position[0] + step_x(target), position[1] + step_y(target)};

    }

    public double calc_max_distance(int energy) {

        double maxd = 10 / (Math.pow(2, energy / 1000));
        return maxd;

    }

    public double calc_angle(double[] pos1, double[] pos2) {

        double a = Math.abs(pos2[1] - pos1[1]);
        double b = Math.abs(pos2[0] - pos1[0]);
        double c = Math.sqrt(Math.pow(a, 2) + Math.pow(b,  2));
        double theta;
        theta = Math.atan2(a, b);
        return theta;

    }

    public double[] calc_target(int snackerId, Map<Integer, Snack> snacks, Map<Integer, Snacker> snackers) {

        double[] pos_target = new double[2];
        double farthestSnackDistance = 0;

        if(!has_target){
            for(Snack s : snacks.values()){
                if(get_distance(s.get_position(), position) > farthestSnackDistance){
                    farthestSnackDistance = get_distance(s.get_position(), position);
                    pos_target = s.get_position();
                    snack_target = s;
                }
            }
            has_target = true;
        }


        //now I pretend as if I calculate some stuff...

        //... calculations... 

        // you should loop through your snacks in order to know, where the next available snack is...

        //here is a random target
        return pos_target;
    }

    public double get_distance(double[] pos1, double[] pos2) {

        double x1 = pos1[0], y1 = pos1[1], x2 = pos2[0], y2 = pos2[1];
        double a = Math.pow(Math.abs(x2 - x1), 2);
        double b = Math.pow(Math.abs(y2 - y1), 2);
        double c = Math.sqrt(a + b);
        return c;

    }

    public double step_x(double[] target){

        double x1 = position[0];
        double y1 = position[1];
        double x2 = target[0];
        double y2 = target[1];
        double a = (y2 - y1);
        double b = (x2 - x1);
        double c = Math.sqrt(Math.pow(a, 2) + Math.pow(b, 2));
        double distance = get_distance(position, target);
        double max_distance = calc_max_distance(snacker.get_energy());
        return b / 500;

    }

    public double step_y(double[] target){

        double x1 = position[0];
        double y1 = position[1];
        double x2 = target[0];
        double y2 = target[1];
        double a = (y2 - y1);
        double b = (x2 - x1);
        double c = Math.sqrt(Math.pow(a, 2) + Math.pow(b, 2));
        double distance = get_distance(position, target);
        double max_distance = calc_max_distance(snacker.get_energy());
        return a / 500;


    }

}

I'm not sure how to make it realize that it has eaten a snack. In the move method I have made an if statement that checks either that it's target snack is null or if it position is the same.

[Taywin]

How do you display those double position value in graphic? Is it possible that it is the rounding error when you attempt to compare 2 double values?

So what I am thinking is that you should have the position of starting and ending (snack position) in int, but the computation is in double.

P.S. Lines 102 & 103, do not waste your time using abs() because the power of 2 will always result in a positive value.

P.S.S. Are you sure you can compare array position with target using == in line 42? Because doing so, you are comparing their references, not values.

[JeffGrigg]

I would very highly recommend using an iterative approach. (...with automated JUnit tests, if you can manage it. ;-)

Like...

Version 1: Always move to the closest snack.

Version 2: Use a simple formula like "snack value divided by distance" to select the "best" snack to head towards.

Then refine strategies from there. Like...

Version N: Search a tree of the next "N" moves (like 5 or 10) to find the best strategy.

Don't worry about factoring in your oponent's moves until later. You'll have "plenty" of time to worry about that, once you get your 'bot minimally working.

(Looks like the "ab" 'bot in the video watches its opponent and works aggressively to deny the opponent high-valued food choices. Once you're faster than them, you could probably "starve them out" by getting to food items before them.)

[Benny_1]

Taywin, you were right about the rounding error (that would be a problem), and there was also the error that the actual position of the food item sprite was the top left corner's coordinates while my bot was heading towards the center of the sprite. I've changed my algorithm so that it gives each item a weight based on the distance and the enrgy, and I am planning on adding the distance between the snack and an enemy to the algorithm. Also, I dug angles back out of the ditch by the request of my teacher. And... IT WORKS! :D

I plan on adding a soundtrack :D

[Benny_1]

Also, I did realize that this was very similar to robocode, and I used to play that game a lot until my classwork became an overload. When this class is over, I'm gonna go robocode crazy :D.

[JeffGrigg]

I plan on adding a soundtrack :D

Waste of time.

But it could be cool to growl like a tiger (or something like this) when going to take food from the opponent. Maybe laughing ("Ha, HA!") when you take food that the opponent was heading towards. >;-> Maybe "packman" sounds when eating.

[Benny_1]

My teacher actually said that if we added a soundtrack, we would get "a fat plus", but after your idea for more event triggered sounds is awesome. Do you think it'll be ok adding both (and the program would not sound kind of 'overdone'), or if not which one should I add? Would it be waste of time to try implementing both, because I only have about 2 days left.

[JeffGrigg]

Personally, I would make the bot smarter, rather than adding sound.

[Benny_1]

I plan on making the bot smarter, but adding background music seems pretty straightforward since I made a .wav file specifically for the game already. The game has a specified duration, and the music is exactly that length.

[Benny_1]

I have three test bots now.

1. Puts most of it's consideration into the snacks calories and a bit of consideration into how far away the snacks are.
2. Puts most of it's consideration into how far away the snacks are and a bit of consideration into the snacks calories.
3. Rushes to the closest one

The suprising part is that the bot that rushes to the closest one wins every time. If I can make a bot to beat that, than it would probably be dominant. Any ideas? So far I've come up with a bot that goes to the highest energy when it can move quickly and once it slows down it goes to the nearest snack. I've put it in a game against all of the other three bots I've just mentioned previously, and it won 1 out of 4 times.

I'm shocked. The most primitive bot I could come up with (and probably the one everybody will come up with) is the best one.

[Ashley157]

 h

[Ashley157]

hey i'm in a similar situation as you where i'm trying to program a snacktime bot and i'm lost as to where I should start, would you mind posting your finished code so I could have something to take guidance from?

[JamesCherrill]

There are lots of people here who will freely give their time to help you become the best Java programmer you can be. There's nobody here who is interested in helping you cheat or doing your homework for you.

DaniWeb Member Rules (which you agreed to when you signed up) include:
"Do provide evidence of having done some work yourself if posting questions from school or work assignments"
http://www.daniweb.com/community/rules

Post what you have done so far and someone will help you from there.

[Benny_1]

The class is now over and our bot turned out awesome! There was a giant snacktime tournament and our bot got to the finals! Sadly, for the finals match our teaher add a dog snack that was -500 points. Darn it, should've added something to avoid negatives!