PARABÉNS a @kuroineko. Ganha a recompensa por uma velocidade excelente (672 movimentos) na pista de Gauntlet.

LÍDER: * Nimi com 2129 leve. Outras entradas são maiores, mas mostram uma certa velocidade.

* O líder pode mudar devido a entradas posteriores.

Sua tarefa é escrever um pequeno programa que possa dirigir um carro de corrida rapidamente.

Regras

Seu programa lerá uma imagem da faixa. Você pode iniciar seu carro com qualquer pixel amarelo e terminar cruzando qualquer pixel preto. O caminho do seu carro deve estar apenas na pista cinza ((c, c, c), onde 30 <= c <= 220).

Seu carro se moverá em uma linha reta a cada turno com a velocidade v composta pelos números inteiros vx e vy (começando com (0,0)). No início de cada turno, seu programa pode alterar vx e vy de modo que:

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

Atualização: aumento da aceleração máxima para 15.

Seu programa traçará uma linha reta da sua localização atual para (localização + v) em branco com um ponto azul no início. Se um pixel abaixo desta linha for preto, você terminou a corrida. Caso contrário, se todos os pixels abaixo dessa linha forem cinza ou amarelo, você poderá continuar na próxima curva.

Seu programa deve gerar a imagem da faixa com o seu caminho em branco e azul adicionado.

Saída adicional (adicionado 2015-01-15):

Se você deseja competir pela vitória ou pelo bônus , seu programa também deve exibir sua lista de pontos (os pontos azuis) para a Cidade ou Manopla, respectivamente. Inclua a lista de pontos com sua resposta (para verificação). Os pontos deve ser parecido: (x0,y0), (x1,y1), ... (xn,yn). Você pode usar o espaço em branco livremente, incluindo '\n'caracteres para ajustar os dados na página.

Você pode usar leitura e gravação de imagens de terceiros, desenho de linhas e bibliotecas de acesso a pixels. Você não pode usar bibliotecas de localização de caminhos. Se desejar, você pode converter as imagens PNG em outros formatos gráficos (como GIF, JPG, BMP), se necessário.

Algumas faixas para dirigir

Uma trilha simples para começar:

Uma pista de corrida:

Um curso de obstáculo:

A cidade:

Nightmare Track: The Gauntlet (se os outros são fáceis demais)

Pontuação

Sua pontuação será baseada no seu resultado na pista da cidade. Os pontos são iguais ao tamanho do seu programa em bytes, mais 10 pontos por cada turno que seu carro de corrida levou para terminar. Menor pontuação ganha. Inclua sua imagem da pista da cidade com sua resposta - gostaríamos de ver seu estilo de direção.

Por favor, use um título para sua resposta no formato:

<Racing Driver or Team Name> <Language> <Score> por exemplo: Slowpoke Perl 5329

Seu programa deve ser capaz de conduzir em qualquer imagem de faixa, seguindo as regras acima. Você não deve codificar o caminho ideal ou quaisquer parâmetros das pistas de teste. As outras brechas padrão se aplicam.

Desafios semelhantes

Este é um quebra-cabeça semelhante ao de Martin: To Vectory! - O Grand Racing de vetor . Este quebra-cabeça tem várias diferenças:

• Dirigir através das paredes não é permitido.
• Você pode usar memória e tempo ilimitados.
• Você não precisa executar o código de outra pessoa no seu computador.
• Você não precisa baixar nada, exceto uma imagem.
• O tamanho do seu código conta na pontuação. Menor é melhor.
• Você plota sua solução na imagem da faixa.
• Você pode criar facilmente suas próprias faixas com um pacote de tinta.
• A resolução mais alta incentiva travagens e curvas mais realistas.
• A aceleração de 15 cria cerca de 450 possibilidades por turno. Isso torna o BFS menos viável e incentiva novos algoritmos interessantes.

Esse quebra-cabeça deve inspirar uma nova rodada de programadores a tentar soluções e permitir que programadores com soluções antigas repensem-nos no novo ambiente.

TS # 1 - Haskell - 1699 + 430 = 2129

Irmão Tutu # 1

Muito parecido com o piloto Tutu original, exceto que ele usa uma espessura de 3 para o caminho inchado e o 2º A * (espaço de posição de velocidade) segue uma heurística constante de 1. A imagem de entrada não é mais transmitida como argumento de linha de comando, deve ser nomeada i. O nome da imagem de saída é o. O programa imprime os pontos calculados no caminho como uma lista de pares x, y (a saída original é uma única linha):

[(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)] 

