GRATULACJE dla @kuroineko. Wygrywa nagrodę za doskonałą prędkość (672 ruchy) na torze Rękawicy.

LIDER: * Nimi zdobył lekką 2129. Inne wpisy są większe, ale wykazują pewną poważną prędkość.

* Lider może ulec zmianie z powodu późniejszych wpisów.

Twoim zadaniem jest napisanie małego programu, który może szybko prowadzić samochód wyścigowy.

Zasady

Twój program odczyta obraz z toru. Możesz uruchomić samochód na dowolnym żółtym pikselu i musisz zakończyć, przekraczając dowolny czarny piksel. Ścieżka samochodu musi znajdować się tylko na szarym ((c, c, c), gdzie 30 <= c <= 220).

Twój samochód będzie poruszał się w linii prostej w każdym zakręcie z prędkością v składającą się z liczb całkowitych vx i vy (zaczynając od (0,0)). Na początku każdej tury twój program może zmieniać vx i vy w taki sposób, że:

abs(vx2-vx1) + abs(vy2-vy1) <= 15

Aktualizacja: Zwiększono maksymalne przyspieszenie do 15.

Następnie program wykreśli prostą linię z bieżącej lokalizacji do (lokalizacja + v) w kolorze białym z niebieską kropką na początku. Jeśli piksel pod tą linią jest czarny, ukończyłeś wyścig. W przeciwnym razie, jeśli wszystkie piksele pod tą linią są szare lub żółte, możesz przejść do następnej tury.

Twój program musi wyświetlać obraz ścieżki z dodaną ścieżką w kolorze białym i niebieskim.

Dodatkowe wyniki (dodano 15.01.2015):

Jeśli chcesz rywalizować o zwycięstwo lub bonus , Twój program powinien również wypisać listę punktów (niebieskie kropki) odpowiednio dla Miasta lub Rękawicy. Dołącz listę punktów do swojej odpowiedzi (do weryfikacji). Punkty powinny wyglądać następująco: (x0,y0), (x1,y1), ... (xn,yn). Możesz swobodnie używać białych '\n'znaków, w tym znaków, aby dopasować dane do strony.

Możesz używać zewnętrznych bibliotek do odczytu i zapisu obrazów, rysowania linii i dostępu do pikseli. Nie można używać bibliotek wyszukiwania ścieżek. Jeśli chcesz, możesz przekonwertować obrazy PNG na inne formaty graficzne (takie jak GIF, JPG, BMP).

Kilka torów do jazdy

Prosta ścieżka na początek:

Tor wyścigowy:

Bieg z przeszkodami:

Miasto:

Nightmare Track: The Gauntlet (jeśli inne są zbyt łatwe)

Punktacja

Twój wynik będzie oparty na twoim wyniku na torze miejskim. Punkty są równe długości programu w bajtach plus 10 punktów za każdy zakręt, który zakończył Twój samochód wyścigowy. Najniższy wynik wygrywa. Dołącz do swojej odpowiedzi zdjęcie trasy biegowej po mieście - chcielibyśmy poznać Twój styl jazdy.

Proszę podać tytuł odpowiedzi w formacie:

<Racing Driver or Team Name> <Language> <Score> np .: Slowpoke Perl 5329

Twój program musi być w stanie prowadzić na dowolnym obrazie ścieżki zgodnie z powyższymi zasadami. Nie wolno kodować na stałe optymalnej ścieżki ani żadnych parametrów ścieżek testowych. Obowiązują inne standardowe luki.

Podobne wyzwania

To podobna łamigłówka do tej zadanej przez Martina: To Vectory! - Grand Prix wyścigów wektorowych . Ta łamigłówka ma wiele różnic:

• Przejazd przez ściany jest niedozwolony.
• Możesz korzystać z nieograniczonej pamięci i czasu.
• Nie musisz uruchamiać cudzego kodu na swoim komputerze.
• Nie musisz pobierać niczego oprócz jednego obrazu.
• Rozmiar twojego kodu liczy się w punktacji. Mniejszy jest lepszy.
• Tworzysz rozwiązanie na obrazie toru.
• Możesz łatwo tworzyć własne ścieżki za pomocą pakietu farb.
• Wyższa rozdzielczość zachęca do bardziej realistycznego hamowania i pokonywania zakrętów.
• Przyspieszenie 15 stwarza około 450 możliwości na turę. To sprawia, że ​​BFS jest mniej wykonalny i zachęca do nowych interesujących algorytmów.

Ta łamigłówka powinna zainspirować nową rundę programistów do wypróbowania rozwiązań i pozwolić programistom ze starych rozwiązań na przemyślenie ich w nowym środowisku.

TS # 1 - Haskell - 1699 + 430 = 2129

Rodzeństwo Tutu # 1

Bardzo podobny do oryginalnego wyścigowca Tutu, z tą różnicą, że używa grubości 3 dla rozdętej ścieżki, a druga A * (przestrzeń prędkości-pos) idzie ze stałą heurystyką 1. Obraz wejściowy nie jest już przekazywany jako argument wiersza poleceń, musi zostać nazwany i. Nazwa obrazu wyjściowego to o. Program drukuje obliczone punkty na ścieżce jako listę par x, y (oryginalne wyjście to pojedynczy wiersz):

[(6,7),(20,6),(49,5),(92,5),(124,4),(141,3),(148,7),(155,26),(172,49),
(189,70),(191,91),(179,111),(174,124),(184,137),(209,150),(244,168),
(279,171),(302,176),(325,196),(350,221),(367,239),(369,257),(360,272),
(363,284),(381,296),(408,314),(433,329),(458,329),(480,318),(492,312),
(504,321),(519,341),(526,364),(523,392),(514,416),(507,427),(511,435),
(529,442),(558,445),(581,456),(592,470),(592,488),(592,513),(606,537)] 

Mógłbym zaoszczędzić wiele bajtów, kiedy zaczynam usuwać całą mapę i ustawiać struktury danych i zastępować je prostymi połączonymi listami. Tylko dwie instrukcje importu pozwoliłyby zaoszczędzić 60 bajtów. Spowolniłoby to program, tak że oczekiwanie na wynik jest czystym bólem. Ta wersja zajmuje ponad 45 minut dla The City, w porównaniu z 7s oryginału. Przestanę tutaj wymieniać bajty na szybkość wykonywania.

