¿Backtracking para buscar caminos?

[Battyhal]

¡Muy buenas a tod@s!

Estoy tomando clases de programación en C++ con el objetivo de crear un videojuego sencillo (de momento estoy con la consola de comandos, nada de entorno gráfico así que imaginaos mi nivel  ^_^'). Actualmente estamos con un RPG básico en el que el mapa es un array de dos dimensiones y se me ha pedido que implemente una función de búsqueda de camino para que los NPCs ataquen al jugador. Hasta aquí todo normal, pero lo que me han dicho es que tengo que usar el algoritmo 'backtracking' para ello y leyendo un poco por varios sitios me ha parecido que dicho algoritmo igual no es el mejor para este tipo de tareas porque, en este caso, daría como solución un 'conjunto' de coordenadas (o sea un camino) que debería seguir el NPC en base a la posición del jugador, pero ¿qué pasa cuando el jugador se mueva?, ¿hay que recalcular todo de nuevo no?. Vamos que estoy más perdido que el Papa en La Vegas, si alguien me puede iluminar un poco al respecto sería la bomba.

Muchas gracias por vuestro tiempo y  un saludo.

[[EX3]]

¿qué pasa cuando el jugador se mueva?, ¿hay que recalcular todo de nuevo no?.

En parte tu mismo te has respondido :)

Aquí realmente tienes varias opciones según el tipo de comportamiento que le quieras dar a la IA. Yo en una practica del master hice que mis enemigos, cuando están en modo patrulla, sin saber del jugador todavía, y detectan la posición de jugador por un evento de alerta (correr, disparos...) pero no lo ven directamente (digamos que lo han "oído") guardan esa posición y se dirigen a ella, haciendo como que lo buscan. Solo cuando tienen localizado y a la vista al jugador sin que un obstáculo este por medio (o este sigue generando eventos de alerta notorios para el enemigo) es cuando recalculan continuamente su posición para llegar a el.

Si te preocupa el estar recalculando continuamente rutas cuando se mueve el jugador, lo que puedes hacer es calcular la ruta cada x tiempo (a intervalos pequeños de tiempo para dar sensación de continuidad).

Salu2...

[Battyhal]

O sea que sirve para calcular la ruta entonces  ^_^', que equivocado estaba. Al leer sobre ello y encontrar que se hablaba sobre todo de otros algoritmos (A*, Dijkstra, Breadth first...) pensaba que igual el profe se había equivocado jejeje. Que atrevida es la ignorancia  ;). Bueno, voy a estudiar el tema a ver si me entero de algo. Pero si alguien conoce algún tutorial o algo por el estilo para 'dummies' que no deje de decírmelo por favor  :D.

¡Mil gracias [EX3]!.

[[EX3]]

O sea que sirve para calcular la ruta entonces  ^_^', que equivocado estaba. Al leer sobre ello y encontrar que se hablaba sobre todo de otros algoritmos (A*, Dijkstra, Breadth first...) pensaba que igual el profe se había equivocado jejeje

Hombre, el A* diría que es el más utilizado, pero vamos, use el que uses, tendrás si o si que recalcular la ruta para seguir la posición del player donde se mueva, no te queda otra.

Salu2...

[ZaGaLo]

Hola Battyhal, si te decides por el A*, este link me fué muy útil en su día.
Explica con mucha claridad (y traducido al español) el funcionamiento del algoritmo.  ;)

http://www.policyalmanac.org/games/articulo1.htm

Saludos!!  :)

[coloal97]

Buenas me gustaría saber como haces para mover al personaje en tiempo real por consola o hacer que los enemigos estén moviéndose e  tiempo real, si es que es así como lo estás haciendo. Que describieras en sí un poco el planteamiento del juego para poder abordarlo yo también ya que no tengo ni idea de usar interfaces gráficas pero si se c++ y todo lo que he hecho es por consola(un tres en raya pochísimo JAJAJAAJA) pero bueno por empezar pòr algún sitio al menos.

[Battyhal]

Hola Battyhal, si te decides por el A*, este link me fué muy útil en su día.
Explica con mucha claridad (y traducido al español) el funcionamiento del algoritmo.  ;)

http://www.policyalmanac.org/games/articulo1.htm

Saludos!!  :)

¡¡ Muchas gracias por la información ZaGaLo !!. Voy a echarle un ojo ahora mismo  :).

[Battyhal]

Buenas me gustaría saber como haces para mover al personaje en tiempo real por consola o hacer que los enemigos estén moviéndose e  tiempo real, si es que es así como lo estás haciendo. Que describieras en sí un poco el planteamiento del juego para poder abordarlo yo también ya que no tengo ni idea de usar interfaces gráficas pero si se c++ y todo lo que he hecho es por consola(un tres en raya pochísimo JAJAJAAJA) pero bueno por empezar pòr algún sitio al menos.

Yo de momento no utilizo ninguna biblioteca gráfica. Empecé a trastear un poco con ALLEGRO 5.0 pero nada más. De momento estoy con la consola  ^_^'. Si quieres puedes ver los videos de este hombre que he encontrado recientemente y es un verdadero CRACK con la consola, hasta se ha hecho un motor. Es en inglés pero se entiende fenomenal.

http://onelonecoder.com/

Espero que te sirva, estoy aprendidendo mucho con esto  :)