Eu pude salvar muitos bytes quando começo a remover todo o mapa e definir estruturas de dados e substituí-los por simples listas vinculadas. Apenas as duas instruções de importação economizariam 60 bytes. No entanto, isso atrasaria o programa para que esperar por um resultado fosse pura dor. Esta versão demora mais de 45 minutos para The City, em comparação com os 7s do original. Vou parar por aqui trocando bytes pela velocidade de execução.

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

O código precisa do sinalizador -XNoMonomorphismRestriction para compilar.

A cidade - TS # 1-43 passos

FirstRacer Java (5825 + 305 * 10 = 8875)

Só para começar. Precisa de 305 segmentos na cidade.

Este programa Java faz pipeline:

1. leia a imagem
2. A * (Uma estrela)

• 2.1 Crie o cenário de pesquisa A *.
• 2.2 Acompanhe para trás procurando apenas as melhores células vizinhas * diretas * (N, S, E, W, NE, NW, SE, SW). Ele encontra a trilha mais curta t0 pixelwise.

3. fique em t0 e otimize-o para velocidade, eliminando pixels. O preenchimento da restrição nunca é superior a 7 (isso significa manter pelo menos a cada 7 pixels).
4. desenhe a trilha na imagem
5. mostra a imagem resultante.

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;
    }

}

Acho que o Race Track dá uma melhor impressão de como o FirstRacer funciona.

cabeçalho PHP (5950 + 470 = 6420)

Outra variação do BFS (simplificada), com algum pré-processamento para reduzir o espaço de pesquisa.

<?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();
?>

Escolha de idioma

PHP é muito bom em lidar com imagens.
Ele também possui memória associativa nativa, o que facilita a programação da pesquisa de nós BFS.

A desvantagem é que o hash dos identificadores de nó não é muito eficiente em termos de tempo, portanto o resultado é tudo menos rápido.

Dos meus experimentos com o desafio de corrida anterior, não tenho dúvidas de que o C ++ 11 e suas tabelas de hash teriam um desempenho muito melhor, mas o código-fonte teria pelo menos o dobro, mais a necessidade de qualquer biblioteca png externa (mesmo o LodePNG) faça uma construção bagunçada.

O Perl e seus descendentes mais avançados provavelmente permitiriam um código mais compacto e eficiente (devido a melhores desempenhos de hash), mas não estou familiarizado o suficiente com nenhum deles para tentar uma porta.

Núcleo BFS

A pesquisa opera em uma posição + espaço de velocidade, ou seja, um nó representa um determinado local visitado com uma determinada velocidade.
É claro que isso cria um espaço de pesquisa bastante grande, mas gera ótimos resultados, desde que todos os locais de trilhas possíveis sejam examinados.

Claramente, dado o número de pixels em uma imagem pequena, uma pesquisa exaustiva está fora de questão.

Cortes

Eu escolhi cortar o espaço da posição, selecionando apenas um subconjunto de pixels da trilha.
O solucionador considerará todas as posições ao seu alcance, limitadas apenas pela aceleração.

A pista é lado a lado com quadrados, cujo tamanho máximo é calculado para que dois quadrados adjacentes possam ser alcançados com a aceleração máxima permitida (ou seja, 14x14 pixels com o limite de velocidade atual).
Depois de embalar a pista com grandes quadrados, ladrilhos cada vez menores são usados ​​para preencher o espaço restante.
Somente o centro de cada bloco é considerado como um destino possível.

Aqui está um exemplo:

Essa escolha heurística é suficiente para fazer com que o solucionador falhe no mapa do pesadelo. Suponho que alguém possa tentar reduzir o tamanho máximo do bloco até encontrar alguma solução, mas, com as configurações atuais, o solucionador dura cerca de uma hora e usa 600 Mb, portanto, resultados mais precisos exigiriam uma quantidade razoável de tempo e memória.

Como segundo corte, quadrados de apenas 1 pixel podem ser deixados de fora.
Obviamente, isso degradará a solução ou até impedirá que o solucionador encontre alguma, mas melhora muito o tempo de computação e geralmente produz resultados bastante próximos em mapas "simples".

Por exemplo, na cidade, deixar de fora os quadrados de 1 x 1 pixel reduz os nós da árvore BFS explorados de 660K para cerca de 90K para soluções de 47 x 53 movimentos.

BFS vs A *

A * precisa de mais código e não garante nem mesmo a obtenção de resultados mais rápidos no espaço de posição / velocidade, pois avaliar o melhor candidato seguinte não é nada tão simples quanto no espaço de posição clássica (que pode ser facilmente derrotado com a cultura de propósito específico). de qualquer maneira).

