Implementar la búsqueda de ruta en un mapa en tres dimensiones ha evidenciado por qué muchos juegos se resisten a explotar las tres dimensiones. Incluso en un espacio relativamente pequeño de 64x64x8 (32.768 casillas), he necesitado paralizar algunas de las búsquedas después de unas 300 peticiones de casillas, porque bloqueaba demasiado el sistema.

Para solucionarlo, en un primer momento pretendí utilizar el multiproceso: enviaría las búsquedas de ruta al resto de núcleos del procesador y que me devolvieran el resultado cuando lo lograran. Por desgracia, cada búsqueda de ruta necesita usar el bloque de memoria del mapa con toda la información sobre las 32.768 casillas (que además incluyen para cada una las coordenadas vecinas y accesibles). El tamaño alcanza unos ocho megas, una cantidad de datos demasiado grande para dispersar por el resto de núcleos sin que paralizara el núcleo principal. Si sólo diseminar las peticiones de búsqueda de ruta a otros núcleos del procesador tarda más que ejecutarlos en el mismo procesador, eso invalida la opción.

Uno de los problemas principales es que la búsqueda de ruta no entiende que por mucho que el destino sea una casilla atravesable por un agente no implica que pueda llegar hasta ella. Por ejemplo, una casilla en la cima de una montaña pero rodeada de acantilados es accesible si ya empiezas en ella, pero no si falta una ruta hasta la cima, y averiguarlo puede implicar que el algoritmo A*, que busca la ruta, pruebe literalmente miles de casillas de las potenciales 32.768.

La solución más interesante que descubrí es la búsqueda de ruta jerárquica: consiste en dividir un mapa en sectores de cierto tamaño (recomendaban 16 casillas en todas las dimensiones), y dentro de cada sector identificar las regiones de casillas accesibles. En mi caso el asunto se complica porque no sólo incluyo tres dimensiones, sino diferentes tipos de movimiento. Mis agentes andan, nadan por aguas poco profundas, por aguas profundas, o por el aire. No hay además impedimentos a nivel programático para que pudieran hacer una combinación de esas cosas: por ejemplo, alguna criatura anfibia, o pájaros que se sumergieran en el agua. Una vez el mapa original está dividido en sectores y regiones, se calcula el centro de masa de cada región para determinar su centro, y serán esos centros de región los que se usarán para buscar una ruta en el mapa. Eso conseguirá que descubrir que no se puede acceder a una casilla aislada se reduzca a mirar quizá unos diez centros de región, en vez de literalmente miles de casillas. Además, una vez se ha determinado una ruta a través de los centros de región, la ruta en el mapa entero puede realizarse de centro de región en centro de región, lo que también limita esas búsquedas a una media de unas 16-20 casillas.

Para asegurar que la programación sectorizaba los mapas correctamente (mapas que además se generan cada vez mediante el algoritmo de ruido Perlin), me planteé programar un visualizador. El siguiente vídeo muestra el primer intento de implementar la sectorización, pero fallé en identificar las regiones correctamente, como explicaré después.

El vídeo muestra las regiones coloreadas en función del número que se les ha asignado; en cada sector las regiones empiezan desde 1, y el contador sube tanto como necesita. Las cruces indican los centros de región. Que regiones aparentemente contiguas aparecieran coloreadas de maneras diferentes habría debido avisarme de que algo funcionaba mal. Aunque las regiones creadas parecían razonables para los agentes voladores y nadadores, los cambios de elevación destrozaban la identificación de regiones para los agentes que andan. Cada vez que la elevación cambiaba se creaba una región nueva, algo que no tiene sentido, ya que los agentes podrían usar las rampas para desplazarse.

Por fortuna yo ya había programado esas comprobaciones complicadísimas de accesibilidad para buscar la ruta de casilla en casilla. Cada casilla del mapa original incluye la información sobre sus vecinos accesibles. De cada una de esas listas convertí las coordenadas al sistema de coordenadas internas de cada sector (de 0 a 15 en las dimensiones x e y, y de 0 a 7 en la z), y las añadí como vecinos internos siempre que el vecino existiera en el mismo sector.

El resultado se ve en el siguiente vídeo.

Muestra con claridad, particularmente en el extremo superior izquierdo del mapa, cómo la sectorización ha considerado que los cambios de elevación formaban parte de la misma región. Hay un caso interesante en el extremo superior derecho del mapa, donde en un sector que coincide con la cima de la montaña se han identificado dos regiones distintas, una en la cima y la otra en la tierra que rodea la base, porque un acantilado impide la ruta.

La sectorización de un mapa para programar una búsqueda de ruta a este nivel implica también reconocer las fronteras de un sector, y si están abiertas al tránsito en esa dirección. Aunque está programado, el visualizador del vídeo no lo muestra.

Ahora queda adaptar el algoritmo A* de búsqueda de ruta, ya programado, para que sólo considere los centros de región, y hará algo similar a lo siguiente: