Keywords: player action, player move, action cost, move plan, scheduler tick, turn system, time system, actor execute, execute system, queue, empty, location. Powered by TextRank.
*This post contains a series of updates to an algorithm that show the evaluation and rationale. You don't end up with what you started.*
The most naive scheduler in a rogue like is just assuming that every character moves at the same speed and iterating over the list to make them move. But that is boring and diminishes the tactics in the game. A huge slug should be slower than the player and a vampire bat should be faster.
A simple way of accomplishing this is to use a priority queue. Each character in the world has a plan function that calculates the move it will make and enqueues it with the scheduler to be executed at a certain time. This time should be the current time + the cost to execute the action. For the human player this plan function is partly when the human is thinking what to do and partly in the input handler for the (when the action is sent to the queue).
After a player input is received the scheduler starts dequeuing the items and executing them. The current time is updated to the time of the action that was executed. This works because of the priority queue and the first item dequeued is the item with the lowest timestamp value. This goes on until a player action is dequeued and executed. One thing to note here is that of actions with the same timestamp the player action should be the last so that other characters actions don't spill over to the next tick.
Player (P) movement cost is 50 Monster (M) movement cost is 25
So we expect the M to move 2 tiles when the player moves 1. The queue is initially empty and the game asks all entities to plan their move. M plans it's move based on it's AI output and queues it with the scheduler
[M(25)]
Now we are waiting for player input. Let's say the player pressed a movement key so we schedule that
[M(25), P(50)]
The input from the player also triggers the scheduler execution. The scheduler gets the first item in the queue and executes the action and updates the current time from 0 to 25. After execution it asks for the owner of that item to run its planning again. So the monster again consults its AI and plans another move. The move is scheduled so the queue is now
[M(50), P(50)]
The scheduler hasn't yet seen a command that belongs to the player so it keeps on dequeuing. The next item is again a monster action so it's dequeued and executed, current time is updated to 50 and another plan is requested. The plan is added to the queue so it is now
[P(50), M(75)]
Next up is the player action which is dequeued and executed and the scheduler loop can be terminated, leaving the queue as
[M(75)]
which is the same state as our initial queue.
The plan & execute system has a design flaw that requires the action code to perform checks which kind leads to either poor code structure or unfair scheduling behavior. The issue first surfaced when I saw that 2 monsters would end up occupying the same tile. Consider the following map setup
######## ....M... ###N#### #.# #.#
Assume that M wants to go left and N wants to go up. When the scheduler asks M for the next M moves, M checks the location on the left and sees thats it's empty so plans a move it that direction. Next N sees that the same location is empty and also plans a move in that direction. Now in the action phase you need to check whether the target location is empty before making the move otherwise the monsters end up being on top of each other. But what does N do if the location is not empty in the action phase? N already spent credits to plan the turn so either N would have to choose an action with the same cost (to make it cost fair) or choose some other action that could cost less or more (or maybe skip the action). All of these seem like unfair solutions. The same unfairness happens when M plans to attack the player but the player isn't there because they got more turns than M. So this type of plan and then execute model is not really suitable. I came up with an alternate model where all the actors in the world are added to priority queue again. But this time around there is no planning phase there is only an action phase. Once the actor executes their action, the action function returns the cost of the action, which is then used to determine the place of the action in the queue. Again queue processing terminates when it's the players turn so we can get input.
Here is an example run:
initially everybody is waiting in the queue
[P(0), M(0), N(0)]
Player moves with cost 100
[M(0), N(0), P(100)]
M moves with cost 50
[N(0), M(50), P(100)]
N moves with cost 50
[M(50), N(50), P(100)]
M moves with cost 50
[N(50), P(100), M(100)]
N moves with cost 50
[P(100), M(100), N(100)]
now we are at the player again, so M, N moved twice for each player move which is correct since their movement cost is half that of the player.
With the new turn system an issue that came up is when the turn processing stops with the player any other actor that was scheduled to act on the same tick gets delayed for a turn. This again leads to unfair time sharing situations. The fix is relatively easy: add a new actor called the TurnSentinel that acts as the demarcation between turns. It has a fixed action cost of the turn length which should be the same as the players movement cost to avoid situations where the player would move more or less than 1 square per turn. With this update the queue structure becomes like this
[P(0), M(0), N(0), TS(100)]
say all the actors took actions that cost 100 points, then the queue becomes
[TS(100), P(100), M(100), N(100)]
we calculate the sentinel action put it to the back of the queue and we terminate the scheduler processing loop because we see the sentinel and wait for player input.
[P(100), M(100), N(100), TS(200)]
I still ran into unfairness issues or other weird behavior with monsters moving more than they should in a turn because of their place in the queue so I decided to switch to an energy based system. It's still similar to the time based execution system but now each actor gets N credits each tick and action costs are deducted from their available credits. I didn't want to change the action api to allow for a credit check as that would mean running the AI twice. One for possibly selecting the action to see the cost then actually running it. This also imposes limits on the actions and NPCs would be could be biased on efficient credit usage rather than best actions. If the actor has a positive credit the scheduler will execute their actions until they run out of credits. This implies that they could end up with a negative balance. The next tick they will get N more credits and can execute their action if they end with a positive balance otherwise they'll have to wait for the next turn. The waiting is ok for the npcs but not the player. You can't have the player press a key and nothing happen because they had a negative credit balance. The solution to this issue is to recursively run the scheduler if the player credits are below -N. Why -N and not zero? Because if they have more than -N they will get N more in the next tick and the player action will execute. That means the last action will be executed twice which is not what we want.
Let's say the action cost is 150, default charge per turn is 100. Every body started with 0 credit.
Now when you charge the next tick, the player will have 0 credits and not move. To prevent this a recursive call is made so every other actor gets their action and the player is now 0.
and the player can move again.
The credits system is working pretty good except for a couple of conditions that arisen due to the position of the player in the queue and animations. This was mainly related to the displacement mechanic that I wanted to implement and how I could have the user perceive that displacement. The player has to be in first position in the queue because when they do a ranged target, I want to calculate if the shot hit the target first. If the player is not first to go, then the monsters could change their location and the shot would miss. This could be accomplished by a preemptive scheduler that queue the shot as a Schedulable then the player could go last but I have to think about that a bit more. A side from that I also changed the implementation to a round robin traversal instead of consuming all the credits of the current actor. I put all the schedulables in to a local queue in the tick function and process that queue. If the current actor has any credits left after their action they get put back in the queue in last position and the processing continues until the queue is empty.
My initial design for the time system was running on the main thread sequentially and the game would render the level at the end of a scheduler tick. This seemed to work well but if an actor gets more than 1 movement action per tick it would look like they jumped around. I decided that this can get hard to judge and predict the next monster location for fast monsters. One turn the monster is far away the next turn it jumped right next to the player. So I wanted to animate the monster movements so it's clear how the enemies are moving. This seems to be a bit more fair in terms of time sharing for all the actors and makes the queue position a bit less important.
1725 words
Powered by TF-IDF/Cosine similarity
First published on 2020-07-11
Generated on 13 Dec 2024 at 12:12 AM
Mobile optimized version. Desktop version.