Além disso, embora o PHP tenha algumas filas prioritárias de tipo, que, a propósito, suporte a reordenação dinâmica contrasta com seus primos C ++, duvido que sejam suficientes para uma implementação A * eficiente e reescrevendo um heap binário ou qualquer estrutura de fila A * dedicada. exigem muitas linhas de código.

Verificação de parede

Eu não usei o algoritmo de Bresenham para verificar colisões na parede, portanto a trajetória pode cortar o pixel da parede ímpar. Não deve permitir atravessar uma parede, no entanto.

Performances

Este solucionador certamente não tem um coelho de seis patas.
Sem o corte extra, um mapa pode levar mais de 10 minutos para ser resolvido no meu PC de gama média.
Sugiro definir o tamanho mínimo do bloco como 2 ou 3, se você quiser mexer no código sem gastar muito tempo esperando pelo resultado.

O consumo de memória é razoável para esse tipo de algoritmo e linguagem: cerca de 100 Mb ou menos, exceto para pesadelos que atingem picos acima de 600 Mb.

Resultados e pontuação

As pontuações são dadas sem o corte "tamanho mínimo do ladrilho".

Como um leitor cuidadoso pode deduzir dos meus comentários gerais, não me importo muito com a parte do golfe desse desafio. Não vejo como executar meu código através de um ofuscador ou excluir algumas otimizações e / ou rotinas de depuração para reduzir a fonte tornaria isso mais divertido.

Por enquanto, apenas S seja o tamanho do byte de origem:

faixa S + 1020

cidade S + 470

obstáculos S + 280

pesadelo -> falha

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

Semelhante ao FirstRacer. Mas diferente nas etapas 2.2 e 3., o que resulta em dirigir com visão de futuro e usar a marcha.

2. A * (Uma estrela)

• 2.1 Crie o cenário de pesquisa A *.
• 2.2 Encontre a melhor célula à vista e leve em consideração a distância euclidiana. (Ainda procurando apenas nas direções N, S, E, W, NE, NW, SE, SW.) Como resultado, o SecondRacer encontra um caminho com muito menos pontos de passagem.

3. A otimização é muito elaborada agora. A idéia é particionar as linhas fornecidas entre dois pontos de passagem em curvas o menos possível, sem violar a restrição de aceleração.

atuação

Nenhuma dessas faixas é um problema para o A *. Apenas alguns segundos (<10) para resolver (até a "Nightmare Track: The Gauntlet") no meu PC de nível médio.

Estilo do caminho

Eu chamo de polvo. De longe, não é tão elegante quanto a solução do cabeçote (de kuroi neko).

Estilo do código

Entrei em um modo de luta moderado, mantendo a legibilidade. Mas adicionou uma versão para golfe.

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 -> AVISO: substitui o arquivo original!

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;}}

Todas as imagens são mostradas na paisagem gradiente A *. Começando de amarelo claro a marrom (= amarelo escuro). Enquanto - de acordo com A * - o caminho resultante é rastreado para trás (aqui do marrom ao amarelo claro).

Pista de Corrida S + 175

Curso de Obstáculo S + 47

Cidade S + 72

Manoplas S + 1133

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

Estratégia:

1. encontre um*
2. inchar o caminho com seus vizinhos (distância 2)
3. encontre novamente A *, mas desta vez na posição + espaço na velocidade, assim como o piloto de corrida

Golfe:

• omitiu a maior parte da verificação de erros; portanto, o programa assume que sempre existem pontos de início e fim no mapa e um caminho entre eles.
• nomes curtos de variáveis

Eu não sou um jogador de golfe Haskell, então não sei quanto pode ser economizado (Edit: acabou por ser um bando).

Atuação:

O Gauntlet funciona em 9: 21min no meu Core i5 a 1,7 GHz de 2011. A cidade leva 7,2 segundos. (usado -O1 com ghc, -O2 torna o programa muito lento)

As opções de ajuste são a espessura do caminho inchado. Para os mapas menores, a distância 3 salva um ou dois passos, mas o Gauntlet corre muito tempo, então eu permaneço com a distância 2. A corrida começa sempre no primeiro pixel amarelo (ou seja, no canto superior esquerdo); a otimização manual deve salvar uma etapa adicional.

Conformidade da regra:

“Você não pode usar bibliotecas de localização de caminhos.” - Sim, mas a fonte está incluída. As funções de pesquisa A * são versões levemente pesadas da biblioteca Data.Graph.AStar de Cale Gibbard (consulte http://hackage.haskell.org/package/astar ).

A cidade - 50 degraus

A Manopla - 722 passos

Ungolfed:

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) }

Golfe:

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

Irmãos tutu -TS # 1 - (1764 + 43 = 2194)

