Portada
mis comunidades
otras secciones
#4:
Artículo completo
https://arstechnica.com/gaming/2019/02/video-to-make-tiberian-sun-westwood-had-to-find-the-right-pathfinding-system/
No se por qué #0 solo ha enlazado al vídeo.
https://arstechnica.com/gaming/2019/02/video-to-make-tiberian-sun-westwood-had-to-find-the-right-pathfinding-system/
No se por qué #0 solo ha enlazado al vídeo.
#9:
No me esperaba que mostrara el "código", pero me ha decepcionado este articulo. Podrían haberlo explicado un poco más o haber puestos ejemplos.
#6:
#4 Interesante. Parece que como dicen es un puto cacao y que la solucion que encontraron es que no pareciera estupido en la mayoria de los casos como buscan las unidades el camino y con eso bastó.
mas datos:
https://en.wikipedia.org/wiki/Pathfinding
mas datos:
https://en.wikipedia.org/wiki/Pathfinding
Comentarios
Artículo completo
https://arstechnica.com/gaming/2019/02/video-to-make-tiberian-sun-westwood-had-to-find-the-right-pathfinding-system/
No se por qué #0 solo ha enlazado al vídeo.
#4 Interesante. Parece que como dicen es un puto cacao y que la solucion que encontraron es que no pareciera estupido en la mayoria de los casos como buscan las unidades el camino y con eso bastó.
mas datos:
https://en.wikipedia.org/wiki/Pathfinding
No me esperaba que mostrara el "código", pero me ha decepcionado este articulo. Podrían haberlo explicado un poco más o haber puestos ejemplos.
#9 Efectivamente lo único que ha dicho es que programaron un algoritmo que no se comportase de forma estúpida
Pues menuda información
#9 sumamente decepcionante.
Cuando uno lee una entradilla donde a se afirma que buscar rutas , "dependiendo del camino, puede ser NP-completo", espera encontrar en la noticia algoritmos, detalles tecnicos y un enfoque de la materia mas o menos tecnico.
Una pena, parecia interesante
Para quien se haya quedado con las ganas :
y
"The best path to artificial intelligente is to avoid artificial idiocy"
Me ha encantado esta cita
Fácil: cuando el jugador no veía las unidades en la pantalla, éstas se desplazaban al destino directamente sin importar los obstáculos.
Red Alert me enganchó mucho más. Hell March!
#24 Si la imagen de fondo que usas como obstáculos es estática (es decir, no cambia durante el 99% del tiempo) te conviene muchísimo pre-procesarla de alguna manera. Los costes de buscar rutas en un grafo simplificado te pueden caer varios órdenes de magnitud si lo haces.
Imagina que tienes un área en la imagen de 300x300 píxeles que están libres de obstáculos. Esos 300x300=90 000 píxeles tendrían que ser procesados por A* (o el que uses) cada vez que se calcula una ruta.
Ahora piensa que puedes representar esos 90 000 píxeles con un solo nodo que representa ese área libre de obstáculos. Y generaliza esto a todo el mapa del juego. En cuántos órdenes de magnitud se simplifica el problema?
El pre-procesamiento del mapa da igual el tiempo que lleve. Se va a realizan una única vez por partida (o cada vez que se modifique el mapa físicamente), que es muchísimo menos frecuente que los cientos de veces por frame que se van a calcular rutas.
Recuerda que las rutas no necesitan ofrecer un plan exhaustivo, pixel a pixel, de qué camino tomar. A menudo es suficiente que retornen un puñado de puntos de ruta por los que se puede ir en línea recta entre dos puntos consecutivos.
No sé qué tipo de roguelike estás haciendo, pero si las casas son colocadas proceduralmente a partir de prototipos (tienes 20 o 30 casas distintas diseñadas y el juego coloca algunas elegidas al azar), los grafos de rutas pueden estar ya incluídos en los propotipos de las casas, con lo que solo tienes que conectar el nodo de las entradas con los nodos del exterior.
La saga de C&C vaya tiempos... sería de los pocos juegos que compré originales en su época.
#5 Yo lo tuve (creo que todavia lo tengo en algun cajon) original aunque he de decir que no lo compre. Me toco en un sorteo de la Micromania si no me equivoco junto a un reloj y una figura.
#21 suertudo! eso en la época era un tesoro!!!
#25 Si que lo era. Creo que todavía tengo la figura por casa y el juego sin duda lo tengo en algun cajon.
#21 También me tocó a mí! . Justo una semana después de comprarlo
El reloj se cayó a cachos hace tiempo, pero la figurita del GDI aún la conservo con orgullo.
Muy bonito pero un poco inútil, siquiera detalla nada. La única pista que te da es que en el algoritmo de pathfinding se ignora a las tropas aliadas (cosa bastante obvia, ya que de otro modo en cuanto las tuvieras enmedio no encontrarías el destino) y que si te cruzas con unas estáticas se apartan.
No aclara los detalles que serían importantes:
- Si es un A* o alguna variante
- Cada cuanto se ejecuta, ¿se recalcula a medida que se mueven los personajes? ¿Se guarda algún tipo de caché y se va modificando? Etc
Precisamente por lo que cuenta de que en un RTS la cosa es mucho más compleja (muchas tropas moviéndose y cada una con una forma de moverse diferente) estaría bien que explicara de verdad cómo lo hicieron
#16 Seguramente use algo parecido a A* adaptado a tiempo real (heurísticas rápidas e imprecisas, puesto que no te interesa encontrar la mejor ruta, sino una suficientemente buena para no parecer estúpida).
Lo más importante son los trucos que se usan para que no chupe toda la CPU, especialmente cuando hay tantas unidades moviéndose. Y esos trucos no dependen del algoritmo de búsqueda en sí, sino de la rutina que mueve las unidades.
Si no me equivoco, esto funciona así más o menos:
1- Las unidades agrupadas solo calculan una ruta por tipo de movimiento (una para voladoras, una para subterraneas, una para las que van a pie, etc).
2- Tan pronto se hace clic en el destino, las unidades reciben una hoja de ruta rápida que ignora obstaculos, y empiezan a moverse hacia el destino, sin calcular la ruta final. La ruta final se calcula en otro hilo y, cuando está lista, se sustituye en las unidades que ya están en movimiento.
3- Se mantiene un grafo simplificado que representa el mapa para calcular las rutas sobre él. En lugar de usar un mapa gigantesco con cientos de miles de "casillas" que A* debería procesar, todas las casillas sin obstáculos que formen un polígono convexo se agrupan en un solo nodo. Las unidades pueden moverse entre casillas de un mismo nodo en linea recta, puesto que no hay obstáculos entre sí.
4- Las rutas no son superdetalladas, casilla por casilla. En lugar de eso tienen puntos de ruta, que o son simplemente referencias a los nodos, o contienen además alguna coordenada dentro de un nodo. Esto simplifica las rutas muchísimo.
5- La mayoría del tiempo, las unidades están caminando dentro de un nodo. Solo deben consultar si la ruta sigue siendo válida cuando pasan de un nodo al siguiente. Y de nuevo, unidades cercanas (en el mismo nodo) del mismo tipo con la misma ruta sólo tienen que hacer esta comprobación una vez para todas ellas, en lugar de una vez cada una.
6- Si los jugadores (IA o humanos) realizan modificaciones al mapa en tiempo real (colocan un edificio, un muro, rompen un puente, etc), el grafo simplificado es actualizado de inmediato. Si el obstáculo se colocó en un nodo, partiéndolo en varios nodos menores, todas las rutas que pasan por ese nodo son invalidadas. Las unidades requerirán un recálculo de la ruta cuando terminen de caminar por el nodo por el que están.
#18 Justo ese es el tipo de contenido y las ideas que planteas son bastante interesantes.
Yo me he pegado con el tema por un lado programando un tipo Nethack y por otro con uno en tiempo real con una imagen utilizada como mapa de fondo, con zonas atravesables y zonas que no; en este último tuve que ir haciendo apaños, ya que como dices en (4) lo de ir casilla por casilla es imposible cuando una casilla es un pixel, pegaba unos trompicones terribles cada vez que tenía que recalcular una ruta. Lo arreglé asignando costes al recorrido y poniendo "raíles", caminos de coste bajo que unían todas las "zonas lógicas" (habitaciones de una casa con su pasillo, etc) por los que acababan discurriendo siempre. También pensé definir nodos o polígonos, pero se me complicaba y lo de los raíles funcionaba
En el tipo Nethack no hay problema al ser pocas casillas, pero sí tienes el dinamismo de muchas cosas moviéndose a la vez. Ahí el mayor problema fue lo de que enmedio del camino es muy probable que haya otros NPCs pero debería ir hacia allá igualmente, lo que planteas en (2). Como lo solucioné de momento fue poniendo un coste más alto a las casillas con NPCs, de modo que por un lado le compense encontrar un atajo, pero por otro que si no lo hay insista (ya que normalmente van a ser enemigos que van a querer ir todos contra ti)
Y luego hacer una caché con la lista de nodos final, para que la use siempre que la siguiente casilla esté liberada en lugar de ir calculando a cada paso.
En portada sin comentarios
#1 ha encontrado el camino sola
#1 Venia a decir lo mismo:
Me estaba viendo el video a trozos, ahora no tengo tiempo, lo bueno creo que empieza aqui:
#1 TS no los necesita. Juegazo.
Queremos un nuevo C&C
#10 ¿antes o después de HL3?
#14
me hago viejo 
#10 El starcraft II casi que lo es
No funcionaba bien, a veces las cosechadoras se estorbaban unas a otras y se quedaban paradas todas en un mismo sitio.
Mission Accomplished
Vi esta película en Putlocker. La norma
Desafortunadamente, Putlocker ha cerrado, pero siempre puedes usar alternativas - https://vpnalist.com/putlocker