Pathfinding mediante homeomorfismos

Question

En primer lugar, me gustaría matizar esto diciendo que no tengo experiencia en topología. Así que tened paciencia conmigo.

He estado contemplando los algoritmos de pathfinding para un juego en el que estoy trabajando. He pensado en la idea de intentar abstraer el mapa en alguna noción de espacio topológico. Me preguntaba si existe una manera de hacer arbitrariamente algo como lo siguiente.

Ignorando cuestiones como los agujeros en el espacio topológico, ¿hay alguna manera de transformar en general algo como la imagen superior en algo como la inferior? Si es así, entonces parece que puedo más o menos dibujar una línea recta para encontrar mi camino y luego mapear las coordenadas de las líneas de nuevo en el primer espacio para obtener mi camino. La incrustación de algo como esto podría hacerse en tiempo de compilación y, por lo tanto, parece que podría ser tremendamente potente para ejecutar un pathfinding rápido.

Para ser preciso, mi pregunta exacta sería probablemente: ¿existe un algoritmo para traducir una versión informática de un mapa (podría ser alguna forma de gráfico, o polígonos) a un cuadrado unitario que preserve la topología de esta manera? Supongamos que el género es cero (hasta ahí llega mi conocimiento de las palabras de moda).

Answer 1

El problema básico de tu enfoque es que quieres sustituir algo discreto (un gráfico), que se entiende muy bien y es adecuado para el procesamiento informático, por una estructura continua, y las cosas continuas son conocidas por implicar todo tipo de problemas nuevos con errores de redondeo, finitud de la representación, etc., cuando intentamos hacer cosas con ellas en los ordenadores.

Es decir no progreso.

Más concretamente, supongamos que tenemos una incrustación de nuestro mapa en el cuadrado de la unidad (lo que siempre es posible de alguna manera si y sólo si el gráfico es plano), y compila alguna representación de esa incrustación en su programa. Entonces, si tienes una línea recta entre dos puntos del cuadrado unitario, ¿cómo vas a averiguar algorítmicamente qué habitaciones del mapa son tocadas por tu línea roja, y en qué orden? Las opciones precisas dependen de cómo elijas representar la incrustación, pero en los casos que puedo imaginar fácilmente, acabarías haciendo o bien algo equivalente a los recorridos de un gráfico, o algo más caro que eso, antes de que su línea roja imaginada pueda convertirse en una lista real de movimientos.

Además, es probable que no termines con un El más corto cuando hay varios posibles. Y si la longitud del camino no te importa, puedes declarar arbitrariamente que una de tus habitaciones es un "centro" y luego calcular estáticamente para cada habitación qué dirección te llevará más cerca del centro. A continuación, construye tu ruta de A a B como la ruta canónica de A a centro, seguida de la ruta canónica inversa de B a centro.