Edit: TS # 1 agora resposta separada.

Edit II: O caminho para a cidade é

[(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)]

Em The Gauntlet, Tutu se move da seguinte maneira

[(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)]

Piloto cruzado em estrela - PHP - 4083 + 440 = muito pesado

Ok, depois de três semanas sem conexão com a Internet (é o que acontece quando um dos concorrentes mais ferozes do seu provedor está no comando do patch bay do edifício, ou pelo menos em Paris, na França), posso finalmente publicar minha próxima tentativa.

Dessa vez, usei o algoritmo A * e uma estratégia de distribuição de waypoints mais eficiente.
Como um bônus adicional, escrevi algum tipo de triturador de PHP para abordar a parte do desafio do golfe.

E agora que o solucionador funciona em todos os mapas propostos, o bug de rastreamento de linha foi corrigido.
Não é mais necessário recorte de parede (embora o pastejo na parede ainda ocorra, como deveria :)).

executando o código

forneça ao código o nome que você quiser ( runner.phppor exemplo) e, em seguida, chame-o da seguinte maneira:

php runner.php track.png

Depois de ficar em silêncio por um bom tempo, ele deve produzir uma _track.pngsaída mostrando a solução.

Como você pode ver nas imagens de saída, o código é realmente lento. Voce foi avisado.

É claro que minha versão privada é cheia de traços e produz representações agradáveis ​​de várias informações (incluindo uma imagem periódica mostrando o progresso A * para ajudar a matar o tempo), mas há um preço a pagar pelo golfe ...

código de golfe

<?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]);

versão ungolfed

<?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]);
?>

Resultados

As fotos são produzidas por uma versão mais rica que gera exatamente a mesma solução com algumas estatísticas na parte inferior (e desenha o caminho com antialiasing).

O mapa da cidade é um bom exemplo de por que algoritmos baseados em posição tendem a encontrar resultados abaixo da média em muitos casos: mais curto nem sempre significa mais rápido.

(672 se move, se você não deseja ampliar)

UMA*

Para minha surpresa, A * tem um bom desempenho no espaço de velocidade da posição. Melhor que o BFS, de qualquer forma.

Eu tive que suar um pouco para produzir uma estimativa de distância heurística de trabalho.

Também tive que otimizá-lo um pouco, já que o número de estados possíveis é enorme (alguns milhões) em comparação com uma variante apenas de posição, que novamente requer mais código.

O limite inferior escolhido para o número de movimentos necessários para alcançar um objetivo a partir de uma determinada posição é simplesmente o tempo necessário para percorrer a distância até o objetivo mais próximo em uma linha reta com velocidade inicial zero .

Obviamente, o caminho da linha reta geralmente leva diretamente a uma parede, mas esse é o mesmo problema que usar a distância reta euclidiana para pesquisas A * com apenas espaço.
Assim como a distância euclidiana para variantes com apenas espaço, a principal vantagem dessa métrica, além de ser aceitável usar a variante A * mais eficiente (com nós fechados), é exigir muito pouca análise topológica da pista.

Dada uma aceleração máxima A , o número n de movimentos necessários para percorrer uma distância d é o menor número inteiro que satisfaz a relação:

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

Resolver isso para n fornece uma estimativa da distância restante.

Para calcular isso, é construído um mapa de distância até a meta mais próxima, usando um algoritmo de preenchimento de inundação semeado com as posições da meta.
Ele tem o agradável efeito colateral de eliminar pontos de trilha de onde nenhum objetivo pode ser alcançado (como acontece em algumas áreas da trilha de pesadelo).
O número de movimentos é calculado como um valor de ponto flutuante, para que os nós mais próximos da meta possam ser discriminados ainda mais.

Waypoints

Como na minha tentativa anterior, a idéia é reduzir o número de pontos de trilha para uma subamostra o menor possível de pontos de referência. O truque é tentar escolher as posições mais "úteis" na pista.

A heurística começa com uma repartição regular em toda a faixa, mas aumenta a densidade em dois tipos de áreas:

1. a borda da pista, ou seja, faixas que estão a 1 ou 2 pixels de distância das paredes
2. zonas de alta curvatura, ou seja, a borda interna de curvas acentuadas.

Aqui está um exemplo.
Áreas de alta densidade estão em vermelho, baixa densidade em verde. Pixels azuis são os waypoints selecionados.
Observe os aglomerados de pontos de referência em curvas acentuadas (entre muitas manchas inúteis em curvas inclinadas, devido à filtragem insuficiente).

