Design pattern for modeling two competing objects

Question

I'm trying to figure out the best design pattern to use for managing a "competition" between two interacting objects. For example, if I want to have a Fox class that chases a Rabbit class through a simple environment. I want to let them "compete" and find out which one wins. Eventually it would become a teaching tool that students can use to experiment with inheritance and other OO programming skills.

Is there an established design patter for this use case?

Here's the best I could come up with: one class to represent the environment that hosts both other objects. I'm keeping it very simple and assuming the animals only run in straight lines and the fox catches the rabbit if he gets close enough to bite the rabbit. Here is some code demonstrating what I'm describing. I used PHP because I can write it quickly, but I don't want to focus on the specifics of the language. My question is really about the design pattern / architecture.

class Forrest() {
        public $fox;
        public $rabbit;
        public $width = 100; //meters?
        public $length = 100;

        __construct() {
                $this->fox = new Fox();
                $this->rabbit = new Rabbit();
                $this->theChase();
        }

        public function theChase() {
                 while (!$this->rabbit->isBitten) {
                         $this->rabbit->react($fox);
                         $this->fox->react($rabbit);
                 }
                 log('The fox got the rabbit!');
        }
}

abstract class Animal() {
        public $speed;
        public $hasTeeth = false;
        public $position;
        public $direction;
        public $isBitten = false;
        public function run($distance) {
                // update coordinates based on direction and speed
        }

        public function bite($someone) {
                 if (isCloseEnough( $someone ) && $this->hasTeeth) {
                          $someone->isBitten = true;
                          log(get_class($this) . ' bit the ' . get_class($someone)); //the Fox bit the Rabbit
                 }
        }

        public abstract function react($someone);
}

class Rabbit extends Animal {
         __construct() {
                  $this->speed = 30;
                  $this->position = [0,0];
                  $this->direction = 'north';
                  log(get_class($this) . ' starts at 0,0');
         }

         public react($fox) {
                //avoid the fox
         }
}

class Fox extends Animal {
          __construct() {
                  $this->speed = 20;
                  $this->position = [100,100];
                  $this->direction = 'south';
                  log (get_class($this) . ' starts at 100,100');
          }

          public react($rabbit) {
                  //try to catch the rabbit
          }
}

There are two immediate problems I see with this approach:

1. This architecture results in sequential, alternating actions. In other words, first the rabbit does something then the fox does something then the rabbit does something... This is more like a card game where each player takes turns moving. It would be more interesting if both objects were able to react simultaneously.

2. There is not yet a system for limiting the amount of activity per "turn". There needs to be some sort of restriction on what can happen in a single "turn" to keep it interesting. Otherwise the fox could simply run() run() run() ... run() until it catches the rabbit on it's first turn. 

There are probably other problems that I haven't noticed yet. I suspect that the answer to both (1) and (2) above is some sort of event system that allows action from one animal to trigger action from the other and visa versa. I also think there may need to be some representation of time associated with each action, but I'm not entirely sure.

Nipissing

Answer 1

So, you are tasked with fitting something like game under design patterns, which originally were created for enterprise kind of software only. Games are not enterprise software by definition, and that's the reason why many people have avoided thinking about design patterns when designing games. That does not mean it's not doable though.

My recommendations:

• Think model first: design your problem as you envision it.
• Remember it's still a game, so it needs to follow game development patterns: there's just one actually - game loop.

So, if you combine the two above (I wish the second was not there), then I'd design it this way (I will mention the design pattern if my suggestions remind me one):

1. Mark current time point.
2. Environment starts game loop.
3. For each loop step, calculate time passed since the last time point. This will give you time span in some units (e.g. N milliseconds passed).
4. Given time span, you need to ask each object to update its state (conceptually, ask them - where would you be now if N milliseconds had passed?). This reminds me of Visitor pattern a bit.
5. After all objects have updated their states, Environment displays results on the screen (in real games this means to draw the current state of the game - each object gets redrawn on the screen; for your simple application, you could check whether Fox has reported that it has caught the rabbit).
6. Obviously, while within the loop step, you need to keep marking the current time, so that the time span difference can be calculated at each step.

