Hunger Gaming - Eat or Die

Question

Hunger Gaming - Eat or Die

If you don't eat, you die. If you eat, you live (until you die). You will die, so try to die last.

Overview

There is an island populated with a herd of prey animals. You control a pack of five predators. Your object is to keep your pack alive. Do this by eating prey. The prey tend to run from predators, and try to stay in a flock otherwise. Of course, your pack will be on the same field as every other pack, so the competition will try to eat them before you can. Do not let this discourage you, or you will starve.

How to play

Create and submit a command line program to direct your pack. It will receive state information from the control program on STDIN, and output commands on STDOUT. The format is outlined in detail below. Each program will only be executed once and must stay running until it has no more pack members alive. You will need to read input as it comes in, and respond quickly. There is a strict timeout of 200ms for each response. If you have not responded by then, your pack will not receive new instructions for the current turn.

If your program cannot be run by the controller, it will not be considered valid. Please include the command line string I will need to use to run your submission. If there are any special instructions(to setup compilers, etc), please include them. If I cannot get it working, I will ask you for assistance in comments. If you do not respond, I will not be able to accept your submission.

Tournament will be held on a 64bit Linux system. Keep this in mind when giving any necessary directions.

Details

• Each creature's position and direction are in the form of a pair of double-precision floating point numbers (eg double) representing their x and y coordinates, respectively.

• Each creature is a considered a point. This means they can overlap and occupy the same space. You will not be bumped aside, and there is no concept of collision with other creatures.

• The island is a square, 500 units to a side. If you try to venture beyond those bounds, you will be clamped onto the edge. The origin {0,0} is in the upper-left, with x increasing to the right and y increasing downward. Again, the map does not wrap.

• The game starts with 1500 + (packCount * 50) prey animals. They will be gathered in the center of the island, but quickly decide to start moving.

• Packs will be arranged in an evenly spaced circle around the perimeter. The pack order is shuffled, so don't count on starting in a particular location.

• Prey animals can see all other animals within a 30 unit radius. They can move at a maximum of 6.0 units per turn.

• Predators can see all other animals within a 50 unit radius They can move at a maximum of 6.1 units per turn. This means they can see prey before being seen and (barely) outrun them.

• Predators live and die according to their hunger level. It starts at 1000, and decreases by one each turn. If, after movement, a predator is within 1 unit of prey, it will automatically eat it. This removes the prey and sets the predator's hunger to 1000. Each predator may only eat one prey per turn. If there are more than one within range, it will eat whichever one the loop gets to first( not necessarily the closest). A predator dies if its hunger reaches zero.

• Packs start with five members each. Every 5000 turns, all packs still in the game will spawn one new member. It will be placed within visible range of a fellow pack member. Make sure your entries can handle more than five members.

• Every 1000 turns, more prey will spawn. The number of new prey will be the number of living predators minus one.

• Predators cannot attack other predators. They eat prey when they catch it. That's it.

• The order within a turn is:

  • All prey make decisions
  • All predators make decisions
  • All prey move
  • All predators move/eat

• The order each pack makes their decisions/moves in will be randomized on each turn.

Protocol (General)

All communications are done in string format US-ASCII. Numbers are converted to strings using Java's Double.toString() or Integer.toString(). Your output must be formatted so that it can be read by Java's Double.valueOf(String) (you will not be outputting integers). For details on parseable formats, see the documentation for Double. All fields on a line are separated by the standard \t character, and newlines are \n. The whole string will be terminated will a null byte \0.

In the examples below, I'm using <> to mark the fields for readability's sake. These are not present in the actual strings.

Protocol (Input)

The input string varies in length, depending on how many creatures are visible to your pack. It can exceed 100k characters, so be prepared for that. The basic setup is:

• Line 0: Basic information about the game. turn is the current turn number, and the counts are the total number of prey and predators left on the field. These are integer in string form.

  <turn>\t<preyCount>\t<predatorCount>\n
  

• Line 1: Your pack members' unique ids and hunger levels. These are not given in the same order for every input. Use the unique ids to track individual members, not the order in which they appear in the input. Again, these are integer as strings. For a pack of two, this would be:

  <id[0]>\t<hunger[0]>\t<id[1]>\t<hunger[1]>\n
  

• Line 2: Your pack members' positions, in the same order as given on line 1. These are double as string:

  <x[0]>\t<y[0]>\t<x[1]>\t<y[1]>\n
  

The following lines are each pack member's visibility, in the same order as given on line 1. These will be given as two lines per member.

The first for each consists of locations for the prey he can see. The second is locations for the predators he can see. These locations are not unique as a whole. For instance, if two pack members can see the same animal, it will be in both member's string. Also, your own pack members will be included. If you want to exclude them, you may want to compare locations with your own members. All locations are in double as string format.

For each living member:

<prey[0].x>\t<prey[0].y>\t<prey[1].x>\t<prey[1].y>\n
<predator[0].x>\t<predator[0].y>\t<predator[1].x>\t<predator[1].y>\n

Finally, the last character will be \0, at the beginning of the next line.

Exception: If you receive the input dead\0, your pack is dead. End your program gracefully, please. The controller should shut down all living processes when closed, but I'd rather not have zombie processes all over the place. As a courtesy, you may include an input timeout. For instance, my example class ends if it does not receive input for 15 seconds.

Protocol (Output)

Output is simple. You will give a pair of double values for each live pack member. These represent the movement you would like them to take on this turn. For example, if your creature is currently at {100.0, 100.0} and you give them a command of {-1.0, 1.0}, they will move to {99.0, 101.0}. All numbers will be on a single line, separated by tab.

For example, if you had 3 pack members alive, this would be a valid response:

1.0\t-1.0\t2.0\t-2.0\t3.0\t-3.0\0

This would move your creatures by {1.0,-1.0}, {2.0,-2.0}, and {3.0,-3.0}. The order is the same as received in the input. Don't forget the ending \0!

If you give invalid input, bad results will follow. If any single number cannot be parsed to a double, it will become zero. If the string as a whole can't be parsed, no new instructions will be given, and your entire pack will use the directions from the previous turn.

All directions will be clamped to a maximum distance of 6.1 units. You can move slower than this if you'd like. For instance, {1, 0} will move you one unit. {6,8}(distance 10) will only move you 6.1 units, and will reduce to around {3.66, 4.88}. The direction remains constant.

Important: The control program reads both your STDOUT and STDERR. If you throw an exception and print to STDERR, it's very unlikely that message will be in the form of a valid response. Try to avoid doing this.

Control Program / Testing

The source for the controller can be found here at bitbucket.org. You will need to compile it before running. The main class is Game, and all classes are in the default package. To run, include each pack's command as a separate argument. For instance, if you want to run a Java ChaserPack and a Python LazyPack.py, you could use:

java Game "java ChaserPack" "python LazyPack.py"

On the map, prey appear in green, and predators in red. However, whichever pack is the first pack given as an argument will be colored blue instead. This is intended to distinguish them more easily for testing purposes. Predators will also flash white for five frames when they eat.

The game will proceed until the last predator starves, writing to the console as starvation or extinction events happen. Once the game is complete, the score will be given for each pack. If you want don't want to see the starvation/extinction events, you can use the -silent argument. Then it will only output the final score. You must pass this as the first argument:

java Game -silent "java ChaserCat" "./someOtherPack"

Included is a skeleton Java pack named GenericPack. It includes the basic input/output operations needed. It is there to give a clear example of how to parse and reply. If you'd like to add a template in another language, let me know.

Also included is a predator based on the template, ChaserPack. It will not be included in the tournament, and is only included for testing purposes. It performs quite badly, due to an intentional targeting flaw. If you can't beat it, keep trying.

Below is an example run of the control program (click for video). The video quality's not great (sorry), but you can get a feel for how the prey move. (caution: audio)

Scoring

Winner will be determined by tournament, gaining points in each round.

Each round proceeds until all predators are dead. Each pack will be scored based on when its last member died of starvation. They will then be assigned points based on the order. Points will accumulate for ten rounds, and the victor is the pack with the highest total points.

First place for each round will receive 100 points. For each place after that, the reward will be reduced by 20%(rounded down). This will continue until the points reach zero(after 17th place). Places 18+ will receive no points for the round. Packs who tie will receive equal points. For example:

1st : 100
2nd : 80
3rd : 64 (T)
3rd : 64 (T)
4th : 51
...
17th: 1
18th: 0
19th: 0

The maximum possible points over the course of the tournament is 1000, from first place all ten times.

If multiple programs end the tournament tied for first place, another ten round tournament will be held with only the first-place entries submitted. This will continue until one victor emerges.

I will try to run a tournament roughly weekly, or as new submissions come in.

Additional Rules (play fair!)

• You may not read or write to any external resources. Since you're not going to be invoking your program mutliple times, any state information can be stored internally.

• Do not interfere with other processes/submissions. This does not mean don't try to steal their prey, outrun them, etc. It means don't interfere with the running of the process. This is at my discretion.

• Contestants are limited to a maximum of three entries. If you submit more, I will only score the first three submitted. If you want to revoke one, delete it.

• Entries may not exist solely to prop up other entries. Each should play to win on its own merit.

• Your program may spawn a maximum of one child process at a time (total descendants, not direct). Either way, ensure you don't go over the timeout. You may not invoke the Game class itself in any way.

Results - 29 April 2014

Here are the results of the latest ten-round tournament:

Clairvoyant         : 1000
EcoCamels           : 752
Netcats             : 688
RubySpiders         : 436
RubyVultures        : 431
CivilizedBeasts     : 382
LazyPack            : 257

Packs submitted before 09:00 EDT 2014/04/29 are included in this run.

You can also view the details for each round. For some reason I decided to number the rounds backwards, so it starts with "round 10".

Updates

2014/04/23: FGreg reported a bug related to timeouts (thanks!). A fix has been implemented, so testers will want to update their control program code.

Answer 1

Clairvoyant

Code updated to face AbleDogs

Woo hoo! Finally beats that Netcats! I expanded existing code (credits to Geobits!) with some small modification to create this future predicting pack. Nothing beats predators who know where the prey will move!

From two tests that I've done, my pack always won against Netcats. But this will not perform as good if there are no other packs, as the prediction still fails if there are too many other preys in vicinity.

Probably I can include the trick of CivilizedBeasts to reduce the number of preys substantially during the first few thousands turns.

Done in 5.21 minutes
Clairvoyant(1)                  : Turn 9270 : Score 100
EcoCamel.pl(3)                  : Turn 8118 : Score 80
Netcats(0)                      : Turn 6111 : Score 64
RubyVultures.rb(5)              : Turn 4249 : Score 51
RubySpiders.rb(4)               : Turn 3495 : Score 40
CivilizedBeasts(2)              : Turn 3176 : Score 32
ChaserPack(6)                   : Turn 2492 : Score 25

From the name of my pack, you should know what strategy I use =D

Edit:

• Updated pack management system to not chase the same prey (and also try to find best match!)
• Improve wandering process when the number of preys is small (this is crucial for a win!).
• Improve special cases when the previous version just stuck at the corner.
• Fixed a bug in predator detecting algorithm (now it's quite accurate!)
• Included prey flock[ALIGN] factor
• Keep one prey as a pet if the food is scarce
• Create a den where the pack will herd their preys into
• Lure nearby predator into chasing our prey, which they won't win

I counted how many preys each pack eats, and here is the result:

Clairvoyant(1)                   consumed 916 preys in 9270 turns (0.099 preys/turn)
EcoCamel.pl(3)                   consumed 73 preys in 8118 turns (0.009 preys/turn)
Netcats(0)                       consumed 563 preys in 6111 turns (0.092 preys/turn)
RubyVultures.rb(5)               consumed 77 preys in 4249 turns (0.018 preys/turn)
RubySpiders.rb(4)                consumed 293 preys in 3495 turns (0.084 preys/turn)
CivilizedBeasts(2)               consumed 10 preys in 3176 turns (0.003 preys/turn)
ChaserPack(6)                    consumed 43 preys in 2492 turns (0.017 preys/turn)

My pack is very aggressive, and most of the 916 counts I think it gets from stealing preys from Netcats, just like RubySpiders.

CivilizedBeasts is unfortunately losing due to the center camel from EcoCamel.

And EcoCamel (with hunger critical 500) is pretty efficient, it eats just enough to survive to the end.

Also with this updated Clairvoyant, the game barely reach 10,000 turns.

The code:

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.TreeSet;

public class Clairvoyant extends GenericPack {
    private static final double MAX_SPEED = 6.1;

    private TreeSet<Animal> foods = new TreeSet<Animal>(new AnimalComparator());
    private TreeSet<Animal> predators = new TreeSet<Animal>(new AnimalComparator());

    private XY abattoirCorner;
    private double abattoirRadius = 100;

    private MyMember[] myMembers = new MyMember[100];

    public class AnimalComparator implements Comparator<Animal>{

        @Override
        public int compare(Animal arg0, Animal arg1) {
            if(arg0.x < arg1.x){
                return -1;
            } else if (arg0.x > arg1.x){
                return 1;
            } else {
                if(arg0.y < arg1.y){
                    return -1;
                } else if(arg0.y > arg1.y){
                    return 1;
                } else {
                    return 0;
                }
            }
        }
    }

    public class MyMember extends Member{
        public XY target;
        public XY herdPos;
        public double herdRadius; 
        public boolean mayEat;
        public XY pos;
        public ArrayList<MyAnimal> closestPreys;
        public boolean outdated;

        public MyMember(int id) {
            super(id);
            this.pos = new XY(x, y);
            closestPreys = new ArrayList<MyAnimal>();
            mayEat = true;
            outdated = true;
        }

        public MyMember(Member member){
            super(member.id);
            this.pos = new XY(x, y);
            closestPreys = new ArrayList<MyAnimal>();
            mayEat = true;
            outdated = true;
        }

        public MyMember(Member member, Animal target){
            super(member.id);
            this.target = new XY(target.x, target.y);
            this.pos = new XY(x, y);
            closestPreys = new ArrayList<MyAnimal>();
            mayEat = true;
            outdated = true;
        }

        public void reset(Member me){
            x = me.x;
            y = me.y;
            pos = new XY(x, y);
            closestPreys.clear();
            mayEat = true;
            outdated = true;
        }
    }

    public class MyAnimal extends Animal{
        public ArrayList<MyMember> chasers;
        public XY pos;
        public boolean resolved;

        public MyAnimal(double x, double y){
            super(x, y);
            pos = new XY(x, y);
            chasers = new ArrayList<MyMember>();
            resolved = false;
        }

        public MyAnimal(Animal ani){
            super(ani.x, ani.y);
            pos = new XY(x, y);
            chasers = new ArrayList<MyMember>();
            resolved = false;
        }
    }

    public static void main(String[] args){
        new Clairvoyant().run();
    }

    public Clairvoyant(){
        for(int i=0; i<100; i++){
            nextIdx[i] = 0;
        }
        int cornerIdx = (int)Math.floor(Math.random()*4);
        switch (cornerIdx){
        case 0: abattoirCorner = new XY(0,0); break;
        case 1: abattoirCorner = new XY(500,0); break;
        case 2: abattoirCorner = new XY(500,500); break;
        case 3: abattoirCorner = new XY(0,500); break;
        }
    }

    @Override
    public void respond(){
        updateData();
        goToTarget();
    }

    private void updateData(){
        for(int i=0; i<100; i++){
            if(myMembers[i]!=null){
                myMembers[i].pos = null;
            }
        }
        foods.clear();
        predators.clear();
        for(Member me: members){
            foods.addAll(me.foods);
            predators.addAll(me.others);
            predators.add(new Animal(me.x, me.y));
            if(myMembers[me.id] != null){
                myMembers[me.id].reset(me);
            } else {
                myMembers[me.id] = new MyMember(me);
            }
        }
        for(int i=0; i<100; i++){
            if(myMembers[i]!=null && myMembers[i].pos == null){
                myMembers[i] = null;
            }
        }

        TreeSet<MyAnimal> closestPreys = new TreeSet<MyAnimal>(new AnimalComparator());
        for(int i=0; i<100; i++){
            if (myMembers[i]==null) continue;
            MyMember me = myMembers[i];
            ArrayList<Animal> animals = findClosest(foods, me.pos, members.size());
            boolean first = true;
            for(Animal ani: animals){
                MyAnimal myAni = new MyAnimal(ani);
                if(closestPreys.contains(ani)){
                    myAni = closestPreys.ceiling(myAni);
                } else {
                    closestPreys.add(myAni);
                }
                if(first){
                    myAni.chasers.add(me);
                    first = false;
                }
                me.closestPreys.add(myAni);
            }
        }
        performMatching();
        for(int i=0; i<100; i++){
            if (myMembers[i] == null) continue;
            MyMember me = myMembers[i];
            if(!me.outdated) continue;
            if(me.closestPreys.size() == 0) continue;
            MyAnimal closestPrey = me.closestPreys.get(0);
            if(closestPrey.resolved) continue;
            if(closestPrey.chasers.size() > 1){
                MyMember hungriest = me;
                MyMember closest = me;
                for(MyMember otherMe: closestPrey.chasers){
                    if(sqDist(closestPrey.pos, otherMe) < sqDist(closestPrey.pos, closest)){
                        closest = otherMe;
                    }
                    if(otherMe.hunger < hungriest.hunger){
                        hungriest = otherMe;
                    }
                }
                if(hungriest.hunger > 200){ // Nobody's critically hungry, the closest takes the prey
                    closest.target = closestPrey.pos;
                    closest.mayEat = true;
                    closest.herdPos = abattoirCorner;
                    closest.herdRadius = abattoirRadius;
                    closest.outdated = false;
                } else {
                    if(hungriest == closest){
                        closest.target = closestPrey.pos;
                        closest.mayEat = true;
                        closest.herdPos = abattoirCorner;
                        closest.herdRadius = abattoirRadius;
                        closest.outdated = false;
                    } else {
                        closest.target = closestPrey.pos;
                        closest.mayEat = false;
                        closest.herdPos = hungriest.pos;
                        closest.herdRadius = 0;
                        closest.outdated = false;
                        hungriest.target = closestPrey.pos;
                        hungriest.mayEat = true;
                        hungriest.herdPos = abattoirCorner;
                        hungriest.herdRadius = 10;
                        hungriest.outdated = false;
                    }
                }
                closestPrey.resolved = true;
            } else {
                me.target = closestPrey.pos;
                me.herdPos = abattoirCorner;
                me.herdRadius = abattoirRadius;
                me.mayEat = true;
                me.outdated = false;
            }
        }
        for(int i=0; i<100; i++){
            if (myMembers[i] == null) continue;
            MyMember me = myMembers[i];
            if(me.outdated){
                me.target = null;
                me.outdated = false;
            }
        }
    }

    private void goToTarget(){
        for(Member me: members){
            MyMember mem = myMembers[me.id];
            if(mem.target == null){
                wander(me, 2*(me.id%2)-1);
                continue;
            } else {
                nextIdx[me.id] = 0;
                XY[] nearestHostile = new XY[100];
                for(Animal other: me.others){
                    XY otherPos = new XY(other.x, other.y);
                    boolean isMember = false;
                    for(Member otherMember: members){
                        if(other.x==otherMember.x && other.y==otherMember.y){
                            isMember = true;
                            break;
                        }
                    }
                    if(!isMember){
                        if(nearestHostile[me.id] == null || XY.sqDistance(mem.pos, otherPos) < XY.sqDistance(mem.pos,  nearestHostile[me.id])){
                            nearestHostile[me.id] = otherPos;
                        }
                    }
                }

                // Go towards the target by predicting its next position
                XY target = predictNextPos(mem.target, me);

                me.dx = (target.x - me.x);
                me.dy = (target.y - me.y); 

                // Try to herd the target to our abattoir if this member is not too hungry
                // and if there is no other hostile predator who is closer to the target than us
                // This will make the other hostile predator to keep targeting this target, while
                // it is certain that we will get the target.
                // This is a win situation for us, since it will make the other predator wasting his turn.
                if((me.hunger <= 200 && XY.sqDistance(mem.target, mem.pos) > 400) || me.hunger <= 50 ||
                        (nearestHostile[me.id] != null && Math.sqrt(XY.sqDistance(mem.target, nearestHostile[me.id])) < Math.sqrt(XY.sqDistance(mem.target, mem.pos)))){
                    continue;
                }

                // Don't eat if not threatened nor hungry
                if(me.hunger > 50 && (nearestHostile[me.id] == null ||
                        Math.sqrt(XY.sqDistance(mem.target, nearestHostile[me.id])) > Math.sqrt(XY.sqDistance(mem.target, mem.pos)) + 6)){
                    mem.mayEat = false;
                }

                // Herd to abattoir corner
                double distFromHerd = Math.sqrt(XY.sqDistance(target, mem.herdPos));
                XY oppositeAbattoirCorner = new XY(500-abattoirCorner.x, 500-abattoirCorner.y);
                double distFromOpposite = Math.sqrt(XY.sqDistance(target, oppositeAbattoirCorner));
                if((me.dx*me.dx+me.dy*me.dy > 64 && distFromHerd > mem.herdRadius && distFromOpposite > abattoirRadius)
                        || (preyCount < 5*predCount)){
                    double herdDistance = 4*(distFromHerd-mem.herdRadius)/(Island.SIZE-mem.herdRadius);
                    if(!mem.mayEat) herdDistance = 4;
                    XY gradient = target.minus(abattoirCorner);
                    me.dx += gradient.x*herdDistance/distFromHerd;
                    me.dy += gradient.y*herdDistance/distFromHerd;
                }
            }
        }
    }

    private void performMatching(){
        for(int i=0; i<100; i++){
            if (myMembers[i] == null) continue;
            MyMember me = myMembers[i];
            if(me.closestPreys.size()==0) continue;
            MyAnimal closestPrey = me.closestPreys.get(0);
            if(closestPrey.chasers.size() > 1){
                resolveConflict(closestPrey);
            }
        }
    }

    private void resolveConflict(MyAnimal prey){
        ArrayList<MyMember> chasers = prey.chasers;
        MyMember winner = null;
        double closestDist = Double.MAX_VALUE;
        for(MyMember me: chasers){
            if(sqDist(prey.pos, me) < closestDist){
                closestDist = sqDist(prey.pos, me);
                winner = me;
            }
        }
        for(int i=chasers.size()-1; i>=0; i--){
            MyMember me = chasers.get(i);
            if(me!=winner){
                me.closestPreys.get(0).chasers.remove(me);
                me.closestPreys.add(me.closestPreys.remove(0));
                me.closestPreys.get(0).chasers.add(me);
            }
        }
    }

    private Animal findClosest(Collection<Animal> preys, XY me){
        Animal target = null;
        double cDist = Double.MAX_VALUE;
        double x, y, sqDist;
        for (Animal food : preys) {
            x = food.x - me.x;
            y = food.y - me.y;
            sqDist = x * x + y * y + Double.MIN_NORMAL;
            if (sqDist < cDist) {
                cDist = sqDist;
                target = food;
            }
        }
        return target;
    }

    private ArrayList<Animal> findClosest(Collection<Animal> preys, XY me, int num){
        ArrayList<Animal> result = new ArrayList<Animal>();
        for(Animal food: preys){
            int addIdx = -1;
            for(int i=0; i<num && i<result.size(); i++){
                Animal regFood = result.get(i);
                if(sqDist(me, food) < sqDist(me, regFood)){
                    addIdx = i;
                    break;
                }
            }
            if(addIdx == -1){
                result.add(food);
            } else {
                result.add(addIdx, food);
            }
            if(result.size() > num){
                result.remove(num);
            }
        }
        return result;
    }

    private Member findClosestToTarget(Collection<Member> members, Animal target){
        Member member = null;
        double cDist = Double.MAX_VALUE;
        double x, y, sqDist;
        for (Member me : members) {
            x = me.x - target.x;
            y = me.y - target.y;
            sqDist = x * x + y * y + Double.MIN_NORMAL;
            if (sqDist < cDist) {
                cDist = sqDist;
                member = me;
            }
        }
        return member;
    }

    private static final XY[] CHECKPOINTS = new XY[]{
        new XY(49.5,49.5),
        new XY(450.5,49.5),
        new XY(450.5,100),
        new XY(49.5,100),
        new XY(49.5,150),
        new XY(450.5,150),
        new XY(450.5,200),
        new XY(49.5,200),
        new XY(49.5,250),
        new XY(450.5,250),
        new XY(450.5,300),
        new XY(49.5,300),
        new XY(49.5,350),
        new XY(450.5,350),
        new XY(450.5,400),
        new XY(49.5,400),
        new XY(49.5,450.5),
        new XY(450.5,450.5)};
    private int[] nextIdx = new int[100];

    private int advanceIdx(int idx, int sign, int amount){
        return sign*(((Math.abs(idx)+CHECKPOINTS.length-1+sign*amount) % CHECKPOINTS.length) + 1);
    }

    private void wander(Member me, int sign) {
        if(preyCount > 20*predCount){
            if (me.dx == 0 && me.dy == 0) {
                me.dx = 250 - me.x;
                me.dy = 250 - me.y;
                return;
            }

            double lx, ly, px, py;
            lx = me.dx / 4;
            ly = me.dy / 4;
            boolean dir = Math.random() < 0.5 ? true : false;
            px = dir ? ly : -ly;
            py = dir ? -lx : lx;

            me.dx += px;
            me.dy += py;
        } else {
            if(nextIdx[me.id]==0){
                XY farthest = new XY(2000,2000);
                int farthestIdx = -1;
                for(int i=0; i<CHECKPOINTS.length; i++){
                    if(sign*sqDist(CHECKPOINTS[i], me) > sign*sqDist(farthest, me)){
                        farthest = CHECKPOINTS[i];
                        farthestIdx = i+1;
                    }
                }
                nextIdx[me.id] = farthestIdx*sign;
                for(Member mem: members){
                    if(mem.id == me.id) continue;
                    if(nextIdx[mem.id]==nextIdx[me.id]){
                        nextIdx[me.id] = advanceIdx(nextIdx[me.id], sign, 5); 
                    }
                }
            }
            if(sqDist(CHECKPOINTS[Math.abs(nextIdx[me.id])-1],me) < 1){
                nextIdx[me.id] = advanceIdx(nextIdx[me.id], sign, 1);
            }
            me.setDirection(CHECKPOINTS[Math.abs(nextIdx[me.id])-1].x-me.x,
                    CHECKPOINTS[Math.abs(nextIdx[me.id])-1].y-me.y);
        }
    }

    private double sqDist(XY me, Animal target){
        double dx = me.x-target.x;
        double dy = me.y-target.y;
        return dx*dx + dy*dy + Double.MIN_NORMAL;
    }

    private double sqDist(XY me, Member target){
        double dx = me.x-target.x;
        double dy = me.y-target.y;
        return dx*dx + dy*dy + Double.MIN_NORMAL;
    }

    private double sqDist(Animal target, Member me){
        double dx = me.x-target.x;
        double dy = me.y-target.y;
        return dx*dx + dy*dy + Double.MIN_NORMAL;
    }

    private List<Animal> getNeighbors(double radius, XY pos, Collection<Animal> candidates) {
        List<Animal> neighbors = new ArrayList<Animal>();
        for(Animal neighbor: candidates){
            if(sqDist(pos, neighbor) < radius * radius){
                neighbors.add(neighbor);
            }
        }
        return neighbors;
    }

    final double[] weights = { 1, 1, 0.96, 2, 4 };
    double weightSum;

    static final int ALIGN = 0;
    static final int SEPARATE = 1;
    static final int COHESION = 2;
    static final int FLEE = 3;
    static final int WALL = 4;
    static final int VISIBLE = 30;
    static final int VISIBLE_PRED = 50;

    private HashMap<Member, List<Animal>> prevPreys = new HashMap<Member, List<Animal>>();

    private XY matchPreys(List<Animal> prevs, List<Animal> curs, XY prey){
        XY result = new XY();
        double sqDist = 0;
        Animal candidate;
        XY otherPos;
        for(Animal otherPrey: curs){
            otherPos = new XY(otherPrey.x, otherPrey.y);
            sqDist = XY.sqDistance(prey, otherPos);
            if(sqDist > VISIBLE * VISIBLE)
                continue;
            candidate = findClosest(getNeighbors(6, otherPos, prevs), prey);
            if(candidate == null){
                return null;
            }
            result.add(otherPos.x-candidate.x, otherPos.y-candidate.y);
        }
        return result;
    }

    private XY predictNextPos(XY prey, Member me) {
        List<Animal> preys = getNeighbors(VISIBLE_PRED, prey, foods);
        List<Animal> preds = getNeighbors(VISIBLE, prey, predators);

        XY flock[] = new XY[weights.length];
        for (int i = 0; i < weights.length; i++)
            flock[i] = new XY();

        double dx, dy, dist, sqDist;
        for (Animal otherPrey : preys) {
            sqDist = XY.sqDistance(prey, new XY(otherPrey.x, otherPrey.y));
            if(sqDist > VISIBLE * VISIBLE)
                continue;
            dx = otherPrey.x - prey.x;
            dy = otherPrey.y - prey.y;
            flock[COHESION].add(dx*sqDist, dy*sqDist);
            flock[SEPARATE].add(-dx*(1d/sqDist), -dy*(1d/sqDist));
            flock[ALIGN].add(new XY(prey.x-me.x,prey.y-me.y));
        }

        if(sqDist(prey, me) < 400){
            if(prevPreys.get(me) == null){
                prevPreys.put(me, preys);
            } else {
                XY flockAlign = matchPreys(prevPreys.get(me), preys, prey);
                if(flockAlign == null){
                    prevPreys.put(me , null);
                } else {
                    flock[ALIGN] = flockAlign;
                    prevPreys.put(me, preys);
                }
            }
        }

        flock[ALIGN].unitize().multiply(5);
        flock[COHESION].unitize().multiply(5);
        flock[SEPARATE].unitize().multiply(5);

        for (Animal predator : preds){
            flock[FLEE].add(prey.x-predator.x, prey.y-predator.y);
        }

        dx = Island.CENTER.x - prey.x;
        dy = Island.CENTER.y - prey.y;
        dist = Math.max(Math.abs(dx), Math.abs(dy));
        if(dist > 240){
            flock[WALL].x = dx * dist;
            flock[WALL].y = dy * dist;
            flock[WALL].unitize().multiply(5);
        }

        XY vec = new XY();
        vec.x = 0;
        vec.y = 0;
        for (int i = 0; i < flock.length; i++) {
            flock[i].multiply(weights[i]);
            vec.add(flock[i]);
        }
        limitSpeed(vec);
        return vec.add(prey);
    }

    private XY limitSpeed(XY move) {
        if (move.x*move.x+move.y*move.y > MAX_SPEED*MAX_SPEED)
            move.unitize().multiply(MAX_SPEED);
        return move;
    }
}

Answer 2

Netcats

Here's a pack to get you guys started. It extends the GenericPack class included with the control program. It's been improved since original posting, and no longer starves itself with a sparse herd.

Netcats use a vee-shaped net formation to trap prey in the corner, where they can eat them at leisure. The net is formed with one "head" member at the center. Once the head eats, it swaps places with the hungriest pack member, since the head is the normally the first to get an opportunity to eat.

The net starts rather small, but widens when the herd gets smaller in order to trawl the field more efficiently.

If no prey are visible, the formation widens into a naive search pattern covering most of the island.

Once the pack gets down to two members, the net just doesn't work. At that point each goes its own way, greedily eating the nearest thing it can find and taking a semi-random walk otherwise.

This version survives much better than the naive Netcats seen in the video linked in the question.

import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

public class Netcats extends GenericPack {

    boolean seeking;
    Member head = null;
    Set<Animal> foods;

    public static void main(String[] args) {
        new Netcats().run();
    }

    @Override
    public void respond() {
        if (foods == null)
            foods = new HashSet<Animal>();
        else
            foods.clear();
        for (Member member : members)
            foods.addAll(member.foods);

        if (members.size() < 3) {
            soloRun();
        } else {
            head = setHead();
            setHeadVec();
            for (int i = 1; i < members.size(); i++) {
                setMemberVec(i);
            }
        }
    }

    Member setHead() {
        if (!members.contains(head))
            return members.get(0);

        Member hungry = head;
        int idx = 0;
        for (int i = 0; i < members.size(); i++) {
            Member me = members.get(i);
            if (me.hunger < hungry.hunger) {
                hungry = me;
                idx = i;
            }
        }

        if (hungry != head) {
            members.remove(hungry);
            members.remove(head);
            members.add(0, hungry);
            members.add(idx, head);
            return hungry;
        }
        return head;
    }

    void setHeadVec() {
        double x = 0, y = 0;

        Collection<Animal> yummy = getFoods(head);

        seeking = false;
        if (yummy.size() == 0) {
            scoutHead();
            return;
        }

        if (members.size() == 1)
            if (findFood(head))
                return;

        for (Animal food : yummy) {
            x += food.x - head.x;
            y += food.y - head.y;
        }
        x *= 10000000;
        y *= 10000000;

        head.dx = x;
        head.dy = y;
        if (members.size() > 1)
            limitSpeed(head, MAX_SPEED * HEAD_MULT);
    }

    void scoutHead() {
        seeking = true;
        head.dy = 250 - head.y;
        head.dx = round % 80 < 40 ? -head.x : 500 - head.x;
    }

    void setMemberVec(int idx) {
        Member me = members.get(idx);
        Member leader;
        leader = idx < 3 ? members.get(0) : members.get(idx - 2);
        if (findFood(me))
            return;

        double lx, ly, px, py, tx, ty, dist;
        lx = -leader.dx;
        ly = -leader.dy;
        dist = Math.sqrt(lx * lx + ly * ly) + Double.MIN_NORMAL;
        lx /= dist;
        ly /= dist;
        px = idx % 2 == 0 ? ly : -ly;
        py = idx % 2 == 0 ? -lx : lx;

        tx = leader.x + leader.dx;
        ty = leader.y + leader.dy;
        int xtrack = seeking ? COMB : preyCount > 400 ? ASIDE : MID_SIDE;
        tx += lx * BEHIND + px * xtrack;
        ty += ly * BEHIND + py * xtrack;

        me.dx = tx - me.x;
        me.dy = ty - me.y;
        limitSpeed(me, MAX_SPEED * (idx < 3 ? MID_MULT : 1));
    }

    Collection<Animal> getFoods(Member me) {
        return me.foods.size() == 0 ? foods : me.foods;
    }

    boolean findFood(Member me) {
        if (me.hunger > 500)
            return false;

        Collection<Animal> yummy = getFoods(me);
        if (yummy.size() == 0)
            return false;

        double x, y, sqDist, cDist = 10 * 10;
        Animal target = null;
        for (Animal food : me.foods) {
            x = food.x - me.x;
            y = food.y - me.y;
            sqDist = x * x + y * y + Double.MIN_NORMAL;
            if (sqDist < cDist) {
                cDist = sqDist;
                target = food;
            }
        }

        if (target == null)
            return false;

        if (cDist < 5 * 5 || me.hunger < 200) {
            me.dx = (target.x - me.x) * 10000000d;
            me.dy = (target.y - me.y) * 10000000d;
            return true;
        }
        return false;
    }

    void soloRun() {
        double x, y, sqDist, cDist;
        for (Member me : members) {
            Collection<Animal> yummy = getFoods(me);
            if (yummy.size() == 0) {
                wander(me);
                continue;
            }

            Animal target = null;
            cDist = Double.MAX_VALUE;
            for (Animal food : yummy) {
                x = food.x - me.x;
                y = food.y - me.y;
                sqDist = x * x + y * y + Double.MIN_NORMAL;
                if (sqDist < cDist) {
                    cDist = sqDist;
                    target = food;
                }
            }

            me.dx = (target.x - me.x) * 100000d;
            me.dy = (target.y - me.y) * 100000d;
        }
    }

    void wander(Member me) {
        if (me.dx == 0 && me.dy == 0) {
            me.dx = 250 - me.x;
            me.dy = 250 - me.y;
            return;
        }

        double lx, ly, px, py;
        lx = me.dx / 4;
        ly = me.dy / 4;
        boolean dir = Math.random() < 0.5 ? true : false;
        px = dir ? ly : -ly;
        py = dir ? -lx : lx;

        me.dx += px;
        me.dy += py;
    }

    void limitSpeed(Member me, double max) {
        double x = me.dx, y = me.dy;
        double dist = Math.sqrt(x * x + y * y) + Double.MIN_NORMAL;
        if (dist > max) {
            x = (x / dist) * max;
            y = (y / dist) * max;
        }
        me.dx = x;
        me.dy = y;
    }

    final static double MAX_SPEED = 6.1;
    final static double HEAD_MULT = 0.85;
    final static double MID_MULT = 0.92;
    final static int BEHIND = -25;
    final static int ASIDE = 15;
    final static int MID_SIDE = 30;
    final static int COMB = 150;
}

Answer 3

Ruby Spiders

As sometimes less is more and many solutions would probably try to corner the prey anyway...

I thought my pack could just split up and wait for others to do the work.

gets
print "3.0\t3.0\t3.0\t-3.0\t-3.0\t-3.0\t-3.0\t3.0\t0.0\t0.0\0"
STDOUT.flush

Caveat: It doesn't actually stay running, neither does it read input as it comes in nor responds quickly. Still, as it works well with the controller I hope it qualifies without further adjustments.

Answer 4

CivilizedBeasts

Finally, time to show off my beasts!

My breed thinks hunting is somewhat primitive so they work together in a team of 4 and so they abandon their 5th ally, because: less predators = more prey for themselves. What they basically do is what humans do, they catch prey, and take good care of their cattle ;)