Para calcular as posições das faixas, a faixa inteira é digitalizada quanto à distância da parede mais próxima. O resultado é um campo de vetores apontando para a borda da pista mais próxima.
Esse campo vetorial é então processado para produzir uma estimativa aproximada da curvatura local.
Finalmente, a curvatura e a distância à parede são combinadas para produzir a densidade local desejada, e um algoritmo bastante desajeitado tenta borrifar os waypoints sobre a pista de acordo.

Uma melhoria notável em relação à estratégia anterior é que as faixas estreitas (aparentemente) sempre terão pontos de passagem suficientes para percorrer, o que permite navegar no mapa do pesadelo.

Como sempre, é uma questão de encontrar um ponto ideal entre tempo de computação e eficiência.
Uma redução de 50% na densidade dividirá o tempo de computação em mais de 4, mas com resultados mais grossos (48 movimentos em vez de 44 na cidade, 720 em vez de 670 no pesadelo).

Golfe

Eu ainda acho que o golfe prejudica a criatividade neste caso específico: remover o antialiasing da saída é suficiente para ganhar 30 pontos e requer muito menos esforço do que ir de 47 para 44 movimentos no mapa da cidade.
Mesmo passando de 720 para 670 jogadas no pesadelo ganharia meros 500 pontos, embora eu duvide que um A * somente na posição possa chegar perto disso.

Apenas por diversão, decidi escrever meu próprio compressor PHP de qualquer maneira.

Como parece, renomear identificadores com eficiência no PHP não é uma tarefa fácil. De fato, não acho que seja possível fazê-lo no caso geral. Mesmo com uma análise semântica completa, a possibilidade de usar cadeias ou variáveis ​​indiretas para designar objetos exigiria o conhecimento de toda semântica de funções.
No entanto, como o analisador embutido muito conveniente permite pular para a análise semântica imediatamente, consegui produzir algo que parece funcionar em um subconjunto de PHP suficiente para escrever código "golfable" (fique longe de $$ e não use chamadas de função indiretas ou outro acesso de seqüência a objetos).
Não há uso prático para falar e nada a ver com o problema original, mas é muito divertido codificar.

Eu poderia ter massacrado o código ainda mais para ganhar 500 caracteres extras, mais ou menos, mas como os nomes da biblioteca gráfica PHP são infelizmente muito longos, é uma espécie de luta árdua.

Desenvolvimentos futuros

O código de seleção do waypoint é uma bagunça horrenda, sintonizada por tentativa e erro. Eu suspeito que fazer mais matemática (usando operadores adequados de gradiente e ondulação) melhoraria bastante o processo.

Estou curioso para ver se uma heurística a distância melhor pode ser encontrada. Tentei levar em consideração a velocidade de várias maneiras, mas isso quebrou o A * ou produziu resultados mais lentos.

Pode ser possível recodificar tudo isso em uma linguagem mais rápida como C ++, mas a versão PHP depende muito da coleta de lixo para manter o consumo de memória razoável. Limpar nós fechados no C ++ exigiria bastante trabalho e uma quantidade considerável de código extra.

Se a pontuação tivesse sido baseada em performances, eu tentaria ansiosamente melhorar os algoritmos. Mas como o critério de golfe é tão avassalador, não há nenhum ponto real, ou é?

ThirdRacer Java (1224 + 93 * 10 = 2154)

Semelhante ao SecondRacer. Mas mudar o foco da velocidade para o tamanho do código (mas ainda usando Java). A otimização da aceleração é muito simplificada agora, resultando tristemente em um carro mais lento.

atuação

Melhor que o SecondRacer.

Estilo do caminho

Como o SecondRacer.

Estilo do código

Entrei em um modo de luta pesado.

golfed -> AVISO: substitui no local o arquivo original!

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;}}

Cidade S + 93

Estrela cruzou o caminho do piloto no mapa do pesadelo

(conforme solicitação popular)

(código não atualizado, pois as modificações são triviais e o desafio somente de desempenho não é jogado)

Desculpe postar mais uma entrada, mas estou atingindo o limite de 30.000 caracteres na anterior.
Apenas diga a palavra e eu excluirei esta.

  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

Driver de domingo, Python 2, 3242

Código reduzido = 2382 bytes

Desempenho: cidade = 86 obstáculos = 46 pista = 188 manopla = 1092

Aqui está o meu programa de prova de conceito que demonstrava que uma solução era possível. Precisa de alguma otimização e melhor golfe.

Operação

• Crie uma estrutura de dados de anéis de distância fora do destino (derivada A * simples, como preenchimento)

• Encontre as séries retas em curto para o destino que não cruzam os pixels que não são da faixa.

• Para cada linha reta, acelere e freie para minimizar as curvas.

Código de golfe (minificado)

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)

Exemplos