¿Qué estructura de datos debo usar para un árbol de talentos estilo Diablo / WoW?

23

Estoy considerando implementar un sistema de árbol de talentos para un juego de rol en línea, similar al visto en World of Warcraft, donde adquirir una habilidad desbloquea el siguiente "nivel" debajo de él en el árbol.

¿Alguien sabe de la mejor manera de implementar esto estructuralmente en la base de datos / código?

RSH1
fuente

Respuestas:

13

Use una estructura como esta para representar un árbol en una base de datos:

#Talent
id  parent  description
1   0       Tackle
2   1       Kick
3   1       Punch
4   3       Fire Punch

Y otra tabla para representar los talentos adquiridos por usuario.

#UserTalent
id  user  talent
1   4     1
2   4     3
3   4     4

Puede verificar las dependencias de talento mediante programación consultando la tabla completa de talentos y creando un árbol vinculado. También puede hacerlo con SQL, pero requerirá subselecciones recursivas o muchas consultas. Mejor hazlo en tu código.

Si hay varias dependencias, como por ejemplo Fire Punchdepende de PunchAND, Immolationuse dos tablas para representar el gráfico de dependencia:

#Talent
id  description
1   Tackle
2   Kick
3   Punch
4   Fire Punch
5   Immolation

#Depedency
id  parent  child
1   0       1
2   0       5
3   1       2
4   1       3
5   3       4
6   5       4
Jonas Bötel
fuente
Su UserTalenttabla no necesita una columna de clave automática. usery talentpueden ser las únicas dos columnas y una clave compuesta: nunca serán duplicados y nunca consultará de idtodos modos.
doppelgreener
No soy un diseñador de bases de datos y me interesaría escuchar lo que uno dice sobre esto: si cada talento tuviera un nombre único, ¿no podría eliminar también cualquier otro campo de ID numérico en este diseño de tabla y usar nombres como claves (con alguna edición en cascada)? ¿Habría algún costo o beneficio significativo al hacerlo?
doppelgreener
3
@ Jonathan Hobbs: una identificación primaria de incremento automático siempre es buena para las operaciones de eliminación / actualización. Nunca es más lento, pero a menudo es más rápido. También el tamaño de la fila no es motivo de preocupación aquí. Lo mismo también es cierto para el caso de nombres de talento únicos. Para un buen rendimiento, querrás unir tus tablas solo con enteros únicos. Ver en.wikipedia.org/wiki/Database_normalization etc.
Jonas Bötel
Gracias. Un diseñador de bases de datos que conocí una vez afirmó que las teclas automáticas eran malas y deberían evitarse, pero nunca he tenido claro si ese es el caso o por qué. Supongo que no lo es.
doppelgreener
No hay una razón real para usar una base de datos para almacenar estos datos a menos que necesite una base de datos para diseñadores porque admite la edición multiusuario o algo así. De lo contrario, solo se interpondrá en el camino. (Yo también nunca utilice una clave de incremento automático principal para esto, porque es casi seguro que desea unirse en nombres lógicos decididos por un diseñador en lugar de una clave proporcionada-DB.)
5

Recomendaría usar un árbol donde cada nodo represente un talento / habilidad específico. Según si el jugador ha ganado o no un talento, se pueden ganar sus talentos infantiles. Por ejemplo, la siguiente estructura de datos

class Talent {
    std::vector<Talent*> children;
    bool earned;
};

Para determinar qué talentos tiene un jugador, toma el talento raíz y camina por el gráfico hasta llegar a los nodos de talento donde lo ganado es falso. Esto también revelará qué talentos están disponibles para obtener: el primer talento en cada rama por debajo del talento raíz donde se ganó es falso.

fantasma
fuente
¿Tienes un puntero a una matriz nativa y un tamaño? Falla: utilice un puntero de tamaño propio propio.
DeadMG
Whoops ... C / C ++ mezcla y un error. He actualizado mi respuesta. Gracias por el aviso.
fantasma
@DeadMG: ¿qué quieres decir exactamente con 'auto-dimensionamiento propio'? ¿Te refieres a algo como el vector de arriba, o estabas pensando en otra cosa?
Kylotan
Un Boost ptr_vectorpodría ser aún mejor.
Zan Lynx
55
La estructura de árbol debe estar completamente separada de si el jugador se la ha ganado, la primera es información estática hecha por diseñadores y la segunda es información por jugador almacenada en un juego guardado o DB.
1

En mi juego lo hago así:

Base de datos:

reference_talent : contiene una ID, nombre, efecto, etc. únicos

talent : id, playerid <- contiene todos los talentos que los jugadores han "aprendido".

En el juego: (en el servidor)

Cargo todos los reference_talents en un 'estático' (solo lectura) std :: map para poder acceder a ellos fácilmente por su id.

Cuando un cliente retira a un jugador, obtengo todos los talentos de la base de datos y los almacena en un std :: vector para que cuando necesite calcular características, etc., los tenga en la RAM. También envío los talentos al cliente.

Eso es todo (excepto ahorrar nuevos talentos, por supuesto, que es solo un 'INSERTAR' en la tabla 'talento' + un mensaje para el cliente).

Valmond
fuente
0

Enfoque relacional

Lo describe como una relación entre desbloqueadores y desbloqueados similar a la de este tutorial . Sugiero aprender más sobre álgebra relacional y bases de datos. Son una buena manera de modelar datos. Si aprende a consultar la información de la base de datos, puede modelar datos con bastante facilidad.

No sé cuánto sabes sobre modelar relaciones. Ese tutorial debería ayudarte con eso.

Una solución

Supongo que WoW funciona como en realidad (ehm), que es

  • El talento desbloquea varios (otros) talentos
  • El talento es desbloqueado por varios (otros) talentos.

Es la relación N: N, lo que implica que necesita "intermediario" una nueva relación entre los dos talentos:

(talent who unlocks id, talent who is unlocked)

De esta manera, puedes tener el talento A desbloqueando B, C y D ((A, B), (A, C), (A, D)) y el talento Y desbloqueado por X, Z y W ((X, Y), ( Z, Y), (W, Y)). En lenguaje imperativo / procesal / orientado a objetos, lo haría como una lista / matriz de pares como allí:

var unlocks_unlocked = [[A, B],[A,C],[A,D],[X,Y],[Z,Y],[W,Y]];

Entonces, para el ejemplo del "mundo real", puede tener:

... ["running fast", "jumping superhigh"], ["antigravity's child", "jumping superhigh"]

y significa que se obtiene el "salto súper alto" después de que tienes los talentos de "correr rápido" y "niño de la antigravedad".

Otra solucion

No he jugado a Diablo recientemente, pero podría ser que solo tenía:

  • talento desbloquea varios otros talentos
  • El talento se desbloquea solo por un talento.

Es la relación 1: N:

 You put "is unlocked by this talent's id" variable into talent's structure

me gusta:

 var Talent[8] = { "name": "superpower", "unlocked by": "being Clark Kent"};
usuario712092
fuente