public class CivilizedBeasts extends GenericPack{

    private static int TL = 0, TR = 0, BL = 0, BR = 0; // TopLeft/BotRight
    private static int teamSize = 0, turnsWaiting = 0, turnsToWait = 20;

    private boolean out = true;
    private double maxSpeed = 6.1, mapSize = 500;

    public CivilizedBeasts(){
    }

    @Override
    public void respond(){
        if(teamSize > members.size()){

            Member check = getMemberById(TL);
            totalLoop:
            if(check == null){
                for (Member member : members) {
                    if(member.id != TR && member.id != BL && member.id != BR){
                        TL = member.id;
                        break totalLoop;
                    }
                }

                TL = 0;
            }

            check = getMemberById(TR);
            totalLoop:
            if(check == null){
                for (Member member : members) {
                    if(member.id != TL && member.id != BL && member.id != BR){
                        TR = member.id;
                        break totalLoop;
                    }
                }

                TR = 0;
            }

            check = getMemberById(BL);
            totalLoop:
            if(check == null){
                for (Member member : members) {
                    if(member.id != TL && member.id != TR && member.id != BR){
                        BL = member.id;
                        break totalLoop;
                    }
                }

                BL = 0;
            }

            check = getMemberById(BR);
            totalLoop:
            if(check == null){
                for(Member member : members) {
                    if(member.id != TL && member.id != TR && member.id != BL){
                        BR = member.id;
                        break totalLoop;
                    }
                }

                BR = 0;
            }
        }else if(teamSize < members.size()){
            for(Member member : members) {
                if(member.id != TL && member.id != TR && member.id != BL && member.id != BR){
                    if(TL == 0)
                        TL = member.id;
                    else if(TR == 0)
                        TR = member.id;
                    else if(BL == 0)
                        BL = member.id;
                    else if(BR == 0)
                        BR = member.id;
                }
            }
        }

        teamSize = members.size();

        double border = 1;
        double x, y;
        boolean reached = true;

        double distance = 16.3;

        for (Member member : members) {
            boolean doesNotCount = false;
            x = 0; y = 0;
            if(member.id == TL){
                if(out){
                    x = -(member.x - border);
                    y = -(member.y - border);
                }else{
                    x = ((mapSize/2 - distance) - member.x);
                    y = ((mapSize/2 - distance) - member.y);
                }
            }else if(member.id == TR){
                if(out){
                    x = (mapSize - member.x - border);
                    y = -(member.y - border);
                }else{
                    x = ((mapSize/2 + distance) - member.x);
                    y = ((mapSize/2 - distance) - member.y);
                }
            }else if(member.id == BL){
                if(out){
                    x = -(member.x - border);
                    y = (mapSize - member.y - border);
                }else{
                    x = ((mapSize/2 - distance) - member.x);
                    y = ((mapSize/2 + distance) - member.y);
                }
            }else if(member.id == BR){
                if(out){
                    x = (mapSize - member.x - border);
                    y = (mapSize - member.y - border);
                }else{
                    x = ((mapSize/2 + distance) - member.x);
                    y = ((mapSize/2 + distance) - member.y);
                }
            }else{
                double dist = 50, temp = 0;
                int index = -1;
                for(int i = 0; i < member.foods.size(); i++){
                    temp = (Math.abs(member.foods.get(i).x - member.x)+Math.abs(member.foods.get(i).y - member.y));
                    if(temp < dist){
                        dist = temp;
                        index = i;
                    }
                }
                if(index != -1){
                    x = (member.foods.get(index).x - member.x);
                    y = (member.foods.get(index).y - member.y);
                }
                doesNotCount = true;
            }

            if(!doesNotCount && Math.abs(x)+Math.abs(y) > maxSpeed)
                reached = false;
            member.setDirection(x,y);
        }

        if(reached){
            if(!out){ // in the middle.
                if(teamSize < 4){
                    int temp = TL;
                    TL = BR;
                    BR = temp;
                    temp = TR;
                    TR = BL;
                    BL = temp;
                    out = true;
                }else{
                    turnsWaiting++;
                }
            }else // no need to wait in the corners
                out = false;

            if(turnsWaiting >= turnsToWait){
                turnsToWait = 15;
                out = true;
                turnsWaiting = 0;
            }

        }

    }