Step #4 involves some complexities, especially if the accuracy is critical. e.g. what if the time span is about a second, and within that second (in the middle somewhere) the fox would have caught the rabbit, but in the end there is still distance? this can happen if the speeds of fox and rabbit are functions of time (sometimes they slow down, sometimes they speed up) [btw, this sounds like a Strategy pattern - variation for calculating current speed - e.g. linear vs time-function). Obviously, if the fox and rabbit both just report their positions at the end of the time span, the catching moment will be missed, which is not desirable.

Here is how I would solve it: for given time span, if it's more than a single millisecond (let's assume millisecond is the shortest acceptable atomic time for good enough accuracy), then split it into the time spans of millisecond length each, and for each millisecond, ask every object to update its state. After all, if the object can update its state based on a time span, we can call it as many times as we want with shorter time spans. Obviously, there is unavoidable side effect - you need to update states in some order, but given that millisecond is too short period of time, it should be just fine to do that.

Pseudo code would look like this:

var foxAndRabbitGame = new FoxAndRabbitGame();
foxAndRabbitGame.RunGame(screen); //visitor
/* when this line is reached, game is over. Do something with it. */

---

class FoxAndRabbitGame
{
    private fox = new Fox(Speed.Linear()); //strategy
    private rabbit = new Rabbit(Speed.Linear()); //strategy


    void RunGame(screen)
    {
        var currentTime = NOW;
        while (true)
        {
            var timePassed = NOW - currentTime;
            currentTime = NOW;

            foreach (millisecond in timePassed)
            {
                fox.UpdateState ( millisecond , rabbit );
                rabbit.UpdateState ( millisecond, fox );

                if (fox.TryBite(rabbit))
                {
                    //game over.
                    return;
                }
            }

            //usually, drawing is much slower than calculating state,
            //so we do it once, after all calculations.
            screen.Draw(this); //visitor
            screen.Draw(Fox); //visitor
            screen.Draw(rabbit); //visitor
        }
    }

}

Reviel

There is one nitpick though - rabbit and fox objects are not properly encapsulated and it doesn't solve the 2nd problem OP has stated. Besides, this is a very technical answer and while that's not necessarily wrong I thought we were discussing an abstract design problem, not how to implement a game engine. – Goldfinch

Also I don't see your point about how design patterns are for enterprise software only. They're not - you've proven that yourself using two of those in your answer. The fact that many people think game development doesn't need good architecture design, object oriented thinking and just good programming is a real problem in the game dev industry (in which I happen to work) – Goldfinch

@Dunno, I thought I answered the second question of OP by suggesting to introduce a minimal atomic time span (1 millisecond in my answer); I don't guarantee that my interpretation of the question is the only true one. As about design patterns and games, I meant that for games framerate is more important than code quality. For that reason, many patterns are not suitable for games; e.g. many of them ask for richer memory allocations for cleaner code, which games will never do, while enterprise adores their maintainability effects. In games, framerate is a king. In enterprise, patterns are. – Reviel

Framerate is affected either by doing costly calculations every frame or by rendering. Unless you're doing a super complex RTS and not doing anything stupid (like iterating over a lot of objects every frame), the latter will cause a lot more problems. Design patterns are just as important in game dev as in any other programming job, it's just that game dev tends to attract poor programmers who just want to have fun and make games. – Goldfinch

@Dunno, I'm glad to hear that from game developer (assuming this is what you do). I was always hesitating to go into that industry just because it seems they don't get patterns and code quality issues. Now I feel it's not me, it's them :-) thanks! – Reviel

Answer 2

In a game-loop, one usually would update the velocities (here in your the react function) of both objects and then update the position of the objects. Thus moving simultaneously.

while(!gameOver) {
 rabbit->react(fox);
 fox->react(rabbit);
 rabbit->updatePosition();
 fox->updatePosition();
}

