Depende del tipo de mapas que quieras usar (y tipo de juego).
Puedes construirlo mediante un grafo de nodos puestos en el editor de mapas, mediante nodos autocalculados a partir de objetos o información específica en el mapa, por floodfill a partir de un punto transitable (comprobando las direcciones en las que puede viajar un objeto que se encuentra en dicho punto), con trayectorias largas precalculadas y radios de libertad, simples colisiones estáticas.
No es necesario que sean tiles, aunque si quieres trabajar con tiles lo mejor en mi opinión sería el floodfill.
Opción 1)
Parte de un punto transitable (puedes ponerlo en el editor de mapas). Comprueba las 8/4/N direcciones en las que se puede mover mediante una esferea o cilindro de colisión (según personaje), si no hay colisión, puede pasar, si hay colisión ese camino A -> B y B -> A no son transitables.
Esto te da un mapa de tiles donde cada tile guarda la información de a qué vecinos se puede viajar desde él.
Opción 2)
Dispara un rayo de colisión (de radio el ancho del personaje) en el eje vertical sobre cada celda. Si hay colisión no es transitable, si no hay colisión es transitable.
Opción 3)
En vez de por colisión, si tienes acceso a los objetos del mapa (leyendo el mapa), puedes coger su bounding box (no alineada) y para cada celda que hay contenida en ella, si ciertos puntos entran dentro no es transitable. (Ciertos puntos = al menos 2 esquinas, al menos 2 esquinas y el centro, 3 esquinas, todos, etc; depende de la estrategia que quieras). Para saber si una celda está dentro, o mejor uno de sus puntos, puedes clasificar el punto en los 4 planos laterales de la bbox (asumiendo que los objetos están en el suelo obviamos las tapas). Si es el punto es interior a los N planos, está dentro. Si cumple la estrategia (N puntos dentro, ..) no es transitable.
En fin. Son algunas ideas, que pueden no ser las mejores, pero que funcionan. Ten en cuenta que es preprocesado, por lo que no tiene que ser extremadamente rápido. (Aunque si es extremadamente lento algún diseñador de mapas se quejará
)
