Del vector a la trayectoria óptima

El objetivo es hacer comprensible el proceso completo: desde la regla de movimiento vectorial hasta las trayectorias que muestra el Editor y las decisiones que toman las inteligencias artificiales. Cuando una propiedad pertenece solo a un ensayo —por ejemplo, la comparación entre dos algoritmos— se identifica expresamente como experimental.

Estado y transición

El estado físico fundamental del Editor es (x, y, vₓ, vᵧ, capa de pista). La capa de pista distingue la calzada inferior de una zona elevada. En cada turno se puede modificar cada componente del vector en −1, 0 o +1; por tanto hay como máximo nueve aceleraciones candidatas.

Un movimiento que mantuviera el vector total en cero no es válido. Además, la validez no se decide mirando únicamente el destino: el segmento debe respetar la superficie de la pista, los arcenes, las capas, las reglas iniciales y el sentido correcto de salida y meta.

El movimiento es un segmento, no un salto

Durante una transición se calculan los cruces con las líneas de salida y meta. Si ambos ocurren en el mismo vector, se conserva su orden exacto. La comparación se realiza mediante fracciones enteras, sin depender de redondeos de coma flotante.

Estado físico y clave de búsqueda

Algunos cálculos añaden una fase temporal mientras está activa la regla de apertura de la carrera. Esa fase pertenece al cálculo de la trayectoria amarilla. El cálculo principal de trayectorias óptimas usa posición, vector y capa de pista; esta diferencia se declara de nuevo entre los límites.

1. Calcula la trayectoria amarilla. Dijkstra encuentra la trayectoria válida de menor longitud euclidiana total.
2. Obtiene una cota de movimientos. Como la trayectoria amarilla es válida, su número de movimientos es un límite superior para cualquier trayectoria óptima.
3. Construye el DAG óptimo. La búsqueda en anchura (BFS) conserva todos los estados y movimientos que participan en trayectorias de mínimo número de movimientos.
4. Protege el resultado. Si la búsqueda con cota devolviera meta inalcanzable, se repite sin ella para comprobar que la poda no ha ocultado una trayectoria válida.
5. Comprueba varias vueltas. Se distingue si la geometría y la cinemática permiten salida–meta–salida–meta.
6. Filtra continuidad. Si es circuito, se determina qué estados finales óptimos permiten otra vuelta completa.
7. Calcula representantes y puntuación. Cobertura roja, trayectorias verde y azul, porcentaje continuable y métricas de diseño.

La orquestación se ejecuta en un Web Worker. El cálculo intensivo queda separado del hilo de interfaz, que permanece receptivo y puede cancelar o ignorar una evaluación obsoleta. El resultado se entrega completo al finalizar, sin mezclarlo con el análisis de una pista nueva.

Búsqueda en anchura (BFS) por capas

Cada capa de BFS corresponde a un número de movimientos. La primera capa que contiene llegadas válidas fija el mínimo. Se completa esa capa para no perder otros estados finales con el mismo número de movimientos y después se eliminan los estados que no pertenecen a ninguna trayectoria óptima.

Programación dinámica con enteros arbitrarios

Para cada estado se acumula cuántas trayectorias llegan hasta él. La programación dinámica reutiliza los resultados compartidos y BigInt conserva exactamente todos los dígitos del conteo.

Sumando los conteos de los estados finales se obtiene el número total de trayectorias óptimas. El mismo principio permite contar solo las que conducen a estados finales continuables. Así se han manejado pistas con más de 10²³ trayectorias óptimas sin construir cada trayectoria por separado.

Complejidad computacional del modelo académico

Holzer y McKenzie estudiaron varias preguntas de decisión sobre el Racetrack académico. Sus resultados respaldan que la representación natural sea un grafo de estados que incluya posición y vector, pero no proporcionan una poda ni una aceleración directa para los cálculos del Editor.

Qué es una trayectoria óptima con continuidad

Esta definición mantiene un significado único para “óptima”: siempre se refiere al menor número absoluto de movimientos. Si ninguna trayectoria óptima absoluta puede continuar, se busca otra clase distinta, la trayectoria continuable de mínimo número de movimientos. Esta segunda necesita más movimientos que la óptima absoluta.

Cómo se calcula

1. Se construye la primera capa de llegadas. La BFS fija m* y conserva en un DAG todos los estados y movimientos que forman trayectorias válidas de esa longitud.
2. Se distinguen los estados finales. Dos trayectorias que terminan en la misma posición pero con vector o capa diferentes no dejan la misma posibilidad para la vuelta siguiente.
3. Se certifica otra vuelta. Desde cada estado final, el Editor comprueba si existe una trayectoria válida que cruce la salida y después vuelva a cruzar la meta.
4. Se filtran y cuentan las llegadas. La programación dinámica suma con BigInt cuántas trayectorias óptimas desembocan en estados finales certificados.
5. Se profundiza solo si hace falta para la IA. Si la capa m* no contiene ninguna continuable, el generador de trai/troi continúa la BFS hasta la primera profundidad mcont que sí la tenga.

