Por cierto, me olvide mencionar dos cosas: -Cuando se halla los costos (como en 5:40 o 6:32), como son distancias pues se ignora la existencia de obstáculos. -Si alguien se este preguntando en 6:32, porque simplemente no usar un pitagoras y ya (Osea dibujar una línea recta desde el nodo hasta el final y hallar esa distancia). Eso es porque hay varias formas de hallar la distancia, usar el pitagoras se llama distancia Euclidiana, la que use yo es una versión adaptada de la distancia Manhattan para mapas que permitan movimientos diagonales (Aunque puse en la notita al terminar la explicación que es una distancia Manhattan, en realidad en su forma mas pura esta NO se puede usar para mapas que permitan movimientos diagonales solo para mapas que permitan movimiento arriba abajo izquierda derecha), del material que me guíe a esa distancia la llaman "Distancia Diagonal". Sobre distancias y Heurísticas pueden guiarse más revisando este Link: theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#diagonal-distance
@@MinombreesSergio Mmm, mientras sean casillas, aunque sean pequeñas se puede usar A*. En juegos donde no se usen, mmm dependeria que juego, en los juegos 3d si usan un enfoque distinto por ejemplo, ahi usan "navmesh".
@@llamaelitista mmm interesante, y es muy enredado ese o aguanta segunda parte con navmesh? :v Me sirve porque quiero hacer un juego en 3D, con movimiento por click.
Es increìble que aprendí todo esto en la universidad y ahora viendo tu video me hiciste recordar y volver a entender todo pero de una manera más interesante
Tal cuál, yo me acuerdo de haberlo programado en C++ para encontrar un camino en el juego Mummy Maze. En ese caso no era necesariamente el más corto, ya que estábamos haciendo heurísticas que también tenían en cuenta la distancia a los enemigos y sus tipos de movimiento, pero fué muy interesante volver a ver la teoría
Básicamente cda vez que avanza un nodo guarda la información de "donde proviene" y cuando llega a la meta le pregunta a cada nodo "hey, ¿De donde vienes?". Me pareció buena la explicación
Este video es de mis favoritos en lo que a programación respecta, me recuerda mucho a uno que ví sobre animaciones procedurales, en el que en vez de mostrar el código y ya está, el autor explica como funcionan las cosas. Me encantan este tipo de videos porque te dejan tener un entendimiento más profundo de un tema y en base a eso podés generar un código en cualquier lenguaje de programación. Y lo más importante, entendés que es lo que hace el código. Por cierto, es impresionante que hayas hecho ese código en python para mostrar esto, se agradece mucho.
Es un video increíble. La facilidad con que explicas el algoritmo. Este algoritmo lo ví por primera vez en la universidad en la materia de Inteligencia Artificial.
no se que me parece mejor, si el hecho de que expliques un algoritmo que me ha llamado la atencion desde hace bastante o que lo hayas explicado con pseudocodigo en un archivo rust. desde ya me suscribo
Mis estudiantes estarán felices... Dios te bendiga... Ojala subas otros algoritmos qué se usan en video juegos... Que Dios te bendiga a ti y a tu familia... ❤❤❤
No se como llegué a este video si no programo videojuegos, pero me pareció super interesante y muy bien desarrollado!! Muchas felicidades, gran contenido!
11:11 Cuando te das cuenta de que el algoritmo A* también se puede implementar para escapar de algo jajajajja Muchas gracias por compartir, haces que internet valga la pena
casualmente hace unos dias hice una visualizacion de este algoritmo en angular, tuve que usar una clase para representar la cuadricula como una matriz de adjacencia, e iba guardando los mejores candidatos al camino mas corto con una cola de prioridad, cuando piensas que no usaras esas estructuras de datos y luego te encuentras en esa situación jajaja, te has ganado un suscriptor amigo.
No diseño videojuegos ni de lejos, pero soy ingeniero y me ha parecido muy interesante y entretenido. Felicidades por este pedazo de video, muy bien explicado
Solo he visto este video de tu canal, pero con esta calidad de explicación de algoritmos, me subscribí sin dudarlo. ¡En horabuena por semejante calidad! Espero sigas así.
Excelente video y explicacion de este algoritmo, es impresionante la forma en la que se omiten caminos costosos frente a rutas eficientes, aunque tambien esta el tema de que A* puede considerarse un algoritmo casi recursivo (evaluar un nodo mas de una vez), y que en casos MUY especificos sea menos eficiente que BFS u otros de crecimiento de area, por lo que en modelos mas complejos se suele implementar filtros que buscan patrones de forma o tamaño que seleccionan el algoritmo mas eficiente a utilizar antes de ejecutar la optimization. Tienes un nuevo sub :)
Me encanta tu contenido sobre algoritmos aplicados a videojuegos ayuda a dar una perspectiva histórica sobre cómo hemos llegado a los videojuegos de hoy. Me pregunto de dónde viene tu formación o qué te llevó a investigar sobre estas cosas.
Explicas de maravilla, gracias! Ahora, sería interesante un vídeo sobre su implementación en diferentes formas de medir distancias en contextos variados.
Increíble video, espero que sigas haciendo videos así! Son muy buenos y logras enseñar matemáticas y las bases de programación utilizando los videojuegos como un medio.
lo que vi en la carrera de ingeniería industrial con ejemplos aburridos ahora me colocan el ejemplo de videojuegos, gracias que buenos recuerdos viciar y entender lo que va atras del telon
Me parece muy interesante e intuitiva tu forma de explicar esos algoritmos.😊 Actualmente estoy estudiando una licenciatura en matemáticas y guardaré el codigo por si me sea necesario en un futuro 😅.
Wow amigo muchas gracias, en verdad me parece fascinante todo el tema matemático y ahora me doy cuenta que me gustaría investigar más el tema, gracias.
Muy interesante tu vídeo, me gusta como explicas ese algoritmo que está detrás de muchos juegos. Igual me gustaría saber cómo se aplicaría en entornos más complejos como por ejemplo caminos con curvas o en tres dimensiones
Los caminos con curvas pueden igualmente volverse una cuadrícula, simplemente tendrías que hacer nodos/casillas mas pequeños y ya, asi simulas una curva. Para modelos 3d, se puede usar A* , pero de forma un poquito mas compleja, a traves de lo que se conoce como "Navmesh", puedes buscar eso para mas info.
buen video. tengo muchisima experiencia en computacion......pero nunca me habia puesto a analizar ese algoritmo de encotrar el camino mas corto. soy mas partidario de la recursion que de la iteracion. estoy aprendiendo love para hacer juegos, creo qeu voy a marcar este video, el juego que tengo en mente no usa realmente rutas, pero algunos de los que tengo pensados si, asi que esto me sera muy util. creo que lo hare con recursion. tenga su like.
@llamaelitista hola acabo de ver el video, me gustó mucho como está explicado, me imagino que ya deben haber implementado una búsqueda de camino más corto que vaya del inicio al fin y del fin al inicio paralelamente que puedan compartir información cuando se lleguen a nodos intersectados por ambas búsquedas, eso debería reducir el tiempo a la mitad, pero no ví que se mencionara algo así en el video
Recuerdo cuando estudiaba en la ingeniería, nos enseñaron este algoritmo pero hacíamos todos los cálculos a mano para programar cómo una paquetería repartiría los pedidos que tuviera y otros ejemplos asì
Gracias a estas bases fue que comencé mucho antes que tú a desarrollar una ToolKit para Stride Engine de Pathfinding para juegos de RTS. La ToolKit que desarrolle se llama Northgard, y te preguntarás ¿por qué le puse ese nombre?, básicamente porque es uno de los juegos que paso gran parte de mi vida enviciado, un juego que a mi en lo personal está tan bien hecho mejor que el AoE, que no solo me genera nostalgia sus temas nórdicos sino, que es precisamente la inspiración que tuve a la hora de programar y producir la herramienta. Sin embargo, tuve que leer libros para entender funciones matemáticas, trigonometría y físicas de bajo nivel. Sin embargo tu vídeo lo resume de tal manera que parece simple pero no lo es. Programar no es lo mismo que desarrollar, desarrollar es cuando utilizas herramientas y funciones creadas por programadores, eso incluye los frameworks y el código scripting, los programadores creamos herramientas para que los desarrolladores lo utilicen, por eso el programador que sabe programar conoce las matemáticas, nunca se va a conformar con lo que le da el motor o framework, siempre buscará una forma de re-inventar la rueda aunque la rueda ya exista, precisamente se debe a esto: La programación es un Descubrimiento, el día de mañana puede existir un Z* del pathfinding por alguien que se animó a experimentar, probar nuevas cositas, el programador que sabe es un inventor por naturaleza, requiere de estudio constante y saber de matemáticas. S2 👨💻
buen video, me gustan las freakeadas sobre juegos, y mas sobre el desarrollo, me gusta la programacion, pero no he hecho aun mi primer juego serio, tengo q seguir avanzando,
6:32 está equivocado el costo H sería calculado por Pitágoras, de otra manera sería calcular los caminos mas cortos en cada iteración y pues no tenemos esa info. Debería ser una línea recta del nodo a la meta, solo contando en x y y, para luego usar sqrt(x*x+y*y)
En realidad hay distintas formas de hallar la distancia en el costo H (Heurística), la que planteas tu se llama distancia Euclidiana (que es hacer un pitagoras y ya), la que use yo es una forma adaptada de la distancia Manhattan, ambas funcionan, ya depende de como quieras adaptar tu algoritmo. Sobre lo del camino mas corto, si tienes razón, en realidad SI es como hallar el camino mas corto PERO cuando no hay obstaculos, como es una distancia, no toma en cuenta obstaculos asi que en realidad no se puede usar para hallar el camino mas corto. Sobre lo de que no existe info, si hay, existe una formula para hallar la distancia que estoy usando sin mas info que la posicion del nodo analizado y la posicion del nodo final. Checate este link, esta con el nombre de "Diagonal distance". theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#diagonal-distance
Muy buen video. Me gusta tu forma de explicar. Muy orientada a la práctica. Pero tengo que mencionar que A* no siempre encuentra el camino mas corto, a veces encuentra solo uno aceptable. Todos los algoritmos tienen algo que los hace mejor y peor que los otros en terminos de rendimiento, memoria y exactitud. A* destaca en los videojuegos por su eficiencia.
Excelente video! Finalmente entendí el algoritmo. No obstante tengo una duda: sería posible añadir un test de visibilidad (trace del nodo al jugador) en cada nodo del A* para que el camino no solo sea el más corto, sino también el más oculto a la vista del jugador? Estoy desarrollando un juego indie en UE5 y busco una forma de hacer que mis enemigos flanqueen de manera inteligente. He probado EQS, FSMs, y demás, pero parece que tendré que modificar el A* del engine para obtener buenos resultados. De ser posible, podría usar EQS para encontrar un punto en la espalda/laterales del jugador, y usar el A* modificado para que el enemigo se mueva hasta ese punto pasando por el camino con más coberturas. En cualquier caso, nuevo sub :) tienes contenido muy interesante, sigue así!
Mmmm, muy interesante, a si a primera prueba se me ocurre que podrías hacer que la vista del jugador se vuelvan nodos obstaculos, por ejemplo si tu jugador ve en línea recta todos esos nodos/casillas hasta choca su vista se vuelven obstáculos, en la realidad no son, pero para el algoritmo si serían por lo que tendría que calcular un camino que no implique pasar por esos nodos/casillas. Algo asi se me ocurre.
@@llamaelitista Una pena no poder poner imágenes por aquí, pero conseguido! Lo que he hecho es un trace desde cada nodo a un vector que llamo VigilVector, este puede ser la posición del jugador, el goal del path, lo que sea. Si hay un hit antes de llegar al Vigil, el nodo esta oculto, si no pues es visible. Si es visible, incurre un costo alto modificable. He metido parámetros para hacer offset variable también y que el trace no choque con el suelo. Me queda ajustar un poco los valores y meterle más parámetros para que se pueda aprovechar para más cosas que flanquear, pero funciona muy bien. No podría haberlo hecho sin ver este vídeo, me has ayudado a entender como funciona en muy poco tiempo y de forma sencilla, eternamente agradecido 🙏
Excelente video! Muy bien explicado.. solo me queda una duda con la parte de programacion... El nodo final se declara como variable tambien? En que parte del codigo se define eso? Osea que el código sepa donde esta el final...
En el age 2 cuando querias enviar algo en barco, muchas veces el barco venia a ti antes que tu al barco quizas la IA detectaba que el barco era mas rapido y por eso hacia eso.
Ese algoritmo no funciona en el AOEII DefinitiveEdition porque ahí hasta se ponen a bailar cuando los mueve en bola, se regresan o se quedan como idiotas caminando contra los edificios
Deberías añadir que A* puede llegar a consumir tanta memoria que se vuelve menos eficiente que Dijkstra. También deberías explicar que la función heurística no tiene por qué ser la Euclidiana (distancia hasta el objetivo) por ejemplo la Manhattan es interesante. Buen vídeo pero podría confundir a algunos que no sepan suficiente ya que A* no siempre es el más rápido y hay muchas alternativas en videojuegos como IDA*, BeFS o Jump Point.
"...También deberías explicar que la función heurística no tiene por qué ser la Euclidiana (distancia hasta el objetivo) por ejemplo la Manhattan es interesante..." En un comentario explicó esa cuestión. "...Buen vídeo pero podría confundir a algunos que no sepan suficiente ya que A* no siempre es el más rápido y hay muchas alternativas en videojuegos como IDA*, BeFS o Jump Point." El algoritmo A* es de utilidad solo cuando conoces el entorno por el que te mueves. En el hipotético caso en que no conozcas los caminos que tienes y los obstáculos con los que te podrías topar entonces puede resultar más perjudicial que beneficioso su uso. A mi parecer la explicación del video está bien para entender la idea o concepto del algoritmo.
Entonces, Tenemos años y años y años interactuando con algoritmos complejos de inteligencia artificial en base a modelos matematicos avanzados, pero las IA de hoy en día son mejores porque a una foto le puedes quitar la ropa a las personas. Pues así estamos
@@knator22 Creo que es la primera vez que alguien capta que uso musica de .hack en algunos de mis videos, no es muy comun encontrar fans de .hack jsjs.
Muy interesante. Oye una pregunta, cómo declaras los obstáculos en el código? Tengo una idea, supongo que le das un valor muy alto en los nodos declarados para así asegurar que no tomen esos valores. Pero no sé, ya hace años que ví estos temas. Fue para mi tesis pero yo usé el método de homotopia. Nunca lo implementamos en aplicaciones solo en simulación. Fue divertido, pero necesitaba trabajar y pos lo dejé.
en mi codigo cada nodo tiene un estado, los obstaculos tienen un status de "obstructed", asi que cuando esta sacando la lista de vecinos al hacer la revisión simplemente los ignora, como si no existieran.
Excelente explicación. Me queda una consulta, en el caso de tener dos caminos con el mismo costo, ¿cómo el programa decide cuál usar? Me imagino que de alguna forma es arbitrario, como que las casillas se analizan en cierto orden y el primero en analizarse será el elegido, pero quisiera tu opinión. Saludos!!
Estupendo vídeo, andaba recién buscando como implementar path finding en mi juego, y había leído que el algoritmo A era el mejor.... Una suerte que ya había decidido subdividir el mundo en una cuadrícula Edit: Lo que me cuesta entender es como se produce la heurística, no es ya de por sí una detección del camino?
Algo que no suelo ver juegos que puedan hacer es detectar cuando una ruta está obstruida con otros personajes En Mount and Blade Warband, si hay dos escaleras para atacar las murallas de un castillo, los atacantes se amontonan todos en la más cercana porque es el camino más directo para acceder al castillo, aunque signifique que tienen que hacer fila para subir, mientras los defensores llueven flechas sobre ellos Si el juego va a tener varios personajes moviendose en simultaneo, el algoritmo debería poder detectar a los otros personajes como obstaculos de forma dinamica, y buscar rutas alternativas
Por cierto, me olvide mencionar dos cosas:
-Cuando se halla los costos (como en 5:40 o 6:32), como son distancias pues se ignora la existencia de obstáculos.
-Si alguien se este preguntando en 6:32, porque simplemente no usar un pitagoras y ya (Osea dibujar una línea recta desde el nodo hasta el final y hallar esa distancia). Eso es porque hay varias formas de hallar la distancia, usar el pitagoras se llama distancia Euclidiana, la que use yo es una versión adaptada de la distancia Manhattan para mapas que permitan movimientos diagonales (Aunque puse en la notita al terminar la explicación que es una distancia Manhattan, en realidad en su forma mas pura esta NO se puede usar para mapas que permitan movimientos diagonales solo para mapas que permitan movimiento arriba abajo izquierda derecha), del material que me guíe a esa distancia la llaman "Distancia Diagonal". Sobre distancias y Heurísticas pueden guiarse más revisando este Link:
theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#diagonal-distance
excelente trabajo.
¿Sabes qué algoritmo se usan para juegos donde no se usan casillas?, o simplemente se hacen muchas casillas pequeñas?
@@MinombreesSergio Mmm, mientras sean casillas, aunque sean pequeñas se puede usar A*. En juegos donde no se usen, mmm dependeria que juego, en los juegos 3d si usan un enfoque distinto por ejemplo, ahi usan "navmesh".
@@llamaelitista mmm interesante, y es muy enredado ese o aguanta segunda parte con navmesh? :v
Me sirve porque quiero hacer un juego en 3D, con movimiento por click.
Es increìble que aprendí todo esto en la universidad y ahora viendo tu video me hiciste recordar y volver a entender todo pero de una manera más interesante
Tal cuál, yo me acuerdo de haberlo programado en C++ para encontrar un camino en el juego Mummy Maze. En ese caso no era necesariamente el más corto, ya que estábamos haciendo heurísticas que también tenían en cuenta la distancia a los enemigos y sus tipos de movimiento, pero fué muy interesante volver a ver la teoría
Que el algoritmo igual te bendiga tu video 🙏🙏🙏
Maravillosa explicación
Literal si jajaja
Qué bonitos deseos!
Y funcionó
Básicamente cda vez que avanza un nodo guarda la información de "donde proviene" y cuando llega a la meta le pregunta a cada nodo "hey, ¿De donde vienes?".
Me pareció buena la explicación
Diste en el clavo!
Este video es de mis favoritos en lo que a programación respecta, me recuerda mucho a uno que ví sobre animaciones procedurales, en el que en vez de mostrar el código y ya está, el autor explica como funcionan las cosas.
Me encantan este tipo de videos porque te dejan tener un entendimiento más profundo de un tema y en base a eso podés generar un código en cualquier lenguaje de programación. Y lo más importante, entendés que es lo que hace el código.
Por cierto, es impresionante que hayas hecho ese código en python para mostrar esto, se agradece mucho.
Es un video increíble. La facilidad con que explicas el algoritmo. Este algoritmo lo ví por primera vez en la universidad en la materia de Inteligencia Artificial.
no se que me parece mejor, si el hecho de que expliques un algoritmo que me ha llamado la atencion desde hace bastante o que lo hayas explicado con pseudocodigo en un archivo rust. desde ya me suscribo
Me preguntaba esto cuando jugaba de pequeño, me alegra saber un poco mas ahora
Mis estudiantes estarán felices... Dios te bendiga... Ojala subas otros algoritmos qué se usan en video juegos... Que Dios te bendiga a ti y a tu familia... ❤❤❤
Gracias :)
Pero más bien.... Lokita!
No se como llegué a este video si no programo videojuegos, pero me pareció super interesante y muy bien desarrollado!! Muchas felicidades, gran contenido!
11:11 Cuando te das cuenta de que el algoritmo A* también se puede implementar para escapar de algo jajajajja Muchas gracias por compartir, haces que internet valga la pena
casualmente hace unos dias hice una visualizacion de este algoritmo en angular, tuve que usar una clase para representar la cuadricula como una matriz de adjacencia, e iba guardando los mejores candidatos al camino mas corto con una cola de prioridad, cuando piensas que no usaras esas estructuras de datos y luego te encuentras en esa situación jajaja, te has ganado un suscriptor amigo.
Bro, estuve viendo tu vídeo por curiosidad, pero el ver que creaste un programa de manera libre me sorprendió. Increíble vídeo
😮 Justo estoy interesado en el Warcraft y lansas video de Warcraft que coincidencia
Hace poco termine un proyecto para rules con nodos, y justo implemente graphos, que genial repaso
No diseño videojuegos ni de lejos, pero soy ingeniero y me ha parecido muy interesante y entretenido. Felicidades por este pedazo de video, muy bien explicado
Ha sido muy interesante!!
Justo estoy empezado en algoritmia y este video me ha ayudado a entender este algoritmo mucho mejor. Gracias! ❤
Solo he visto este video de tu canal, pero con esta calidad de explicación de algoritmos, me subscribí sin dudarlo.
¡En horabuena por semejante calidad!
Espero sigas así.
Excelente video y explicacion de este algoritmo, es impresionante la forma en la que se omiten caminos costosos frente a rutas eficientes, aunque tambien esta el tema de que A* puede considerarse un algoritmo casi recursivo (evaluar un nodo mas de una vez), y que en casos MUY especificos sea menos eficiente que BFS u otros de crecimiento de area, por lo que en modelos mas complejos se suele implementar filtros que buscan patrones de forma o tamaño que seleccionan el algoritmo mas eficiente a utilizar antes de ejecutar la optimization. Tienes un nuevo sub :)
Me encanta tu contenido sobre algoritmos aplicados a videojuegos ayuda a dar una perspectiva histórica sobre cómo hemos llegado a los videojuegos de hoy. Me pregunto de dónde viene tu formación o qué te llevó a investigar sobre estas cosas.
Soy ingeniero, pero me puse a investigar estas cosas por mi cuenta, por mi gusto por la programación y videojuegos.
¡Excelente video! Me encantó que usaste Pygame para mostrar el funcionamiento del algoritmo
Gracias Dios te bendiga... Mi estudiantees estarán felices, con tu video... Ojala publiques otros videos de algoritmos de video juegos...
Explicas de maravilla, gracias! Ahora, sería interesante un vídeo sobre su implementación en diferentes formas de medir distancias en contextos variados.
Increíble video, espero que sigas haciendo videos así! Son muy buenos y logras enseñar matemáticas y las bases de programación utilizando los videojuegos como un medio.
Genial video y explicación. Debo decir que la IA es una gran ayuda, al momento de intentar recrear el algoritmo
Tremendo video, lo vi en la universidad, pero me habria encantado verlo asi graficamente
wow, increible. me gusta la explicacion de las matematicas yalgoritmos detras de los videojuegos. nuevo sub. ojala sigas asiendo videos asi
lo que vi en la carrera de ingeniería industrial con ejemplos aburridos ahora me colocan el ejemplo de videojuegos, gracias que buenos recuerdos viciar y entender lo que va atras del telon
Me parece muy interesante e intuitiva tu forma de explicar esos algoritmos.😊 Actualmente estoy estudiando una licenciatura en matemáticas y guardaré el codigo por si me sea necesario en un futuro 😅.
Que buen video amigo, espero que estes mas activo, el algoritmo esta beneficiandote
amigo, te amo demasiado. por favor que estos vídeos nunca terminen 😭🙏🏻
Esta genial el video , muy buen trabajo promete el canal .
Wow amigo muchas gracias, en verdad me parece fascinante todo el tema matemático y ahora me doy cuenta que me gustaría investigar más el tema, gracias.
Esto es incredible, Todo muy Bien explicado e interesante.. +suscribed
Me acabas de recordar de un bot que hice para un viejo juego llamado Dofus, buen video
Maquina, mostro, fiera , animal, mastodonte, sos el mejor, nuevo sub!
Buen video hermano, crecerás mucho más sigue así con el contenido! 🇵🇪
Causa es la bandera de Canadá?? :V
Muy interesante tu vídeo, me gusta como explicas ese algoritmo que está detrás de muchos juegos. Igual me gustaría saber cómo se aplicaría en entornos más complejos como por ejemplo caminos con curvas o en tres dimensiones
Los caminos con curvas pueden igualmente volverse una cuadrícula, simplemente tendrías que hacer nodos/casillas mas pequeños y ya, asi simulas una curva. Para modelos 3d, se puede usar A* , pero de forma un poquito mas compleja, a traves de lo que se conoce como "Navmesh", puedes buscar eso para mas info.
Esto si que me ha ayudado para el juego que estoy haciendo, muchas gracias!!!
buen video.
tengo muchisima experiencia en computacion......pero nunca me habia puesto a analizar ese algoritmo de encotrar el camino mas corto.
soy mas partidario de la recursion que de la iteracion.
estoy aprendiendo love para hacer juegos, creo qeu voy a marcar este video, el juego que tengo en mente no usa realmente rutas, pero algunos de los que tengo pensados si, asi que esto me sera muy util.
creo que lo hare con recursion.
tenga su like.
Gran video, bro! Esta clase de contenido es muy interesante.
Increíble video amigo. Te ganaste un sub, un like, un follow en todo lado y un stalker a medio tiempo.
buen material! Lo voy a tener en cuenta en mis futuros proyectos
Excelente video y explicación, te ganaste un subscritor.
Exelente video amigo, muchas gracias por dedicarle tu tiempo.
Súper vídeo.
Lo has explicado clarinete.
Felicidades!
Yo pensando que este concepto que ví en inteligencia artificial solo iba a estar en una clase, gran vídeo!
Bro, este año estas subiendo obras maestras 💅💅💄
@llamaelitista hola acabo de ver el video, me gustó mucho como está explicado, me imagino que ya deben haber implementado una búsqueda de camino más corto que vaya del inicio al fin y del fin al inicio paralelamente que puedan compartir información cuando se lleguen a nodos intersectados por ambas búsquedas, eso debería reducir el tiempo a la mitad, pero no ví que se mencionara algo así en el video
Excelente video, a los que estamos aprendiendo programación nos da mucha ayuda.
Ni idea que hago aquí, pero me ha gustado bastante 🫶 gracias!
Entre por curioso y termine recordando Python, muchas gracias por el video
El contenido que merezco
Genial recomendación por parte de RUclips. Gracias por el contenido. Por cierto, ¿como se llama el soundtrack inicial del video? Saludos.
@@MostVicious3d Buscalo como ".hack//infection Desktop theme"
Que genial tu canal amigo, te admiro mucho.
En godot creo que estaba implementado y simplemente es ponerlo como miembro, como no sé pa que servía, me vi este video xd
Nuevo Sub, muy buen contenido y excelente explicación
Muy buen video, se entendió perfecto y de forma que sea interesante
Recuerdo cuando estudiaba en la ingeniería, nos enseñaron este algoritmo pero hacíamos todos los cálculos a mano para programar cómo una paquetería repartiría los pedidos que tuviera y otros ejemplos asì
Gracias a estas bases fue que comencé mucho antes que tú a desarrollar una ToolKit para Stride Engine de Pathfinding para juegos de RTS. La ToolKit que desarrolle se llama Northgard, y te preguntarás ¿por qué le puse ese nombre?, básicamente porque es uno de los juegos que paso gran parte de mi vida enviciado, un juego que a mi en lo personal está tan bien hecho mejor que el AoE, que no solo me genera nostalgia sus temas nórdicos sino, que es precisamente la inspiración que tuve a la hora de programar y producir la herramienta. Sin embargo, tuve que leer libros para entender funciones matemáticas, trigonometría y físicas de bajo nivel. Sin embargo tu vídeo lo resume de tal manera que parece simple pero no lo es. Programar no es lo mismo que desarrollar, desarrollar es cuando utilizas herramientas y funciones creadas por programadores, eso incluye los frameworks y el código scripting, los programadores creamos herramientas para que los desarrolladores lo utilicen, por eso el programador que sabe programar conoce las matemáticas, nunca se va a conformar con lo que le da el motor o framework, siempre buscará una forma de re-inventar la rueda aunque la rueda ya exista, precisamente se debe a esto: La programación es un Descubrimiento, el día de mañana puede existir un Z* del pathfinding por alguien que se animó a experimentar, probar nuevas cositas, el programador que sabe es un inventor por naturaleza, requiere de estudio constante y saber de matemáticas. S2 👨💻
Muy buena explicación! Estudiaste algo relacionado a informática o programación? O aprendiste esto por tu cuenta?
Soy inge, no informatico aunque toque algunos temas en cursos, todo lo que sé de computer science y programación lo aprendí por mi cuenta.
buen video, me gustan las freakeadas sobre juegos, y mas sobre el desarrollo, me gusta la programacion, pero no he hecho aun mi primer juego serio, tengo q seguir avanzando,
6:32 está equivocado el costo H sería calculado por Pitágoras, de otra manera sería calcular los caminos mas cortos en cada iteración y pues no tenemos esa info. Debería ser una línea recta del nodo a la meta, solo contando en x y y, para luego usar sqrt(x*x+y*y)
En realidad hay distintas formas de hallar la distancia en el costo H (Heurística), la que planteas tu se llama distancia Euclidiana (que es hacer un pitagoras y ya), la que use yo es una forma adaptada de la distancia Manhattan, ambas funcionan, ya depende de como quieras adaptar tu algoritmo. Sobre lo del camino mas corto, si tienes razón, en realidad SI es como hallar el camino mas corto PERO cuando no hay obstaculos, como es una distancia, no toma en cuenta obstaculos asi que en realidad no se puede usar para hallar el camino mas corto. Sobre lo de que no existe info, si hay, existe una formula para hallar la distancia que estoy usando sin mas info que la posicion del nodo analizado y la posicion del nodo final. Checate este link, esta con el nombre de "Diagonal distance". theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#diagonal-distance
Excelente explicación ❤
Excelente aplicación de la Investigación de Operaciones, o mejor dicho, Ciencias de la Computación.
Eres un capo bro! Sigue así
No estudio mada relacionado a esto perp igual vi el vídeo completo. Me atrapó el tema y lo entendí perfecto, gracias
0:55 soy tán viejo que reconocí el odiado GOTOXY 🤣🤮
Muchísimas gracias por este gran vídeo
Excelente video !!! Es muy útil !!
Hermosa , buenos videos , un saludo
Excelente aporte, muchas gracias.
Muy buen video. Me gusta tu forma de explicar. Muy orientada a la práctica. Pero tengo que mencionar que A* no siempre encuentra el camino mas corto, a veces encuentra solo uno aceptable. Todos los algoritmos tienen algo que los hace mejor y peor que los otros en terminos de rendimiento, memoria y exactitud. A* destaca en los videojuegos por su eficiencia.
"...A* destaca en los videojuegos por su eficiencia."
Siempre que conozcas TODOS los caminos posibles
Como en el lol cuando le das a punto donde quieres ir en el mapa te marca el camino mas corto para llegar.
Excelente video! Finalmente entendí el algoritmo. No obstante tengo una duda: sería posible añadir un test de visibilidad (trace del nodo al jugador) en cada nodo del A* para que el camino no solo sea el más corto, sino también el más oculto a la vista del jugador?
Estoy desarrollando un juego indie en UE5 y busco una forma de hacer que mis enemigos flanqueen de manera inteligente. He probado EQS, FSMs, y demás, pero parece que tendré que modificar el A* del engine para obtener buenos resultados. De ser posible, podría usar EQS para encontrar un punto en la espalda/laterales del jugador, y usar el A* modificado para que el enemigo se mueva hasta ese punto pasando por el camino con más coberturas.
En cualquier caso, nuevo sub :) tienes contenido muy interesante, sigue así!
Mmmm, muy interesante, a si a primera prueba se me ocurre que podrías hacer que la vista del jugador se vuelvan nodos obstaculos, por ejemplo si tu jugador ve en línea recta todos esos nodos/casillas hasta choca su vista se vuelven obstáculos, en la realidad no son, pero para el algoritmo si serían por lo que tendría que calcular un camino que no implique pasar por esos nodos/casillas. Algo asi se me ocurre.
@@llamaelitista Una pena no poder poner imágenes por aquí, pero conseguido!
Lo que he hecho es un trace desde cada nodo a un vector que llamo VigilVector, este puede ser la posición del jugador, el goal del path, lo que sea. Si hay un hit antes de llegar al Vigil, el nodo esta oculto, si no pues es visible. Si es visible, incurre un costo alto modificable. He metido parámetros para hacer offset variable también y que el trace no choque con el suelo.
Me queda ajustar un poco los valores y meterle más parámetros para que se pueda aprovechar para más cosas que flanquear, pero funciona muy bien.
No podría haberlo hecho sin ver este vídeo, me has ayudado a entender como funciona en muy poco tiempo y de forma sencilla, eternamente agradecido 🙏
@@NekoDevX 🫡
el desarollo de videojuegos es arte casi lloro
Excelente video! Muy bien explicado.. solo me queda una duda con la parte de programacion... El nodo final se declara como variable tambien? En que parte del codigo se define eso? Osea que el código sepa donde esta el final...
En el age 2 cuando querias enviar algo en barco, muchas veces el barco venia a ti antes que tu al barco quizas la IA detectaba que el barco era mas rapido y por eso hacia eso.
Que buen video hermano🙌
super buena explicacion!
muy didactico
Videojuegos: Encontrar la ruta más corta. 🏃
Age of empires 2 DE: 🐢
muy interesante, gracias!
Ese algoritmo no funciona en el AOEII DefinitiveEdition porque ahí hasta se ponen a bailar cuando los mueve en bola, se regresan o se quedan como idiotas caminando contra los edificios
La verdad este algoritmo puede fallar en ciertos casos
Hace 1 mes me puse a aprender a programar juegos, el video me viene de 10.
Excelente video saca más así
Hermoso ver la matematica aplicada :3
Deberías añadir que A* puede llegar a consumir tanta memoria que se vuelve menos eficiente que Dijkstra.
También deberías explicar que la función heurística no tiene por qué ser la Euclidiana (distancia hasta el objetivo) por ejemplo la Manhattan es interesante.
Buen vídeo pero podría confundir a algunos que no sepan suficiente ya que A* no siempre es el más rápido y hay muchas alternativas en videojuegos como IDA*, BeFS o Jump Point.
"...También deberías explicar que la función heurística no tiene por qué ser la Euclidiana (distancia hasta el objetivo) por ejemplo la Manhattan es interesante..."
En un comentario explicó esa cuestión.
"...Buen vídeo pero podría confundir a algunos que no sepan suficiente ya que A* no siempre es el más rápido y hay muchas alternativas en videojuegos como IDA*, BeFS o Jump Point."
El algoritmo A* es de utilidad solo cuando conoces el entorno por el que te mueves.
En el hipotético caso en que no conozcas los caminos que tienes y los obstáculos con los que te podrías topar entonces puede resultar más perjudicial que beneficioso su uso.
A mi parecer la explicación del video está bien para entender la idea o concepto del algoritmo.
Entonces, Tenemos años y años y años interactuando con algoritmos complejos de inteligencia artificial en base a modelos matematicos avanzados, pero las IA de hoy en día son mejores porque a una foto le puedes quitar la ropa a las personas. Pues así estamos
Se merece su suscripción
Hombre de cultura con el tema de desktop de los juegos viejos de .hack
@@knator22 Creo que es la primera vez que alguien capta que uso musica de .hack en algunos de mis videos, no es muy comun encontrar fans de .hack jsjs.
Que buena explicación!!
Excelente explicacion, un algoritmo me trajo aqui.
Increíble tu canal buen video
Muy interesante.
Oye una pregunta, cómo declaras los obstáculos en el código?
Tengo una idea, supongo que le das un valor muy alto en los nodos declarados para así asegurar que no tomen esos valores. Pero no sé, ya hace años que ví estos temas.
Fue para mi tesis pero yo usé el método de homotopia. Nunca lo implementamos en aplicaciones solo en simulación. Fue divertido, pero necesitaba trabajar y pos lo dejé.
en mi codigo cada nodo tiene un estado, los obstaculos tienen un status de "obstructed", asi que cuando esta sacando la lista de vecinos al hacer la revisión simplemente los ignora, como si no existieran.
Solo concia el algoritmo minimax pero este me parece mucho mas divertido gracias.
Excelente explicación. Me queda una consulta, en el caso de tener dos caminos con el mismo costo, ¿cómo el programa decide cuál usar? Me imagino que de alguna forma es arbitrario, como que las casillas se analizan en cierto orden y el primero en analizarse será el elegido, pero quisiera tu opinión.
Saludos!!
Estupendo vídeo, andaba recién buscando como implementar path finding en mi juego, y había leído que el algoritmo A era el mejor.... Una suerte que ya había decidido subdividir el mundo en una cuadrícula
Edit: Lo que me cuesta entender es como se produce la heurística, no es ya de por sí una detección del camino?
Algo que no suelo ver juegos que puedan hacer es detectar cuando una ruta está obstruida con otros personajes
En Mount and Blade Warband, si hay dos escaleras para atacar las murallas de un castillo, los atacantes se amontonan todos en la más cercana porque es el camino más directo para acceder al castillo, aunque signifique que tienen que hacer fila para subir, mientras los defensores llueven flechas sobre ellos
Si el juego va a tener varios personajes moviendose en simultaneo, el algoritmo debería poder detectar a los otros personajes como obstaculos de forma dinamica, y buscar rutas alternativas
la mejor explicación del tema
22 años despues y todavia se sigue hablando de warcraft III