    public static void main(String[] args){
        new CivilizedBeasts().run();
    }
}

It becomes quite difficult for my breasts to survive with less than 200 prey at turn +-12.000 with only enemy Netcats in the game. You will be happy with this breed since it really devours massive amounts of prey with speed like no other breed ever can (not that quick and big slaughters grants victory, but it influences the (long) time a whole round takes considerably).

Answer 5

Ruby Vultures

Here comes a pack of more active parasites. They are trying to surround closest moving predator, so that they can steal his prey. They are a bit luck dependent as they have no smart way of choosing who to follow but they are usually beating chasers and sometimes spiders.

They are not quite finished, as I posted this to push the tempo :)

I'm hoping to:

• make them search for predators outside of the field of view
• take prey into account - often one of them is between another pack and the prey!
• start rotating them to avoid one starving when all other are well fed

22 April 2014: Added boredom, which makes them less less sticky and allows them to hunt for prey on their own and search for predators

class Animal
  attr_accessor :x, :y
end

class Hunter < Animal
  attr_accessor :id, :bored

  def initialize diff
   @diff = diff
   @lastGoal = nil
   @bored = false
  end

  def move goal
    if not goal.nil? 
      if @bored or goal != @lastGoal
        @lastGoal = goal
        return [goal.first - x + @diff.first, goal.last - y + @diff.last]
      end
    end
    [250 - x + 3*@diff.first, 250.0 - y + 3*@diff.last]
  end
end

class Pack
  def initialize
    @file = File.open "pack_log", "w"
    @count = 0
    @pack = []
    @order = []
    @hunters = []
    @closest = nil
    @random_goal = [250.0, 250.0]
    @locations = []
    @timer = 0
    d = 25.0
    diffs = [[d, d], [d, -d], [-d, -d], [-d, d], [0.0, 0.0]]
    5.times do |i|
      @pack << (Hunter.new diffs[i])
    end
    line = 0
    s = gets
    loop do
      s = gets
      if not (s =~ /dead\0/).nil?
        break
      end
      if line == 0
        get_structure s
      elsif line == 1
        get_positions s
      end
      @pack.length.times do |i|
        if line == i*2 + 3
          look_for_hunters s
          if @count <= i+1
            @closest = closest_hunter
            move
          end
        end
      end
      if not (s =~ /\0/).nil?
        line = 0
        @hunters = []
      else
        line += 1
      end
    end
  end

  def member_by_id id
    member = nil
    @pack.each do |v|
      if v.id == id
        member = v
        break
      end
    end
    member
  end

  def member_by_order index
    member_by_id @order[index]
  end

  def distance a, b
    Math.sqrt((a.first - b.first)**2 + (a.last - b.last)**2)
  end

  def bored?
    bored = true
    l1 = @locations.first
    @locations.each do |l2|
      if distance(l1, l2) > 20
        bored = false
      end
    end 
    bored
  end

  def bored_move v
    if @timer <= 0
      @random_goal = [rand(1000).to_f - 250, rand(1000).to_f - 250]
      @pack.each do |m|
        m.bored = true
      end
      @timer = 250 
    else
      @timer -= 1
    end
    v.move @random_goal
  end

  def move
    first_one = true
    answer = ""
    @order.each do |id|
      v = member_by_id id
      x, y = 0, 0
      if bored?
        x, y = (bored_move v)
      elsif @timer > 0
        @location = []
        x, y = (bored_move v)
      else
        @pack.each do |m|
          m.bored = false
        end
        @timer = 0
        x, y = v.move @closest
      end
      if not first_one
        answer << "\t"
      end
      answer << "#{x.to_i}.0\t#{y.to_i}.0"
      first_one = false
    end
    answer << "\0"
    print answer
    STDOUT.flush
  end

  def get_structure line
    @order = []
    if @pack.first.id.nil? 
      @count = 0
      line.split.each_with_index do |v, i|
        if i % 2 == 0
          @order << v.to_i
          @pack[i/2].id = v.to_i
          @count += 1
        end
      end
    else
      @count = 0
      line.split.each_with_index do |v, i|
        if i % 2 == 0
          @order << v.to_i
          @count += 1
        end
      end
    end
  end

  def get_positions line
    if not @order.empty?
      line.split.each_with_index do |v, i|
        if i % 2 == 0
          member_by_order(i/2).x = v.to_f
        else
          member_by_order(i/2).y = v.to_f
        end
      end
    end
  end

  def look_for_hunters line
    line.split.each_with_index do |v, i|
      if i % 2 == 0
        @hunters << [v.to_f]
      else
        @hunters.last << v.to_f
      end
    end
  end

  def closest_hunter
    mass_center
    closest = nil
    bestDist = 500*500
    if not @hunters.nil? and not @hunters == []
      @hunters.each do |h|
        our = false
        @pack.each do |v|
          if h.first == v.x and h.last == v.y
            our = true
          end
        end
        if our
          next
        end
        sqDist = (@mass_center.first - h.first)**2 + (@mass_center.last - h.last)**2
        if sqDist < bestDist
          closest = []
          closest << h.first
          closest << h.last
        end
      end
    end
    closest
  end

  def mass_center
    center_x = 0
    center_y = 0
    @pack.each do |v|
      center_x += v.x
      center_y += v.y
    end
    @mass_center = [center_x.to_f / @count, center_y.to_f / @count]
    if @locations.length > 30
      @locations.shift
      @locations << @mass_center
    else
      @locations << @mass_center
    end
  end