For limiting activity per turn/frame you'd have to think of something clever. For example you could make a certain set of actions that one can do, and each action has an energy cost. You would get a certain amount of energy each turn to use. You'd have to have more than one run() action though to make this interesting :).

Antitrust

I think I understand. By splitting the react() and the update() it allows each object to move at the same time. – Nipissing

In the real version there would be a few different actions definitely. So the outcome is less predictable. I just tried to make this example very minimal. – Nipissing

Answer 3

• I would suggest the Mediator pattern. It generally promotes loose direct coupling between a set of objects (in your case fox and rabbit). You would need to introduce another object which captures the state of the system as a result of the actions of the rabbit and the fox (eg call it "the chase").
• A mediator object would handle the interaction between all objects. I.e evaluate the actions requested by rabbit and fox, then determine what the actual result of these actions will be (everything goes through the mediator!) and update "the chase" accordingly. This way you can control your issues 1 and 2 above, or other issues.
• I have previously implemented this pattern for HMI interfaces, where users could interact with a system via keypad & screen, and depending on selections/system state / previous selection, etc appropriate state transitions needed to occur.

Templar

Answer 4

On a general idea my approach would be:

1. Each subject (fox, rabbit, etc) has a state (in your case velocity, position and direction).
2. The environment (container) has a state which is a combination of the states of the subjects and others constraint if needed (impenetrable zones, ruined terrain, etc).
3. Each subject has a cost function to be minimized (the fox has the distance between the subjects, the rabbit the inverse of such distance)
4. Each subject must have some constraint (such as max_distance_per_turn, max_direction_changes_per_turn, etc) to prevent the first subject to win at time 1.
5. The environment state can affect the subject actions (e.g. the fox running has dug a hole which can't be passed by the rabbit), so each action must be aware of the global current state.
6. Each subject modify its state starting only from the starting environment + subjects states; the fox moves accordingly to rabbit's position at time 0 (and the rabbit does the same). Note that this is different from fox.react(rabbit); rabbit.react(fox); because the rabbit knows where the fox is at time 1 (after it moved).
7. If needed, also the whole transaction should be examinated: if at time 0 the rabbit is not biteable, and at time 1 it is also not biteable, but during the transition it reached a point in where it was biteable, the fox should win. To avoid this th goal is to make the "turns" as atomic as possible, in order to ignore those transactions. Alternatively you can add a transaction check to the environment to be run after each turn.

In a more general view, you can think of that environment as a closed system with retroaction: each action modify the whole state which will affect the new actions. In this scenario each istruction is still sequential, but each "turn" is indeed a closed transaction from one state to the next one, in which all the subjects execute simultaneously.

Mink

Answer 5

Elaborating on the mediator pattern suggestion, to add the illusion of simultaneity the game state could be extracted to a separate object (plain old data) and updated after all objects made their decisions. For example (in java-ish language)

public class OpponentData {
    private Position theirPosition; // + public get

    // constructor with theirPosition param, keeping the class immutable
}

public interface Animal {
    // returns data containing their updated data
    OpponentData React(OpponentData data);
    Position GetPosition();
}

public class Fox implements Animal {
    public OpponentData React(OpponentData data) {
        if (this.position == data.GetPosition())
            // this method can be a little tricky to write, depending on your chosen technology, current architecture etc
            // Fox can either have a reference to GameController to inform it about victory, or fire an event
            // or maybe even do it itself, depending if you need to destroy the rabbit object in game controller
            EatTheRabbit();
        else {
            // since the game state won't be updated immediately, I can't just run until I reach the rabbit
            // I can use a bunch of strategies: always go 1 meter forward, or use a random value or something more complicated
            ChaseTheRabbit();
        }
        return new OpponentData(this.position);
    }
}

public class Rabbit implements Animal {
        public OpponentData React(OpponentData data) {
            KeepRunningForYourLife();
            // maybe you can add something more for the rabbit to think about
            // for example, bushes it can run to and hide in
            return new OpponentData(this.position);
        }
}

public class GameController {
    private Fox fox;
    private Rabbit rabbit;
    private OpponentData foxData;
    private OpponentData rabbitData;

    private void Init() {
        fox = new Fox();
        rabbit = new Rabbit();
        foxData = new OpponentData(fox.GetPosition());
        rabbitData = new OpponentData(rabbit.GetPosition());
    }

    private void PerformActions() {
        var oldData = foxData;
        foxData = fox.React(rabbitData);
        // giving the old data to the rabbit so it doesn't know where the fox just moved
        rabbitData = rabbit.React(oldData);
    }
}

If you want the game to depend on more factors than just the position, you can easily extend the OpponentData class adding health level, strength etc.

This approach solves both your problems, because each of the players (fox and rabbit) doesn't know what the other is doing in the same turn so the rabbit can evade the fox and the fox can't just run() run() run() to it's victim (because it doesn't know where the rabbit is going to move). Fun fact - the Game of Thrones board game uses the same technique to create an illusion of giving orders to your armies simultaneously with other players.

