Tecnología, Internet y juegos
167 meneos
3372 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
93 74 6 K 280
28 comentarios
93 74 6 K 280
Comentarios destacados:        
  2. #2 --137040--
    #1 ha encontrado el camino sola
    45 K 334
  4. redscare #4 redscare
    Artículo completo
    arstechnica.com/gaming/2019/02/video-to-make-tiberian-sun-westwood-had

    No se por qué #0 solo ha enlazado al vídeo.
    9 K 66
  5. #5 --472390--
    La saga de C&C vaya tiempos... sería de los pocos juegos que compré originales en su época.
    1 K 13
  7. EspañoI #7 EspañoI
    #1 TS no los necesita. Juegazo.
    0 K 9
  9. #9 SpeakerBR
    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 K 63
  10. Tuatara #10 Tuatara
    ¬¬ Queremos un nuevo C&C
    0 K 7
  11. #11 --160040--
    Mission Accomplished
    0 K 6
  12. #12 --209417-- *
    Red Alert me enganchó mucho más. Hell March!
    2 K 19
  13. #13 starblank
    #9 Efectivamente lo único que ha dicho es que programaron un algoritmo que no se comportase de forma estúpida

    Pues menuda información
    5 K 42
  14. omegapoint #14 omegapoint
    #10 ¿antes o después de HL3?
    2 K 27
  15. Tuatara #15 Tuatara
    #14 xD me hago viejo :'(
    0 K 7
  16. yemeth #16 yemeth *
    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 ¬¬
    0 K 12
  17. unodemadrid #17 unodemadrid
    No funcionaba bien, a veces las cosechadoras se estorbaban unas a otras y se quedaban paradas todas en un mismo sitio.
    0 K 6
  19. Ainur #19 Ainur
    #10 El starcraft II casi que lo es
    0 K 10
  21. arkhadi #21 arkhadi
    #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.
    2 K 22
  22. vviccio #22 vviccio
    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:
    1 K 20
  23. chorche77 #23 chorche77 *
    "The best path to artificial intelligente is to avoid artificial idiocy"

    Me ha encantado esta cita xD
    1 K 20
  24. yemeth #24 yemeth *
    #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 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 xD

    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.
    0 K 12
  25. vacuonauta #25 vacuonauta
    #21 suertudo! eso en la época era un tesoro!!!
    0 K 10
  26. arkhadi #26 arkhadi
    #25 Si que lo era. Creo que todavía tengo la figura por casa y el juego sin duda lo tengo en algun cajon.
    0 K 6
  28. arcangel2p #28 arcangel2p
    #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.
    0 K 6
comentarios cerrados

menéame