end

Pack.new

Answer 6

Evil Eco Camels

Edit: Mutation #2. Oh, no, I'm late with my implementation of prey movement prediction, to be the first to beat the Netcats. OK, so be it.

This mutation has $hunger_critical variable (constant). Changing it to value above 1000 makes Camels to always hunt, like Clairvoyants. Then:

Done in 11.93 minutes
camels1.pl(0)                   : Turn 23112    : Score 100
Netcats(1)                      : Turn 22508    : Score 80

If $hunger_critical is set to e.g. 500 (as below), then my Camels (after seeing the horrors of civilization) try to behave in Eco-friendly manner (hence they have changed the name of their breed), i.e. they kill only when hungry. If not hungry, they patrol critical Island areas - center and corners, to prevent pointless butchering by some other hunters. Well, with center, it more or less works. The idea of circling in corners was to shoo the prey away and make life more difficult for the Cats and parasites. Well, it doesn't work. Stupid prey goes into corners anyway.

Its interesting, also, that the flock[ALIGN] component can only be guessed, by predators, and my implementation is different than justhalf's. I'm afraid there's some minor bug in my rip-off implementation of Geobits' code, watching/comparing individual hunting of Camels vs Clairvoyants.

And program is kind of long now, sorry.

---

Edit : Mutation #1. The Island turns out to be quite radioactive (that explains lack of vegetation and unexplainable nature of 'prey' creatures), so here's first mutation of my Camels. Any of them can become solo hunter, if hungry or if there's no free corner for everyone. Hunter tries to actively pursue nearby prey. If there's none, it patrols in wide circle around center of the island, then chases nearest creature when finds it. Unfortunately, prey's direction becomes unpredictable when it's near its swarm (worth investigating...), so solo chase is not very efficient. But if it succeeds, the Camel goes to digest to the nearest free corner (if any). When hunger level is below certain level, any Camel abandons its corner (probably cursing Netcats ('where's food?')) and goes free roaming on its own. And so on.

---

Same joke told twice is not funny, but (1) I had to start somewhere and I'm new to these things, (2) Honest, I thought about corner tactics (and who didn't?), watching Netcats, before Ruby Spiders appeared on the Island.

