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

Tanto el DAG óptimo como el cálculo de la trayectoria amarilla distinguen la fase temporal de apertura. Mientras la restricción inicial está activa, llegar al mismo estado físico tras cuatro movimientos o tras cinco puede permitir continuaciones diferentes. Después del quinto movimiento esa fase ya no restringe y se fusionan las historias equivalentes. En la búsqueda con lluvia se conserva la inercia anterior solo desde el umbral de velocidad que hace relevante ese dato.

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 condición topológica previa y después explora la secuencia de dos vueltas con los movimientos válidos del Editor. El juego usa el mismo criterio y puede detenerse en cuanto demuestra que existe una segunda vuelta; la evaluación completa conserva los conteos que necesita. La condición previa evita clasificar un tramo como Espiral como circuito por un regreso geométricamente posible en sentido contrario a la 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. En ese caso, la cobertura roja y los representantes verde y azul muestran todas las óptimas absolutas y sus extremos de distancia. Ese mismo conjunto permite evaluar Distribución, Diversidad y Ventaja experta; Continuidad aporta 0/15 y la pista sigue siendo un circuito, sin renormalizar los otros pesos. 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. La continuidad nula aporta 0 de sus 15 puntos, sin imponer un límite adicional a la nota final.

Las bandas de calificación son:

Alonso

• Frente a un humano conduce el coche azul, que sale segundo. Intenta reutilizar trai, la representante precalculada más larga entre las óptimas elegibles, para evitar una nueva búsqueda; en circuitos, además, debe ser continuable.
• Reutiliza su trayectoria calculada mientras el siguiente movimiento siga disponible.
• El Web Worker reproduce la trayectoria preferida desde posición, vector, capa, fase de apertura y Meteo actuales; comprueba llegada y continuidad cuando procede. Si la acepta, la reutiliza sin buscar otra. El acceso rápido solo emplea resultados ya validados para ese contexto, no basta con que el primer movimiento esté disponible. Esta validación comprueba validez y continuidad; el carácter óptimo de trai procede de su cálculo previo, no se demuestra otra vez.
• 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 de hasta 60.000 estados, ampliable a 220.000 sin reiniciarla si aún no hay llegada. Agotar el presupuesto significa cálculo inconcluso, no ausencia de trayectoria: en ese caso continúa con el motor exacto en un Web Worker.
• Al elegir una nueva trayectoria, intenta añadir un 8 % al mínimo de movimientos restantes hasta meta, redondeado al entero más cercano. Si un bloqueo o un cambio de Meteo exige recalcular, aplica el porcentaje al nuevo mínimo restante, sin un presupuesto acumulado por vuelta ni un ajuste en cada movimiento.
• Parte de una trayectoria mínima; la búsqueda local sortea entre hasta tres de menor longitud euclidiana. Sustituye tramos cortos por alternativas válidas con un movimiento adicional, conservando posición, velocidad, nivel y memoria de inercia al reincorporarse. La primera intersección y el tramo de llegada se conservan.
• No se le exige continuidad. El ajuste está limitado a 30.000 estados y 256 intentos, con un máximo de 1.500 estados por intento. Si no alcanza el objetivo, conserva la mejor aproximación encontrada. No añade esperas en una misma intersección ni bucles para retrasarse y respeta las mismas reglas de lluvia y movimiento del Editor.
• No sigue troi; conserva la trayectoria mientras sea válida. Aplica el mismo ajuste a las nuevas trayectorias obtenidas del motor exacto o del respaldo almacenado, sin modificar la biblioteca ni los resultados óptimos en caché.

Demo

El objetivo se calcula sobre lo que queda por conducir

Si N es el número de movimientos de la trayectoria mínima desde el estado actual hasta meta, se calcula un incremento entero Δ. El objetivo usa movimientos; la longitud euclidiana solo ayuda a elegir la trayectoria de partida.

Una trayectoria mínima de 50 movimientos da un objetivo de 54. Para 26, se buscan 28: dos movimientos más equivalen al 7,69 %. Si solo quedan seis, el incremento redondea a cero. Estos ejemplos explican por qué el porcentaje es aproximado.

Sustituir tramos sin descomponer el resto de la trayectoria

1. Obtener la referencia. La búsqueda local encuentra mínimos movimientos y sortea entre hasta tres trayectorias de menor longitud euclidiana. Si el cálculo local queda inconcluso, puede recurrir al motor exacto; el respaldo almacenado también puede aportar una trayectoria validada. El ajuste opera sobre una copia de la referencia recibida.
2. Reconstruir los estados. Cada intersección lleva asociadas velocidad, nivel, movimientos acumulados y memoria de si el movimiento anterior fue de inercia. Se comprueba la trayectoria con las mismas reglas de movimiento y Meteo que usa el Editor.
3. Buscar una sustitución corta. Se examinan tramos de 4, 6 u 8 movimientos y se intenta sustituir cada uno por otro de 5, 7 o 9. Cada sustitución aceptada añade exactamente un movimiento. Se conservan la primera intersección elegida y el tramo final de llegada.
4. Reincorporarse al mismo estado cinemático. La alternativa debe terminar en la misma posición, con la misma velocidad, nivel y memoria de inercia. Después se valida de nuevo toda la trayectoria modificada antes de aceptarla.
5. Repetir hasta alcanzar el objetivo o agotar la búsqueda. Las siguientes sustituciones avanzan por la trayectoria y el incremento nunca supera Δ. Si faltan alternativas válidas, se conserva el incremento conseguido, que puede ser menor o incluso cero.

