¿Cuál es la forma más rápida de determinar si una serpiente tiene un camino hacia su cola?

Si está interesado en leer sobre el trabajo de CS en problemas similares, esta es esencialmente una versión restringida de conectividad st no dirigida (existe una ruta entre los vértices syt) conocida como “accesibilidad de gráfico de cuadrícula”. La mayor parte del enfoque de la investigación se ha centrado en la complejidad espacial de la pregunta de accesibilidad, ya que los algoritmos habituales de ruta más corta darán una solución de tiempo lineal.

Un problema alternativo interesante sería un “solucionador” de serpientes: dado un juego de serpientes en un estado particular, ¿existe una estrategia para llevar a la serpiente a su comida, sabiendo que la cola sigue el camino de la cabeza? (y más allá de eso, ¿qué estrategia para llegar a la comida maximizará la probabilidad de la comida subsecuente, colocada al azar?)

Comience en la cabeza. traza hacia atrás a lo largo del costado de tu serpiente, como si acabara de girar. rastrear alrededor de cada objeto que encuentre.
Si golpeas la cabeza nuevamente antes de llegar a la cola, no tienes camino: simplemente trazaste el exterior del área que puedes alcanzar, determinaste que no hay aberturas y que la cola no está dentro de esta área. Este será el costo mínimo para descartar un camino.
Si existe una ruta, entonces A * probablemente podrá encontrar esa ruta más rápido que esto, pero si no existe ninguna ruta, creo que tiene que explorar el área completa a la que puede llegar. Imagine una situación como la que muestra, solo que la mayor parte del tablero está dentro del área, con la cola en una sola fila debajo de ella. esta rutina tendrá un costo del perimitador, mientras que A * tendrá un costo del área.

Estoy tratando de averiguar si hay un atajo. Por ejemplo. Sé que si dibujas una forma arbitraria, puedes averiguar si un punto está contenido dentro de él por cuántas veces una línea que va fuera de la forma lo intersectará. Si es extraño, estás dentro, incluso si estás afuera. Sin embargo, no creo que eso ayude aquí. Puede idear formas con números arbitrarios de segmentos entre usted y la cola.

Algoritmo de Lee
Creo que puedes aprender más de la traducción de Google de un artículo rumano sobre él, que lo explica mucho mejor: Algoritmul lui Lee.
Es decir, una búsqueda de Breadth first si desea una solución directa.

Posiblemente el algoritmo A * (A-star). Básicamente es un algoritmo que encuentra la forma más rápida del punto A al punto B. Puede leer este artículo wiki para comprender mejor cómo funciona. A * algoritmo de búsqueda

Hay dos preguntas separadas:

1. ¿Está atrapada la serpiente?
2. ¿Tiene un camino hacia su cola?

Para la pregunta que hizo (2), haría un relleno (buscarlo en wikipedia) desde un extremo y comprobar si me encuentro con la cola en algún momento.

Pero esto no es equivalente a la primera pregunta. Por ejemplo, si solo invertimos la cabeza y la cola en su imagen, la serpiente no queda atrapada, aunque no haya un camino desde la cola hasta la cabeza.