El porcentaje que muestra el Editor se calcula siempre sobre las trayectorias de m*. Por eso puede mostrar 0 % aunque el generador de biblioteca encuentre después una trayectoria continuable de mcont movimientos.

Dos preguntas distintas

Aptitud general

¿Existe alguna trayectoria válida que cruce meta, vuelva a cruzar salida y alcance meta otra vez?

Continuidad óptima

De todas las llegadas con el mínimo número absoluto de movimientos, ¿cuántas permiten completar otra vuelta?

La primera comprobación aplica una precondición topológica y después explora exhaustivamente la secuencia de dos vueltas. La precondición evita que un tramo como Espiral sea clasificado como circuito por una vuelta atrás geométricamente posible pero ajena al sentido de carrera.

Para la segunda pregunta, cada estado final conserva posición, vector y capa. No basta con que el coche haya llegado a meta: importa cómo ha llegado.

Qué ocurre si ninguna óptima absoluta continúa

El análisis visible del Editor conserva el dato: 0 óptimas continuables. Al generar los representantes de biblioteca para la IA, el planificador tiene otra obligación práctica: buscar la primera profundidad posterior que sí contiene trayectorias continuables. trai y troi pueden, por tanto, emplear algún movimiento más que el óptimo absoluto si esa es la mínima penalización necesaria para encadenar vueltas.

Distancia euclidiana

La longitud de una trayectoria es la suma de las longitudes de sus vectores. Para verde y azul se comparan expresiones exactas como sumas de radicales y también se cuentan exactamente los empates.

La amarilla se selecciona con Dijkstra usando valores numéricos y una tolerancia de 10⁻⁶. Una vez escogida, su longitud se reconstruye como expresión radical exacta. Por ello, no debe describirse su proceso de selección como aritmética simbólica completamente exacta.

trai, troi y tray

Aunque sus nombres proceden de extensiones históricas, trai, troi y tray se almacenan como campos asociados a cada pista dentro de la biblioteca de trayectorias. Si existen óptimas absolutas con continuidad, los representantes trai y troi tienen m* movimientos; si no existen, usan la primera profundidad continuable mcont.

Descomposición por ejes

Tras n movimientos, las aceleraciones elegidas determinan un intervalo exacto de velocidades y posiciones posibles en cada eje. El motor combina después los intervalos horizontal y vertical.

Fijados n y el cambio total de vector, las posiciones posibles llenan un intervalo entero exacto, sin huecos. El motor precalcula máscaras de alcanzabilidad hasta un segmento finito de meta y cruza las condiciones de X e Y para hallar el primer número de movimientos cinemáticamente posible.

Por qué la poda es segura

La envolvente es una relajación: ignora la forma concreta de la pista, capas, ocupación y algunas restricciones de validez. Puede aceptar un falso positivo —“quizá sea posible”—, pero un resultado negativo demuestra que ni siquiera la cinemática libre alcanza el objetivo. Solo esos negativos se usan para podar.

Frenado discreto de F1-RaceTrack

Si una componente tiene velocidad entera u, la distancia acumulada al reducirla en una unidad por turno hasta cero es:

Esta expresión no es la distancia v²/4 de la variante física de Vawter: aquella emplea otras aceleraciones y otra actualización de posición.

Dos usos diferentes

El caso de A*

Se construyó una prueba comparativa con una heurística admisible derivada de las envolventes. Redujo estados, pero no ofreció una mejora temporal uniforme y cambió la trayectoria visible cuando había empates. El motor conserva BFS porque mantiene todos los empates necesarios para el conteo y ofrece una elección estable de representantes.

Cada combinación se midió en un proceso independiente, con una pasada de calentamiento y tres pasadas cronometradas. Los porcentajes siguientes describen ese entorno de ensayo y no una promesa de rendimiento para cualquier equipo o pista.

En los tramos no circulares el bloque de continuidad no es aplicable y los otros tres pesos se renormalizan. La cobertura obtiene su puntuación máxima al alcanzar el 50 % de la superficie relevante; la ventaja experta, cuando la trayectoria euclidiana más corta necesita un 25 % más de movimientos; y la diversidad combina un 40 % de separación euclidiana con un 60 % de separación espacial.

Corrector por trayectorias separadas, límites y calificación

Un corrector entre 0,90 y 1 pondera si las trayectorias aprovechan opciones espacialmente separadas. Es un indicador heurístico: no demuestra por sí mismo que existan ramales topológicos. Si el porcentaje de continuidad mostrado se redondea a 0,00 %, la nota final queda limitada a 19 puntos.