So, ever heard about carnivore camels? Poor animals woke up one day on this god-forsaken Island to find no grass nor trees at all, but plenty of strange green though edible fast moving (quite annoying) little things. Having no hunting habits (but they'll mutate soon, I hope), my Camels developed very evil scheme to survive: they split and go each into 1 of 4 corners, and 5th one goes to the center (to die there first, as it turnes out). On their destinations they patiently wait, performing kind of camel war-dance, or maybe they just try not to tread on other animals already there, spiders and all...

#!/usr/bin/env perl
use strict;
use warnings;

binmode STDOUT;
binmode STDIN;
$| = 1;
$, = "\t";

my $hunger_critical = 500;
my %pack;
my ($turn, $prey_count, $predators_count);
my $patrol_radius_hunt = 150;
my $patrol_radius_corner = 16;
my $patrol_radius_center = 1;
my @roles = qw/C LL LR UL UR/; # or P (patrol if > 5), H (hunt)
my %places = (
    UL => {x =>   1 + $patrol_radius_corner, y =>   1 + $patrol_radius_corner},
    UR => {x => 499 - $patrol_radius_corner, y =>   1 + $patrol_radius_corner},
    LR => {x => 499 - $patrol_radius_corner, y => 499 - $patrol_radius_corner},
    LL => {x =>   1 + $patrol_radius_corner, y => 499 - $patrol_radius_corner},
    C  => {x => 250, y => 250},
);

sub sq_dist {
    my ($x1, $y1, $x2, $y2) = @_;
    return ($x1 - $x2)**2 + ($y1 - $y2)**2
}

sub distance {
    return sqrt(&sq_dist)
}

sub assign_role {
    my $camel = shift;
    if (@roles) {
        my %choice = (d => 1000, i => 0);
        for my $i (0..$#roles) {
            my $r = $roles[$i];
            if ($r eq 'C') {
                if ($prey_count > 700) {
                    $choice{i} = $i;
                    last
                }
                else {
                    next
                }
            }
            my $d = distance($camel->{x}, $camel->{y}, $places{$r}{x}, $places{$r}{y});
            if ($d < $choice{d}) {
                @choice{qw/d i/} = ($d, $i)
            }
        }
        return splice @roles, $choice{i}, 1
    }
    else {
        return 'P'
    }
}

sub xy_average {
    my $xy = shift;
    my $x = my $y = 0;
    if ($xy && @$xy) {
        for my $item (@$xy) {
            $x += $item ->{x};
            $y += $item->{y}
        }
        $x /= @$xy;
        $y /= @$xy
    }
    return $x, $y
}

sub patrol {
    my ($xc, $yc, $radius, $camel) = @_;
    my ($x, $y) = ($camel->{x} - $xc, $camel->{y} - $yc);
    my $d = distance(0, 0, $x, $y);
    my $a = atan2($y, $x);
    if (abs($d - $radius) < 3) {
        $a += 6 / $radius
    }
    return $radius * cos($a) - $x, $radius * sin($a) - $y
}

while (1) {

    # Get input

    my @in;
    # Line 0 - turn, counts
    $_ = <>;
    die if /dead/;
    ($turn, $prey_count, $predators_count) = /\0?(\S+)\t(\S+)\t(\S+)/;
    # Line 1 - pack's ids and hunger
    $_ = <>;
    while (/(\S+)\t(\S+)/g) {
        push @in, {id => $1, hunger => $2}
    };
    # Line 2 - positions
    $_ = <>;
    for my $animal (@in) {
        /(\S+)\t(\S+)/g;
        ($animal->{x}, $animal->{y}) = ($1, $2);
    }
    # 2 lines per member, visible prey and predators
    for my $animal (@in) {
        $_ = <>;
        my @prey;
        while (/(\S+)\t(\S+)/g) {
            push @prey, {x => $1, y => $2}
        };
        $animal->{prey} = \@prey;
        $_ = <>;
        my @beasts;
        while (/(\S+)\t(\S+)/g) {
            push @beasts, {x => $1, y => $2}
        };
        $animal->{beasts} = \@beasts
    }
    # trailing \0 zero will be prepended to next turn input

    # Update my pack

    for my $n (0..$#in) {
        my $animal = $in[$n];
        my $id = $animal->{id};
        # old average prey position
        my @opp = xy_average($pack{$id}{prey});
        # new average prey position
        my @npp = xy_average($animal->{prey});
        # average prey displacement
        my %apd = (x => $npp[0] - $opp[0], y => $npp[1] - $opp[1]);
        $pack{$id}{apd}    = \%apd;
        $pack{$id}{hunger} = $animal->{hunger};
        $pack{$id}{x}      = $animal->{x};
        $pack{$id}{y}      = $animal->{y};
        $pack{$id}{prey}   = $animal->{prey};
        $pack{$id}{beasts} = $animal->{beasts};
        $pack{$id}{num}    = $n;
        $pack{$id}{dead}   = 0
    }

    # Bury dead animals, retrieve their roles

    while (my ($id, $camel) = each %pack) {
        if ($camel->{dead}) {
            my $role = $camel->{role};
            push @roles, $role if $role ne 'P' and $role ne 'H';
            delete $pack{$id};
        }
        else {
            $camel->{dead} = 1
        }
    }

    # See that everyone has a role and lives accordingly

    my @out;
    for my $camel (values %pack) {
        my $role = $camel->{role} ||= assign_role($camel);
        if ($camel->{hunger} < $hunger_critical and $role ne 'H') {
            push @roles, $role if $role ne 'P';
            $role = $camel->{role} = 'H'
        }
        if ($camel->{hunger} > $hunger_critical and ($role eq 'H' or $role eq 'P') and $prey_count > 400) {
            $role = $camel->{role} = assign_role($camel)
        }
        my @vector = (0, 0);
        if ($role eq 'H') {
            my @prey = @{$camel->{prey}};
            if (@prey) {
                my %nearest = (p => undef, dd => 2500);
                for my $prey (@prey) {
                    my $dd = sq_dist($camel->{x}, $camel->{y}, $prey->{x}, $prey->{y});
                    if ($dd <= $nearest{dd}) {
                        @nearest{qw/p dd/} = ($prey, $dd)
                    }
                }
                my $target = $nearest{p};
                if ($nearest{dd} > 900) {
                    @vector = ($target->{x} - $camel->{x}, $target->{y} - $camel->{y})
                }
                else {
                    my @vect = map{{x => 0, y => 0}}1..5;
                    my $n = 0;
                    for my $prey (@prey) {
                        next if $prey eq $target;
                        my $dd = sq_dist($target->{x}, $target->{y}, $prey->{x}, $prey->{y}) + 1/(~0);
                        next if $dd > 900;
                        $n ++;
                        my $dx = $prey->{x} - $target->{x};
                        my $dy = $prey->{y} - $target->{y};
                        $vect[1]{x} -= $dx / $dd;
                        $vect[1]{y} -= $dy / $dd;
                        $vect[2]{x} += $dx * $dd;
                        $vect[2]{y} += $dy * $dd
                    }
                    $vect[0] = {x => $n * $camel->{apd}{x}, y => $n * $camel->{apd}{y}};
                    my $dx = abs(250 - $target->{x});
                    my $dy = abs(250 - $target->{y});
                    my $d = $dx > $dy ? $dx : $dy;
                    if ($d > 240) {
                        $vect[4]{x} = $dx * $d;
                        $vect[4]{y} = $dy * $d;
                    }
                    for my $v (@vect) {
                        my $d = sqrt($v->{x}**2 + $v->{y}**2) + 1/(~0);
                        $v->{x} /= $d;
                        $v->{y} /= $d;
                    }
                    for my $beast (@{$camel->{beasts}}, $camel) {
                        my $dd = sq_dist($target->{x}, $target->{y}, $beast->{x}, $beast->{y});
                        next if $dd > 900;
                        $vect[3]{x} += $target->{x} - $beast->{x};
                        $vect[3]{y} += $target->{y} - $beast->{y};
                    }
                    $vector[0] = 5 * 1   * $vect[0]{x}
                               + 5 * 1   * $vect[1]{x}
                               + 5 * .96 * $vect[2]{x}
                               + 1 * 2   * $vect[3]{x}
                               + 5 * 4   * $vect[4]{x};
                    $vector[1] = 5 * 1   * $vect[0]{y}
                               + 5 * 1   * $vect[1]{y}
                               + 5 * .96 * $vect[2]{y}
                               + 1 * 2   * $vect[3]{y}
                               + 5 * 4   * $vect[4]{y};
                    my $dd = $vector[0]**2 + $vector[1]**2;
                    if ($dd > 36) {
                        my $d = sqrt($dd);
                        @vector = map {$_ * 6.1 /$d} @vector
                    }
                }
            }
            else {
                @vector = patrol(250, 250, $patrol_radius_hunt, $camel)
            }
        }
        elsif ($role eq 'P') {
            @vector = patrol(250, 250, $patrol_radius_hunt, $camel)
        }
        else {
            my $r = $role eq 'C' 
                ? $patrol_radius_center 
                : $patrol_radius_corner;
            @vector = patrol($places{$role}{x}, $places{$role}{y}, $r, $camel)
        }
        my $id_x = $camel->{num} << 1;
        my $id_y = $id_x + 1;
        @out[$id_x, $id_y] = @vector
    }

    # And let the cruel world know about it

    print @out;
    print "\0"
}

__END__

Answer 7

AbleDogs - PHP

These nice dogs have learned how to bite a prey's calves to goad it along walls. They also love to roam the pasture in search of new preys. Lastly, they have been taught to refrain from eating unless they really need the calories.

Put the code into an AbleDogs file and run it with php AbleDogs

<?php
// simulation parameters

define ("ARENA_SIZE", 500);

define ("HUNGER_MAX", 1000);

define ("PREY_SPEED", 6);
define ("PRED_SPEED", 6.1);

define ("PREY_VISION", 30);
define ("PRED_VISION", 50);

define ("WALL_BOUNCE", 10); // distance from a wall from which a prey starts bouncing

// derived constants

define ("PRED_SPEED2" , PRED_SPEED  * PRED_SPEED );
define ("PRED_VISION2", PRED_VISION * PRED_VISION);
define ("PREY_VISION2", PREY_VISION * PREY_VISION);

// grid to speedup preys lookup

define ("GRID_SIZE", ceil (ARENA_SIZE/PRED_VISION));
define ("GRID_STEP", ARENA_SIZE/GRID_SIZE);

// search patterns

define ("SEARCH_OFFSET", WALL_BOUNCE+PRED_VISION/sqrt(2));
define ("SEARCH_WIDTH" , 2*sqrt(PRED_VISION2-PRED_SPEED2/4));
define ("SEARCH_HEIGHT", ARENA_SIZE-2*SEARCH_OFFSET);
define ("SEARCH_SIZE"  , ceil(SEARCH_HEIGHT/SEARCH_WIDTH));
define ("SEARCH_STEP"  , SEARCH_HEIGHT/SEARCH_SIZE);
define ("SEARCH_LEGS"  , 2*SEARCH_SIZE+1);

// tracking

define ("MAX_TRACK_ERROR", 10); // max abs distance for prey tracking correlation
define ("TRACKING_HUNGER_START", HUNGER_MAX*.9); // hunger limit to try and eat the tracked prey (start of game)
define ("TRACKING_HUNGER_END", 4);     // idem, for endgame
define ("TRACKING_DISTANCE", PREY_SPEED*2.5);
define ("TRACKING_DISTANCE2", TRACKING_DISTANCE * TRACKING_DISTANCE);

class Point {
    public $x = 0;
    public $y = 0;

    function __construct ($x=0, $y=0)
    {
        $this->x = (float)$x;
        $this->y = (float)$y;
    }

    function __toString() // for comparisons
    {
        return "$this->x,$this->y";
    }

    function multiply ($scalar)
    {
        return new Point ($this->x * $scalar, $this->y * $scalar);
    }

    function add ($v)
    {
        return new Point ($this->x + $v->x, $this->y + $v->y);
    }

    function dot($v)
    {
        return $this->x * $v->x + $this->y * $v->y;
    }

    function rotate90()
    {
        return new Point (-$this->y, $this->x);
    }

    function vector_to ($goal)
    {
        return new Point ($goal->x - $this->x, $goal->y - $this->y);
    }

    function norm2 ()
    {
        return $this->dot ($this);
    }

    function norm ()
    {
        return sqrt ($this->norm2());
    }

    function normalize ($norm = 1)
    {
        $n = $this->norm();
        if ($n != 0) $n = $norm/$n;
        return $this->multiply ($n);
    }

    function limit ($norm)
    {
        return $this->norm() > $norm
             ? $this->normalize($norm)
             : clone $this;
    }
}

class Search {

    function __construct ($direction)
    {
        switch ($direction % 4)
        {
            case 0: $this->pos = new Point (          0,           0); break;
            case 1: $this->pos = new Point (SEARCH_SIZE,           0); break;
            case 2: $this->pos = new Point (SEARCH_SIZE, SEARCH_SIZE); break;
            case 3: $this->pos = new Point (          0, SEARCH_SIZE); break;
        }
        $this->start();
    }

    private function start ()
    {
        $this->dir = $this->pos->x == $this->pos->y;
        $this->adj = $this->pos->x ? -1 : 1;
        $this->target = new Point ($this->pos->x * SEARCH_STEP + SEARCH_OFFSET,
                                   $this->pos->y * SEARCH_STEP + SEARCH_OFFSET);
        $this->leg = 0;
    }

    function point ($pos)
    {
        if ($pos == $this->target)
        {
            if ($this->leg % 2)
            {
                if ($this->dir) $this->pos->y+= $this->adj;
                else            $this->pos->x+= $this->adj;
            }
            else
            {
                if ($this->dir) $this->pos->x = $this->pos->x ? 0 : SEARCH_SIZE;
                else            $this->pos->y = $this->pos->y ? 0 : SEARCH_SIZE;
            }
            $this->leg++;
            if ($this->leg == SEARCH_LEGS) $this->start();
            $this->target = new Point ($this->pos->x * SEARCH_STEP + SEARCH_OFFSET,
                                       $this->pos->y * SEARCH_STEP + SEARCH_OFFSET);
        }
        return $this->target;
    }
}

class Pack {

    public static $turn;   // turn number
    public static $size;   // number of live members
    public static $member; // array of members

    public static $prev_preys;     // previous coordinates of all preys
    public static $prev_preds;     // previous coordinates of foreign predators

    public static $n_preys; // total number of preys     (including those not currently seen)
    public static $n_preds; // total number of predators (including those not currently seen)

    public static $preys;     // coordinates of all preys
    public static $preds;     // coordinates of all predators
    public static $own_preds; // coordinates of all predators in our pack
    public static $foe_preds; // coordinates of all foreign predators

    public static $arena_center; // arena center

    private static $output_order; // to send output according to input order

    function init ()
    {
        Pack::$member = array();
        Pack::$arena_center = new Point (ARENA_SIZE/2, ARENA_SIZE/2);
    }

    function read_line ($line)
    {
        $values = array();
        if ($line == "") return $values;
        $input = explode ("\t", $line);
        $num = count($input);
        if ($num % 2) panic ("read_line: invalid input $line num $num");
        $num /= 2;
        for ($i = 0 ; $i != $num ; $i++)
        {
            $values[] = new Point ($input[$i*2  ], $input[$i*2+1]);
        }
        return $values;
    }

    function read_input ()
    {
        // read controller input (blocking)
        $input = "";
        while (($in = fread(STDIN, 1)) !== false)
        {
            if ($in == "\0") break;
            $input .= $in;
        }

        // check extinction
        if ($input == "dead") return false;
        $lines = explode ("\n", $input);

        // save previous predators and preys positions
        Pack::$prev_preys = Pack::$preys;
        Pack::$prev_preds = Pack::$foe_preds;

        // line 0: turn, preys, predators
        list (self::$turn, Pack::$n_preys, Pack::$n_preds) = explode ("\t", $lines[0]);

        // line 1: list of ids and hunger levels
        $id = array();
        Pack::$size = 0;
        Pack::$output_order = array();
        foreach (Pack::read_line($lines[1]) as $i=>$v)
        {
            $id[$i] = $v->x;
            Pack::$output_order[] = $id[$i];

            if (!isset (Pack::$member[$id[$i]])) Pack::$member[$id[$i]] = static::new_member();
            Pack::$size++;
            Pack::$member[$id[$i]]->hunger = $v->y;
            Pack::$member[$id[$i]]->ttl = self::$turn;
        }

        // line 2: member positions
        Pack::$own_preds = array();
        foreach (Pack::read_line($lines[2]) as $i=>$pos)
        {
            Pack::$member[$id[$i]]->pos = $pos;
            Pack::$own_preds[] = $pos;
        }

        // lines 3 to 2*#members+3: coordinates of all visible preys and predators
        $preys = array();
        $preds = array();
        $y_seen = array();
        $d_seen = array();
        for ($i = 0 ; $i != Pack::$size ; $i++)
        {
            // visible preys
            foreach (Pack::read_line($lines[2*$i+3]) as $coords)
            {
                if (!in_array ($coords, $preys) || !isset($y_seen[(string)$coords]))
                {
                    $preys[] = $coords;
                }
            }
            foreach ($preys as $p) $y_seen[(string)$p] = true;

            // visible predators
            foreach (Pack::read_line($lines[2*$i+4]) as $coords)
            {
                if (!in_array ($coords, $preds) || !isset($d_seen[(string)$coords]))
                {
                    $preds[] = $coords;
                }
            }
            foreach ($preds as $p) $d_seen[(string)$p] = true;
        }

        // remove dead members
        foreach (Pack::$member as $k => $m)
        {
            if ($m->ttl != self::$turn)
            {
                unset (Pack::$member[$k]);
            }
        }

        // filter out own positions from predators list
        Pack::$foe_preds = array_diff ($preds, Pack::$own_preds);
        Pack::$preds = Pack::$foe_preds;
        foreach (Pack::$own_preds as $p) Pack::$preds[] = $p;
        Pack::$preys = $preys;

        // done
        return true;
    }

    function output_moves ()
    {
        $output = array();
        foreach (Pack::$output_order as $i)
        {
            $output[] = Pack::$member[$i]->move->x;
            $output[] = Pack::$member[$i]->move->y;
        }
        echo implode ("\t", $output) . "\0";
    }

    static function point_closest_to_walls ($pos)
    {
        $delta = $pos->vector_to (Pack::$arena_center);
        if (abs ($delta->x) > abs ($delta->y))
        {
            $y = $pos->y;
            $x = $delta->x > 0 ? -1 : ARENA_SIZE+1;
        }
        else
        {
            $x = $pos->x;
            $y = $delta->y > 0 ? -1 : ARENA_SIZE+1;
        }
        return new Point ($x, $y);
    }

    static function in_arena ($pos)
    {
        $delta = $pos->vector_to (Pack::$arena_center);
        return abs ($delta->x) <= ARENA_SIZE/2 && abs ($delta->y) <= ARENA_SIZE/2;
    }

    static function clamp_to_arena (&$pos)
    {
        // mimics the slightly strange behaviour of the Java engine setInZeroBounds function
        if ($pos->x >= ARENA_SIZE) $pos->x = ARENA_SIZE-1; // should rather be ARENA_SIZE
        if ($pos->x <           0) $pos->x = 0;
        if ($pos->y >= ARENA_SIZE) $pos->y = ARENA_SIZE-1;
        if ($pos->y <           0) $pos->y = 0;
    }

    function get_closest ($pos, $set, $max_dist)
    {
        // check for empty set
        if (count ($set) == 0) return null;

        // construct an array of distances with the same indexes as the points
        $dist = array();
        $max_dist *= $max_dist;
        foreach ($set as $k=>$pt)
        {
            $d = $pos->vector_to($pt)->norm2();
            if ($d <= $max_dist) $dist[$k] = $d;
        }
        if (count($dist) == 0) return false;

        // get the key of the smallest distance and use it to retrieve the closest point
        $keys = array_keys ($dist, min($dist));
        return $set[$keys[0]];
    }

    function get_visible ($pos, $set)
    {
        $res = array();
        $skipped = false;
        $pts = 0;
        foreach ($set as $point)
        {
            $d = $pos->vector_to($point)->norm2();
            if ($d == 0 && !$skipped)
            {
                $skipped = true;
                continue; // skip ourself
            }
            if ($d > PREY_VISION2) continue; // skip far points
            $res[] = $point;
            if ($pts++ > 10) break; // too many points are useless since prediction will go haywire anyway
        }
        return $res;
    }
}
Pack::init();

class PackMember {
    public $pos; // current position
    public $ttl; // last turn reported alive

    function move_to ($goal)
    {
        $this->move = $this->pos->vector_to ($goal);
    }

    function intercept ($target_pos, $target_speed)
    {
        // change reference to position difference
        $delta = $this->pos->vector_to($target_pos);
        $i = $delta->normalize();
        $j = $i->rotate90();

        // match tangential speeds
        $vj = $target_speed->dot ($j);

        // deduce axial speed
        $vi = PRED_SPEED2 - $vj*$vj; // this should always be positive since predators are faster than preys
        $vi = sqrt ($vi);

        // return intercept speed in original reference coordinates
        return $i->multiply($vi)->add($j->multiply($vj));
    }
}

class Target {
    public $pos;      // current position
    public $pos_next; // predicted position
    public $speed;    // estimated speed

    function __construct ($pos)
    {
        $this->pos    = $pos;
        $this->speed  = new Point(0,0);
        $this->predict();
    }

    private function predict()
    {
        // predators contribution
        $preds = Pack::get_visible ($this->pos, Pack::$preds);
        $this->preds = count ($preds);
        $res = new Point();
        foreach ($preds as $predator)
        {
            $res = $res->add ($predator->vector_to ($this->pos));
        }
        $res = $res->multiply (2);

        // preys contribution
        $preys = Pack::get_visible ($this->pos, Pack::$preys);
        $this->preys = count ($preys);

        $f_cohesion  = new Point;
        $f_separate  = new Point();
        foreach ($preys as $prey)
        {
            $delta = $this->pos->vector_to ($prey);
            $d2 = $delta->norm2();
            if ($d2 != 0)
            {
                $f_cohesion  = $f_cohesion ->add ($delta->multiply ($d2));
                $f_separate  = $f_separate ->add ($delta->multiply (-1/$d2));
            }
        }

        $res = $res
        ->add ($this->speed->normalize(5*.96)) // assume all preys have same speed as target
        ->add ($f_cohesion ->normalize(5*1))
        ->add ($f_separate ->normalize(5*1));
        $delta = $this->pos->vector_to(Pack::$arena_center);
        $dist = max (abs($delta->x), abs($delta->y));
        if ($dist > (ARENA_SIZE/2-WALL_BOUNCE))
        {
            $res = $res->add ($delta->normalize(5*4));
        }

        $this->raw_speed = $res;
        $this->speed = $res->limit(PREY_SPEED);
        $this->pos_next = $this->pos->add ($this->speed);
        Pack::clamp_to_arena ($this->pos_next);
    }

    function track ()
    {
        // see if we can find our prey at the start of a new turn
        $min = 1e10;
        foreach (Raptors::$free_preys as $k=>$prey)
        {
            $dist = abs ($this->pos_next->x - $prey->x) + abs ($this->pos_next->y - $prey->y);
            if ($dist < $min)
            {
                $min = $dist;
                $new_pos = $prey;
                $new_k = $k;
                if ($min < .001) break;
            }
        }
        if ($min > MAX_TRACK_ERROR) return false;

        // remove this prey from free preys
        unset(Raptors::$free_preys[$new_k]);

        $delta = $new_pos->vector_to($this->pos_next);

        // update postion and speed
        if ($this->speed->norm2() == 0)
        {
            // this can be either an endgame prey not yet moving
            // OR initial speed for a new target
            $this->speed = $this->pos->vector_to ($new_pos);
        }
        $this->pos = $new_pos;

        // predict speed and position
        $this->predict();
        return true;
    }
}

class Raptor extends PackMember {

    // possible states
    const IDLE     = 1;
    const TRACKING = 2;
    const HUNTING  = 3;
    const RUSHING  = 4;
    public $state;

    public  $target;  // current prey
    public  $patrol;  // patrol governor

    private static $id_gen;

    function __construct ()
    {
        $this->patrol = new Search (++self::$id_gen);
        $this->target  = null;
        $this->state = Raptor::IDLE;
        $this->pos = null;
        $this->hunger = HUNGER_MAX;
    }

    function __destruct ()
    {
        $this->tracking_lost();
    }

    function tracking_lost()
    {
        $this->target  = null;
        $this->state = Raptor::IDLE;
    }

    function track_prey()
    {
        // stop tracking if hunger went back to max
        if ($this->hunger == HUNGER_MAX)
        {
            $this->tracking_lost();
        }

        // try to acquire a new target
        if (!$this->target)
        {
            $victim = Pack::get_closest ($this->pos, Raptors::$free_preys, PRED_VISION);
            if (!$victim) return;
            $this->target = new Target ($victim);
            $this->state = Raptor::TRACKING;
        }

        // track prey
        if (!$this->target->track (Pack::$preys))
        {
            // prey was eaten or move prediction failed
            $this->tracking_lost();
        }
    }

    function beat_competition ()
    {
        if ($this->target === null) return;
        $pm = $this->target->pos_next->vector_to ($this->pos);
        $dm = $pm->norm2();
        foreach (Pack::$foe_preds as $f)
        {
            $pf = $this->target->pos_next->vector_to($f);
            $df = $pf->norm2();
            if ($df > PRED_VISION2) continue;
//          if ($df < ($dm*2))
            {
                $this->state = Raptor::RUSHING;
                return;
            }
        }
        if ($this->state == Raptor::RUSHING) $this->state = Raptor::TRACKING;
        return;
    }
}

class Raptors extends Pack {
    public static $free_preys; // coordinates of all preys that are not targeted

    // allows generic Pack to create a proper pack member instance
    static function new_member()
    {
        return new Raptor();
    }

    // main AI loop
    static function think ()
    {
        $hunger_limit = Pack::$n_preys > 2 * Pack::$n_preds ? TRACKING_HUNGER_START : TRACKING_HUNGER_END;
        self::$free_preys = static::$preys;

        // update targets and members states
        foreach (Pack::$member as $m)
        {
            // track current targets
            $m->track_prey();

            // rush to target if a competitor draws near
            $m->beat_competition();

            // hunt if hungry enough
            if ($m->state == Raptor::TRACKING && $m->hunger < $hunger_limit)
            {
                $m->state = Raptor::HUNTING;
            }
        }

        // move members
        foreach (Pack::$member as $m)
        {
            switch ($m->state)
            {
            case Raptor::IDLE:
                $destination = $m->patrol->point($m->pos);
                break;
            case Raptor::TRACKING:
                $wall_point = Pack::point_closest_to_walls ($m->target->pos_next);
                $destination = $wall_point->vector_to ($m->target->pos_next)->normalize (TRACKING_DISTANCE)->add($m->target->pos_next);
                break;
            case Raptor::HUNTING:
                $wall_point = Pack::point_closest_to_walls ($m->target->pos_next);
                $to_hunter = $m->target->pos_next->vector_to ($m->pos);
                $dist_to_target = $to_hunter->norm();

                if ($dist_to_target > (PREY_VISION-PREY_SPEED)) // intercept the prey
                {
                    // use actual speed (i.e. true position delta, including wall stops)
                    $target_true_speed = $m->target->pos->vector_to ($m->target->pos_next);
                    $intercept_speed = $m->intercept ($m->target->pos, $target_true_speed);
                    $destination = $m->pos->add ($intercept_speed);
                }
                else if ($dist_to_target < PRED_SPEED) // pounce on the prey!
                {
                    $destination = $m->target->pos_next;
                }
                else if ($to_hunter->dot($m->target->speed) > 0)
                {
                    $destination = $m->target->pos_next;
                }
                else // goad the prey
                {
                    $to_wall = $m->target->pos->vector_to ($wall_point);
                    $wall_point = $wall_point;
                    $raw_speed = $m->target->raw_speed->add($m->target->pos->vector_to($m->pos)->multiply(2))->multiply (-0.5);
                    $wpd_t = $m->target->pos->vector_to ($wall_point)->normalize()->rotate90(); // wpd = Wanted Prey Direction
                    $delta = $wpd_t->multiply ($raw_speed->dot ($wpd_t));
                    $destination = $delta->vector_to ($m->target->pos_next);
                    if (!Pack::in_arena ($destination)) $destination = $m->target->pos_next;
                }
                break;
            case Raptor::RUSHING:
                $destination = $m->target->pos_next;
                break;
            }
            $m->move_to ($destination);
        }
    }
}

while (Raptors::read_input())
{
    Raptors::think();
    Raptors::output_moves();
}
?>

General considerations

• It's the endgame that counts. You can have the smartest hunting algorithm ever, if you don't spot and catch the last few single preys quicker than the opposition, you lose.

• If your predators can't catch a prey alone (or at least in pairs), you're toast as soon as prey density drops low enough to rely either on blind luck or blocking preys to corners.

• A prey movement predictor is basically mandatory. I can't imagine beating a predictor-based program without having your own predictor.

Tail chase

The most inefficient way to catch a prey is to tail chase it. Assuming a single predator chasing a single prey and no external influences (walls, other preys, etc), a tail chase could last forever. As soon as you enter the prey vision radius of 30 units, the prey flees as speed 6 for your 6.1, so you gain .1 distance per turn: in a straight line, you'll need about 300 turns to get it.

Taking the arena size into account, a prey will travel at most the diagonal of a 500 units square before hitting a wall or a corner, which will take at most 117 turns.

The winning strategy is obviously to find a way to slow down the preys, namely by having either another predator or a wall/corner in front of it.

Predictor

With a prey speed of 6, a prey can move to an area of 36*pi units squared. With a catching radius of 1, a blind guess as to where the prey will be next has a 1/36*pi (about 1%) chance to succeed. Clearly something has to be done to enhance that!

Looking at the simulation engine code, you can see that the inputs are:

• visible prey and predator positions
• previous prey speeds

While all positions are available, previous prey speeds are not. The only way to compute these speeds would be to track every single prey from one turn to the next, which is nigh impossible to do (unless you implement a very smart motion tracking algorithm). So a predictor can easily reproduce all terms of the computation, except for the speed contribution that has to be guessed.

In the case of a single prey, the speed can be tracked without too much problems, which allows to build a "perfect" predictor to catch a prey isolated from the flock. Which is basically all you need for the endgame, when preys are too few to interact with each other. When preys are plentiful and flock effect is strong enough to fool the predictor, the sheer density of preys will compensate for the errors (if you don't catch the one you were aiming for, chances are you'll get one of its nearest buddies).

Goading preys

With the exact knowledge of prey speed computation, it is possible to "steer" a given prey toward a desired direction, by adjusting a predator's position.

This allows to pin a prey against a wall, or direct it toward another pack member. I tried some refined strategies, like pinching a prey between two pack members. Unfortunately, this proved less efficient than the current "pin and scan" routine, since keeping two predators busy to chase a single prey leaves the opposition with too many predators free to scout the pasture.

Stealing preys

One characteristic of preys behavior is that the influence of a predator increases proportionally to its distance from the prey (provided it remains within the prey vision radius). The closest a predator comes to a prey, the least the prey will steer away from it.

It means that when two predators compete to catch a prey, the closest is bound to get it first. Even a super smart contender that would manage to position itself right in front of the chaser/prey axis would basically scare the prey into the jaws of the contender.

To manage to steal a prey, at least a pair of predators are needed. One will go for the kill, and the other(s) will remain just within the prey vision radius, as far form the prey as possible to maximize influence and goad the prey toward the hunter.

Besides, every change of direction will allow the competition to cut the corner toward the prey, and keeping behind the contender is only possible if the "goader" was close enough to the prey at the beginning of the action.

So prey stealing has only a chance to succeed if the initial positions of the "stealers" are favorable and you can spare at least a second predator. In my experience, this is not worth the complexity.

Suggested changes

To allow for more complex strategies, moving the predator above prey top speed could have a cost in hunger points, proportional to speed excess. Say for instance moving up to speed 6 is free and every speed point above 6 costs 100 hunger points (going to 6.3 costs 30 hunger points per turn, burning 1000 hunger points would allow to reach speed 16 for one turn - and die if you don't catch a prey doing so!).

Instead of giving the kill to a random predator when more than one are close enough to eat a prey, I suggest dividing the gain (for instance 3 predators would get 333.33 hunger points each). This would allow for more intrersting endgame strategies (shadowing an enemy predator would become useful if you reckon you have more hunger points, for instance).

The special color for first pack is rather difficult to see. I suggest cyan or orange instead of blue.

Answer 8

Lazy Pack Haskell

import Control.Monad
import Control.Concurrent

main :: IO ()
main=do
    t<-forkIO $ forever $ (putStrLn "Pack is paralyzed with indecision.\0")
    loop
    killThread t
        where
            loop=do
                line <- getLine
                case line of
                    "dead\0" -> return ()
                    _        -> loop

You will need the haskell platform to run this. Then you use the runhaskell command to run it. My pack waits for the prey to come to them.

Answer 9

Not an entry, I'm always interested in adding customized color for each participating entry in king-of-the-hill ;)

And also the eating process is not visualized by changing the color, but changing the size instead, so that we can see multiple eating events in short time.

Game.java

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import javax.swing.JFrame;

public class Game {

    static int preyStartCount = 0; // 0 means 1500 + (packs * 50)
    static int turn;
    static boolean silent = false;
    long startTime;

    JFrame frame;
    BufferedImage img;
    Color[] colors;

    Island map;
    List<Prey> preys;
    List<Predator> predators;
    List<Pack> packs;
    List<Pack> initPacks;

    public static void main(String[] args) throws InterruptedException {

        Game game = new Game();
        game.init(args);
        if (game.packs.size() > 0){
            game.run();
            game.score();
        }
        game.end();
    }

    void end() {
        frame.setVisible(false);
        frame.dispose();
        for (Pack pack : packs)
            pack.handler.end();
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
        } finally {
            for (Pack pack : packs)
                pack.handler.shutdown();
        }

        System.exit(0);
    }

    void score() {
        Collections.sort(initPacks);
        int score = 100;
        initPacks.get(0).score = score;
        for (int i = 1; i < initPacks.size(); i++) {
            Pack pack = initPacks.get(i);
            if (pack.extinctionTurn < initPacks.get(i - 1).extinctionTurn)
                score = score < 1 ? score : score * 80 / 100;
            pack.score = score;
        }
        print("", true);
        print("Done in " + getElapsedTime(), true);
        for (Pack pack : initPacks)
            print(pack.toString() + "\t: Turn " + pack.extinctionTurn + "\t: Score " + pack.score, true);
    }

    String getElapsedTime(){
        double elapsed = (System.currentTimeMillis() - startTime) / 1000d;
        if(elapsed < 60)
            return String.format("%.2f", elapsed) + " seconds";
        elapsed /= 60;
        if(elapsed < 60)
            return String.format("%.2f", elapsed) + " minutes";
        elapsed /= 60;
        return String.format("%.2f", elapsed) + " hours";       
    }


    public Game() {
        initPacks = new ArrayList<Pack>();
        packs = new ArrayList<Pack>();
        preys = new ArrayList<Prey>();
        predators = new ArrayList<Predator>();
    }

    void run() throws InterruptedException {
        frame.setVisible(true);
        turn = 0;
        Graphics2D g = img.createGraphics();

        printStatus();
        while (true) {
            turn++;

            getAllMoves();
            moveAll();
            spawn();
            removeDead();
            shuffle();

            if (turn % 500 == 0)
                printStatus();
            paint(frame, g);
            Thread.sleep(5);
            if (packs.size() < 1)
                break;
        }
    }

    void getAllMoves(){
        for (Prey prey : preys)
            prey.setNextMove();
        for (Pack pack : packs){    
            pack.talk(preys.size(), predators.size(), turn);
        }
        while(true){
            int doneCount = 0;
            for(Pack pack : packs)
                if(pack.doneTalking)
                    doneCount++;
            if(doneCount >= packs.size())
                break;
            try {Thread.sleep(1);}catch(InterruptedException e){}
        }
    }

    void moveAll(){
        for (Creature prey : preys) 
            prey.move();
        for(Pack pack : packs){
            for (Predator predator : pack.members) {
                predator.move();
                predator.eatOrStarve();
            }
        }
    }

    void paint(JFrame frame, Graphics2D g){
        g.setPaint(Color.BLACK);
        g.fillRect(0, 0, img.getWidth(), img.getHeight());

        for(Prey prey : preys)
            prey.paint(g);
        for(Pack pack : packs)
            for(Predator predator : pack.members)
                predator.paint(g);

        frame.repaint();
    }

    List<Prey> deadPreys;
    List<Predator> deadPredators;
    List<Pack> deadPacks;

    void removeDead(){
        deadPreys.clear();
        for (Prey prey : preys)
            if (!prey.alive)
                deadPreys.add(prey);
        preys.removeAll(deadPreys);

        deadPredators.clear();
        for (Predator predator : predators)
            if (!predator.alive)
                deadPredators.add(predator);
        predators.removeAll(deadPredators);

        deadPacks.clear();
        for (Pack pack : packs)
            if (!pack.alive)
                deadPacks.add(pack);
        packs.removeAll(deadPacks);

        for (Pack pack : packs) {
            pack.members.removeAll(deadPredators);
        }

        map.rebuildLists(preys, predators);
    }

    void shuffle(){
        Collections.shuffle(packs);
        for(Pack pack : packs)
            Collections.shuffle(pack.members);
    }

    void spawn(){
        if(turn % 5000 == 0)
            addPredators(1);
        if(turn % 1000 == 0)
            populatePrey(predators.size()-1, false);
    }

    void addPredators(int count){
        for(Pack pack : packs){
            if(!pack.alive)
                continue;
            if(pack.aliveCount == 0)
                continue;
            Predator parent = null;
            for(Predator predator : pack.members)
                if(predator.alive)
                    parent = predator;
            if(parent != null){
                for(int i=0;i<count;i++){
                    XY pos = new XY(Math.random() * 30, Math.random()   * 30);
                    pos.add(parent.pos);
                    pos.setInZeroBounds(Island.SIZE, Island.SIZE);
                    Predator child = new Predator(pack);
                    child.color = colors[pack.id];
                    child.moveTo(pos, Island.getCellByPosition(pos));
                    predators.add(child);
                    pack.members.add(child);
                    pack.aliveCount++;
                }
            }
        }
    }

    Color[] generateColors(int n){
        Color[] result = new Color[n];
        double maxR = -1000;
        double minR = 1000;
        double maxG = -1000;
        double minG = 1000;
        double maxB = -1000;
        double minB = 1000;
        double[][] colors = new double[n][3];
        for(int i=0; i<n; i++){
            double cos = Math.cos(i * 2 * Math.PI / n);
            double sin = Math.sin(i * 2 * Math.PI / n);
            double bright = 1;
            colors[i][0] = bright + sin/0.88;
            colors[i][1] = bright - 0.38*cos - 0.58*sin;
            colors[i][2] = bright + cos/0.49;
            maxR = Math.max(maxR, colors[i][0]);
            minR = Math.min(minR, colors[i][0]);
            maxG = Math.max(maxG, colors[i][1]);
            minG = Math.min(minG, colors[i][1]);
            maxB = Math.max(maxB, colors[i][2]);
            minB = Math.min(minB, colors[i][2]);
        }
        double scaleR = 255/(maxR-minR);
        double scaleG = 255/(maxG-minG);
        double scaleB = 255/(maxB-minB);
        for(int i=0; i<n; i++){
            int R = (int)Math.round(scaleR*(colors[i][0]-minR));
            int G = (int)Math.round(scaleG*(colors[i][1]-minG));
            int B = (int)Math.round(scaleB*(colors[i][2]-minB));
            result[i] = new Color(R,G,B);
        }
        return result;
    }

    void populatePredators(String[] args) {
        int start = 0;
        if(args[0].equals("-silent")){
            silent = true;
            start = 1;
        }

        colors = generateColors(args.length-start);
        if(colors.length==1){
            colors[0] = Color.BLUE;
        }

        for (int i = start; i < args.length; i++) {
            Pack pack = new Pack(args[i]);
            if (pack.handler.init()) {
                packs.add(pack);
                initPacks.add(pack);
            }
        }
        Collections.shuffle(packs);
        XY[] positions = map.getPackStartLocations(packs.size());
        XY offset = new XY(-15, -15);
        for(int i=0;i<packs.size();i++){
            Pack pack = packs.get(i);
            for (Predator predator : pack.members) {
                predator.color = colors[pack.id];
                XY pos = new XY(Math.random() * 30, Math.random()   * 30);
                pos.add(positions[i]);
                pos.add(offset);
                pos.setInZeroBounds(Island.SIZE, Island.SIZE);
                predator.moveTo(pos, Island.getCellByPosition(pos));
                predators.add(predator);
            }
        }
        deadPredators = new ArrayList<Predator>(predators.size());
        deadPacks = new ArrayList<Pack>(packs.size());
    }

    void populatePrey(int count, boolean center) {
        XY pos = new XY();
        for (int i = 0; i < count; i++) {
            Prey prey = new Prey();
            if(center){
                pos.x = Math.random() * 100 + 200;
                pos.y = Math.random() * 100 + 200;
            } else {
                pos.x = Math.random() * 500;
                pos.y = Math.random() * 500;
            }

            prey.moveTo(pos, Island.getCellByPosition(pos));
            preys.add(prey);
        }
        deadPreys = new ArrayList<Prey>(preys.size());
    }

    static void print(String txt){
        print(txt, false);
    }

    static void print(String txt, boolean override){
        if(!silent || override)
            System.out.println(txt);
    }

    void printStatus(){
        print("Turn " + turn + " : Prey " + preys.size()
                + " : Predators " + predators.size() + " (" + getElapsedTime() + " elapsed)");
    }

    @SuppressWarnings("serial")
    void init(String[] args) {
        startTime = System.currentTimeMillis();
        map = new Island();
        populatePredators(args);
        if (preyStartCount == 0)
            preyStartCount = 1500 + (packs.size() * 50);

        populatePrey(preyStartCount, true);
        map.rebuildLists(preys, predators);
        img = new BufferedImage(Island.SIZE, Island.SIZE, 1);
        frame = new JFrame() {
            @Override
            public void paint(Graphics g) {
                g.drawImage(img, 32, 32, null);
            }
        };
        frame.setSize(Island.SIZE+64, Island.SIZE+64);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        Runtime.getRuntime().addShutdownHook(new Thread() {
            @Override
            public void run() {
                for (Pack pack : packs)
                    pack.handler.end();
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                } finally {
                    for (Pack pack : packs)
                        pack.handler.shutdown();
                }
            }
        });
    }
}