Goldfinch

Answer 6

I thought, there should be two abstract classes related to animal abstract class.(Omnivore and carnivore classes, both have different attributes)

here is Animal Abstract class

public abstract class Animal implements Runnable{
private double speed = 0 ; // Default
private Point location = new Point(new Random().nextInt(50) + 1 , new Random().nextInt(50) + 1);

abstract void runAway(Animal animal);
abstract void chase(Animal animal);
abstract void search4Feed();
abstract void feed();

public synchronized Point getLocation() {
    return location;
}
public synchronized void setLocation(Point location) {
    this.location = location;
}

public double getSpeed() {
    return speed;
}

public void setSpeed(double speed) {
    this.speed = speed;
}

}

Here is Carnivore and Omnivore Classes

public abstract class Carnivore extends Animal {
Animal targetAnimal ;

}

public abstract class Omnivore extends Animal {
Animal chasingAnimal;

}

For forest class and its implementation, Iforest may be implemented by different forest classes.And it needs to keep its own animal ecosystem.

public class Forest implements IForest {
private List<Animal> animalList = new ArrayList<Animal>();

public Forest() {

}

@Override
public void addAnimalToEcoSystem(Animal animal) {
    animalList.add(animal);
}

@Override
public void removeAnimalFromEcoSystem(Animal animal) {
    animalList.remove(animal);
}

@Override
public void init() {
    // to do:       
}

@Override
public List<Animal> getAnimals() {
    return this.animalList;
}

}

public interface IForest {
void removeAnimalFromEcoSystem(Animal animal);
void addAnimalToEcoSystem(Animal animal);
List<Animal> getAnimals();
void init();

}

Here is rabbit and fox classes. Rabbit and fox classes have IForest class instance in their constructor. Chasing an animal or running away from any animal needs to be forest ecosystem And these classes has to notify their movements to Forest classes via IForest interface.Here I used Runnable thread because these classes needs to move independently, not sequential.In run method you can define rules for hunter or hunt's according to your specified conditions.

public class Rabbit extends Omnivore {

private IForest forest = null ;

public Rabbit(IForest forest) {
    this.forest = forest;
    this.setSpeed(40);
}

@Override
public void runAway(Animal animal) {
    this.chasingAnimal = animal;
    this.run();
}

@Override
public void chase(Animal animal) {
    // same as fox's
}

@Override
void feed() {
    // todo:        
}

@Override
void search4Feed() {

}

@Override
public void run() {
    double distance = 10000; //default,
    this.chasingAnimal.runAway(this); // notify rabbit that it has to run away
    while(distance < 5){ // fox gives chasing up when distance is greater than 5
        distance = Math.hypot(this.getLocation().x - this.chasingAnimal.getLocation().x, 
                this.getLocation().y - this.chasingAnimal.getLocation().y);
        if(distance < 1) {
            break; // eaten
        }
        //here set  new rabbit's location according to rabbit's location
    }
}

}