import Codec.Picture
import Codec.Picture.RGBA8
import Codec.Picture.Canvas
import qualified Data.Map as M
import qualified Data.Set as S
import qualified Data.PSQueue as Q
m(a,b)(c,d)|a==c||b==d=2|t=3;n=Nothing;q=PixelRGBA8;s=abs;t=1<2;u=signum;z=255;fl=S.fromList;(#)=M.insert
main=do
 i<-readImageRGBA8"i";let(Right c)=imageToCanvas i;j=canvasWidth c-1;gY=canvasHeight c-1;v(x,y)|all(==0)[r,g,b]=3|r+g==510&&b==0=2|r==g&&r==b&&29<r&&r<221=0|t=1 where(PixelRGBA8 r g b _)=getColor x y c
 let s':_=[(x,y)|x<-[0..j],y<-[0..gY],v(x,y)==2];n8 p@(x,y)=filter((/=1).v)$if y*x==0||y==gY||x==j then[p]else[(a,b)|a<-[x-1..x+1],b<-[y-1..y+1],a/=x||b/=y];r=s':aS(fl.n8)m((==3).v)s';f=concatMap n8;p=head r;w=map fst$(p,(0,0)):aS(\((a,b),(h,i))->fl[(e,(h+j,i+k))|j<-[-15..15],k<-[s j-15..15-s j],not$all(==0)[j,k,h,i],let e=(a+h+j,b+i+k),S.member e(fl$f$f$f r),all((/=1).v)(br(a,b)e)])(\_ _->99)((==last r).fst)(p,(0,0))
 writePng"o"$canvasToImage$foldl(\e((a,b),(c,d))->setColor a b(q 0 0 z z)$drawLine a b c d(q z z z z)e)c(zip w(tail w));print w
br q@(i,j)r@(k,l)=w q$f`div`2where w p@(y,x)e|p==r=[p]|e-o<0=p:w(y+g,x+h)(e-o+f)|t=p:w(y+m,x+n)(e-o);a=s$l-j;b=s$k-i;h=u$l-j;g=u$k-i;(n,m,o,f)|a>b=(h,0,b,a)|t=(0,g,a,b)
data A a c=A{a::S.Set a,h::Q.PSQ a c,k::M.Map a c,p::M.Map a a,w::Maybe a}
aS g d o u=b$w s where b(Just j)=(reverse$takeWhile(/=u)$iterate(p s M.!)j);s=l$A S.empty(Q.singleton u 0)(M.singleton u 0)M.empty n;i x y v s=s{p=y#x$p s,k=y#v$k s,h=Q.insert y(v+1)$h s};l s=b$Q.minView$h s where b(Just(x Q.:->_,w'))|o x=s{w=Just x}|t=l$foldl(r x)(s{h=w',a=S.insert x(a s)})$S.toList$g x S.\\a s;b _=s;r x s y=b$Q.lookup y$h s where v=k s M.!x+d x y;b Nothing=i x y v s;b _|v<k s M.!y=i x y v s|t=s

Kod wymaga flagi -XNoMonomorphismRestriction do skompilowania.

Miasto - TS # 1 - 43 kroki

FirstRacer Java (5825 + 305 * 10 = 8875)

Po prostu na początek. Potrzebuje 305 segmentów w mieście.

Ten program Java wykonuje potok:

1. przeczytaj obraz
2. A * (gwiazda)

• 2.1 Zbuduj krajobraz wyszukiwania A *.
• 2.2 Śledź wstecz, szukając tylko najlepszych * bezpośrednich * 8 sąsiednich komórek (N, S, E, W, NE, NW, SE, SW). Znajduje najkrótszą ścieżkę t0 pikselową.

3. pozostań na t0 i zoptymalizuj go pod kątem prędkości, eliminując piksele. Spełnienie ograniczenia nigdy nie może być szybsze niż 7 (przekłada się to na zachowanie co najmniej co 7 pikseli).
4. narysuj ścieżkę w obrazie
5. pokaż wynikowy obraz.

package race;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Vector;

import javax.imageio.ImageIO;
import javax.swing.JFrame;
import javax.swing.WindowConstants;

public class AStar {

    private static BufferedImage img;
    private static int Width;
    private static int Height;
    private static int[][] cost;
    private static int best=Integer.MAX_VALUE;
    private static Point pBest;

    public static void main(String[] args) throws IOException {
        String file = "Q46YG.png";
        img = read(file);
        Width=img.getWidth();
        Height=img.getHeight();

        Vector<Point> track = astar();
        track = optimize(track);
        draw(track);
        System.out.println(10 * track.size());

        JFrame frame = new JFrame(file) {
            public void paint(Graphics g) {
                setSize(Width+17, Height+30+10);
                g.drawImage(img,8,30,null);
            }
        };
        frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
        frame.setVisible(true);
    }

    private static Vector<Point> optimize(Vector<Point> track) {
        Vector<Point> opt=new Vector<Point>();
        Point p0 = track.get(0);
        Point p1 = track.get(1);
        int v=0;
        opt.add(p0);
        int vx0=p1.x-p0.x, vy0=p1.y-p0.y;
        for (int i = 2; i < track.size(); i++) {
            Point p = track.get(i);
            if (v<7 && vx0==p.x-p1.x && vy0==p.y-p1.y) {
                v++;
            } else {
                v=0;
                opt.add(p1);
                vx0=p.x-p1.x;
                vy0=p.y-p1.y;
            }
            p1=p;
        }
        opt.add(p1);
        return opt;
    }

    private static void draw(Vector<Point> track) {
        Graphics2D g = img.createGraphics();
        Point p0 = track.get(0);
        for (int i = 1; i < track.size(); i++) {
            Point p1 = track.get(i);
            g.setColor(Color.WHITE);
            g.drawLine(p0.x, p0.y, p1.x, p1.y);
            img.setRGB(p0.x, p0.y, 0xff0000ff);
            img.setRGB(p1.x, p1.y, 0xff0000ff);
            p0=p1;
        }
    }

    private static Vector<Point> astar() {
        Vector<Point> v0=findStart();
        for(int i=0; ; i++) {
            Vector<Point> v1=next(v0);
            if (v1.size()==0) break;
            v0=v1;
        }
        Vector<Point> track=new Vector<Point>();
        Point p0 = pBest;
        int x0=p0.x, y0=p0.y;
        int c0=cost[x0][y0];
        while(true) {
            int x=x0, y=y0;
            track.add(0, new Point(x, y));
            for (int x1 = x-1; x1 <= x+1; x1++) {
                for (int y1 = y-1; y1 <= y+1; y1++) {
                    int i1=getInfo(x1, y1);
                    if ((i1&2)==2) {
                        int c=cost[x1][y1];
                        if (c0>c) {
                            c0=c;
                            x0=x1;
                            y0=y1;
                        }
                    }
                }
            }
            if(x0==x &&y0==y) break;
        }
        return track;
    }

    private static Vector<Point> next(Vector<Point> v0) {
        Vector<Point> v1=new Vector<Point>();
        for (Point p0 : v0) {
            int x=p0.x, y=p0.y;
            int c0=cost[x][y];
            for (int x1 = x-1; x1 <= x+1; x1++) {
                for (int y1 = y-1; y1 <= y+1; y1++) {
                    int i1=getInfo(x1, y1);
                    if ((i1&2)==2) {
                        int c1=c0+1414;
                        if (x1==x || y1==y) {
                            c1=c0+1000;
                        }
                        int c=cost[x1][y1];
                        if (c1<c) {
                            cost[x1][y1]=c1;
                            Point p1=new Point(x1, y1);
                            v1.add(p1);
                            if (i1==3) {
                                if (best>c1) {
                                    best=c1;
                                    pBest=p1;
                                }
                            }
                        }
                    }
                }
            }

        }
        return v1;
    }

    private static Vector<Point> findStart() {
        cost=new int[Width][Height];
        Vector<Point> v=new Vector<Point>();
        for (int i = 0; i < Width; i++) {
            for (int j = 0; j < Height; j++) {
                if (getInfo(i,j)==1) {
                    cost[i][j]=0;
                    v.add(new Point(i, j));
                } else {
                    cost[i][j]=Integer.MAX_VALUE;
                    pBest=new Point(i, j);
                }
            }
        }
        return v;
    }

    /**
     * 1: You can start your car on any yellow pixel, 
     * 3: and you must finish by crossing any black pixel. 
     * 2: The path of your car must be only on the grey ((c,c,c) where 30 <= c <= 220) track.
     * 0: else
     * 
     * @param x
     * @param y
     * @return
     */
    private static int getInfo(int x, int y) {
        if (x<0 || x>=Width || y<0 || y>=Height) return 0;
        int rgb = img.getRGB(x, y);
        int c=0;
        switch (rgb) {
        case 0xffffff00: c=1; break;
        case 0xff000000: c=3; break;
        default: 
            int r=0xff&(rgb>>16);
            int g=0xff&(rgb>> 8);
            int b=0xff&(rgb>> 0);
            if (30<=r&&r<=220&&r==g&&g==b) c=2;
        }
        return c;
    }

    private static BufferedImage read(String file) throws IOException {
        File img = new File("./resources/"+file);
        BufferedImage in = ImageIO.read(img);
        return in;
    }

}

Myślę, że tor wyścigowy daje lepsze wrażenie, jak działa FirstRacer.

pighead PHP (5950 + 470 = 6420)

Kolejna odmiana BFS (z główkami), z pewnym wstępnym przetwarzaniem w celu zmniejszenia przestrzeni poszukiwań.

<?php
define ("ACCEL_MAX", 15);
define ("TILE_SIZE_MAX", 2*floor (ACCEL_MAX/2)-1);
define ("TILE_SIZE_MIN", 1);

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

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

class Tile {
    public $center;
    private static $id = 0;

    public function __construct ($corner_x, $corner_y, $size, $type)
    {
        $this->type = $type;
        $this->id = ++self::$id;
        $half = round ($size/2);
        $this->center = new Point ($corner_x+$half, $corner_y+$half));
        for ($x = 0 ; $x != $size ; $x++)
        for ($y = 0 ; $y != $size ; $y++)
            Map::$track[$x+$corner_x][$y+$corner_y] = 0;
        Map::$tile_lookup[$this->center->x][$this->center->y] = $this;
    }

    public function can_reach ($target)
    {
        if (isset($this->reachable[$target->id])) return $this->reachable[$target->id];
        $ex = $target->center->x;
        $ey = $target->center->y;
        $ox = $this->center->x;
        $oy = $this->center->y;
        $sx = $ex - $ox;
        $sy = $ey - $oy;
        $range = max (abs ($sx), abs ($sy));
        if ($range == 0) return false;
        $reachable = true;
        for ($s = 1 ; $s != $range ; $s++)
            if (!isset (Map::$track[$ox + $s/$range*$sx][$oy + $s/$range*$sy]))
            {
                $reachable = false;
                break;
            }
        return $this->reachable[$target->id] = $target->reachable[$this->id] = $reachable;
    }
}

class Node {
    public $posx  , $posy  ;
    public $speedx, $speedy;
    private $parent;

    public function __construct ($posx, $posy, $speedx, $speedy, $parent)
    {
        $this->posx = $posx;
        $this->posy = $posy;
        $this->speedx = $speedx;
        $this->speedy = $speedy;
        $this->parent = $parent;
    }

    public function path ()
    {
        $res = array();
        for ($node = $this ; $node != null ; $node = $node->parent)
        {
            array_unshift ($res, new Point ($node->posx, $node->posy));
        }
        return $res;
    }
}

class Map {
    public static $track;       // map of track pixels
    public static $tile_lookup; // retrieve tile from a position

    private static $tiles;        // all track tiles
    private static $sx, $sy;      // map dimensions
    private static $cell;         // cells of the map
    private static $start;        // starting point
    private static $acceleration; // possible acceleration values
    private static $img; // output image
    private static $output_name;

    const GOAL  = 0;  // terrain types
    const START = 1;
    const TRACK = 2;

    private static function create_tile ($cx, $cy, $size)
    {
        for ($x = $cx ; $x != $cx + $size ; $x++)
        for ($y = $cy ; $y != $cy + $size ; $y++)
            if (!isset (self::$track[$x][$y]) || !self::$track[$x][$y]) return false;
        for ($x = $cx ; $x != $cx + $size ; $x++)
        for ($y = $cy ; $y != $cy + $size ; $y++)
            self::$track[$x][$y] = 0;
//Trace::msg ("track tile $cx $cy $size");
        return new Tile ($cx, $cy, $size, self::TRACK);
    }

    public static function init ($filename)
    {
        // read map definition
        $img = imagecreatefrompng ($filename) or die ("could not read $filename");
        self::$img = $img;
        self::$output_name = "_".$filename;
        self::$sx = imagesx ($img);
        self::$sy = imagesy ($img);

        for ($x = 0 ; $x != self::$sx ; $x++)
        for ($y = 0 ; $y != self::$sy ; $y++)
        {
            $color = imagecolorat ($img, $x, $y) & 0xFFFFFF;
            if      ($color  ==        0) self::$tiles[]                  = new Tile ($x, $y, 1, Map::GOAL);
            else if ($color  == 0xFFFF00) self::$tiles[] = self::$start[] = new Tile ($x, $y, 1, Map::START);
            else
            {
                $r = ($color >> 16) & 0xFF;
                $g = ($color >>  8) & 0xFF;
                $b =  $color        & 0xFF;
                if ($r == $g && $r == $b && $r >= 30 && $r <= 220) @self::$track[$x][$y] = 1;
            }
        }

        for ($size = TILE_SIZE_MAX ; $size >= TILE_SIZE_MIN ; $size--)
        for ($x = 0 ; $x != self::$sx ; $x++)
        for ($y = 0 ; $y != self::$sy ; $y++)
        {
            $tile = self::create_tile ($x, $y, $size);
            if ($tile) self::$tiles[] = $tile;
        }

        self::$acceleration = array();
        for ($x = -ACCEL_MAX ; $x <= ACCEL_MAX ; $x++)
        for ($y = -ACCEL_MAX ; $y <= ACCEL_MAX ; $y++)
        {
            if (abs ($x) + abs ($y) <= ACCEL_MAX) self::$acceleration[] = new Point ($x, $y);
        }
    }

    public static function solve ()
    {
        $res = $border = $present = array();
        foreach (self::$start as $start)
        {
            $border[] = new Node ($start->center->x, $start->center->y, 0, 0, null);
            $present[$start->center->x." ".$start->center->y." 0 0"] = 1;
        }
        while (count ($border))
        {
            $node = array_shift ($border);
            $px = $node->posx;
            $py = $node->posy;
            $vx = $node->speedx;
            $vy = $node->speedy;
            $current = self::$tile_lookup[$px][$py];
            foreach (self::$acceleration as $a)
            {
                $nvx = $vx + $a->x;
                $nvy = $vy + $a->y;
                $npx = $px + $nvx;
                $npy = $py + $nvy;
                @$tile = self::$tile_lookup[$npx][$npy];
                if (!$tile || !$tile->can_reach ($current)) continue;
                if ($tile->type == self::GOAL)
                {
                    $end = new Node ($npx, $npy, $nvx, $nvy, $node);
                    $res = $end->path ();
                    $ox = $res[0]->x;
                    $oy = $res[0]->y;
                    for ($i = 1 ; $i != count ($res) ; $i++)
                    {
                        $ex = $res[$i]->x;
                        $ey = $res[$i]->y;
                        imageline (self::$img, $ox, $oy, $ex, $ey, 0xFFFFFF);
                        $ox = $ex; $oy = $ey;
                    }
                    for ($i = 0 ; $i != count ($res) ; $i++)
                    {
                        imagesetpixel (self::$img, $res[$i]->x, $res[$i]->y, 0xFF);
                    }
                    imagepng (self::$img, self::$output_name);
printf (count($present)." nodes, ".round(memory_get_usage(true)/1024)."K\n");
printf ((count($res)-1)." moves\n");
                    return;
                }
                $signature = "$npx $npy $nvx $nvy";
                if (isset ($present[$signature])) continue;
                $border[] = new Node ($npx, $npy, $nvx, $nvy, $node);
                $present[$signature] = 1;
            }
        }
    }
}

ini_set("memory_limit","1000M");
Map::init ($argv[1]);
Map::solve();
?>

Wybór języka

PHP jest całkiem dobry w obsłudze obrazów.
Ma również natywną pamięć asocjacyjną, dzięki czemu programowanie wyszukiwania węzłów BFS jest dziecinnie proste.

Minusem jest to, że haszowanie identyfikatorów węzłów nie jest strasznie czasochłonne, więc wynik jest szybki.

Z moich eksperymentów z poprzednim wyzwaniem wyścigowym nie mam wątpliwości, że C ++ 11 i jego tablice skrótów działałyby znacznie lepiej, ale kod źródłowy przynajmniej by się podwoił, plus potrzeba jakiejkolwiek zewnętrznej biblioteki png (nawet LodePNG) zrobić niechlujną wersję.

Perl i jego bardziej zaawansowane potomstwo prawdopodobnie pozwoliłyby na bardziej zwarty i wydajny kod (ze względu na lepszą wydajność mieszania), ale nie znam się na żadnym z nich, aby wypróbować port.

Rdzeń BFS

Wyszukiwanie działa na pozycji + przestrzeń prędkości, tzn. Węzeł reprezentuje daną lokalizację odwiedzaną z określoną prędkością.
To oczywiście zapewnia dość dużą przestrzeń wyszukiwania, ale daje optymalne wyniki, pod warunkiem, że zbadane zostaną wszystkie możliwe lokalizacje torów.

Oczywiście, biorąc pod uwagę liczbę pikseli nawet na małym obrazie, wyczerpujące wyszukiwanie nie wchodzi w rachubę.

Kawałki

Wybrałem przecięcie przestrzeni pozycji, wybierając tylko podzbiór pikseli ścieżki.
Solver weźmie pod uwagę wszystkie pozycje w zasięgu, ograniczone tylko przyspieszeniem.

Ścieżka jest wyłożona kwadratami, których maksymalny rozmiar jest obliczany, dzięki czemu można uzyskać dwa sąsiednie kwadraty z maksymalnym dozwolonym przyspieszeniem (tj. 14 x 14 pikseli przy aktualnym ograniczeniu prędkości).
Po zapakowaniu toru dużymi kwadratami, do wypełnienia pozostałej przestrzeni używa się coraz mniejszych płytek.
Tylko środek każdej płytki jest uważany za możliwy cel.

Oto przykład:

Ten heurystyczny wybór wystarczy, aby solver zawiódł na mapie koszmaru. Przypuszczam, że można spróbować zmniejszyć maksymalny rozmiar kafelka, dopóki nie zostanie znalezione jakieś rozwiązanie, ale przy obecnych ustawieniach solver działa przez około godzinę i używa 600 Mb, więc dokładniejsze wyniki wymagałyby nieuzasadnionego czasu i pamięci.

Jako drugie cięcie można pominąć kwadraty o wielkości zaledwie 1 piksela.
To oczywiście pogorszy rozwiązanie, a nawet uniemożliwi znalezienie solwera, ale znacznie skraca czas obliczeń i zwykle daje całkiem bliskie wyniki na „prostych” mapach.

Na przykład w mieście pominięcie kwadratów piksela 1 x 1 zmniejsza zbadane węzły drzewa BFS z 660 K do około 90 K dla rozwiązań 47 vs 53 ruchów.

BFS vs A *

* Wymaga więcej kodu i nie ma nawet gwarancji, że przyniesie szybsze wyniki w przestrzeni pozycji / prędkości, ponieważ ocena najlepszego następnego kandydata nie jest tak prosta, jak w klasycznej spacji tylko dla pozycji (którą można łatwo pokonać dzięki celowo opracowanemu kulturowi w każdym razie de-sacs).

Poza tym, chociaż PHP ma pewne priorytetowe kolejki, które, nawiasem mówiąc, obsługują dynamiczne zmienianie kolejności kont w swoich kuzynach C ++, wątpię, czy wystarczyłyby do wydajnej implementacji A * i przepisania stosu binarnego lub innej dedykowanej struktury kolejki A * wymagają o wiele za dużo linii kodu.

Kontrola ściany

Nie użyłem algorytmu Bresenhama do sprawdzania kolizji na ścianie, więc trajektoria może obciąć nieparzysty piksel na ścianie. Nie powinno jednak pozwolić na przejście przez ścianę.

Występy

Ten solver na pewno nie ma sześcionożnego jackrabbit.
Bez dodatkowego cięcia mapa może zająć ponad 10 minut na rozwiązaniu na moim komputerze średniego zasięgu.
Sugeruję ustawienie minimalnego rozmiaru kafelka na 2 lub 3, jeśli chcesz bawić się kodem bez spędzania wieków na oczekiwaniu na wynik.

Zużycie pamięci jest rozsądne dla tego rodzaju algorytmu i języka: około 100 Mb lub mniej, z wyjątkiem koszmaru o wartości szczytowej powyżej 600 Mb.

Wyniki i punktacja

Wyniki są podawane bez cięcia „minimalnego rozmiaru płytki”.

Jak uważny czytelnik może wywnioskować z moich ogólnych komentarzy, nie dbam o golfową część tego wyzwania. Nie rozumiem, jak uruchomienie mojego kodu przez obfuscator lub usunięcie niektórych optymalizacji i / lub procedur debugowania w celu zmniejszenia źródła sprawiłoby, że byłoby to jeszcze przyjemniejsze.

Niech na razie rozmiar S będzie bajtem źródłowym:

ścieżka S + 1020

miasto S + 470

przeszkody S + 280

koszmar -> kończy się niepowodzeniem

SecondRacer Java (1788 + 72 * 10 = 2508) (2708) (2887) (3088) (3382) (4109 + 72 * 10 = 4839) (4290 + 86 * 10 = 5150)

Podobne do FirstRacer. Różni się to jednak w krokach 2.2 i 3., co prowadzi do dalekowzroczności i używania sprzętu.

2. A * (gwiazda)

• 2.1 Zbuduj krajobraz wyszukiwania A *.
• 2.2 Znajdź najlepszą komórkę w * zasięgu wzroku * i weź pod uwagę odległość euklidesową. (Wciąż patrzy tylko w kierunkach N, S, E, W, NE, NW, SE, SW.) W rezultacie SecondRacer znajduje ścieżkę o znacznie mniejszej liczbie punktów nawigacyjnych.

3. Optymalizacja jest teraz bardzo skomplikowana. Chodzi o podzielenie danych linii między punktami dwukierunkowymi na możliwie najmniejszą liczbę zakrętów, bez naruszania ograniczenia przyspieszenia.

Wydajność

Żadna z tych ścieżek nie stanowi problemu dla A *. Zaledwie kilka sekund (<10) do rozwiązania (nawet „Nightmare Track: The Gauntlet”) na moim komputerze średniego zasięgu.

Styl ścieżki

Nazywam to ośmiornicą. Zdecydowanie nie tak elegancki, jak rozwiązanie dla świni (od kuroi neko).

Styl kodu

Przeszedłem do umiarkowanego trybu walki, zachowując czytelność. Ale dodano wersję golfową.

import java.awt.*;
import java.awt.image.*;
import java.io.*;
import java.util.*;
import javax.imageio.*;
import javax.swing.*;
import static java.lang.Math.*;

class AStar2 {
    BufferedImage img;
    int Width;
    int Height;
    int[][] cost;
    int best=Integer.MAX_VALUE;
    Point pBest;

    public static void main(String[] args) throws IOException {
        new AStar2().exec(args);
    }

    void exec(String[] args) throws IOException {
        img = ImageIO.read(new File(args[0]));
        Width=img.getWidth();
        Height=img.getHeight();

        draw(optimize(astar()));

        JFrame frame = new JFrame() {
            public void paint(Graphics g) {
                setSize(Width+17, Height+30+10);
                g.drawImage(img,8,30,null);
            }
        };
        frame.setVisible(true);
    }

    Vector<Point> astar() {
        Vector<Point> v0=findStart();
        while(v0.size()>0) v0=next(v0);

        for(Point p0 = pBest; p0!=null; p0=trackBack(p0)) v0.add(p0);
        return v0;
    }

    Vector<Point> findStart() {
        cost=new int[Width][Height];
        Vector<Point> v=new Vector<Point>();
        for (int i = 0; i < Width; i++)
            for (int j = 0; j < Height; j++) {
                if (getInfo(i,j)==1) {
                    cost[i][j]=0;
                    v.add(new Point(i, j));
                } else {
                    cost[i][j]=Integer.MAX_VALUE;
                    pBest=new Point(i, j);
                }
            }
        return v;
    }

    Vector<Point> next(Vector<Point> v0) {
        Vector<Point> v1=new Vector<Point>();
        for (Point p0 : v0) {
            int x=p0.x, y=p0.y,x1,y1,i1,c1, c0=cost[x][y];
            for (Point p : n(new Point(x,y))) {
                x1 = p.x; y1 = p.y;
                i1=getInfo(x1, y1);
                if (i1/2==1) {
                    c1=c0+(x1==x||y1==y?10:14);
                    if (c1<cost[x1][y1]) {
                        cost[x1][y1]=c1;
                        Point p1=new Point(x1, y1);
                        v1.add(p1);
                        if (i1==3) {
                            if (best>c1) {
                                best=c1;
                                pBest=p1;
                            }
                        }
                    }
                }
            }
        }
        return v1;
    }

    Point trackBack(Point p0) {
        Point p1=null, t;
        int x=p0.x, y=p0.y, i;
        double c0=0, c;
        for (Point p : n(new Point(0,0))) {
            for (i = 1; getInfo((t= new Point(x+i*p.x, y+i*p.y)).x, t.y)>0; i++) {
                c=cost[t.x][t.y]-cost[x][y]+5*sqrt((x-t.x)*(x-t.x) + (y-t.y)*(y-t.y));
                if (c0>c) {
                    c0=c;
                    p1= t;
                }
            }
        }
        return p1;
    }

    Vector<Point> n(Point p) {
        int [] c=new int[] {0, -1,-1, -1,-1, 0,-1, 1,0,1,1, 1,1, 0,1, -1};
        Vector<Point> v=new Vector<Point>();
        for (int i = 0; i < c.length; i+=2) v.add(new Point(p.x+c[i], p.y+c[i+1]));
        return v;
    }

    Vector<Point> optimize(Vector<Point> track) {
        Vector<Point> opt=new Vector<Point>();
        Point p0 = track.get(0);
        opt.add(p0);
        for (int i = 1; i < track.size(); i++) segmentAcceleration(opt, track.get(i));
        return opt;
    }

    boolean constraint(Point p0, Point p1, Point p2) {
        return abs(p2.x-p1.x-p1.x+p0.x) + abs(p2.y-p1.y-p1.y+p0.y) <= 15;
    }

    void segmentAcceleration(Vector<Point> opt, Point p1 ) {
        Point p0 = opt.lastElement();
        int d=max(abs(p0.x-p1.x), abs(p0.y-p1.y)), x=(p1.x-p0.x)/d, y=(p1.y-p0.y)/d, start=opt.size(),i;
        for (i = 0; i <=d; i++) opt.add(new Point(p0.x+x*i, p0.y+y*i));

        for(int success=1; success==1;) {
            success=0;
            for (int j = start; j < opt.size()-1; j++) {
                Point q=new Point(opt.get(j).x+x, opt.get(j).y+y);
                if (opt.get(j).x==opt.get(j+1).x && opt.get(j).y==opt.get(j+1).y) {
                    opt.remove(j);
                    success=1;
                } else if (j>1&&constraint(opt.get(j-2), opt.get(j-1), q) && constraint(opt.get(j-1), q, opt.get(j+1)) && (j>opt.size()-3 || constraint(q, opt.get(j+1), opt.get(j+2)))) {
                    opt.set(j, q);
                    success=1;
                }
            }
        }
    }

    void draw(Vector<Point> track) {
        Graphics2D g = img.createGraphics();
        Point p0=track.get(0);
        for (Point p1: track) {
            g.setColor(Color.WHITE);
            g.drawLine(p0.x, p0.y, p1.x, p1.y);
            img.setRGB(p0.x, p0.y, 0xff0000ff);
            img.setRGB(p1.x, p1.y, 0xff0000ff);
            p0=p1;
        }
    }

    int getInfo(int x, int y) {
        if (x<0 || x>=Width || y<0 || y>=Height) return 0;
        int rgb = img.getRGB(x, y), r=0xff&(rgb>>16), g=0xff&(rgb>> 8), b=0xff&(rgb>> 0);
        switch (rgb) {
        case 0xffffff00: return 1;
        case 0xff000000: return 3;
        default: if (30<=r&&r<=220&&r==g&&g==b) return 2;
        }
        return 0;
    }
}

golfed -> OSTRZEŻENIE: zastępuje oryginalny plik!

import java.awt.*;import javax.imageio.*;import static java.lang.Math.*;class
A{class B{int C,D;}class E extends java.util.Vector<B>{};static java.awt.image.BufferedImage
F;int G=F.getWidth(),H=F.getHeight(),I[][]=new int[G][H],J=-1>>>1,K,L,M=255,N;B
O,P,Q;public static void main(String[]R)throws Exception{F=ImageIO.read(new
java.io.File(R[0]));new A().S();ImageIO.write(F,"PNG",new java.io.File(R[0]));}void
S(){E U=new E(),V=new E();for(K=0;K<G;K++)for(L=0;L<H;L++)if(W(K,L)==1)U.add(X(K,L));else
I[K][L]=J;while(U.size()>0){P=U.remove(0);int C=P.C,D=P.D,Y,Z,a,b;for(N=0;N<9;N++)if(N!=4)if((a=W(Y=C+N/3-1,Z=D+N%3-1))>0&&I[Y][Z]>(b=I[C][D]+(Y==C||Z==D?10:14))){I[Y][Z]=b;U.add(X(Y,Z));if(a==3&&J>b){J=b;O=Q;}}}P=O;while(O!=null){U.add(O);J=O.C;L=O.D;double
c=0,d;O=null;for(N=0;N<9;N++)if(N!=4)for(K=1;W(X(J+K*(N/3-1),L+K*(N%3-1)).C,Q.D)>0;K++)if(c>(d=I[Q.C][Q.D]-I[J][L]+5*sqrt((J-Q.C)*(J-Q.C)+(L-Q.D)*(L-Q.D)))){c=d;O=Q;}}Graphics2D
e=F.createGraphics();V.add(P);for(K=1;K<U.size();K++){O=P;P=U.get(K);e.setColor(Color.WHITE);e.drawLine(O.C,O.D,P.C,P.D);int
f=max(abs(O.C-P.C),abs(O.D-P.D)),C=(P.C-O.C)/f,D=(P.D-O.D)/f,start=V.size();for(L=0;L<=f;L++)V.add(X(O.C+L*C,O.D+L*D));while(f>0)for(f=0,L=start;L<V.size()-1;L++)if(V.get(L).C==V.get(L+1).C&&V.get(L).D==V.get(L+1).D)V.remove(L);else
if(L>1&&g(V.get(L-2),V.get(L-1),X(V.get(L).C+C,V.get(L).D+D))&&g(V.get(L-1),Q,V.get(L+1))&&(L>V.size()-3||g(Q,V.get(L+1),V.get(L+2)))){V.set(L,Q);f=1;}}for(B
h:V)F.setRGB(h.C,h.D,~0xffff00);}B X(int C,int D){Q=new B();Q.C=C;Q.D=D;return
Q;}boolean g(B O,B P,B i){return abs(i.C-P.C-P.C+O.C)+abs(i.D-P.D-P.D+O.D)<16;}int
W(int C,int D){if(C>=0&&C<G&&D>=0&&D<H){int j=F.getRGB(C,D),Q=j>>16&M,e=j>>8&M;if(j==~M)return
1;if(j==M<<24)return 3;if(30<=Q&&Q<=220&&Q==e&&e==(M&j))return 2;}return
0;}}

Wszystkie obrazy są wyświetlane na krajobrazie gradientowym A *. Począwszy od jasnożółtego do brązowego (= ciemnożółty). Podczas gdy - zgodnie z A * - uzyskana ścieżka jest śledzona do tyłu (tutaj od brązowego do jasnożółtego).

Tor wyścigowy S + 175

Tor przeszkód S + 47

Miasto S + 72

Rękawica S + 1133

Tutu - Haskell - ( 3460 2654 2476 2221 2060 1992 1900 + 50x10 = 2400)

Strategia:

1. Znajdź*
2. wzdęcia ścieżki z sąsiadami (odległość 2)
3. znajdź ponownie A *, ale tym razem w pozycji + spacja, podobnie jak zawodnik

Golf:

• pominięto większość sprawdzania błędów, więc program zakłada, że ​​na mapie zawsze znajdują się punkty początkowe i końcowe oraz ścieżka między nimi.
• krótkie nazwy zmiennych

Nie jestem golfistą Haskell, więc nie wiem, ile jeszcze można zaoszczędzić (edycja: okazało się, że to całkiem sporo).

Wydajność:

Gauntlet działa w 9: 21min na moim 1,7 GHz Core i5 od 2011 roku. Miasto zajmuje 7,2 sekundy. (użyte -O1 z ghc, -O2 powoduje, że program jest strasznie wolny)

Opcje przeróbki to grubość rozdętej ścieżki. Dla mniejszych map odległość 3 oszczędza jeden lub dwa kroki, ale Rękawica działa zbyt długo, więc pozostaję z odległością 2. Wyścig rozpoczyna się zawsze od pierwszego (tj. Lewego górnego) żółtego piksela, optymalizacja ręcznie powinna zaoszczędzić dodatkowy krok.

Zgodność reguł:

„Nie możesz używać bibliotek wyszukiwania ścieżek.” - Tak, ale źródło jest włączone. Funkcje wyszukiwania A * są nieco mocno golfowymi wersjami biblioteki Data.Graph.AStar Cale'a Gibbarda (patrz http://hackage.haskell.org/package/astar ).

Miasto - 50 kroków

Gauntlet - 722 kroki

Nie golfowany:

import System.Environment
import Data.Maybe (fromJust)
import Graphics.GD
import qualified Data.Matrix as M
import qualified Data.List as L
import qualified Data.Set as S
import qualified Data.Map as Map
import qualified Data.PSQueue as PSQ

main = do
    trPNG <- loadPngFile =<< fmap head getArgs
    (sX, sY) <- imageSize trPNG
    px <- mapM (flip getPixel trPNG) [(x,y) | y <- [0..sY-1],x <- [0..sX-1]]
    let tr = M.fromList sY sX (map (rgbaToTok . toRGBA) px)
    let rt = findRt tr
    let vrt = findVRt (head rt) (last rt) (bloat rt tr) tr
    let wayPt = map ((\(a,b)->(b-1,a-1)) . fst) vrt
    mapM (\(p1,p2) -> drawLine p1 p2 (rgb 255 255 255) trPNG
        >> setPixel p1 (rgb 0 0 255) trPNG) (zip wayPt (tail wayPt))
    savePngFile "out1.png" trPNG 
    print $ length vrt - 1

findVRt p1 p2 rt tr = (p1, (0,0)) : fromJust (aStar nghb (\_ _ -> 100)
        (\(pos,_) -> fromJust $ Map.lookup pos rt)
        ((==) p2 . fst) (p1, (0,0)))
    where
    nghb ((y,x), (vy,vx)) =
        S.fromList [(newp, (vy+dy,vx+dx)) |
            dy <- [-15 .. 15],
            let ady = abs dy,
            dx <- [-15+ady .. 15-ady],
            not $ dy==0 && dx == 0 && vy == 0 && vx == 0,
            let newp = (y+vy+dy,x+vx+dx),
            Map.member newp rt,
            all ((/=) 1 . (M.!) tr) (bresenham (y,x) newp)]

bloat rt tr = foldr (\(p,h) -> Map.insert p h) Map.empty
                (zip (reverse $ f $ f rt) [0..])
    where
    f = concatMap (n8 tr)

rgbaToTok (r, g, b, _)
    | r+g+b == 0 = 3
    | r==255 && g==255 && b==0 = 2
    | r==g && r==b && 30 <= r && r <= 220 = 0
    | otherwise = 1

findRt tr = s : fromJust (aStar nghb cost (const 1) ((==) 3 . (M.!) tr) s)
    where
    cost (y1,x1) (y2,x2) = if (x1==x2 || y1==y2) then 408 else 577
    nghb = S.fromList . n8 tr
    s = head [(y,x) | y <- [1..M.nrows tr], x <- [1..M.ncols tr],
            M.getElem y x tr == 2]

n8 tr p@(y,x) = filter ((/=) 1 . (M.!) tr) (n8' y x)
    where
    n8' y x | y==1 || x==1 || y == M.nrows tr || x == M.ncols tr = [p]
        | otherwise = [ (y-1,x-1), (y-1,x), (y-1,x+1), (y,x-1),
                (y,x+1), (y+1,x-1), (y+1,x), (y+1,x+1) ]

bresenham start@(y0,x0) end@(y1,x1) = walk start (el `div` 2)
    where
    walk p@(y,x) err
        | p == end = [p]
        | err-es < 0 = p : walk (y+sdy,x+sdx) (err-es+el)
        | otherwise = p : walk (y+pdy,x+pdx) (err-es)

    dx = x1-x0; dy = y1-y0;
    adx = abs dx; ady = abs dy
    sdx = signum dx; sdy = signum dy
    (pdx,pdy,es,el) = if adx > ady then (sdx,0,ady,adx) else (0,sdy,adx,ady)

data AStar a c = AStar {
    vi :: !(S.Set a), wa :: !(PSQ.PSQ a c), sc :: !(Map.Map a c),
    mH :: !(Map.Map a c), ca :: !(Map.Map a a), en :: !(Maybe a) }
    deriving Show

aStarInit s = AStar S.empty (PSQ.singleton s 0) (Map.singleton s 0)
    Map.empty Map.empty Nothing

aStar graph dist heur goal start =
    let s = runAStar graph dist heur goal start
    in case en s of
        Nothing -> Nothing
        Just e -> Just (reverse . takeWhile (not . (== start))
                    . iterate (ca s Map.!) $ e)

runAStar graph dist heur goal start = aStar' (aStarInit start)
    where
    aStar' s = case PSQ.minView (wa s) of
        Nothing -> s
        Just (x PSQ.:-> _, w') ->
            if goal x
            then s { en = Just x }
            else aStar' $ L.foldl' (expand x) (s { wa = w',
                    vi = S.insert x (vi s)})
                    (S.toList (graph x S.\\ vi s))
    expand x s y =
        let vi = sc s Map.! x + dist x y
        in case PSQ.lookup y (wa s) of
            Nothing -> link x y vi (s { mH
                    = Map.insert y (heur y) (mH s) })
            Just _ -> if vi<sc s Map.! y then link x y vi s else s
    link x y v s = s {
            ca = Map.insert y x (ca s),
            sc = Map.insert y v (sc s),
            wa = PSQ.insert y (v + mH s Map.! y) (wa s) }

Gra w golfa:

import System.Environment;import Graphics.GD;import Data.Matrix;import qualified Data.Set as S;import qualified Data.Map as J;import qualified Data.PSQueue as Q
j(Just x)=x;e(y,x)=(x-1,y-1);u=signum;q=J.empty;m=reverse;n=Nothing;z=255;s=abs;t=1<2;f(a,b)(c,d)|b==d||a==c=2|t=3;rT(r,g,b,_)|r+g+b==0=3|r==z&&g==z&&b==0=2|r==g&&r==b&&30<=r&&r<=220=0|t=5
main=do
 i:_<-getArgs;t<-loadPngFile i;(a,b)<-imageSize t;p<-mapM(flip getPixel t)[(x,y)|y<-[0..b-1],x<-[0..a-1]];let r=fromList b a$map(rT.toRGBA)p;s:_=[(y,x)|y<-[1..b],x<-[1..a],getElem y x r==2];c p@(y,x)=filter((<5).(!)r)$if y==1||x==1||y==b||x==a then[p]else[(a,b)|a<-[y-1..y+1],b<-[x-1..x+1],a/=y||b/=x];y=s:j(aS(S.fromList.c)f(\_->1)((==3).(!)r)s);l=concatMap c;w=map(e.fst)$fV(head y)(last y)(foldr(\(p,h)->J.insert p h)q$zip(m$l$l y)[0..])r
 mapM(\(c,d)->drawLine c d(rgb z z z)t>>setPixel c(rgb 0 0 z)t)$zip w$tail w;savePngFile"o.png"t
fV c d r t=(c,(0,0)):j(aS l(\_ _->99)(\(q,_)->j$J.lookup q r)((==d).fst)(c,(0,0)))where l((y,x),(a,b))=S.fromList[(w,(a+c,b+d))|c<-[-15..15],d<-[s c-15..15-s c],any(/=0)[a,b,c,d],let w=(y+a+c,x+b+d),J.member w r,all((<5).(!)t)$br(y,x)w]
br q@(i,j)r@(k,l)=w q$f`div`2where w p@(y,x)e|p==r=[p]|e-o<0=p:w(y+g,x+h)(e-o+f)|t=p:w(y+m,x+n)(e-o);a=s$l-j;b=s$k-i;h=u$l-j;g=u$k-i;(n,m,o,f)|a>b=(h,0,b,a)|t=(0,g,a,b)
data A a c=A{v::S.Set a,w::Q.PSQ a c,k::J.Map a c,mH::J.Map a c,ca::J.Map a a,en::Maybe a}deriving Show
aS g d h o u=b$en s where b Nothing=n;b(Just e)=Just(m.takeWhile(/=u).iterate(ca s J.!)$e);s=l$A S.empty(Q.singleton u 0)(J.singleton u 0)q q n;i x y v s=s{ca=J.insert y x$ca s,k=J.insert y v$k s,w=Q.insert y(v+mH s J.!y)$w s};l s=b$Q.minView$w s where b Nothing=s;b(Just(x Q.:->_,w'))|o x=s{en=Just x}|t=l$foldl(r x)(s{w=w',v=S.insert x$v s})$S.toList$g x S.\\v s;r x s y=b$Q.lookup y$w s where v=k s J.!x+d x y;b Nothing=i x y v$s{mH=J.insert y(h y)$mH s};b(Just _)|v<k s J.!y=i x y v s|t=s

Rodzeństwo Tutu -TS # 1 - (1764 + 43 = 2194)

Edycja: TS # 1 teraz osobna odpowiedź.

Edycja II: Ścieżka do miasta jest

[(6,7),(21,7),(49,5),(92,3),(126,4),(145,5),(149,6),(153,22),(163,47),(180,64),
(191,73),(191,86),(185,107),(177,122),(175,130),(187,137),(211,147),(237,162),
(254,171),(277,171),(299,175),(321,194),(345,220),(364,237),(370,252),(365,270),
(360,276),(368,284),(387,296),(414,315),(438,330),(463,331),(484,321),(491,311),
(498,316),(508,333),(524,354),(525,375),(519,404),(511,424),(508,434),(513,437),
(533,440),(559,444),(580,458),(591,468),(591,482),(591,511),(598,532),(605,539),
(606,537)]

W The Gauntlet Tutu porusza się w następujący sposób

[(99,143),(114,143),(137,150),(150,161),(149,173),(145,180),(141,197),(138,223),
(135,234),(143,241),(166,248),(186,250),(192,251),(192,261),(192,279),(195,285),
(209,287),(232,284),(248,273),(257,261),(272,256),(279,255),(284,245),(294,243),
(309,231),(330,226),(354,233),(380,253),(400,265),(421,271),(436,268),(438,266),
(440,269),(441,277),(450,278),(470,276),(477,276),(478,285),(481,307),(490,330),
(486,352),(471,370),(449,384),(435,391),(433,401),(446,411),(462,430),(464,450),
(459,477),(454,493),(457,514),(462,522),(472,523),(479,529),(491,531),(493,538),
(496,547),(503,546),(516,545),(519,549),(524,566),(531,575),(531,581),(535,576),
(538,557),(541,523),(545,475),(551,414),(559,342),(565,282),(570,236),(574,204),
(575,184),(574,177),(572,179),(568,174),(568,158),(569,144),(572,143),(578,154),
(585,160),(588,155),(593,140),(598,140),(605,153),(610,156),(611,170),(611,182),
(608,182),(598,175),(594,171),(590,176),(587,195),(589,224),(593,266),(599,321),
(605,376),(609,418),(612,446),(610,465),(615,478),(608,494),(605,521),(611,542),
(618,549),(622,551),(621,563),(611,572),(614,581),(623,581),(630,581),(630,573),
(636,556),(639,551),(642,531),(647,520),(640,511),(637,491),(639,461),(641,416),
(643,356),(647,289),(650,235),(652,195),(647,163),(645,143),(645,136),(653,136),
(670,138),(673,139),(676,155),(679,175),(681,181),(669,188),(662,194),(662,208),
(665,234),(669,274),(674,328),(681,395),(687,457),(692,505),(696,540),(700,560),
(703,566),(706,557),(707,535),(708,498),(711,448),(716,385),(720,325),(723,278),
(726,246),(729,229),(732,227),(733,238),(733,263),(733,303),(733,358),(733,428),
(733,483),(733,523),(732,549),(731,560),(728,558),(726,565),(726,575),(721,575),
(720,586),(720,592),(716,594),(715,608),(715,619),(711,619),(692,619),(658,619),
(609,619),(545,619),(466,619),(372,619),(285,619),(213,619),(155,619),(112,619),
(84,619),(70,618),(70,616),(70,599),(70,567),(70,520),(70,458),(70,381),
(70,300),(70,234),(70,183),(70,147),(70,126),(71,119),(80,119),(104,119),
(143,119),(197,119),(266,119),(350,119),(449,119),(563,119),(681,120),(784,121),
(873,121),(947,121),(1006,121),(1050,121),(1079,121),(1093,121),(1093,122),
(1086,131),(1069,145),(1059,151),(1040,151),(1006,151),(973,150),(955,149),
(950,150),(956,155),(977,160),(994,175),(1003,183),(1003,197),(993,214),
(987,220),(993,223),(1011,223),(1044,223),(1079,229),(1104,240),(1124,242),
(1134,239),(1134,231),(1134,221),(1139,218),(1156,218),(1177,217),(1183,216),
(1191,202),(1208,182),(1231,154),(1249,135),(1259,123),(1264,121),(1264,129),
(1264,152),(1264,190),(1264,243),(1264,311),(1264,393),(1264,460),(1264,512),
(1264,550),(1264,573),(1263,582),(1256,582),(1234,582),(1197,582),(1160,575),
(1132,562),(1118,548),(1113,538),(1107,541),(1099,549),(1102,561),(1113,570),
(1110,578),(1095,583),(1073,581),(1066,579),(1060,566),(1063,559),(1075,554),
(1072,549),(1065,542),(1051,539),(1043,528),(1023,520),(990,511),(970,500),
(953,501),(935,516),(911,534),(899,551),(891,573),(883,580),(867,581),(859,575),
(858,571),(843,566),(830,553),(832,540),(828,527),(819,520),(825,513),(839,506),
(842,495),(843,474),(844,468),(854,468),(877,467),(891,460),(895,452),(901,452),
(906,447),(909,443),(909,441),(915,435),(912,430),(914,429),(908,423),(904,421),
(899,418),(893,417),(879,409),(854,400),(842,390),(842,377),(839,362),(836,362),
(820,360),(812,352),(812,337),(812,307),(814,288),(815,282),(827,280),(834,284),
(850,282),(873,277),(889,280),(891,284),(891,301),(897,320),(903,324),(916,320),
(925,310),(935,314),(953,325),(967,337),(976,345),(981,346),(986,362),(999,378),
(1006,385),(1007,387),(1008,387),(1015,382),(1017,382),(1018,381),(1022,386),
(1021,401),(1008,413),(1009,425),(1014,426),(1031,425),(1038,429),(1047,425),
(1053,429),(1067,426),(1076,425),(1090,427),(1099,424),(1113,426),(1134,427),
(1147,431),(1150,430),(1152,437),(1147,438),(1128,438),(1105,443),(1093,450),
(1089,453),(1085,449),(1075,452),(1064,460),(1055,458),(1052,462),(1049,460),
(1042,464),(1025,463),(1015,463),(1010,470),(1013,471),(1021,472),(1027,476),
(1033,477),(1042,484),(1052,480),(1059,486),(1076,487),(1099,497),(1134,510),
(1169,523),(1191,535),(1205,540),(1210,539),(1210,528),(1210,502),(1210,461),
(1209,409),(1208,372),(1207,349),(1206,341),(1192,335),(1165,327),(1132,310),
(1084,293),(1045,273),(997,256),(961,240),(934,229),(922,218),(919,201),
(917,197),(906,199),(892,212),(876,212),(845,212),(809,212),(781,219),(768,226),
(768,235),(768,259),(768,298),(768,352),(768,421),(769,489),(769,543),(769,582),
(769,606),(769,615),(775,615),(796,615),(832,615),(883,615),(949,615),
(1030,615),(1110,615),(1175,615),(1225,615),(1261,614),(1282,613),(1288,612),
(1296,598),(1296,577),(1296,541),(1296,490),(1296,424),(1296,343),(1296,264),
(1296,200),(1296,151),(1296,116),(1296,96),(1295,90),(1285,90),(1260,90),
(1220,90),(1165,90),(1095,90),(1010,90),(920,90),(844,90),(783,90),(737,90),
(706,90),(690,90),(688,89),(689,86),(681,78),(671,82),(663,90),(648,90),
(618,90),(573,90),(517,90),(476,90),(450,90),(438,89),(439,86),(431,78),
(421,82),(413,90),(398,90),(381,88),(369,78),(357,83),(353,90),(341,90),
(314,90),(297,88),(287,78),(277,82),(269,90),(254,90),(224,90),(179,90),
(123,90),(82,90),(56,90),(43,92),(43,96),(43,115),(43,149),(43,198),(43,262),
(43,341),(43,428),(43,500),(43,557),(43,599),(44,627),(45,640),(49,641),
(67,641),(100,641),(148,641),(211,641),(289,641),(382,641),(490,641),(613,641),
(750,641),(872,641),(979,641),(1071,641),(1148,641),(1212,640),(1261,639),
(1295,638),(1315,636),(1321,633),(1321,621),(1321,594),(1321,552),(1321,495),
(1321,423),(1321,336),(1321,254),(1321,187),(1321,135),(1321,98),(1321,75),
(1320,66),(1313,66),(1291,66),(1254,66),(1207,67),(1175,68),(1157,68),(1154,68),
(1154,75),(1146,75),(1123,75),(1102,74),(1096,73),(1096,69),(1091,66),(1074,66),
(1042,66),(1007,66),(986,65),(980,64),(980,60),(975,57),(958,57),(926,57),
(891,58),(871,59),(866,60),(865,66),(855,66),(830,66),(790,66),(735,66),
(667,66),(614,66),(575,66),(550,65),(540,64),(540,60),(535,57),(518,57),
(489,58),(474,60),(474,62),(472,66),(459,66),(431,66),(388,66),(330,66),
(269,66),(223,66),(191,66),(174,66),(171,65),(168,56),(158,55),(150,61),
(149,66),(138,66),(112,66),(98,63),(95,57),(83,57),(65,59),(61,62),(59,66),
(46,66),(25,67),(18,69),(18,79),(18,104),(18,144),(18,199),(18,269),(18,354),
(18,441),(18,513),(18,570),(18,612),(18,639),(19,652),(26,656),(38,663),
(58,663),(93,663),(143,663),(208,663),(288,663),(383,663),(493,663),(618,663),
(758,663),(884,663),(995,663),(1091,663),(1172,663),(1239,663),(1291,663),
(1328,663),(1350,663),(1358,662),(1361,651),(1376,637),(1378,621),(1374,597),
(1378,574),(1378,541),(1375,519),(1383,501),(1376,483),(1370,478),(1370,464),
(1373,438),(1379,400),(1379,366),(1369,337),(1369,303),(1369,272),(1368,255),
(1382,238),(1381,221),(1371,209),(1375,196),(1380,170),(1374,143),(1367,129),
(1372,112),(1373,85),(1365,64),(1358,57),(1356,41),(1353,39),(1350,41),
(1346,37),(1336,36),(1333,32),(1317,30),(1288,30),(1244,30),(1185,30),(1141,30),
(1102,22),(1057,22),(1026,21),(1005,23),(993,21),(988,25),(975,22),(972,24),
(959,21),(943,24),(937,29),(920,30),(889,30),(843,30),(788,30),(747,30),
(706,39),(664,36),(629,38),(591,34),(559,34),(538,30),(506,30),(465,30),
(431,22),(391,23),(356,22),(328,23),(308,30),(280,30),(237,30),(179,30),
(106,30),(30,28)]

Gwiazda skrzyżowana - PHP - 4083 + 440 = zdecydowanie za ciężki

Ok, po 3 tygodniach bez połączenia z Internetem (dzieje się tak, gdy jeden z najbardziej okrutnych konkurentów twojego dostawcy odpowiada za zatokę budowlaną, a przynajmniej tak dzieje się w Paryżu, Francja) Mogę wreszcie opublikować moja następna próba.

Tym razem użyłem algorytmu A * i bardziej wydajnej strategii dystrybucji punktów.
Jako dodatkowy bonus napisałem coś w rodzaju PHP Crunchera, aby rozwiązać golfową część wyzwania.

A teraz, gdy solver działa na wszystkich proponowanych mapach, błąd śledzenia linii został naprawiony.
Nigdy więcej przycinania ścian (choć nadal wypasuje się, tak jak powinien :)).

uruchomienie kodu

nadaj kodowi dowolną nazwę ( runner.phpna przykład), a następnie wywołaj go w następujący sposób:

php runner.php track.png

Po dłuższym milczeniu powinien wygenerować _track.pngwynik pokazujący rozwiązanie.

Jak widać na obrazach wyjściowych, kod jest bardzo wolny. Zostałeś ostrzeżony.

Oczywiście moja prywatna wersja jest pełna śladów i tworzy ładne przedstawienia różnych informacji (w tym okresowe zdjęcie pokazujące postęp A *, aby pomóc zabić czas), ale za grę w golfa trzeba zapłacić ...

kod do gry w golfa

<?php
define("_",15);define("a",1e3);class _{function _($a=0,$_=0){$this->a=$a;$this->_=$_;}function b(){return sqrt($this->a*$this->a+$this->_*$this->_);}function a(){$_=$this->b();if($_==0)$_=1;return new _($this->a/$_,$this->_/$_);}}class c{static$_=0;function c($_,$a,$b){$this->c=$b;$this->a=++c::$_;$this->_=new _($_,$a);a::$a[$_][$a]=$this;}function _($_){return(isset($this->b[$_->a]))?$this->b[$_->a]:$this->b[$_->a]=$_->b[$this->a]=a($_->_->a,$_->_->_,$this->_->a,$this->_->_);}}define("c",8/_);define("b",2/a);class d{function d($a,$b,$c=0,$d=0,$_=null){$this->a=$a;$this->_=$b;$this->f=$c;$this->e=$d;$this->d=$_;$this->b=$_==null?0:$_->b+a;$this->c=floor((sqrt(1+c*abs(a::$_[$a][$b]))-1)/b)-a;}}function a($c,$b,$g,$f){$e=$g-$c;$d=$f-$b;$_=2*max(abs($e),abs($d));if($_==0)return 1;$c+=.5;$b+=.5;for($a=1;$a<=$_;$a++)if(!isset(a::$_[$c+$a/$_*$e][$b+$a/$_*$d]))return 0;return 1;}class b{static$a,$_;function _($l,$_,$k){$g=log(.5)/log($l/$_);for($a=-$_;$a<=$_;$a++)for($b=-$_;$b<=$_;$b++){$d=sqrt($a*$a+$b*$b);if($d>=$_)continue;$j=pow(sin(M_PI*pow($d/$_,$g)),$k);$c=new _($a,$b);$i=$c->a();$c->b=$d;$c->d=$j*$i->a;$c->c=$j*$i->_;$h[]=$c;}usort($h,function($b,$a){$_=$b->b-$a->b;return($_>0)?1:(($_<0)?-1:0);});foreach($h as$e)b::$a[$e->b][]=$e;for($a=-$_;$a<=$_;$a++)for($b=-$_;$b<=$_;$b++){$e=new _($a,$b);$d=sqrt($a*$a+$b*$b);for($f=$_;$f>=$d;$f--)b::$_[$f][]=$e;}foreach(b::$_ as$g=>$m)usort(b::$_[$g],function($b,$a){$_=$b->b()-$a->b();return($_<0)?-1:(($_>0)?1:0);});}}b::_(2.5,6,8);class a{static$a,$_;static function _($S){$k=imagecreatefrompng($S);for($a=0;$a!=imagesx($k);$a++)for($_=0;$_!=imagesy($k);$_++){$n=0;$o=imagecolorat($k,$a,$_);if($o==0){$d_[]=new _($a,$_);$n=1;}else if($o==0xFFFF00){$e_[]=new _($a,$_);$n=2;}else{$m=($o>>16)&0xFF;$c_=($o>>8)&0xFF;$a_=$o&0xFF;if($m==$c_&&$m==$a_&&$m>=30&&$m<=220)$n=3;}if($n){$Z[$a][$_]=1;if($n!=3)$b_[]=new c($a,$_,$n);}}for($a=-_;$a<=_;$a++)for($_=-_;$_<=_;$_++)if(abs($a)+abs($_)<=_)$f_[]=new _($a,$_);$l_=array(new _(-1,0),new _(1,0),new _(0,-1),new _(0,1));foreach($d_ as$v){$c[]=new _($v->a,$v->_);a::$_[$v->a][$v->_]=0;}while(count($c)){$t=array_shift($c);$g_=a::$_[$t->a][$t->_]+1;foreach($l_ as$e){$f=$t->a+$e->a;$j=$t->_+$e->_;if(!isset($Z[$f][$j]))continue;if(isset(a::$_[$f][$j]))continue;a::$_[$f][$j]=$g_;$c[]=new _($f,$j);}}foreach(a::$_ as$a=>$g)foreach($g as$_=>$q){$i=0;$E=$H=0;foreach(b::$a as$n_=>$J){foreach($J as$b){if(!isset(a::$_[$a+$b->a][$_+$b->_])){$E+=$b->d;$H+=$b->c;$i++;}}if($i!=0){$E/=$i;$H/=$i;break;}}$W[$a][$_]=new _($E,$H);}foreach(a::$_ as$a=>$g)foreach($g as$_=>$q){$T=$W[$a][$_];$u=$T->a();$R=0;$i=0;foreach(b::$_[1]as$e){@$b=$W[$a+$e->a][$_+$e->_];if(!$b)continue;$V=$b->a();$d=$e->a();$R-=($u->a*$V->_-$u->_*$V->a)*($u->a*$d->_-$u->_*$d->a);$i++;}$p[$a][$_]=(12*$R/$i+1)*$T->b();}$m_=1;$Y=6;$x=0;foreach($p as$a=>$g)foreach($g as$_=>$q)$x=max($x,$q);$h_=($m_-$Y)/$x;foreach($p as$a=>$g)foreach($g as$_=>$q)$X[($Y+$h_*max($q,0))*1e5][]=new _($a,$_);ksort($X);foreach($X as$m=>$J)foreach($J as$b){$a=$b->a;$_=$b->_;if(!isset($p[$a][$_]))continue;$b_[]=new c($a,$_,3);unset($p[$a][$_]);$k_=0;foreach(b::$_[$m/1e5]as$U){$f=$a+$U->a;$j=$_+$U->_;if(a($a,$_,$f,$j))unset($p[$f][$j]);else if(++$k_==2)break;}}foreach($e_ as$s){$e=new d($s->a,$s->_);$c[$e->b+$e->c][]=$e;$y[$s->a." ".$s->_." 0 0"]=$e;}ksort($c);while(count($c)){reset($c);$z=key($c);$r=array_shift($c[$z]);if(empty($c[$z]))unset($c[$z]);$A=$r->a;$C=$r->_;$M=$r->f;$O=$r->e;$i_=a::$a[$A][$C];$l="$A $C $M $O";unset($y[$l]);$j_[$l]=1;foreach($f_ as$P){$B=$M+$P->a;$D=$O+$P->_;$G=$A+$B;$F=$C+$D;@$I=a::$a[$G][$F];if(!$I)continue;$l="$G $F $B $D";if(@$j_[$l]||@$y[$l])continue;if(!$I->_($i_))continue;$d=new d($G,$F,$B,$D,$r);$b=$d->b+$d->c;$__=!isset($c[$b]);$c[$b][]=$d;if($__)ksort($c);$y[$l]=$d;if($I->c==1){for($h=array();$d!=null;$d=$d->d)array_unshift($h,$d);$N=$h[0]->a;$K=$h[0]->_;for($w=1;$w!=count($h);$w++){$L=$h[$w]->a;$Q=$h[$w]->_;imageline($k,$N,$K,$L,$Q,0xFFFFFF);$N=$L;$K=$Q;}foreach($h as$b)imagesetpixel($k,$b->a,$b->_,0xFF);imagepng($k,"_".$S);return;}}}}}ini_set("memory_limit","3G");a::_($argv[1]);

wersja bez golfa

<?php
define ("ACCEL_MAX", 15);   // maximal acceleration value
define ("MOVE_UNIT", 1000); // heuristic distance to goal precision

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

    function norm () { return sqrt ($this->x*$this->x + $this->y*$this->y); }

    function normalized() { $n=$this->norm(); if ($n == 0) $n=1; return new Point ($this->x / $n, $this->y / $n); }
}

class Waypoint {
    static $id = 0;

    function __construct ($x, $y, $type)
    {
        // create waypoint
        $this->type = $type;
        $this->id = ++self::$id;
        $this->center = new Point ($x, $y);

        // update waypoint lookup map
        Map::$waypoint_lookup[$x][$y] = $this;
    }

    function can_reach ($target)
    {
        return (isset($this->reachable[$target->id])) 
            ? $this->reachable[$target->id]
            : $this->reachable[$target->id] = $target->reachable[$this->id] = on_track ($target->center->x, $target->center->y, $this->center->x, $this->center->y);
    }
}

define ("L", 8/ACCEL_MAX);
define ("M", 2/MOVE_UNIT);
class Node {
    function __construct ($x, $y, $speedx=0, $speedy=0, $parent=null)
    {
        $this->x = $x;
        $this->y = $y;
        $this->speedx = $speedx;
        $this->speedy = $speedy;
        $this->parent = $parent;

        // previous moves
        $this->moves = $parent == null ? 0 : $parent->moves+MOVE_UNIT;

        // remaining moves heuristic estimation
        $this->dist = floor((sqrt (1+L*abs(Map::$dist_to_goal[$x][$y])) - 1)/M) - MOVE_UNIT;
    }
}

function on_track ($ox, $oy, $ex, $ey)
{
    $sx = $ex - $ox;
    $sy = $ey - $oy;
    $range = 2*max (abs ($sx), abs ($sy));
    if ($range == 0) return 1;
    $ox+=.5;
    $oy+=.5;
    for ($s = 1 ; $s <= $range ; $s++) if (!isset (Map::$dist_to_goal[$ox + $s/$range*$sx][$oy + $s/$range*$sy])) return 0;
    return 1;
}

class Border {
    static $circle, $area;

    function init ($dopt, $dmax, $erf)
    {
        $k = log (.5)/log($dopt/$dmax);

        for ($x = -$dmax ; $x <= $dmax ; $x++)
        for ($y = -$dmax ; $y <= $dmax ; $y++)
        {
            $d = sqrt ($x*$x+$y*$y);
            if ($d >= $dmax) continue;
            $i = pow(sin (M_PI*pow($d/$dmax,$k)),$erf); // a function that will produce a kind of asymetric gaussian
            $pt = new Point($x,$y);
            $pn = $pt->normalized();
            $pt->d = $d;
            $pt->ix = $i * $pn->x;
            $pt->iy = $i * $pn->y;
            $points[] = $pt;
        }
        usort ($points, function ($a,$b) { $d = $a->d - $b->d; return ($d > 0) ? 1 : (($d < 0) ? -1 : 0); });
        foreach ($points as $p) self::$circle[$p->d][] = $p;

        for ($x = -$dmax ; $x <= $dmax ; $x++)
        for ($y = -$dmax ; $y <= $dmax ; $y++)
        {
            $p = new Point ($x, $y);
            $d = sqrt ($x*$x+$y*$y);
            for ($r = $dmax ; $r >= $d ; $r--) self::$area[$r][] = $p;
        }
        foreach (self::$area as $k=>$a) usort (self::$area[$k], function ($a,$b) { $d = $a->norm()-$b->norm(); return ($d < 0) ? -1 : (($d > 0) ? 1 : 0); });
    }
}
Border::init(2.5,6,8);

class Map {
    static
        $waypoint_lookup, // retrieve waypoint from a position
        $dist_to_goal;    // upper bound of distance to closest goal for each track point
                          // also used to check if a point is on track

/*      
    const NONE  = 0;  // terrain types
    const GOAL  = 1;
    const START = 2;
    const TRACK = 3;
*/      
    static function solve ($filename)
    {
        // read map definition
        $img = imagecreatefrompng ($filename);// or die ("could not read $filename");
        $img_dx = imagesx ($img);
        $img_dy = imagesy ($img);

        // extract track pixels
        for ($x = 0 ; $x != $img_dx ; $x++)
        for ($y = 0 ; $y != $img_dy ; $y++)
        {
            $type = 0 /*Map::NONE*/;
            $color = imagecolorat ($img, $x, $y);
            if      ($color  ==        0) { $goals [] = new Point ($x, $y); $type = 1 /*Map::GOAL*/;  }
            else if ($color  == 0xFFFF00) { $starts[] = new Point ($x, $y); $type = 2 /*Map::START*/; }
            else
            {
                $r = ($color >> 16) & 0xFF;
                $g = ($color >>  8) & 0xFF;
                $b =  $color        & 0xFF;
                if ($r == $g && $r == $b && $r >= 30 && $r <= 220) $type = 3 /*Map::TRACK*/;
            }
            if ($type /* != Map::NONE */)
            {
                $track[$x][$y] = 1; // mark all track points
                if ($type != 3 /*Map::TRACK*/) $waypoints[] = new Waypoint ($x, $y, $type); // add start and goal positions as waypoints
            }
        }

        // compute possible acceleration values
        for ($x = -ACCEL_MAX ; $x <= ACCEL_MAX ; $x++)
        for ($y = -ACCEL_MAX ; $y <= ACCEL_MAX ; $y++)
            if (abs ($x) + abs ($y) <= ACCEL_MAX) $acceleration[] = new Point ($x, $y);

        // compute goal distance
        $neighbours = array (new Point (-1, 0), new Point (1, 0), new Point (0, -1), new Point (0, 1)); 
        foreach ($goals as $goal)
        {
            $border[] = new Point ($goal->x, $goal->y);
            Map::$dist_to_goal[$goal->x][$goal->y] = 0;
        }
        while (count ($border))
        {
            $pos = array_shift ($border);
            $dist = Map::$dist_to_goal[$pos->x][$pos->y] + 1;
            foreach ($neighbours as $n)
            {
                $nx = $pos->x + $n->x;
                $ny = $pos->y + $n->y;
                if (!isset ($track[$nx][$ny])) continue;
                if (isset (Map::$dist_to_goal[$nx][$ny])) continue;
                Map::$dist_to_goal[$nx][$ny] = $dist;
                $border[] = new Point ($nx, $ny);
            }
        }

        // compute wall distance vector field
        foreach (self::$dist_to_goal as $x=>$col)
        foreach ($col as $y=>$c)
        {
            $num = 0;
            $ix = $iy = 0;
            foreach (Border::$circle as $d=>$points)
            {
                foreach ($points as $p)
                {
                    if (!isset (Map::$dist_to_goal[$x+$p->x][$y+$p->y]))
                    {
                        $ix += $p->ix;
                        $iy += $p->iy;
                        $num++;
                    }
                }
                if ($num != 0)
                {
                    $ix /= $num;
                    $iy /= $num;
                    break;
                }
            }
            $wall_vector[$x][$y] = new Point ($ix, $iy);
        }

        // compute local curvature and deduce desired waypoint density
        foreach (self::$dist_to_goal as $x=>$col)
        foreach ($col as $y=>$c)
        {
            $o = $wall_vector[$x][$y];
            $oo = $o->normalized();
            $curvature = 0;
            $num = 0;
            foreach (Border::$area[1] as $n)
            {
                @$p = $wall_vector[$x+$n->x][$y+$n->y];
                if (!$p) continue;
                $pp = $p->normalized();
                $nn = $n->normalized();
                $curvature -= ($oo->x*$pp->y-$oo->y*$pp->x) * ($oo->x*$nn->y-$oo->y*$nn->x);
                $num++;
            }
            $waypoint_density[$x][$y] = (12*$curvature/$num + 1) * $o->norm(); // a wierd mix of curvature and wall distance
        }

        // compute track waypoints
        $rmin = 1;
        $rmax = 6;
        $c_max = 0;
        foreach ($waypoint_density as $x=>$col)
        foreach ($col as $y=>$c)
            $c_max = max ($c_max, $c);
        $ra = ($rmin-$rmax)/$c_max;
        foreach ($waypoint_density as $x=>$col)
        foreach ($col as $y=>$c)
            $placement[($rmax + $ra * max ($c, 0))*1e5][] = new Point ($x, $y);
        ksort($placement);
//var_dump($placement);exit(0);
        foreach ($placement as $r=>$points)
        foreach ($points as $p)
        {
            $x = $p->x;
            $y = $p->y;
            if (!isset ($waypoint_density[$x][$y])) continue;
            $waypoints[] = new Waypoint ($x, $y, 3 /*Map::TRACK*/);
            unset ($waypoint_density[$x][$y]);
            $out=0;
            foreach (Border::$area[$r/1e5] as $delta)
            {
                $nx = $x+$delta->x;
                $ny = $y+$delta->y;
                if (on_track ($x, $y, $nx, $ny)) unset ($waypoint_density[$nx][$ny]);
                else if (++$out == 2) break;
            }
        }

        // unleash the mighty A*
//$begining=microtime(true);
        foreach ($starts as $start)
        {
            $n = new Node ($start->x, $start->y);
            $border[$n->moves+$n->dist][] = $n;
            $open[$start->x." ".$start->y." 0 0"] = $n;
        }
        ksort ($border);
        while (count ($border))
        {
            // get one of the most prioritary nodes
            reset ($border);
            $p_list = key ($border);
            $node = array_shift ($border[$p_list]);
            if (empty ($border[$p_list])) unset ($border[$p_list]);

            $px = $node->x;
            $py = $node->y;
            $vx = $node->speedx;
            $vy = $node->speedy;
            $current = Map::$waypoint_lookup[$px][$py];

            // move node from open to closed list
            $signature = "$px $py $vx $vy";
            unset ($open[$signature]);
            $closed[$signature] = 1;

            // try all possible accelerations
            foreach ($acceleration as $a)
            {
                $nvx = $vx + $a->x;
                $nvy = $vy + $a->y;
                $npx = $px + $nvx;
                $npy = $py + $nvy;

                // select waypoints within reach
                @$waypoint = Map::$waypoint_lookup[$npx][$npy];
                if (!$waypoint) continue;

                // skip already know nodes
                $signature = "$npx $npy $nvx $nvy";
                if (@$closed[$signature] || @$open[$signature]) continue;

                // check track geometry
                if (!$waypoint->can_reach ($current)) continue;

                // insert new node into priority list
                $nn = new Node ($npx, $npy, $nvx, $nvy, $node);
                $p = $nn->moves+$nn->dist;
                $resort = !isset($border[$p]);
                $border[$p][] = $nn;
                if ($resort) ksort ($border);
                $open[$signature] = $nn;

                // check termination
                if ($waypoint->type == 1 /*Map::GOAL*/)
                {
                    for ($path=array() ; $nn != null ; $nn = $nn->parent) array_unshift ($path, $nn);
                    $ox = $path[0]->x;
                    $oy = $path[0]->y;
                    for ($i = 1 ; $i != count($path) ; $i++)
                    {
                        $ex = $path[$i]->x;
                        $ey = $path[$i]->y;
                        imageline ($img, $ox, $oy, $ex, $ey, 0xFFFFFF);
                        $ox = $ex; $oy = $ey;
                    }
                    foreach ($path as $p) imagefilledellipse ($img, $p->x, $p->y, 2, 2, 0xFF);
                    imagepng ($img, "_".$filename);
//echo (count($path)-1)." moves, ".count($waypoints)." waypoints, ".count($closed)."+".count($open)." nodes, ".(round((microtime(true)-$begining)*100)/100)."s, ".round(memory_get_usage(true)/1024)."K";
                    return;
                }
            }
        }
    }
}

ini_set("memory_limit","2G"); // just in case...
Map::solve ($argv[1]);
?>

Wyniki

Zdjęcia są tworzone przez bogatszą wersję, która wyświetla dokładnie to samo rozwiązanie z pewnymi statystykami na dole (i rysuje ścieżkę za pomocą antyaliasingu).

Mapa miasta jest dość dobrym przykładem tego, dlaczego algorytmy oparte na pozycji muszą w wielu przypadkach znaleźć słabe wyniki: krótszy nie zawsze oznacza szybszy.

(672 ruchów, jeśli nie chcesz powiększać)

ZA*

Ku mojemu zaskoczeniu, A * radzi sobie dość dobrze na przestrzeni prędkości i pozycji. W każdym razie lepsze niż BFS.

Musiałem jednak trochę się pocić, aby uzyskać działający heurystyczny szacunek odległości.

Musiałem to nieco zoptymalizować, ponieważ liczba możliwych stanów jest ogromna (kilka milionów) w porównaniu z wariantem tylko pozycji, który ponownie wymaga więcej kodu.

Dolna granica wybrana dla liczby ruchów niezbędnych do osiągnięcia celu z danej pozycji to po prostu czas potrzebny do pokonania odległości do najbliższego celu w linii prostej z zerową prędkością początkową .

Oczywiście ścieżka linii prostej zwykle prowadzi bezpośrednio do ściany, ale jest to mniej więcej ten sam problem, co użycie prostej odległości euklidesowej do wyszukiwania A * tylko w przestrzeni.
Podobnie jak odległość euklidesowa dla wariantów zajmujących tylko przestrzeń, główną zaletą tej metryki, oprócz tego, że dopuszczalne jest użycie najbardziej wydajnego wariantu A * (z zamkniętymi węzłami), wymaga bardzo niewielkiej analizy topologicznej toru.

Przy maksymalnym przyspieszeniu A liczba n ruchów potrzebnych do pokonania odległości d jest najmniejszą liczbą całkowitą spełniającą zależność:

d <= A n (n + 1) / 2

Rozwiązanie tego dla n daje oszacowanie pozostałej odległości.

Aby to obliczyć, tworzona jest mapa odległości do najbliższego celu, przy użyciu algorytmu wypełniania zalewem obsadzonego pozycjami celów.
Ma przyjemny efekt uboczny polegający na eliminowaniu punktów toru, z których nie można osiągnąć celu (jak to ma miejsce w niektórych obszarach toru koszmaru).
Liczba ruchów jest obliczana jako wartość zmiennoprzecinkowa, dzięki czemu węzły bliżej celu mogą być dalej dyskryminowane.

Punkty trasy

Podobnie jak w mojej poprzedniej próbie, pomysł polega na zmniejszeniu liczby punktów trasy do jak najmniejszej podpróbki punktów drogi. Sztuką jest wybranie najbardziej „przydatnych” pozycji na torze.

Heurystyka zaczyna się od regularnego podziału na całą ścieżkę, ale zwiększa gęstość w dwóch rodzajach obszarów:

1. krawędź toru, tj. pasy biegnące 1 lub 2 piksele od ścian
2. strefy o wysokiej krzywiźnie, tj. wewnętrzna krawędź ostrych zakrętów.

Oto przykład.
Obszary o wysokiej gęstości są w kolorze czerwonym, a obszary o niskiej gęstości w kolorze zielonym. Niebieskie piksele to wybrane punkty.
Zwróć uwagę na skupiska punktów na ostrych zakrętach (wśród wielu bezużytecznych plam na pochyłych łukach, z powodu niewystarczającego filtrowania).

Aby obliczyć pozycje pasów ruchu, cała ścieżka jest skanowana w poszukiwaniu odległości do najbliższej ściany. Wynikiem jest pole wektorów wskazujące w kierunku najbliższej granicy ścieżki.
To pole wektorowe jest następnie przetwarzane w celu zgrubnego oszacowania lokalnej krzywizny.
Wreszcie, krzywizna i odległość do ściany są łączone, aby uzyskać pożądaną lokalną gęstość, a raczej niezgrabny algorytm próbuje odpowiednio przelać punkty na ścieżce.

Istotną poprawą w stosunku do poprzedniej strategii jest to, że wąskie pasy zawsze (jak się wydaje) zawsze będą miały wystarczającą liczbę punktów do przejechania, co pozwala poruszać się po mapie koszmaru.

Jak zawsze chodzi o znalezienie optymalnego punktu między czasem obliczeń a wydajnością.
Zmniejszenie gęstości o 50% spowoduje podzielenie czasu obliczeń przez więcej niż 4, ale z grubszymi wynikami (48 ruchów zamiast 44 w mieście, 720 zamiast 670 w koszmarze).

Gra w golfa

Nadal uważam, że gra w golfa szkodzi kreatywności w tym konkretnym przypadku: usunięcie antyaliasingu z wyjścia wystarczy, aby zdobyć 30 punktów i wymaga dużo mniej wysiłku niż przejście z 47 do 44 ruchów na mapie miasta.
Nawet przejście od 720 do 670 ruchów w koszmarze zyskałoby zaledwie 500 punktów, choć bardzo wątpię, aby A * tylko pozycja był w stanie zbliżyć się do tego miejsca.

Dla zabawy postanowiłem napisać własny kompresor PHP.

Jak się wydaje, wydajna zmiana nazwy identyfikatorów w PHP nie jest łatwym zadaniem. W rzeczywistości nie sądzę, że można to zrobić w ogólnym przypadku. Nawet przy pełnej analizie semantycznej możliwość użycia ciągów lub zmiennych pośrednich do wyznaczenia obiektów wymagałaby znajomości semantyki każdej funkcji.
Ponieważ jednak bardzo wygodny wbudowany parser pozwala od razu przejść do analizy semantycznej, udało mi się stworzyć coś, co wydaje się działać na podzbiorze PHP wystarczającym do napisania kodu „golfable” (trzymaj się z dala od $$ i nie użyj pośrednich wywołań funkcji lub innego dostępu do obiektów przez łańcuch).
Nie ma praktycznego zastosowania do mówienia i nie ma nic wspólnego z pierwotnym problemem, ale dużo zabawy z kodowaniem.

Mogłem zmodyfikować kod, aby uzyskać dodatkowe 500 znaków, ale ponieważ nazwy bibliotek graficznych PHP są niestety dość długie, jest to rodzaj trudnej walki.

Dalsze zmiany

Kod wyboru punktu trasy to przerażający bałagan, dostrajany metodą prób i błędów. Podejrzewam, że wykonanie większej liczby obliczeń matematycznych (przy użyciu odpowiednich operatorów gradientu i zawijania) znacznie poprawiłoby ten proces.

Jestem ciekawy, czy można znaleźć lepszą heurystykę na odległość. Próbowałem wziąć pod uwagę prędkość na kilka sposobów, ale albo złamał A *, albo przyniósł wolniejsze wyniki.

Może być możliwe przekodowanie tego wszystkiego w szybszym języku, takim jak C ++, ale wersja PHP w dużej mierze opiera się na wyrzucaniu elementów bezużytecznych, aby utrzymać rozsądne zużycie pamięci. Czyszczenie zamkniętych węzłów w C ++ wymagałoby sporo pracy i znacznej ilości dodatkowego kodu.

Gdyby ocena opierała się na wynikach, chętnie próbowałbym ulepszyć algorytmy. Ale ponieważ kryterium gry w golfa jest tak przytłaczające, nie ma sensu, prawda?

ThirdRacer Java (1224 + 93 * 10 = 2154)

Podobne do SecondRacer. Ale zmiana fokusu z prędkości na rozmiar kodu (ale nadal przy użyciu Java). Optymalizacja przyspieszenia jest teraz znacznie uproszczona, co niestety skutkuje wolniejszym samochodem.

Wydajność

Lepsze niż SecondRacer.

Styl ścieżki

Jak SecondRacer.

Styl kodu

Weszłam w tryb ciężkiej walki.

golfed -> OSTRZEŻENIE: zastępuje oryginalny plik w miejscu!

import javax.imageio.*;class A{class B extends java.util.Vector<C>{};class
C{int D,E;}C F(int D,int E){G=new C();G.D=D;G.E=E;return G;}static java.awt.image.BufferedImage
H;int I=H.getWidth(),J=H.getHeight(),K[][]=new int[I][J],L,M,N,O,P=~0xffff00,Q,D,E,R,S,T,U,V=255,W,X,Y;C
Z,G;public static void main(String[]a)throws Exception{java.io.File b=new
java.io.File(a[0]);H=ImageIO.read(b);new A().c();ImageIO.write(H,"PNG",b);}void
c(){B d=new B();for(L=0;L<I;L++)for(M=0;M<J;M++)if(e(L,M)!=1||!d.add(F(L,M)))K[L][M]=-1>>>1;while(M!=3)for(Z=d.remove(N=0),D=Z.D,E=Z.E;N<9;N++)if((M=e(T=D+N/3-1,U=E+N%3-1))>0&&K[T][U]>(L=K[D][E]+(T==D||U==E?10:14))&&d.add(F(T,U)))K[T][U]=L;for(D=G.D,E=G.E,R=D,S=E;M!=4;){H.createGraphics().drawLine(R,S,D,E);H.setRGB(R,S,P);N=0;T=2-M%2;U=0;for(L=0;L<Q;L++,N+=T)if((N+T)*(N+T)/30.0>Q-L+7||N-O>15-T){H.setRGB(R+L*(M/3-1),S+L*(M%3-1),P);U=L;O=N;N=0;}O=T*(U-Q);R=D;S=E;M=4;double
f=0,g;for(N=0;N<9;N++)for(L=1;e(T=R+L*(N/3-1),U=S+L*(N%3-1))>0;L++)if(f>(g=K[T][U]-K[R][S]+5*java.lang.Math.sqrt((R-T)*(R-T)+(S-U)*(S-U)))){f=g;D=T;E=U;M=N;Q=L;}}H.setRGB(R,S,P);}int
e(int D,int E){return D<0||D>=I||E<0||E>=J?0:(W=H.getRGB(D,E))==~V?1:W==V<<24?3:30<=(X=W>>16&V)&&X<=220&&X==(Y=W>>8&V)&&Y==(V&W)?2:0;}}

Miasto S + 93

Gwiazda skrzyżowała ścieżkę wyścigową na mapie koszmaru

(zgodnie z popularnym żądaniem)

(kod nie został zaktualizowany, ponieważ modyfikacje są trywialne, a wyzwanie polegające wyłącznie na wydajności nie jest rozgrywane)

Przepraszam, że opublikowałem kolejny wpis, ale osiągam limit 30 000 znaków w stosunku do poprzedniego.
Po prostu powiedz słowo, a ja je usunę.

  1: 112 154 -> 127 154
  2: 127 154 -> 142 154
  3: 142 154 -> 151 161
  4: 151 161 -> 149 171
  5: 149 171 -> 143 190
  6: 143 190 -> 131 208
  7: 131 208 -> 125 219
  8: 125 219 -> 132 230
  9: 132 230 -> 147 243
 10: 147 243 -> 169 249
 11: 169 249 -> 185 248
 12: 185 248 -> 190 251
 13: 190 251 -> 190 263
 14: 190 263 -> 194 282
 15: 194 282 -> 201 289
 16: 201 289 -> 219 299
 17: 219 299 -> 240 297
 18: 240 297 -> 256 289
 19: 256 289 -> 271 267
 20: 271 267 -> 283 241
 21: 283 241 -> 297 228
 22: 297 228 -> 315 226
 23: 315 226 -> 343 229
 24: 343 229 -> 370 246
 25: 370 246 -> 393 263
 26: 393 263 -> 415 270
 27: 415 270 -> 435 267
 28: 435 267 -> 454 251
 29: 454 251 -> 464 240
 30: 464 240 -> 468 238
 31: 468 238 -> 472 247
 32: 472 247 -> 475 270
 33: 475 270 -> 481 302
 34: 481 302 -> 489 323
 35: 489 323 -> 489 343
 36: 489 343 -> 476 365
 37: 476 365 -> 455 380
 38: 455 380 -> 437 389
 39: 437 389 -> 432 398
 40: 432 398 -> 437 405
 41: 437 405 -> 450 411
 42: 450 411 -> 462 430
 43: 462 430 -> 465 454
 44: 465 454 -> 457 482
 45: 457 482 -> 453 503
 46: 453 503 -> 460 523
 47: 460 523 -> 469 530
 48: 469 530 -> 485 530
 49: 485 530 -> 505 526
 50: 505 526 -> 514 522
 51: 514 522 -> 523 533
 52: 523 533 -> 526 552
 53: 526 552 -> 527 572
 54: 527 572 -> 531 581
 55: 531 581 -> 535 577
 56: 535 577 -> 539 559
 57: 539 559 -> 542 527
 58: 542 527 -> 544 481
 59: 544 481 -> 550 425
 60: 550 425 -> 558 356
 61: 558 356 -> 565 296
 62: 565 296 -> 572 250
 63: 572 250 -> 575 213
 64: 575 213 -> 575 188
 65: 575 188 -> 565 168
 66: 565 168 -> 567 147
 67: 567 147 -> 569 141
 68: 569 141 -> 574 144
 69: 574 144 -> 582 158
 70: 582 158 -> 587 160
 71: 587 160 -> 592 148
 72: 592 148 -> 593 139
 73: 593 139 -> 597 141
 74: 597 141 -> 605 151
 75: 605 151 -> 616 165
 76: 616 165 -> 616 177
 77: 616 177 -> 609 181
 78: 609 181 -> 599 174
 79: 599 174 -> 592 168
 80: 592 168 -> 591 171
 81: 591 171 -> 589 188
 82: 589 188 -> 591 216
 83: 591 216 -> 595 257
 84: 595 257 -> 599 312
 85: 599 312 -> 605 367
 86: 605 367 -> 611 408
 87: 611 408 -> 614 438
 88: 614 438 -> 609 461
 89: 609 461 -> 597 477
 90: 597 477 -> 594 499
 91: 594 499 -> 604 520
 92: 604 520 -> 605 536
 93: 605 536 -> 598 556
 94: 598 556 -> 598 569
 95: 598 569 -> 610 580
 96: 610 580 -> 622 581
 97: 622 581 -> 629 582
 98: 629 582 -> 636 568
 99: 636 568 -> 642 541
100: 642 541 -> 645 526
101: 645 526 -> 645 517
102: 645 517 -> 634 505
103: 634 505 -> 636 493
104: 636 493 -> 639 467
105: 639 467 -> 641 427
106: 641 427 -> 644 373
107: 644 373 -> 648 309
108: 648 309 -> 651 258
109: 651 258 -> 652 218
110: 652 218 -> 652 190
111: 652 190 -> 647 167
112: 647 167 -> 645 147
113: 645 147 -> 645 138
114: 645 138 -> 655 134
115: 655 134 -> 670 137
116: 670 137 -> 675 142
117: 675 142 -> 676 156
118: 676 156 -> 679 168
119: 679 168 -> 680 178
120: 680 178 -> 667 188
121: 667 188 -> 661 195
122: 661 195 -> 663 208
123: 663 208 -> 667 233
124: 667 233 -> 671 271
125: 671 271 -> 676 322
126: 676 322 -> 681 386
127: 681 386 -> 687 445
128: 687 445 -> 693 492
129: 693 492 -> 695 530
130: 695 530 -> 698 554
131: 698 554 -> 701 565
132: 701 565 -> 704 564
133: 704 564 -> 707 548
134: 707 548 -> 709 518
135: 709 518 -> 710 474
136: 710 474 -> 716 420
137: 716 420 -> 720 355
138: 720 355 -> 724 305
139: 724 305 -> 724 266
140: 724 266 -> 726 239
141: 726 239 -> 727 225
142: 727 225 -> 729 224
143: 729 224 -> 732 235
144: 732 235 -> 734 260
145: 734 260 -> 734 296
146: 734 296 -> 734 347
147: 734 347 -> 734 413
148: 734 413 -> 734 479
149: 734 479 -> 734 533
150: 734 533 -> 735 573
151: 735 573 -> 735 599
152: 735 599 -> 732 616
153: 732 616 -> 729 618
154: 729 618 -> 713 618
155: 713 618 -> 683 618
156: 683 618 -> 638 618
157: 638 618 -> 578 618
158: 578 618 -> 503 618
159: 503 618 -> 413 618
160: 413 618 -> 320 618
161: 320 618 -> 242 618
162: 242 618 -> 179 618
163: 179 618 -> 131 618
164: 131 618 ->  98 618
165:  98 618 ->  80 618
166:  80 618 ->  72 617
167:  72 617 ->  69 606
168:  69 606 ->  69 585
169:  69 585 ->  69 549
170:  69 549 ->  69 498
171:  69 498 ->  69 432
172:  69 432 ->  69 351
173:  69 351 ->  69 276
174:  69 276 ->  69 216
175:  69 216 ->  69 171
176:  69 171 ->  69 141
177:  69 141 ->  69 126
178:  69 126 ->  75 118
179:  75 118 ->  87 118
180:  87 118 -> 114 118
181: 114 118 -> 156 118
182: 156 118 -> 213 118
183: 213 118 -> 285 118
184: 285 118 -> 372 118
185: 372 118 -> 474 118
186: 474 118 -> 591 118
187: 591 118 -> 701 120
188: 701 120 -> 800 120
189: 800 120 -> 884 120
190: 884 120 -> 953 120
191: 953 120 -> 1007 120
192: 1007 120 -> 1049 120
193: 1049 120 -> 1076 120
194: 1076 120 -> 1089 120
195: 1089 120 -> 1092 123
196: 1092 123 -> 1087 132
197: 1087 132 -> 1073 145
198: 1073 145 -> 1046 160
199: 1046 160 -> 1015 164
200: 1015 164 -> 986 156
201: 986 156 -> 964 150
202: 964 150 -> 954 147
203: 954 147 -> 951 151
204: 951 151 -> 959 156
205: 959 156 -> 981 162
206: 981 162 -> 996 169
207: 996 169 -> 1002 182
208: 1002 182 -> 997 194
209: 997 194 -> 986 208
210: 986 208 -> 988 222
211: 988 222 -> 995 226
212: 995 226 -> 1013 226
213: 1013 226 -> 1044 224
214: 1044 224 -> 1079 229
215: 1079 229 -> 1103 238
216: 1103 238 -> 1119 245
217: 1119 245 -> 1133 243
218: 1133 243 -> 1147 256
219: 1147 256 -> 1153 270
220: 1153 270 -> 1160 270
221: 1160 270 -> 1162 260
222: 1162 260 -> 1165 237
223: 1165 237 -> 1182 213
224: 1182 213 -> 1210 185
225: 1210 185 -> 1231 157
226: 1231 157 -> 1245 135
227: 1245 135 -> 1257 123
228: 1257 123 -> 1261 118
229: 1261 118 -> 1263 124
230: 1263 124 -> 1263 143
231: 1263 143 -> 1263 176
232: 1263 176 -> 1263 224
233: 1263 224 -> 1263 287
234: 1263 287 -> 1263 365
235: 1263 365 -> 1263 437
236: 1263 437 -> 1263 494
237: 1263 494 -> 1263 536
238: 1263 536 -> 1263 563
239: 1263 563 -> 1263 578
240: 1263 578 -> 1258 583
241: 1258 583 -> 1243 583
242: 1243 583 -> 1213 583
243: 1213 583 -> 1180 580
244: 1180 580 -> 1146 568
245: 1146 568 -> 1125 558
246: 1125 558 -> 1117 546
247: 1117 546 -> 1115 539
248: 1115 539 -> 1107 538
249: 1107 538 -> 1098 550
250: 1098 550 -> 1103 561
251: 1103 561 -> 1114 567
252: 1114 567 -> 1113 575
253: 1113 575 -> 1099 581
254: 1099 581 -> 1078 582
255: 1078 582 -> 1067 579
256: 1067 579 -> 1059 570
257: 1059 570 -> 1061 560
258: 1061 560 -> 1070 556
259: 1070 556 -> 1074 553
260: 1074 553 -> 1069 544
261: 1069 544 -> 1058 542
262: 1058 542 -> 1045 530
263: 1045 530 -> 1017 518
264: 1017 518 -> 990 509
265: 990 509 -> 972 501
266: 972 501 -> 955 500
267: 955 500 -> 938 514
268: 938 514 -> 914 528
269: 914 528 -> 902 543
270: 902 543 -> 895 562
271: 895 562 -> 893 572
272: 893 572 -> 880 581
273: 880 581 -> 869 579
274: 869 579 -> 858 571
275: 858 571 -> 844 567
276: 844 567 -> 834 558
277: 834 558 -> 830 553
278: 830 553 -> 832 540
279: 832 540 -> 829 529
280: 829 529 -> 821 522
281: 821 522 -> 819 517
282: 819 517 -> 831 512
283: 831 512 -> 838 506
284: 838 506 -> 843 488
285: 843 488 -> 843 473
286: 843 473 -> 844 469
287: 844 469 -> 856 469
288: 856 469 -> 883 469
289: 883 469 -> 906 458
290: 906 458 -> 918 449
291: 918 449 -> 924 433
292: 924 433 -> 920 418
293: 920 418 -> 904 406
294: 904 406 -> 883 404
295: 883 404 -> 859 402
296: 859 402 -> 844 394
297: 844 394 -> 843 385
298: 843 385 -> 841 366
299: 841 366 -> 838 361
300: 838 361 -> 828 363
301: 828 363 -> 813 356
302: 813 356 -> 807 343
303: 807 343 -> 805 321
304: 805 321 -> 810 298
305: 810 298 -> 813 285
306: 813 285 -> 821 282
307: 821 282 -> 842 280
308: 842 280 -> 868 278
309: 868 278 -> 887 280
310: 887 280 -> 898 288
311: 898 288 -> 898 300
312: 898 300 -> 895 314
313: 895 314 -> 901 324
314: 901 324 -> 909 324
315: 909 324 -> 917 318
316: 917 318 -> 921 311
317: 921 311 -> 930 314
318: 930 314 -> 947 322
319: 947 322 -> 956 329
320: 956 329 -> 962 339
321: 962 339 -> 970 337
322: 970 337 -> 973 338
323: 973 338 -> 978 334
324: 978 334 -> 992 326
325: 992 326 -> 1000 327
326: 1000 327 -> 1008 335
327: 1008 335 -> 1015 351
328: 1015 351 -> 1021 373
329: 1021 373 -> 1022 390
330: 1022 390 -> 1013 404
331: 1013 404 -> 1006 417
332: 1006 417 -> 1012 430
333: 1012 430 -> 1023 436
334: 1023 436 -> 1029 434
335: 1029 434 -> 1049 432
336: 1049 432 -> 1063 426
337: 1063 426 -> 1079 425
338: 1079 425 -> 1093 418
339: 1093 418 -> 1113 417
340: 1113 417 -> 1128 414
341: 1128 414 -> 1139 421
342: 1139 421 -> 1154 426
343: 1154 426 -> 1158 430
344: 1158 430 -> 1149 436
345: 1149 436 -> 1130 438
346: 1130 438 -> 1108 442
347: 1108 442 -> 1096 447
348: 1096 447 -> 1087 441
349: 1087 441 -> 1079 443
350: 1079 443 -> 1072 446
351: 1072 446 -> 1060 454
352: 1060 454 -> 1052 461
353: 1052 461 -> 1034 463
354: 1034 463 -> 1016 463
355: 1016 463 -> 1010 464
356: 1010 464 -> 1011 472
357: 1011 472 -> 1012 479
358: 1012 479 -> 1025 484
359: 1025 484 -> 1048 488
360: 1048 488 -> 1083 491
361: 1083 491 -> 1119 505
362: 1119 505 -> 1154 520
363: 1154 520 -> 1183 530
364: 1183 530 -> 1201 537
365: 1201 537 -> 1209 539
366: 1209 539 -> 1209 535
367: 1209 535 -> 1209 517
368: 1209 517 -> 1209 484
369: 1209 484 -> 1210 437
370: 1210 437 -> 1210 392
371: 1210 392 -> 1210 362
372: 1210 362 -> 1210 347
373: 1210 347 -> 1203 340
374: 1203 340 -> 1184 333
375: 1184 333 -> 1156 320
376: 1156 320 -> 1116 306
377: 1116 306 -> 1069 285
378: 1069 285 -> 1023 265
379: 1023 265 -> 985 249
380: 985 249 -> 955 235
381: 955 235 -> 933 227
382: 933 227 -> 923 221
383: 923 221 -> 923 211
384: 923 211 -> 917 195
385: 917 195 -> 901 176
386: 901 176 -> 881 159
387: 881 159 -> 848 144
388: 848 144 -> 815 144
389: 815 144 -> 788 153
390: 788 153 -> 769 169
391: 769 169 -> 764 185
392: 764 185 -> 766 209
393: 766 209 -> 767 247
394: 767 247 -> 769 299
395: 769 299 -> 769 362
396: 769 362 -> 769 440
397: 769 440 -> 769 503
398: 769 503 -> 769 551
399: 769 551 -> 769 584
400: 769 584 -> 769 605
401: 769 605 -> 770 613
402: 770 613 -> 780 616
403: 780 616 -> 801 616
404: 801 616 -> 837 616
405: 837 616 -> 888 616
406: 888 616 -> 954 616
407: 954 616 -> 1035 616
408: 1035 616 -> 1113 616
409: 1113 616 -> 1176 616
410: 1176 616 -> 1224 616
411: 1224 616 -> 1257 616
412: 1257 616 -> 1278 616
413: 1278 616 -> 1294 607
414: 1294 607 -> 1295 598
415: 1295 598 -> 1295 577
416: 1295 577 -> 1295 541
417: 1295 541 -> 1295 490
418: 1295 490 -> 1295 424
419: 1295 424 -> 1295 343
420: 1295 343 -> 1295 265
421: 1295 265 -> 1295 202
422: 1295 202 -> 1295 154
423: 1295 154 -> 1295 121
424: 1295 121 -> 1295 100
425: 1295 100 -> 1294  92
426: 1294  92 -> 1283  89
427: 1283  89 -> 1262  89
428: 1262  89 -> 1226  89
429: 1226  89 -> 1175  89
430: 1175  89 -> 1109  89
431: 1109  89 -> 1028  89
432: 1028  89 -> 938  89
433: 938  89 -> 860  89
434: 860  89 -> 797  89
435: 797  89 -> 749  89
436: 749  89 -> 716  89
437: 716  89 -> 698  89
438: 698  89 -> 690  94
439: 690  94 -> 682 102
440: 682 102 -> 673 100
441: 673 100 -> 661  89
442: 661  89 -> 646  89
443: 646  89 -> 616  89
444: 616  89 -> 571  89
445: 571  89 -> 517  89
446: 517  89 -> 478  89
447: 478  89 -> 454  89
448: 454  89 -> 442  92
449: 442  92 -> 432 102
450: 432 102 -> 423 100
451: 423 100 -> 411  89
452: 411  89 -> 396  89
453: 396  89 -> 381  92
454: 381  92 -> 371 102
455: 371 102 -> 362 100
456: 362 100 -> 349  89
457: 349  89 -> 334  89
458: 334  89 -> 309  91
459: 309  91 -> 298  92
460: 298  92 -> 288 102
461: 288 102 -> 279 100
462: 279 100 -> 267  89
463: 267  89 -> 252  89
464: 252  89 -> 222  89
465: 222  89 -> 177  89
466: 177  89 -> 123  89
467: 123  89 ->  84  89
468:  84  89 ->  60  89
469:  60  89 ->  48  89
470:  48  89 ->  42  97
471:  42  97 ->  42 112
472:  42 112 ->  42 142
473:  42 142 ->  42 187
474:  42 187 ->  42 247
475:  42 247 ->  42 322
476:  42 322 ->  42 409
477:  42 409 ->  42 484
478:  42 484 ->  42 544
479:  42 544 ->  42 589
480:  42 589 ->  42 619
481:  42 619 ->  42 634
482:  42 634 ->  47 640
483:  47 640 ->  59 640
484:  59 640 ->  86 640
485:  86 640 -> 128 640
486: 128 640 -> 185 640
487: 185 640 -> 257 640
488: 257 640 -> 344 640
489: 344 640 -> 446 640
490: 446 640 -> 563 640
491: 563 640 -> 690 640
492: 690 640 -> 816 639
493: 816 639 -> 930 639
494: 930 639 -> 1029 639
495: 1029 639 -> 1113 639
496: 1113 639 -> 1182 639
497: 1182 639 -> 1236 639
498: 1236 639 -> 1275 639
499: 1275 639 -> 1300 639
500: 1300 639 -> 1316 633
501: 1316 633 -> 1320 630
502: 1320 630 -> 1322 615
503: 1322 615 -> 1322 588
504: 1322 588 -> 1322 546
505: 1322 546 -> 1322 489
506: 1322 489 -> 1322 417
507: 1322 417 -> 1322 330
508: 1322 330 -> 1322 252
509: 1322 252 -> 1322 186
510: 1322 186 -> 1322 135
511: 1322 135 -> 1322  99
512: 1322  99 -> 1322  78
513: 1322  78 -> 1320  68
514: 1320  68 -> 1310  65
515: 1310  65 -> 1289  65
516: 1289  65 -> 1253  65
517: 1253  65 -> 1208  65
518: 1208  65 -> 1178  65
519: 1178  65 -> 1163  65
520: 1163  65 -> 1155  71
521: 1155  71 -> 1149  76
522: 1149  76 -> 1135  74
523: 1135  74 -> 1111  74
524: 1111  74 -> 1102  74
525: 1102  74 -> 1091  65
526: 1091  65 -> 1076  65
527: 1076  65 -> 1046  65
528: 1046  65 -> 1013  65
529: 1013  65 -> 992  65
530: 992  65 -> 986  65
531: 986  65 -> 975  56
532: 975  56 -> 960  56
533: 960  56 -> 930  56
534: 930  56 -> 899  58
535: 899  58 -> 878  58
536: 878  58 -> 870  59
537: 870  59 -> 864  65
538: 864  65 -> 849  65
539: 849  65 -> 819  65
540: 819  65 -> 774  65
541: 774  65 -> 714  65
542: 714  65 -> 651  65
543: 651  65 -> 603  65
544: 603  65 -> 570  65
545: 570  65 -> 552  65
546: 552  65 -> 546  65
547: 546  65 -> 535  56
548: 535  56 -> 520  56
549: 520  56 -> 492  58
550: 492  58 -> 478  59
551: 478  59 -> 472  65
552: 472  65 -> 457  65
553: 457  65 -> 427  65
554: 427  65 -> 382  65
555: 382  65 -> 322  65
556: 322  65 -> 265  65
557: 265  65 -> 223  65
558: 223  65 -> 193  65
559: 193  65 -> 178  65
560: 178  65 -> 170  71
561: 170  71 -> 164  76
562: 164  76 -> 156  74
563: 156  74 -> 145  65
564: 145  65 -> 130  65
565: 130  65 -> 109  65
566: 109  65 -> 103  65
567: 103  65 ->  92  56
568:  92  56 ->  77  56
569:  77  56 ->  65  59
570:  65  59 ->  57  68
571:  57  68 ->  46  67
572:  46  67 ->  29  65
573:  29  65 ->  20  68
574:  20  68 ->  17  80
575:  17  80 ->  17 104
576:  17 104 ->  17 143
577:  17 143 ->  17 197
578:  17 197 ->  17 266
579:  17 266 ->  17 350
580:  17 350 ->  19 435
581:  19 435 ->  19 507
582:  19 507 ->  19 564
583:  19 564 ->  19 606
584:  19 606 ->  19 633
585:  19 633 ->  19 648
586:  19 648 ->  33 662
587:  33 662 ->  48 664
588:  48 664 ->  76 664
589:  76 664 -> 118 664
590: 118 664 -> 175 664
591: 175 664 -> 245 664
592: 245 664 -> 328 664
593: 328 664 -> 423 663
594: 423 663 -> 532 661
595: 532 661 -> 654 661
596: 654 661 -> 784 662
597: 784 662 -> 900 662
598: 900 662 -> 1002 662
599: 1002 662 -> 1089 662
600: 1089 662 -> 1166 662
601: 1166 662 -> 1231 664
602: 1231 664 -> 1283 664
603: 1283 664 -> 1320 664
604: 1320 664 -> 1344 662
605: 1344 662 -> 1355 662
606: 1355 662 -> 1359 654
607: 1359 654 -> 1372 640
608: 1372 640 -> 1377 630
609: 1377 630 -> 1376 613
610: 1376 613 -> 1376 586
611: 1376 586 -> 1376 550
612: 1376 550 -> 1374 527
613: 1374 527 -> 1374 517
614: 1374 517 -> 1381 508
615: 1381 508 -> 1381 494
616: 1381 494 -> 1370 477
617: 1370 477 -> 1372 459
618: 1372 459 -> 1370 432
619: 1370 432 -> 1367 418
620: 1367 418 -> 1354 401
621: 1354 401 -> 1355 384
622: 1355 384 -> 1351 361
623: 1351 361 -> 1343 330
624: 1343 330 -> 1344 295
625: 1344 295 -> 1346 271
626: 1346 271 -> 1347 256
627: 1347 256 -> 1336 240
628: 1336 240 -> 1336 224
629: 1336 224 -> 1345 210
630: 1345 210 -> 1341 196
631: 1341 196 -> 1338 172
632: 1338 172 -> 1340 153
633: 1340 153 -> 1349 132
634: 1349 132 -> 1345 109
635: 1345 109 -> 1347  80
636: 1347  80 -> 1356  59
637: 1356  59 -> 1359  42
638: 1359  42 -> 1356  34
639: 1356  34 -> 1341  29
640: 1341  29 -> 1316  29
641: 1316  29 -> 1276  29
642: 1276  29 -> 1221  29
643: 1221  29 -> 1177  32
644: 1177  32 -> 1143  31
645: 1143  31 -> 1118  24
646: 1118  24 -> 1084  23
647: 1084  23 -> 1045  31
648: 1045  31 -> 1011  29
649: 1011  29 -> 991  26
650: 991  26 -> 972  19
651: 972  19 -> 953  22
652: 953  22 -> 934  31
653: 934  31 -> 909  31
654: 909  31 -> 872  29
655: 872  29 -> 822  29
656: 822  29 -> 775  31
657: 775  31 -> 742  32
658: 742  32 -> 713  37
659: 713  37 -> 683  36
660: 683  36 -> 650  40
661: 650  40 -> 619  35
662: 619  35 -> 577  34
663: 577  34 -> 547  32
664: 547  32 -> 505  32
665: 505  32 -> 455  25
666: 455  25 -> 401  23
667: 401  23 -> 346  22
668: 346  22 -> 296  31
669: 296  31 -> 240  32
670: 240  32 -> 172  31
671: 172  31 ->  91  31
672:  91  31 ->  14  25

Sunday Driver, Python 2, 3242

Kod minimalny = 2382 bajty

Wydajność: miasto = 86 przeszkód = 46 tor wyścigowy = 188 rękawica = 1092

Oto mój program weryfikacji koncepcji, który miał wykazać, że rozwiązanie jest możliwe. Wymaga optymalizacji i lepszego gry w golfa.

Operacja

• Utwórz strukturę danych pierścieni odległości na zewnątrz miejsca docelowego (prosta pochodna A *, jak wypełnienie zalewowe)

• Znajdź zwartą serię prostych linii do miejsca docelowego, które nie przecinają pikseli nie śledzących.

• Dla każdej linii prostej przyspiesz i hamuj, aby zminimalizować liczbę zakrętów.

Kod w golfa (zminimalizowany)

import pygame as P,sys,random
Z=255
I=int
R=range

X=sys.argv[1]
pic=P.image.load(X)
show=P.display.flip
W,H=pic.get_size()
M=P.display.set_mode((W,H))
M.blit(pic,(0,0))
show()
U=complex
ORTH=[U(-1,0),U(1,0),U(0,-1),U(0,1)]
def draw(line,O):
 for p in line:
  M.set_at((I(p.real),I(p.imag)),O)
def plot(p,O):
 M.set_at((I(p.real),I(p.imag)),O)
def J(p):
 return abs(I(p.real))+abs(I(p.imag))
locs=[(x,y)for x in R(W)for y in R(H)]
n={}
for p in locs:
 O=tuple(M.get_at(p))[:3]
 if O not in n:
  n[O]=set()
 n[O].add(U(p[0],p[1]))
z=set()
for c in n:
 if c[0]==c[1]==c[2]and 30<=c[0]<=220 or c==(0,0,0)or c==(Z,Z,0):
  z|=n[c]
first=next(iter(n[(0,0,0)]))
ring=set([first])
s={0:ring}
g={first:0}
T=set()
G=0
done=0
while not done:
 G+=1
 T|=ring
 D=set()
 for dot in ring:
  for K in[dot+diff for diff in ORTH]:
   if K in n[(Z,Z,0)]:
    V=K;done=1
   if K in z and K not in T:
    D.add(K);g[K]=G
 ring=D
 s[G]=ring
def A(p1,p2):
 x1,y1=I(p1.real),I(p1.imag)
 x2,y2=I(p2.real),I(p2.imag)
 dx=x2-x1
 dy=y2-y1
 line=[]
 if abs(dx)>abs(dy):
  m=1.0*dy/dx
  line=[U(x,I(m*(x-x1)+y1+.5))for x in R(x1,x2,cmp(dx,0))]
 else:
  m=1.0*dx/dy
  line=[U(I(m*(y-y1)+x1+.5),y)for y in R(y1,y2,cmp(dy,0))]
 return line+[U(x2,y2)]
def f(p1,p2):
 return all(p in z for p in A(p1,p2))
def a(j,G):
 l=list(s[G])
 for F in R(150):
  w=random.choice(l)
  if f(j,w):
   return w
 return None
def d(j):
 u=g[j]
 E=k=0
 r=j
 while 1:
  w=a(j,k)
  if w:
   u=k;r=w
  else:
   E=k
  k=(u+E)/2
  if k==u or k==E:
   break
 return r
def h(p1,p2):
 if abs(p2-p1)<9:
  return p2
 line=A(p1,p2)
 tries=min(20,len(line)/2)
 test=[line[-i]for i in R(1,tries)]
 q=[(p,d(p))for p in test]
 rank=[(abs(p3-p)+abs(p-p1),p)for p,p3 in q]
 return max(rank)[1]
o=V
path=[V]
while g[o]>0:
 o=d(o)
 if o not in n[(0,0,0)]:
  o=h(path[-1],o)
 path.append(o)
 if o in n[(0,0,0)]:
  break
def t(line,N):
 v=[]
 S=len(line)/2+2
 base=i=0
 b=0
 while i<len(line):
  C=(i<S)
  Q=line[i]-line[base]
  accel=Q-N
  L=(J(accel)<=15)
  if L:
   b=1
  if C:
   if b and not L:
    i-=1;v.append(i);N=Q;base=i;b=0
  else:
   if b and J(Q)>13:
    v.append(i);N=Q;base=i;b=0
  i+=1
 v.append(i-1)
 return v,Q
turns=0
vel=U(0,0)
for V,stop in zip(path,path[1:]):
 line=A(V,stop)
 Y,vel=t(line,vel)
 turns+=len(Y)
 draw(line,(Z,Z,Z))
 plot(line[0],(0,0,Z))
 for m in Y:
  plot(line[m],(0,0,Z))
B=X.replace('.','%u.'%turns)
P.image.save(M,B)

Przykłady