La búsqueda de la alternativa descarta posiciones repetidas dentro del tramo y las que ya pertenecen a otras partes de la trayectoria. No introduce paradas en la misma intersección ni bucles para consumir movimientos, y no permite cruzar meta antes del tramo final.

Lluvia, bloqueos y vueltas sucesivas

La memoria de inercia forma parte del estado de reincorporación porque, con lluvia, condiciona el siguiente movimiento permitido. Las intersecciones ocupadas se comprueban para el movimiento inmediato; las posiciones futuras del rival no se dan por conocidas.

Mientras la trayectoria sigue siendo válida, Amateur la conserva: no añade otro 8 % en cada movimiento. Si un bloqueo o un cambio de Meteo obliga a calcular otra, el porcentaje se aplica a los movimientos mínimos que quedan desde el nuevo estado. Por ejemplo, si en ese momento quedan 25 movimientos mínimos, el nuevo objetivo es 27; los movimientos ya realizados no se vuelven a incrementar.

No hay un presupuesto acumulado por vuelta. Por ello, los recálculos, las penalizaciones y las distintas posiciones de partida pueden producir una diferencia final distinta del 8 %. En Demo, además, los coches intercambian Alonso y Amateur según el orden al iniciar cada vuelta; comparar los totales rojo y azul no equivale a comparar dos pilotos fijos.

Amateur no exige continuidad multivuelta. El ajuste mantiene el estado con el que termina la trayectoria de referencia: si esa llegada permite continuar, las sustituciones conservan esa posibilidad. El porcentaje por sí solo no convierte una llegada no continuable en continuable. Tampoco se vuelve a demostrar que un respaldo almacenado sea el mínimo absoluto desde cualquier estado.

Cómo se acota el coste de cálculo

El ajuste explora como máximo 30.000 estados en total, 1.500 por intento y 256 intentos. Antes de desarrollar una alternativa, unas cotas por eje descartan desplazamientos incompatibles con las velocidades inicial y final y los movimientos disponibles. También se evita repetir estados de búsqueda ya visitados.

Es una búsqueda acotada de sustituciones, no una enumeración de todas las trayectorias más largas. Al llegar a un límite devuelve la trayectoria válida conseguida. La función que implementa el ajuste es buildAmateurAiPlan, en src/ai-core.ts; chooseAiMove lo aplica una vez al obtener una nueva referencia. Las óptimas almacenadas, la caché y las decisiones de Alonso se conservan.

Resultados medidos y alcance del objetivo

Los ensayos del 23 de septiembre de 2026 incluyeron 17 trayectorias completas desde la parrilla; todas alcanzaron su objetivo redondeado. El ajuste adicional tardó entre 8 y 66 ms en este PC, ejecutando el motor en Node. Estas cifras excluyen la búsqueda inicial del mínimo y no predicen el tiempo de un iPad ni de otra plataforma.

Dos Demos de diez vueltas en Granada, una en seco y otra con Meteo cambiante, alcanzaron el objetivo en las 27 nuevas trayectorias de Amateur calculadas entre ambas. Son ejemplos comprobados; la búsqueda acotada no garantiza alcanzar siempre el porcentaje ni una frecuencia determinada de victorias humanas.

Mediciones de las envolventes

Son mediciones históricas orientativas de tiempo de pared en un entorno local, anteriores a la revisión de cálculos de septiembre de 2026. 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. Equivalencia de estados. La fase de apertura forma parte del DAG óptimo mientras afecta a las continuaciones. La corrección se contrasta con tres pistas válidas y una búsqueda independiente: 6 movimientos y 118 trayectorias; 9 y 588; 6 y 7. Con lluvia se distingue la inercia anterior solo cuando puede cambiar las opciones futuras. Coincidir en posición no basta para fusionar estados.
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. La poda del DAG se desactiva si se permiten llegadas exteriores que la envolvente no representa. Fuera del dominio compatible el sistema 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 juego comparte el criterio exacto del Editor: condición topológica previa y existencia de una segunda vuelta completa con las mismas reglas. Para responder sí o no puede detenerse con la primera demostración positiva y reutilizarla mientras no cambie la pista; no necesita contar todas las posibilidades.
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. En pistas complicadas el cálculo inicial, incluida la continuidad de una trayectoria guardada, puede tardar según el procesador del dispositivo. El punto del HUD parpadea mientras se calcula; cancelar la carrera también cancela el trabajo pendiente que ya no sirve.

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.