Hüte deine Dose mit deinem Leben!

10

Lass uns Kick The Can spielen!

Obwohl Moogie der aktuelle Gewinner ist, wird jeder dazu ermutigt, wenn er seine Krone nehmen kann

Kick the Can ist ein Kinderspiel. Beteiligung eines Verteidigers und mehrerer Angreifer. Heute ist es kein solches Spiel mehr! Ihre Aufgabe ist es, einen Bot zu schreiben, der ihn spielt, um den Stil zu gewinnen!

https://en.wikipedia.org/wiki/Kick_the_can

Es gibt einige wesentliche Unterschiede in diesem Spiel. Der erste wesentliche Unterschied besteht darin, dass das Spiel im Mehrspielermodus (5 gegen 5) gespielt wird. Der zweite entscheidende Unterschied besteht darin, dass beide Bots feindliche Spieler mit Minen und geworfenen Bomben töten und eliminieren können! Bots können keine Minen (unabhängig von der Entfernung) oder Spieler in mehr als fünf Blocks Entfernung sehen!

Die Karte ist wie folgt ein Labyrinth.

Matze

Dieses Labyrinth wird prozedural erzeugt, indem zuerst ein Labyrinth unter Verwendung eines tiefenrekursiven Rückverfolgungsalgorithmus erstellt wird. Und dann platzieren Sie die gezeigten Löcher in (und machen das Labyrinth "unvollkommener". Das Labyrinth ist 65x65 Blöcke breit und null indiziert. Somit ist die blaue Flagge (Dose) bei 1,1 und die rote Flagge (Dose) ist bei 63,63. Blaues Team spawnt bei 2,2 und 3,3 4,4 usw. Rotes Team spawnt bei 62,62 und 61,61, 60,60 usw. Die Blöcke in Cyan sind Bots im blauen Team und Die Blöcke in Magenta sind rote Bots. Das Spiel ist immer fünf gegen fünf. Jeder Bot im Team verwendet Ihren Code (kann jedoch andere Instanzvariablen speichern (oder lokale Dateien erstellen), um den Status zu verfolgen und Rollen zu unterscheiden.


Spielweise

Minen können platziert werden, wie Sie in grau sehen können. Und Bomben können mit einer maximalen Entfernung von bis zu vier Blöcken geworfen werden. Diese reisen bis zu vier Blocks durch Wände und andere Spieler töten nur die Feinde, die Ihnen im Weg stehen. Nach jedem Schritt haben sie eine 40% ige Chance, wegzufallen. Sie haben also eine 100% ige Chance auf 1 Reichweite 60% bei 2 Reichweite 36% bei 3 Reichweite und 21,6% bei drei Reichweite Das Platzieren einer Mine oder das Werfen einer Bombe erfordert eine Teammunition. Dies beginnt bei 0 und kann durch Sammeln der orangefarbenen Kästchen erhöht werden. Beachten Sie, dass vier (4) dieser Munitionscaches bequem zentriert werden. Die Bots sind in einer Reihe von zwei roten und zwei blauen angeordnet. IE RRRRRBBBBB. Das Gaurding der Flagge ist erlaubt, aber beachten Sie, dass die Nähe zur Flagge (dh weniger als fünf Blöcke) zu Langsamkeit führt und nur Bewegung zulässt. alle drei Umdrehungen. Die Arena wählt für jede Runde einen zufälligen Starter. ICH.

Zielsetzung

Programmieren Sie Ihre fünf Bots (jeder hat dieselbe Klassendatei), um erfolgreich durch das Labyrinth zu navigieren und die gegnerische Dose zu berühren, während Sie darauf achten, nicht versehentlich die eigene Dose umzuwerfen oder auf eine Mine zu treten.

Programmierung

Die Arena- und Bot-Einträge befinden sich derzeit in Java. Für andere Sprachen ist jedoch ein Standard- / Out-Wrapper vorhanden.

Der Arena-Code wird zur Verfügung gestellt, aber hier sind die relevanten Details.

Bot Klasse

public class YourUniqueBotName extends Bot{
public YourUniqueBotName(int x , int y, int team){
super(x,y,team);
//optional code
}
public Move move(){//todo implement this method 
//it should output  a Move();
//A move has two paramaters
//direction is from 0 - 3 as such
//         3
//       2-I-0
//         1
// a direction of 4 or higher means a no-op (i.e stay still)
//And a MoveType. This movetype can be    
//MoveType.Throw
//MoveType.Mine
//MoveType.Defuse defuse any mine present in the direction given
//MoveType.Move
}
}

Wichtige Methoden verfügbar

Beachten Sie, dass die Verwendung von Techniken zum Ändern oder Zugreifen auf Daten, auf die Sie im Allgemeinen keinen Zugriff haben sollten, nicht zulässig ist und zur Disqualifikation führt.

Arena.getAmmo()[team];//returns the shared ammo cache of your team

Arena.getMap();//returns an integer[] representing the map. Be careful since all enemies more than 5 blocks away (straight line distance) and all mines are replaced with constant for spaces
//constants for each block type are provided such as Bot.space Bot.wall Bot.mine Bot.redTeam Bot.blueTeam Bot.redFlag Bot.blueFlag

Arena.getAliveBots();//returns the number of bots left

getX();//returns a zero indexed x coordinate you may directly look at (but not change X)

getY();//returns a zero indexed y coordinate (y would work to, but do not change y's value)

//Although some state variables are public please do not cheat by accessing modifying these

StdIn / Out-Wrapper-Schnittstellenspezifikation

Die Schnittstelle besteht aus zwei Modi: Initialisierung und Ausführung.

Während des Initialisierungsmodus wird ein einzelner INIT-Frame über stdout gesendet. Die Spezifikation dieses Rahmens lautet wie folgt:

INIT
{Team Membership Id}
{Game Map}
TINI

Wobei: {Team Membership Id} ein einzelnes Zeichen ist: R oder B. B bedeutet blaues Team, R bedeutet rotes Team.

{Game Map} ist eine Reihe von Reihen von ASCII-Zeichen, die eine Reihe der Karte darstellen. Die folgenden ASCII-Zeichen sind gültig: F = blaue Flagge G = rote Flagge O = offener Raum W = Wand

Das Spiel sendet dann Spielframes über stdout an jeden Bot wie folgt:

FRAME
{Ammo}
{Alive Bot Count}
{Bot X},{Bot Y}
{Local Map}
EMARF

Wo:

{Munition} ist eine Ziffernfolge, der Wert ist 0 oder höher. {Alive Bot Count} ist eine Ziffernfolge, der Wert ist 0 oder höher. {Box X} ist eine Ziffernfolge, die die X-Koordinate des Bots darstellt auf der Spielkarte. Der Wert ist 0 <= X <Kartenbreite. {Box Y} ist eine Ziffernfolge, die die Y-Koordinate des Bots auf der Spielkarte darstellt. Der Wert ist 0 <= Y <Kartenhöhe. {Local Map} ist eine Reihe von Reihen von ASCII-Zeichen, die die gesamte Karte darstellen, die den Bot umgibt. Die folgenden ASCII-Zeichen sind gültig: F = blaue Flagge G = rote Flagge O = offener Raum W = Wand R = roter Teambot B = blauer Teambot M = meine A = Munition

Der Controller erwartet, dass Ihr Bot dann eine einzeilige Antwort im folgenden Format ausgibt (an stdout):

{Action},{Direction}

Wo:

{Action} ist eine von: Move Defuse Mine Throw

{Richtung} ist eine einzelne Ziffer zwischen 0 und 4 einschließlich. (siehe Richtungsangaben früher)

HINWEIS: Alle Zeichenfolgen werden durch das Zeichen \ n Zeilenende begrenzt.

Dies wird ein Ausscheidungsturnier sein. Meine Sample-Bots werden als Füllstoffe teilnehmen, aber ich werde mir den Gewinn nicht selbst vergeben. Im Falle eines Sieges durch einen meiner Bots geht der Titel an das zweitplatzierte Mitglied und wird fortgesetzt, bis es einen Bot gibt, der nicht einer von mir ist. Jedes Match besteht aus 11 Kick-the-Can-Runden. Wenn keine der beiden Mannschaften ein einziges Spiel gewonnen hat, werden beide eliminiert. Bei einem Unentschieden ungleich Null wird ein Unentschieden gespielt. Bleibt ein Unentschieden bestehen, werden beide eliminiert. Spätere Runden können aus mehr Spielen bestehen. Die Aussaat des Turniers basiert auf der Anzahl der Upvotes zum 31.7.16 (Änderungen vorbehalten).

Jedes Match dauert 4096 Runden. Ein Sieg gewährt einen Punkt. Ein Unentschieden oder Verlust gewährt null Punkte. Viel Glück!

Schauen Sie sich den Code an oder kritisieren Sie ihn in diesem GitHub Repo.

https://github.com/rjhunjhunwala/BotCTF/blob/master/src/botctf/Arena.java


Beachten Sie, dass ich auf meinem Computer keine Dolmetscher für zu viele Sprachen habe und möglicherweise Freiwillige benötige, um die Simulation auf ihrem Computer auszuführen. Oder ich kann den Sprachdolmetscher herunterladen. Bitte stellen Sie sicher, dass Ihre Bots.

  • Antworten Sie in angemessener Zeit (z. B. 250 ms).
  • Beschädigt meinen Host-Computer nicht
Rohan Jhunjhunwala
quelle
@ Moogie Ich habe beschlossen, dies zu veröffentlichen
Rohan Jhunjhunwala
Was wird auf der lokalen Karte für Kacheln angezeigt, die außerhalb der Sicht der Bots liegen?
halb
Es zeigt die Karte. Das einzige ist, dass Sie die Bots in größerer Entfernung nicht sehen können. Ihre Bots erhalten eine aktuelle Karte der Arena, aber möglicherweise nicht dort, wo sich heimliche Gegner verstecken. @justhalf
Rohan Jhunjhunwala
@ Moogie, ich habe mich gefragt, ob Sie einen Python-Bot für mich schreiben könnten, damit ich den stdin / stdout-Wrapper testen kann
Rohan Jhunjhunwala
Die Karte jenseits der Bots-Vision wird also nur als leerer Raum angezeigt, oder?
halb

Antworten:

4

NavPointBot, Java 8

Geben Sie hier die Bildbeschreibung ein Bot ist weiß / blau

Dieser Bot ernennt aus jedem Frame einen Anführer aus befreundeten Bots, der dann jedem Bot Navigationspunkte zuweist, zu denen er navigieren kann.

Zunächst sind alle Bots im Munitionsdepot, dann werden zwei Bots als Wachen eingesetzt, der Rest sucht nach Munition und greift dann die feindliche Flagge an.

Ich habe festgestellt, dass das Spiel sehr stark vom Startort der Depots abhängt. Als solches kann ich nicht wirklich sagen, dass dieser Bot besser ist als alle anderen.

Laufen Sie mit java NavPointBot

import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.UUID;

public final class NavPointBot implements Serializable 
{
    private static final int[][] offsets = new int[][]{{-1,0},{0,-1},{1,0},{0,1}};
    private static final List<int[]> navPointsBlue = Arrays.asList(new int[][]{{1,2},{2,1}});
    private static final List<int[]> navPointsRed = Arrays.asList(new int[][]{{63,62},{62,63}});
    transient private static int mapWidth=0;
    transient private static int mapHeight=0;
    transient private char[][] map;
    transient private char team;
    transient private int ammo;
    transient private int botsAlive;
    transient private int enemyFlagX;
    transient private int enemyFlagY;
    private int frameCount;
    private int botX;
    private int botY;
    private String id;
    private int navPointX;
    private int navPointY;

    transient static Object synchObject = new Object(); // used for file read/write synchronisation if multiple instances are run in the same VM

    final static class Data implements Serializable
    {
        int frameCount;
        boolean[][] diffusedMap = new boolean[mapWidth][mapHeight];
        Map<String,NavPointBot> teamMembers = new HashMap<>();
    }

    interface DistanceWeigher
    {
        double applyWeight(NavPointBot p1Bot, PathSegment p1);
    }

    static class PathSegment
    {
        public PathSegment(int tileX, int tileY, int fscore, int gscore, PathSegment parent, int direction, int targetX, int targetY)
        {
            super();
            this.tileX = tileX;
            this.tileY = tileY;
            this.fscore = fscore;
            this.gscore = gscore;
            this.parent = parent;
            this.direction = direction;
            this.targetX = targetX;
            this.targetY = targetY;
        }
        public PathSegment(PathSegment parent)
        {
            this.parent = parent;
            this.targetX = parent.targetX;
            this.targetY = parent.targetY;
        }
        int tileX;
        int tileY;
        int fscore;
        int gscore;
        int direction;
        PathSegment parent; 
        int targetX;
        int targetY;
    }

    public static void main(String[] args) throws Exception
    {
        new NavPointBot(UUID.randomUUID().toString());
    }

    private NavPointBot(String id) throws Exception
    {
        this.id = id;
        System.err.println("NavPointBot ("+id+") STARTED");

        Data data;
        while(true)
        {
            String line=readLine(System.in);

            // decode initial frame
            if ("INIT".equals(line))
            {
                // read team membership
                team = readLine(System.in).charAt(0);

                // get the map
                line = readLine(System.in);

                List<char[]> mapLines = new ArrayList<>();
                while(!"TINI".equals(line))
                {
                    mapLines.add(line.toCharArray());
                    line = readLine(System.in);
                }
                map = mapLines.toArray(new char[][]{});
                mapHeight = map.length;
                mapWidth = map[0].length;

                out:
                for (int y = 0; y<mapHeight;y++)
                {
                    for (int x=0; x<mapWidth;x++)
                    {
                        if (map[y][x]==(team=='B'?'G':'F'))
                        {
                            enemyFlagX = x;
                            enemyFlagY = y;
                            break out;
                        }
                    }
                }
                data = readSharedData();
                data.diffusedMap=new boolean[mapWidth][mapHeight];
                writeSharedData(data);

            }
            else
            {
                System.err.println("Unknown command received: "+line);
                return;
            }

            line = readLine(System.in);
            while (true)
            {
                // decode frame
                if ("FRAME".equals(line))
                {
                    frameCount = Integer.parseInt(readLine(System.in));
                    ammo = Integer.parseInt(readLine(System.in));
                    botsAlive = Integer.parseInt(readLine(System.in));
                    line = readLine(System.in);
                    String[] splits = line.split(",");
                    botX = Integer.parseInt(splits[0]);
                    botY = Integer.parseInt(splits[1]);

                    // get the map
                    line = readLine(System.in);

                    int row=0;
                    while(!"EMARF".equals(line))
                    {
                        map[row++] = line.toCharArray();
                        line = readLine(System.in);
                    }
                }
                else
                {
                    System.err.println("Unknown command received: "+line);
                    return;
                }


                data = readSharedData();

                // this bot is nomitated to be the leader for this frame
                if (data.frameCount<frameCount || (frameCount==0 && data.frameCount > 3))
                {
                    data.frameCount=frameCount;

                    List<NavPointBot> unassignedBots = new ArrayList<>(data.teamMembers.values());

                    // default nav points to be enemy flag location.
                    unassignedBots.forEach(t->{t.navPointY=enemyFlagY;t.navPointX=enemyFlagX;});

                    // after 700 frames assume dead lock so just storm the flag, otherwise...
                    if (frameCount<700)
                    {
                        // if the after the initial rush then we will assign guard(s) while we have enemies
                        if (frameCount>70 && botsAlive > data.teamMembers.size())
                        {
                            Map<NavPointBot, PathSegment> navPointDistances = assignBotShortestPaths(unassignedBots,team=='B'?navPointsBlue:navPointsRed,true, new DistanceWeigher() {

                                @Override
                                public double applyWeight( NavPointBot owner ,PathSegment target) {
                                    return target.gscore;
                                }
                            });
                            navPointDistances.keySet().forEach(s->{s.navPointX=navPointDistances.get(s).targetX;s.navPointY=navPointDistances.get(s).targetY;});
                        }


                        // the remaining bots will go to ammo depots with a preference to the middle ammo depots
                        List<int[]> ammoDepots = new ArrayList<>();
                        for (int y = 0; y<mapHeight;y++)
                        {
                            for (int x=0; x<mapWidth;x++)
                            {
                                if (map[y][x]=='A')
                                {
                                    ammoDepots.add(new int[]{x,y});
                                }
                            }
                        }

                        System.err.println("ammoDepots: "+ammoDepots.size());
                        if (ammoDepots.size()>0)
                        {
                            Map<NavPointBot, PathSegment> ammoDistances = assignBotShortestPaths(unassignedBots,ammoDepots,true, new DistanceWeigher() {

                                @Override
                                public double applyWeight( NavPointBot owner ,PathSegment target) {
                                    return target.gscore + (Math.abs(target.targetX-mapWidth/2)+Math.abs(target.targetY-mapHeight/2)*10);
                                }
                            });


                            // assign ammo depot nav points to closest bots
                            ammoDistances.keySet().forEach(s->{s.navPointX=ammoDistances.get(s).targetX;s.navPointY=ammoDistances.get(s).targetY;});
                        }
                    }

                    System.err.println("FRAME: "+frameCount+" SET");
                    data.teamMembers.values().forEach(bot->System.err.println(bot.id+" nav point ("+bot.navPointX+","+bot.navPointY+")"));
                    System.err.println();
                }


                // check to see if enemies are in range, if so attack the closest
                List<int[]> enemies = new ArrayList<>();
                for (int y = 0; y<mapHeight;y++)
                {
                    for (int x=0; x<mapWidth;x++)
                    {
                        if (map[y][x]==(team=='B'?'R':'B'))
                        {
                            int attackDir = -1;
                            int distance = -1;
                            if (x==botX && Math.abs(y-botY) < 4) { distance =  Math.abs(y-botY); attackDir = botY-y<0?1:3;}
                            if (y==botY && Math.abs(x-botX) < 4) { distance =  Math.abs(x-botX); attackDir = botX-x<0?0:2;}
                            if (attackDir>-1)
                            {
                                enemies.add(new int[]{x,y,distance,attackDir});
                            }
                        }
                    }
                }

                enemies.sort(new Comparator<int[]>() {

                    @Override
                    public int compare(int[] arg0, int[] arg1) {
                        return arg0[2]-arg1[2];
                    }
                });

                String action;

                // attack enemy if one within range...
                if (enemies.size()>0)
                {
                    action = "Throw,"+enemies.get(0)[3];
                }
                else
                {
                    // set action to move to navpoint
                    PathSegment pathSegment = pathFind(botX,botY,navPointX,navPointY,map,true);
                    action = "Move,"+pathSegment.direction;

                    // clear mines if within 5 spaces of enemy flag

                    if ((team=='B' && botX>=mapWidth-5 && botY>=mapHeight-5 ) ||
                        (team=='R' && botX<5 && botY<5 ))
                    {
                        if (!data.diffusedMap[pathSegment.parent.tileX][pathSegment.parent.tileY])
                        {
                            action = "Defuse,"+pathSegment.direction;
                            data.diffusedMap[pathSegment.parent.tileX][pathSegment.parent.tileY]=true;
                        }
                    }

                }

                writeSharedData(data);
                System.out.println(action);
                line = readLine(System.in);
            }
        }
    }

    /**
     * assigns bots to paths to the given points based on distance to the points with weights adjusted by the given weigher implementation 
     */
    private Map<NavPointBot, PathSegment> assignBotShortestPaths(List<NavPointBot> bots, List<int[]> points, boolean exact, DistanceWeigher weigher) {

        Map<Integer,List<PathSegment>> pathMap = new HashMap<>();
        final Map<PathSegment,NavPointBot> pathOwnerMap = new HashMap<>();

        for (NavPointBot bot : bots)
        {
            for(int[] navPoint: points)
            {
                List<PathSegment> navPointPaths = pathMap.get((navPoint[0]<<8)+navPoint[1]);
                if (navPointPaths == null)
                {
                    navPointPaths = new ArrayList<>();
                    pathMap.put((navPoint[0]<<8)+navPoint[1],navPointPaths);
                }
                PathSegment path = pathFind(bot.botX,bot.botY,navPoint[0],navPoint[1],map,exact);
                pathOwnerMap.put(path, bot);
                navPointPaths.add(path);
            }
        }


        // assign bot nav point based on shortest distance
        Map<NavPointBot, PathSegment> results = new HashMap<>();
        for (int[] navPoint: points )
        {
            List<PathSegment> navPointPaths = pathMap.get((navPoint[0]<<8)+navPoint[1]);

            if (navPointPaths !=null)
            {
                Collections.sort(navPointPaths, new Comparator<PathSegment>() {

                    @Override
                    public int compare(PathSegment p1, PathSegment p2) {

                        NavPointBot p1Bot = pathOwnerMap.get(p1);
                        NavPointBot p2Bot = pathOwnerMap.get(p2);
                        double val = weigher.applyWeight(p1Bot, p1) - weigher.applyWeight(p2Bot, p2);
                        if (val == 0)
                        {

                            return p1Bot.id.compareTo(p2Bot.id);
                        }
                        return val<0?-1:1;
                    }
                });

                for (PathSegment shortestPath : navPointPaths)
                {
                    NavPointBot bot = pathOwnerMap.get(shortestPath);

                    if (!results.containsKey(bot) )
                    {
                        results.put(bot,shortestPath);
                        bots.remove(bot);
                        break;
                    }
                }
            }
        }
        return results;
    }

    /**
     * reads in the previous bot's view of teammates aka shared data
     */
    private Data readSharedData() throws Exception
    {
        synchronized(synchObject)
        {
            File dataFile = new File(this.getClass().getName()+"_"+team);

            Data data;
            if (dataFile.exists())
            {
                FileInputStream in = new FileInputStream(dataFile);
                try {
                    java.nio.channels.FileLock lock = in.getChannel().lock(0L, Long.MAX_VALUE, true);
                    try {
                        ObjectInputStream ois = new ObjectInputStream(in);
                        data = (Data) ois.readObject();
                    } catch(Exception e)
                    {
                        System.err.println(id+": CORRUPT shared Data... re-initialising");
                        data = new Data();
                    }
                    finally {
                        lock.release();
                    }
                } finally {
                    in.close();
                }
            }
            else
            {
                System.err.println(id+": No shared shared Data exists... initialising");
                data = new Data();
            }

            //purge any dead teammates...
            for (NavPointBot bot : new ArrayList<>(data.teamMembers.values()))
            {
                if (bot.frameCount < frameCount-3 || bot.frameCount > frameCount+3)
                {
                    data.teamMembers.remove(bot.id);
                }
            }

            // update our local goals to reflect those in the shared data
            NavPointBot dataBot = data.teamMembers.get(id);
            if (dataBot !=null)
            {
                this.navPointX=dataBot.navPointX;
                this.navPointY=dataBot.navPointY;
            }

            // ensure that we are a team member
            data.teamMembers.put(id, this);

            return data;
        }
    }

    private void writeSharedData(Data data) throws Exception
    {
        synchronized(synchObject)
        {
            File dataFile = new File(this.getClass().getName()+"_"+team);
            FileOutputStream out = new FileOutputStream(dataFile);

            try {
                java.nio.channels.FileLock lock = out.getChannel().lock(0L, Long.MAX_VALUE, false);
                try {
                    ObjectOutputStream oos = new ObjectOutputStream(out);
                    oos.writeObject(data);
                    oos.flush();
                } finally {
                    lock.release();
                }
            } finally {
                out.close();
            }
        }
    }

    /**
     * return the direction to move to travel for the shortest route to the desired target location
     */
    private PathSegment pathFind(int startX, int startY, int targetX,int targetY,char[][] map,boolean exact)
    {
        // A*
        if (startX==targetX && startY==targetY)
        {
            return new PathSegment(targetX,targetY,0, 0,null,4,targetX,targetY);//PathSegment.DEFAULT;
        }
        else
        {
            int[][] tileIsClosed = new int[mapWidth][mapHeight];

            // find an open space in the general vicinity if exact match not required
            if (!exact)
            {
                out:
                for (int y=-1;y<=1;y++)
                {
                    for (int x=-1;x<=1;x++)
                    {
                        if (startX == targetX+x && startY==targetY+y)
                        {
                            return new PathSegment(targetX,targetY,0, 0,null,4,targetX,targetY);//PathSegment.DEFAULT;
                        }
                        else if (targetY+y>=0 && targetY+y<mapHeight && targetX+x>=0 && targetX+x < mapWidth && map[targetY+y][targetX+x]=='O')
                        {
                            targetX+=x;
                            targetY+=y;
                            break out;
                        }
                    }
                }
            }

            PathSegment curSegment = new PathSegment(targetX,targetY,1,1,null,4,targetX,targetY);
            PathSegment newSegment;
            Set<PathSegment> openList = new HashSet<PathSegment>();
            openList.add(curSegment);

            do
            {
                if (openList.isEmpty())
                {
                    break;
                }
              PathSegment currentBestScoringSegment = openList.iterator().next();
              //  Look for the lowest F cost square on the open list
              for (PathSegment segment : openList)
              {
                if (segment.fscore<currentBestScoringSegment.fscore)
                {
                  currentBestScoringSegment = segment;
                }
              }
              curSegment = currentBestScoringSegment;

              // found path
              if (startX==curSegment.tileX && startY==curSegment.tileY)
              {
                break;
              }

              // if not in closed list
              if (tileIsClosed[curSegment.tileX][curSegment.tileY]==0)
              {
                    // Switch it to the closed list.
                    tileIsClosed[curSegment.tileX][curSegment.tileY]=1;
                    // remove from openlist
                    openList.remove(curSegment);


                    // add neigbours to the open list if necessary
                    for (int i=0;i<4;i++)
                    {

                        int surroundingCurrentTileX=curSegment.tileX+offsets[i][0];
                        int surroundingCurrentTileY=curSegment.tileY+offsets[i][1];
                        if (surroundingCurrentTileX>=0 && surroundingCurrentTileX<mapWidth &&
                            surroundingCurrentTileY>=0 && surroundingCurrentTileY<mapHeight )
                        {
                            newSegment = new PathSegment( curSegment);
                            newSegment.tileX = surroundingCurrentTileX;
                            newSegment.tileY = surroundingCurrentTileY;
                            newSegment.direction = i;

                            switch(map[surroundingCurrentTileY][surroundingCurrentTileX])
                            {
                                case 'W':
                                case 'F':
                                case 'G':
                                    continue;
                            }

                          int surroundingCurrentGscore=curSegment.gscore+1 + ((surroundingCurrentTileX!=startX && surroundingCurrentTileY!=startY && map[surroundingCurrentTileY][surroundingCurrentTileX]==team)?20:0);//+map[surroundingCurrentTileY][surroundingCurrentTileX]!='O'?100:0;
                          newSegment.gscore=surroundingCurrentGscore;
                          newSegment.fscore=surroundingCurrentGscore+Math.abs( surroundingCurrentTileX-startX)+Math.abs( surroundingCurrentTileY-startY);
                          openList.add(newSegment);
                        }
                    }
              }
              else
              {
                  // remove from openlist
                  openList.remove(curSegment);    
              }
            } while(true);

            return curSegment;
        }
     }

    /**
     * Reads a line of text from the input stream. Blocks until a new line character is read.
     * NOTE: This method should be used in favor of BufferedReader.readLine(...) as BufferedReader buffers data before performing
     * text line tokenization. This means that BufferedReader.readLine() will block until many game frames have been received. 
     * @param in a InputStream, nominally System.in
     * @return a line of text or null if end of stream.
     * @throws IOException
     */
    private static String readLine(InputStream in) throws IOException
    {
       StringBuilder sb = new StringBuilder();
       int readByte = in.read();
       while (readByte>-1 && readByte!= '\n')
       {
          sb.append((char) readByte);
          readByte = in.read();
       }
       return readByte==-1?null:sb.toString();

    }

}
Moogie
quelle
schöne Animation, nur aus Neugier Was ist der ungefähre Gewinnprozentsatz meines Bots?
Rohan Jhunjhunwala
Ich habe keine wirklichen Statistiken erstellt, aber ich würde 60% meines Bots gegenüber 40% Ihres Bots gefährden? hängt aber wirklich von der Platzierung der Munition ab
Moogie
Ok, gg auf den Sieg!
Rohan Jhunjhunwala
Sollte ich mehr Munition haben oder sollte ich die Munition so konfigurieren, dass sie gleichermaßen erscheint?
Rohan Jhunjhunwala
@RohanJhunjhunwala Ich denke, es ist das, was es ist, zu spät, um das Verhalten jetzt zu ändern. Verwenden Sie es als Lernerfahrung für die nächste gestellte Frage :)
Moogie
1

Optimierter Pathfinder JAVA

Vielen Dank an @Moogie für die Unterstützung bei der Optimierung meiner unordentlichen Pfadfindung für Überschwemmungen. Hier ist die Quelle für den Bot. Dieser Typ weiß, wie wichtig es ist, seine Flagge zu verteidigen. Er teilt drei Verteidiger und zwei Angreifer zu. Die Verteidiger lehnen sich zurück und verteidigen / sammeln Munition, die beiden Angreifer nehmen einen (ziemlich geraden) Weg zur Flagge (und sammeln die Munition in der Mitte). Er erschießt jeden, den er sieht, und sollte eine harte Konkurrenz sein. Die Verteidiger platzieren Minen um die Flagge und lagern, bis keine Opposition mehr vorhanden ist, damit sie die Dose treten können.

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 * todo fight
 */
package botctf;

import botctf.Move.MoveType;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 *
 * @author rohan
 */
public class PathFinderOptimised extends Bot {
    private static final int[][] offsets = new int[][]{{0,-1},{1,0},{0,1},{-1,0}};
    public static boolean shouldCampingTroll = true;
    private int moveCounter = -1;//dont ask
    public boolean defend;

    public PathFinderOptimised(int inX, int inY, int inTeam) {

        super(inX, inY, inTeam);
        //System.out.println("Start");
        //floodFillMap(getX(), getY());
        //System.out.println("Finish");
        defend=inX%2==0;
    }
    public static int[][] navigationMap;

    boolean upMine = false;
    boolean sideMine = false;

        int[][] myMap;

    @Override
    public Move move() {
                moveCounter++;
        myMap=getMap();
        int targetX, targetY;
        int enemyTeam=team==redTeam?blueTeam:redTeam;
        ArrayList<Coord> enemyCoordinates=new ArrayList<>();
        for(int i = 0; i<65;i++){
            for(int j = 0;j<65;j++){
                if(map[i][j]==enemyTeam){
                    enemyCoordinates.add(new Coord(i,j));
                }
            }
        }
        for(Coord enemy:enemyCoordinates){
            int enemyX=enemy.x;
            int enemyY=enemy.y;
         int dX= enemy.x-this.x;
            int dY= enemy.y-this.y;
            //System.out.println(dX+"|"+dY);
            if((dX==0||dY==0)){

                if(Arena.getAmmo()[this.team]>0){

                    if(dX>0&&dX<5){
                    return new Move(0,MoveType.Throw);
                }
                if(dX<0&&dX>-5){
                    return new Move(2,MoveType.Throw);
                }
                if (dY>0&&dY<5){
                    return new Move(1, MoveType.Throw);
                }
                if(dY<0&&dY>-5){
                    return new Move(3,MoveType.Throw);
                }
            }
        }
        }
        if(myMap[x+1][y]==ammo){
            return new Move(0,MoveType.Move);
        }
                if(myMap[x-1][y]==ammo){
            return new Move(2,MoveType.Move);
        }
                                if(myMap[x][y+1]==ammo){
            return new Move(1,MoveType.Move);
        }
                                                                if(myMap[x][y-1]==ammo){
            return new Move(3,MoveType.Move);
        }


int bestOption = 4;                                                             
        if (defend) {
if(Arena.getAliveBots()==1){
    defend=false;
}
            int bestAmmoX = -1;
            int bestAmmoY = -1;
            int bestAmmoDist = Integer.MAX_VALUE;
            for (int i = 0; i < 65; i++) {
                for (int j = 0; j < 65; j++) {
                    if (myMap[i][j] == ammo) {
                        int path = pathFind(getX(),getY(),i,j,myMap);
                        if ((path & 0xFFFFFF) < bestAmmoDist) {
                            bestAmmoX = i;
                            bestAmmoY = j;
                            bestAmmoDist = (path & 0xFFFFFF);
                            bestOption = path >> 24;
                        }
                    }
                }
            }
            if (bestAmmoDist<15||Arena.getAmmo()[this.team]==0){
                targetX = bestAmmoX;
                targetY = bestAmmoY;
            } else {
                targetX = team == redTeam ? 62 : 2;
                targetY = team == redTeam ? 62 : 2;
            }
        } else {

            if(this.x>18&this.x<42&&this.y>16&&this.y<44&&myMap[33][33]==ammo){
                targetX=33;
                targetY=33;
            }else{
            if (this.team == redTeam) {
                targetX = 1;
                targetY = 1;
            } else {
                targetX = 63;
                targetY = 63;
            }
            }
        }
        if(upMine&&sideMine){
            if(targetX==2||targetX==62){
                if(targetY==2||targetY==62){
                    targetX+=targetX==2?3:-3;
                    targetY+=targetY==2?3:-3;
                }
            }
        }else if (targetX == getX() && targetY == getY()) {
            if (!upMine) {
                upMine = true;
                if (this.team == redTeam) {
                    return new Move(0, MoveType.Mine);
                } else {
                    return new Move(2, MoveType.Mine);
                }
            }else if(!sideMine){
                sideMine=true;      
                if (this.team == redTeam) {
                    return new Move(1, MoveType.Mine);
                } else {
                    return new Move(3, MoveType.Mine);
                }
            }   else {
                return new Move(5, MoveType.Move);
            }
        }

        bestOption = pathFind(getX(),getY(),targetX,targetY,myMap) >> 24;


MoveType m=MoveType.Move;
if(moveCounter%2==0){
    if(this.team==redTeam?x<25&&y<25:x>39&&y>39){
        m=MoveType.Defuse;
    }
}
//System.out.println(bestOption);
        return new Move(bestOption, m);
    }

    /**
     * returns a result that is the combination of movement direction and length of a path found from the given start position to the target
     * position. result is ((direction) << 24 + path_length)
     */
    private int pathFind(int startX, int startY, int targetX,int targetY,int[][] map)
    {
        class PathSegment
        {
            public PathSegment(int tileX, int tileY, int fscore, int gscore, PathSegment parent)
            {
                super();
                this.tileX = tileX;
                this.tileY = tileY;
                this.fscore = fscore;
                this.gscore = gscore;
                this.parent = parent;
            }
            public PathSegment(PathSegment parent)
            {
                this.parent = parent;
            }
            int tileX;
            int tileY;
            int fscore;
            int gscore;
            PathSegment parent; 
        }
        // A*
        if (startX==targetX && startY==targetY)
        {
            return 4;
        }
        else
        {
            int[][] tileIsClosed = new int[64][64];

            PathSegment curSegment = new PathSegment(targetX,targetY,1,1,null);
            PathSegment newSegment;
            Set<PathSegment> openList = new HashSet<PathSegment>();
            openList.add(curSegment);

            do
            {
                if (openList.isEmpty())
                {
                    break;
                }
              PathSegment currentBestScoringSegment = openList.iterator().next();
              //  Look for the lowest F cost square on the open list
              for (PathSegment segment : openList)
              {
                if (segment.fscore<currentBestScoringSegment.fscore)
                {
                  currentBestScoringSegment = segment;
                }
              }
              curSegment = currentBestScoringSegment;

              // found path
              if (startX==curSegment.tileX && startY==curSegment.tileY)
              {
                break;
              }

              // if not in closed list
              if (tileIsClosed[curSegment.tileX][curSegment.tileY]==0)
              {
                    // Switch it to the closed list.
                    tileIsClosed[curSegment.tileX][curSegment.tileY]=1;
                    // remove from openlist
                    openList.remove(curSegment);


                    // add neigbours to the open list if necessary
                    for (int i=0;i<4;i++)
                    {
                        final int surroundingCurrentTileX=curSegment.tileX+offsets[i][0];
                        final int surroundingCurrentTileY=curSegment.tileY+offsets[i][1];
                        if (surroundingCurrentTileX>=0 && surroundingCurrentTileX<64 &&
                            surroundingCurrentTileY>=0 && surroundingCurrentTileY<64 )
                        {
                            newSegment = new PathSegment( curSegment);
                            newSegment.tileX = surroundingCurrentTileX;
                            newSegment.tileY = surroundingCurrentTileY;

                          if (map[surroundingCurrentTileX][surroundingCurrentTileY]=='W')
                          {
                              continue;
                          }

                          int surroundingCurrentGscore=curSegment.gscore+1;
                          newSegment.gscore=surroundingCurrentGscore;
                          newSegment.fscore=surroundingCurrentGscore+Math.abs( surroundingCurrentTileX-startX)+Math.abs( surroundingCurrentTileY-startY);
                          openList.add(newSegment);
                        }
                    }
              }
              else
              {
                  // remove from openlist
                  openList.remove(curSegment);    
              }
            } while(true);

            if (curSegment.parent.tileX-startX<0) return (2 << 24) | curSegment.gscore;
            else if (curSegment.parent.tileX-startX>0) return (0 << 24) | curSegment.gscore;
            else if (curSegment.parent.tileY-startY<0) return (3 << 24) | curSegment.gscore;
            else if (curSegment.parent.tileY-startY>0) return (1 << 24) | curSegment.gscore;
        }
        throw new RuntimeException("Path finding failed");
     }
}
Rohan Jhunjhunwala
quelle