Las bandas de calificación son:

Alonso

• Intenta alinearse con trai, la representante precalculada más larga entre las óptimas elegibles; en circuitos, además, debe ser continuable.
• Reutiliza su trayectoria calculada mientras el siguiente movimiento siga disponible.
• La vía directa comprueba posición y vector y valida el movimiento inmediato; cuando la trayectoria se entrega como preferencia al Web Worker, el planificador reproduce y valida la trayectoria completa.
• Si la trayectoria ya no encaja o el siguiente destino está ocupado, recalcula mediante BFS desde el estado actual.
• En circuitos exige continuidad. Si ninguna óptima absoluta continúa, busca la primera profundidad continuable.

Amateur

• Usa una búsqueda local con límites de 60.000 estados y un reintento ampliado de 220.000.
• Si existe una trayectoria de un movimiento adicional, la elige con una probabilidad del 42 %.
• En los demás casos sortea entre hasta tres óptimas de menor longitud euclidiana.
• No se le exige continuidad, porque debe dejar margen a un humano experimentado para batirlo.
• No sigue troi; su política se calcula desde la situación actual y conserva la trayectoria hasta agotarla o bloquearse.

Demo

Mediciones de las envolventes

Son mediciones orientativas de tiempo de pared en un entorno local. El recálculo de 4_Esquinas resume seis ejecuciones; las evaluaciones completas de Caleidoscopio y Candelabro usan la mediana de tres procesos independientes por pista. La carga del equipo y del navegador puede cambiar los tiempos, pero no los conteos deterministas.

Estos datos muestran una mejora medible sin alterar los resultados del conjunto de control. No permiten extrapolar la misma mejora a todas las pistas ni a todos los estados.

Límites formales y de implementación

1. Fase de apertura en el DAG óptimo. La clave principal no incluye la fase saturada de apertura. Existe un caso adversarial teórico si un mismo estado cinemático reaparece en fases distintas antes de que la regla deje de importar.
2. Selección amarilla. Dijkstra compara distancias con number y tolerancia 10⁻⁶; la expresión exacta se reconstruye después, no gobierna toda la cola de prioridad.
3. Dominio de las envolventes. El horizonte precalculado llega a 256 movimientos, exige coordenadas enteras seguras y metas ortogonales. Fuera de ese dominio el sistema falla de forma conservadora: no poda.
4. Punto de evaluación. El Editor analiza el coche y la dirección inicial configurados en la pista; no recalcula todas las plazas posibles de una parrilla multijugador.
5. Circularidad durante la carga. El Editor realiza una comprobación exhaustiva para analizar la pista. El lector de pistas del juego conserva límites operativos de estados y movimientos para mantener una carga ágil.
6. Fase del movimiento final. La carrera conserva un cruce de salida posterior a meta dentro del mismo movimiento. La certificación del Editor parte del estado cinemático final y exige un cruce de salida posterior; por ello puede explorar más movimientos de los necesarios para la regla de carrera.
7. Ocupación dinámica. Una trayectoria válida en un turno puede bloquearse en el siguiente por el rival; por eso el juego valida el destino inmediato y recalcula cuando procede.
8. Rendimiento. Una reducción de estados no implica automáticamente menor tiempo de pared. Caché, asignaciones y orden de empates también influyen.

1. Michael A. Bekos, Till Bruckdorfer, Henry Förster, Michael Kaufmann, Simon Poschenrieder y Thomas Stüber, Algorithms and Insights for RaceTrack, FUN 2016, LIPIcs 49:6. Fuente académica principal sobre grafos de estados, BFS, regiones de aterrizaje, estrategias limitadas y complejidad. Publicada con licencia CC BY 3.0.
2. Markus Holzer y Pierre McKenzie, The Computational Complexity of RaceTrack, FUN 2010, LNCS 6099, pp. 260–271. Clasifica la complejidad de varios problemas de decisión del modelo académico de Racetrack; no clasifica el conjunto completo de reglas ni el rendimiento práctico de F1-RaceTrack.
3. Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics, 1968. Referencia fundacional de A*, utilizada para situar la prueba comparativa.
4. Richard Vawter, Physics of the game of racetrack, American Journal of Physics 46, 1978. Variante físicamente motivada con reglas distintas a la cinemática de F1-RaceTrack.
5. Keith A. Joyner y Clyde J. Smith, Comments on “Physics of the game of racetrack”, American Journal of Physics 47, 1979. Representación posición–vector y catálogo de variantes de reglas.
6. Martin Gardner, Mathematical Games, Scientific American, enero de 1973. Una de las referencias históricas de difusión del juego sobre papel cuadriculado.
7. Racetrack (game), Wikipedia. Referencia secundaria para terminología, reglas comunes y variantes; no se usa como autoridad del comportamiento específico de F1-RaceTrack.