EDICIóN GENERAL
167 meneos
3349 clics
Cómo Command & Conquer: Tiberian Sun resolvió el problema de encontrar el camino (pathfinding) [ENG]

Cómo Command & Conquer: Tiberian Sun resolvió el problema de encontrar el camino (pathfinding) [ENG]  

Uno de los objetivos de "TibSun" (como se llama al juego cuando uno sabe de lo que habla) era no tener límite en el número de unidades que los jugadores podían construir y controlar, y ese objetivo venía con dificultades. A pesar de lo simple que puede parecer a simple vista ("¡Sólo vete de aquí para allá!"), la búsqueda de senderos es en realidad un desafío de programación extremadamente complejo. dependiendo del camino, puede ser NP-completo. [vía arstecnica]

| etiquetas: command conquer , pathfinder
En portada sin comentarios
#1 ha encontrado el camino sola
#1 TS no los necesita. Juegazo.
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.
Vi esta película en Putlocker. La norma
Desafortunadamente, Putlocker ha cerrado, pero siempre puedes usar alternativas - vpnalist.com/putlocker
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 :

youtu.be/-bdFEaNeZMM

y

youtu.be/-L-WgKMFuhE
¬¬ Queremos un nuevo C&C
#10 ¿antes o después de HL3?
#14 xD me hago viejo :'(
#10 El starcraft II casi que lo es
Mission Accomplished
Red Alert me enganchó mucho más. Hell March!
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…   » ver todo el comentario
#18 Justo ese es el tipo de contenido :-D 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…   » ver todo el comentario
#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…   » ver todo el comentario
No funcionaba bien, a veces las cosechadoras se estorbaban unas a otras y se quedaban paradas todas en un mismo sitio.
Fácil: cuando el jugador no veía las unidades en la pantalla, éstas se desplazaban al destino directamente sin importar los obstáculos. :troll:
"The best path to artificial intelligente is to avoid artificial idiocy"

Me ha encantado esta cita xD

menéame