¿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?
Use una estructura como esta para representar un árbol en una base de datos:
#Talent
id parent description10Tackle21Kick31Punch43FirePunch
Y otra tabla para representar los talentos adquiridos por usuario.
#UserTalent
id user talent141243344
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
1Tackle2Kick3Punch4FirePunch5Immolation#Depedency
id parent child
101205312413534654
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
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.
¿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).
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:
UserTalent
tabla no necesita una columna de clave automática.user
ytalent
pueden ser las únicas dos columnas y una clave compuesta: nunca serán duplicados y nunca consultará deid
todos modos.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
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.
fuente
ptr_vector
podría ser aún mejor.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).
fuente
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
Es la relación N: N, lo que implica que necesita "intermediario" una nueva relación entre los dos talentos:
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í:
Entonces, para el ejemplo del "mundo real", puede tener:
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:
Es la relación 1: N:
me gusta:
fuente