¿Qué estructura (s) de datos respaldar una cola de Final Fantasy ATB? (una cola de espera)

Question

Situación: Hay varias entidades en un entorno simulado, que tiene una noción artificial de tiempo llamada "tics", que no tiene ningún vínculo con el tiempo real. Cada entidad se turna para moverse, pero algunas son más rápidas que otras. Esto se expresa por un retraso, en tics. Así que la entidad A puede tener un retraso de 10 y B 25. En este caso, el orden de turno iría:

A A B A A

Me pregunto qué estructura de datos para su uso. Al principio pensé automáticamente "cola de prioridad", pero los retrasos son relativos a "hora actual", lo que complica las cosas. Además, habrá entidades con retrasos más grandes y no es imprevisible que el programa se ejecutará a través de millones de tics. Parece tonto que un contador interno se construya cada vez más alto cuando los retrasos se mantienen relativamente pequeños y no aumentan.

Entonces, ¿cómo resolverías esto?

Answer 1

Almacena las entidades en un Heap y las agrupa por el tiempo que quedan para esperar. El grupo de entidades que están próximas a moverse estaría en la parte superior del Heap. Solo tienes que actualizar estas entidades. Cuando su tiempo restante para esperar cae a 0, los quita del montón. Ponga el siguiente grupo de entidades en línea en la parte superior del Heap mientras disminuye su tiempo para esperar por la cantidad de tiempo que acaba de pasar antes del movimiento anterior.

Por ejemplo:

su montón tiene 3 nodos (A, B, y C), la parte superior es el nodo A con dos entidades tanto que tiene de 5 garrapatas restante. Los niños tienen 10 y 12 garrapatas restantes, respectivamente.

• En el momento t = 5 se mueve todas las entidades que están en el nodo A bucketed
• eliminar una de las Montón
• B se mueve hacia la parte superior de la pila con 10-5 = 5 garrapatas restante entonces
• repetir.

Answer 2

Opción # 1: sondeo

que probablemente construir un controlador que puede descubrir el retardo para todas las diferentes entidades y mantener un garrapatas que le queda a cada entidad. El controlador pasaría cíclicamente a través de tics y en cada tic-tac reduciría los ticks-remaining para todas las entidades en el juego.

Una vez que el valor remanente de las entidades de garrapatas llega a cero, usted sabe que es su turno, ya sea controlado por el método de latido que maneja las marcas o un método que usted llama.

Opción # 2 Eventos

pensar como el paradigma de interfaz de usuario, la interfaz no sondea constantemente el botón para ver cuando se hace clic. Más bien, permite que el botón notifique a la interfaz de usuario cuando se ha hecho clic a través de eventos. Haga que sus Entidades (o un EntityBattleContext) activen un evento cuando esté listo. Tendrás que manejar el tiempo de juego de alguna manera, ya que no se basa en el tiempo real en todo lo que puedas necesitar para que todas las Entidades escuchen un evento GameTick y cuando lo reciban actualice su variable Interal TicksRemaining.

Antes de seguir la ruta controlada por eventos, asegúrese de que la ruta de sondeo no funcione. Recuerde que la regla cardinal optimiza siempre más tarde porque con más frecuencia no necesita la optimización.

Answer 3

Si suponemos que sus entidades están observando o mirando el tiempo de simulación, cada uno de ellos podría implementar una interfaz que les haga seguir el ticks left y proporcione un método para obtener la cantidad de tics para una entidad en particular. En cada una garrapata, la entidad reduce su ticks left en 1.

A continuación, puede mantener una cola conjunto ordenado (juego debido a que cada entidad será en la cola de una sola vez) de estas entidades, ordenados en base a get ticks left, por lo que el 0th la entidad es la que se mueve a continuación, y la enésima entidad es la "más lenta".

Cuando el método get ticks left de la entidad es 0, se elimina del conjunto ordenado, el temporizador ticks left se restablece y se vuelve a insertar en el conjunto ordenado.

Answer 4

Me parece por su descripción que el concepto de "¿qué sigue?" es más importante que "¿cuánto tiempo pasará hasta la siguiente acción?". Siendo este el caso, ordene su cola por "next-to-go" o el menor número de ticks restantes al más alto.Las inserciones, por supuesto, se ingresan en el orden apropiado, y las entradas alteradas (hechizos de "aceleración") se eliminan de la cola, se modifican y luego se vuelven a ingresar de manera apropiada.

Luego, acaba de sacar el siguiente trabajo de la cola. Cualquiera que sea el número de tics que le quedaron debe ser el "tiempo transcurrido". Pasa por la cola, disminuyendo el campo restante de tics de cada entrada por la cantidad de ticks que acaba de descubrir.

Esto tiene la ventaja de hacer un seguimiento del concepto de tiempo restante, pero también de no tener que disparar eventos o ejecutar cualquier otro código para tics que pasan cuando no hay que tomar ninguna acción. Puede permitirse esto, ya que no hay ninguna relación con el tiempo real en absoluto. Solo hay "¿qué sigue?" Y "¿Cuánto tiempo tardó en llegar allí?".

Answer 5

Mire cómo se implementa el DelayQueue de Java.