public class Fox extends Carnivore {

private IForest forest = null ;

public Fox(IForest forest) {
    this.forest = forest;
    this.setSpeed(60);
}

@Override
public void chase(Animal animal) {
    this.targetAnimal = animal;
    this.run();
}

@Override
public void run() {
    double distance = 10000; //default,
    this.targetAnimal.runAway(this); // notify rabbit that it has to run away
    while(distance < 5){ // fox gives chasing up when distance is greater than 5
        distance = Math.hypot(this.getLocation().x - this.targetAnimal.getLocation().x, 
                this.getLocation().y - this.targetAnimal.getLocation().y);
        if(distance < 1) {
            feed();
            break;
        }
        //here set  new fox's location according to rabbit's location
    }
}

@Override
public void runAway(Animal animal) {
    // same as rabbit's
}

@Override
public void feed() {
    // remove from forest's animal list for the this.targetAnimal
}

@Override
void search4Feed() {
    // here fox searches for closest omnivore
    double distance = -1;
    Animal closestFeed = null;
    List<Animal> l = this.forest.getAnimals();
    for (Animal a : l) {
        double d = Math.hypot(this.getLocation().x - a.getLocation().x, this.getLocation().y - a.getLocation().y);
        if (distance != -1) {
            if(d < distance){
                this.chase(a);
            }
        }
        else{
            distance = d ;
        }
    }
}

} init method below

public static void main(String[] args) {
    // you can use abstract factory pattern instead.
    IForest forest = new Forest();
    forest.addAnimalToEcoSystem(new Rabbit(forest));
    forest.addAnimalToEcoSystem(new Fox(forest));
    forest.init();
}

if you want to make this more complicated such as collabration or something else you need to use observable pattern. It can be used to create animals,forest via abstract factory pattern. Sorry for the messy code due to the fact that I dont have much time. I hope this helps you.

Lamere

Answer 7

The competition between rabbits, foxes and possibly other animals can be modeled using discrete event simulation, which could be considered a design pattern per se (simulation clock, event queue, …).

The objects may implement Strategy pattern. The execute method could be named decideAction in this case – it would get the old state of the world (read-only) and produce a decision (description of an action).

The simulation would plan the event that results from the decision, then. When the event is processed, the simulation will change the state of the world. Thus, the simulation could be considered an instance of Mediator pattern because it isolates the agents from direct interaction – they just see the state of the world and produce decisions, while production of new state of the world and evaluation of rules (such as velocities and detection of successful bite or escape) is left to the simulation.

---

To make all agents’ (animals’) decisions simultaneous, plan all events to happen simultaneously (in the simulation time) and update the world state only after all events occurring at the same simulation time have been processed (the decisions have been made).

You would not need the event queue and simulation clock, then. Just a loop that gathers all the decisions and finally updates the state of the world in each iteration would be enough.

This may not be what you want, though, e.g. because initially, it might take some time to a rabbit to notice that a fox is approaching. It might be more interesting if the timeout between events for an animal (reaction time) varies with its state (alert, sleeping, etc.).

---

The amount of activity per “turn” cannot be limited, when the animal can directly change the world state and is implemented using almost arbitrary code. If the animal just describes its action, its type and parameters can be validated by the simulation and possibly rejected.

Turbot

This is a good answer. I don't understand the last two sentences though. Why can't the amount of activity be limited? Why is the code arbitrary? – Nipissing

By arbitrary code I mean code written by someone other than you, who is not constrained in any way other than technical when writing it. Anything the code could do technically, it may do actually. When you expose the world state to this code and the code is allowed to write it directly, you would have to do really crazy things to limit the amount of activity – like keep a copy of the original state and get the action description from comparison of the two states and only then validate it. Better get the action description directly. – Turbot

By the way, you may want to limit not only the actions, but also the processor time spent when calculating the action. Otherwise, the players may spend insane amounts of time computing the optimum strategy. This constraint is technically more demanding to implement, though, and is unnecessary if your students are going to just play with the simulation instead of actually writing good AI for the animals. – Turbot

Limiting of action by describing the action in a declarative way seems to really be the standard practice. For anecdotal evidence, see Survival Game - Create Your Wolf on Code Golf. Especially EmoWolf is great. :-) – Turbot