1

I am tracking the position of characters on a 2D grid (this is a computer game). At every step each character can attempt to move (stationary, up, down, left, or right).

There are some rules that govern what moves are allowed. Example:

  • Characters cannot move outside the confines of the grid.
  • Characters cannot pass through each-other while moving.
  • Characters cannot move into squares that contain another character.
  • If two characters try to move into the same square:
    • Characters moving directly down get priority.
    • Characters moving diagonally down get 2nd priority.
    • Characters moving horizontally get 3rd priority..
    • Etc.
  • If two characters try to move into the same square and neither has priority neither character is allowed to move.

So the nature of these rules is that the character's movements cannot be applied to the state sequentially, because the movements of other characters may affect if they are able to move or not.

I'm finding this code surprisingly complex to write. And that concerns me because I will

  • Want to extend this system in the future to have more rules.
  • Need to create similar systems where the inputs must be resolved together but depend on each-other.

My question is. Is there a pattern or framework that I could apply to simplify or at least standardize the approach for this kind of problem?

If I had to try and state the problem abstractly it would be: Making a rules based change to a state given multiple inputs which would, if processed in isolation, lead to conflicting final states.

2

You could represent your intended moves as a batch of updates that are fed through a pipeline that you construct externally. Each stage of the pipeline decides whether the batch is valid, valid with adjustments (and applies them), or invalid (and throws an exception).

One stage would apply the boundary rules, the next stage would halt characters that try to pass through each other, the next stage would resolve same-square conflicts, and so on. Only once all stages of the pipeline have resolved do you pass the corrected batch of updates on to a phase that applies those updates.

An implementation strategy like this gives you the isolation and modularity you seek, at the expense of taking multiple passes over the updates list. If that list is small, that might not be an issue. If profiling reveals that performance matters here, you might be stuck fusing everything together anyway. And in that case, the best-performing design is the best one.

0

Treat not moving, as moving to the current location

Simplifying the movement logic to treat not moving as a form of movement rather than an exceptional case, makes life easier.

Because now instead of having to check to make sure a mover has left the square first, we can consider it as just another form of collision and apply collision logic to resolve disputes over location ownership.

Simply add another rule: a mover always has priority when moving to the same location it was already in.

This will always guarantee a valid solution: No one moves.

Try Two State Movement

Each and every map location has two sets of state: The current state, and the next state.

After each round of applying the rules the current state becomes the next state, and the next state becomes the current state. This is easily done by using two arrays and swapping the pointer to each.

Additionally at the start of a round of applying rules the next state is reset, (set to blank/empty). Resetting at the start of the round instead of at the end allows the game AI to look at the next state as a history state. This can be useful in making adaptive AI agents.

Now calculating the next state can become a lot simpler. You have access to a guaranteed good current state. The next state is just a best guess after having processed the first K movers, which is empty when K=0. The K+1 mover can easily check for a collision by checking the desired cell in next state.

  • If it is empty happy days.
  • If it is not empty then a collision has occurred and the ownership of the spot is in question.

    • Apply the collision resolution rules. This will kick one of the movers out.
    • Determine the next desired move for the kicked out mover.
    • Attempt to move to the new location, by checking to see if it is empty first, and applying the collision resolution logic if not.

Process every mover in the world, and resolve each collision as it happens. Now swap the next and current state labels and move on to the next stage of processing.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.