Predator.java

import java.awt.Graphics2D;


public class Predator extends Creature {

    static int count = 0;

    int id;
    int hunger;
    Pack pack;

    public Prey eatOrStarve() {
        for (Prey prey : preys) {
            if (prey.alive && pos.isCloserThan(prey.pos, eatDist)) {
                prey.die();
                hunger = MAX_HUNGER;
                return prey;
            }
        }
        if (hunger-- < 1)
            die();
        return null;
    }

    @Override
    public void die() {
        super.die();
        pack.aliveCount--;
        Game.print(pack.toString() + " starved! " + pack.aliveCount + " members remaining.");
    }

    @Override
    void paint(Graphics2D g){
        g.setPaint(color);
        int size = ((hunger + 10) > MAX_HUNGER && Game.turn > 10) ? 3+(int)Math.pow((hunger+10-MAX_HUNGER)/4,3) : 3;
        g.drawOval((int)pos.x - 1, (int)pos.y - 1, size, size);
        g.fillOval((int)pos.x - 1, (int)pos.y - 1, size, size);
    }

    Predator(Pack pack) {
        super();
        id = count++;
        this.pack = pack;
        MAX_SPEED = 6.1;
        VISIBLE = 50;
        hunger = MAX_HUNGER;
    }

    final double eatDist = 1;
    final static int MAX_HUNGER = 1000;
}