• Advertisement
Sign in to follow this  

Experiment : object-less design

This topic is 3549 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm in the process of making a simple experiment : design a game without using classic object-oriented techniques (in particular, inheritance and sub-typing). To be honest, I don't have the smallest idea of how the chosen approach is called, but I'll relate it here to give people ideas and perhaps learn a little more about it. The code is in OCaml, but I'll provide some explanations to non-Caml users. This post is more for your particular information than for asking any question, though opinions and insight are welcome. The game world, called the Simulation, is merely a list of entities (each associated with an identifier that the other entities can use to refer to it). Each entity is associated with (but does not store internally):
  • A trajectory, which is a function that gives the entity's position as a function of time. This function is affine, which allows me to avoid updating the entities 50 times a second just to integrate their position—instead, the rendered entities get their positions evaluated, and the updated entities get their trajectory changed when applicable.
  • A next-think time. Entities 'think' at fixed intervals, and thus each of them has a time when the next think step must happen for that entity. I'll explain later what thinking means.
  • A collision hull. This is a fixed geometric shape, used by the collision detection system to compute collisions between entities.
Thinking and collision responses are handled by the Entity module, which provides the infrastructure for having an entity think, and two entities respond to their collision. Both involve a functional value-replacement process:
  • The think function is typed as entity -> (inmsg -> answer) -> (entity option) * (outmsg list). Let's interpret this: thinking involves an entity as well as a function which can answer the entity's questions about the surrounding world. It returns a new entity (which represents the new state of the entity, and should thus replace the old state inside the simulation), or no new entity (explaining that the entity is dead and should be removed) as well as a list of out-messages which represent the attempts of the entity to interact with the rest of the simulation. This allows the entity module to be completely blind to the actual nature of the simulation module.
  • The collide function has a similar entity * (inmsg -> answer) -> entity * (inmsg -> answer) -> ((entity option) * (outmsg list)) * ((entity option) * (outmsg list)) type: two entities (with their answer-question-about-world functions) are turned into two new entity states (and their corresponding list of outbound messages).
What are the inmsg and outmsg types here? Here are some examples:
type inmsg  = [ `GetSelfPosition of vector question
              | `GetCurrentTime of float question
              | `GetNearbyEntities of entity_id list question
              | `GetPressedKeys of key list question ]

type outmsg = [ `SetNextThink of float 
              | `SetVelocity of vector ]
Before going on, let's look at the Answer module:
type 'a question
type answer
val answer : 'a question -> 'a -> answer
val ask : ('a question -> answer) -> 'a
The point of this module is to allow the simulation to provide a single "observe the world" function, that can return any type based on the message that was sent to it. I can write an implementation of that function for a given entity as:
let input entity = function
  | `GetSelfPosition q   -> answer q entity.position
  | `GetCurrentTime q    -> answer q now
  | `GetNearbyEntities q -> answer q (get_nearby_entities entity)
  | `GetPressedKeys q    -> answer q (keyboard # get_keys)
And somewhere inside the entity code:
let now = ask (fun q -> input (`GetCurrentTime q)) in ...
The end result is that the single 'input' function can now be used to retrieve values of any type, without having to use an additional variant type, and without giving up type-safety. This function also provides lazy evaluation, since the returned value is not computed until the function is actually called. Now, what is the purpose of using such messages, instead of passing around a class with those methods? The answer is different for the input and for the output messages. The question is most difficult for input messages: after all, it would be possible to use:
class type input = object
  method self_position : vector
  method current_time : float
  method nearby_entities : entity_id list
  method pressed_keys : key list
end
In practice, the two solutions are identical, neither of them requiring significantly more work than the other or being less safe than the other. Since output messages have a good reason to be variants instead of classes, and for the sake of having an uniform interface, I decided to go with the variant instead of the class type. As for the output message, there are two main difficulties. First, what class should be instantiated? The fact that the class to be instantiated (and the messages to be sent) depend on the simulation implementation, the base output message class must be passed as an argument. Second, since this is a functional framework, the output message class must be modified and then returned (because it cannot be modified in place) and its final state must then be parsed by the simulation to determine the modifications to be applied. The simulation itself being immutable, it's simply impossible to apply the output messages directly in the methods of the class. And so, the class would look something like this :
class type output = object
  method move : vector -> output
  method next_think : float -> output
end
The difficulty of implementing these methods, plus the parsing code, are much higher than simply building a list of variant values, and then parsing that same list. In fact, the cleanest way to implement the class would actually be with an internal variant value list! Now that the principles of input-output and thinking are laid down, how does polymorphic behavior appear in this framework? Assuming that our game has enemies, players and bullets, how to allow entities to be polymorphic instances of these three types of elements? The solution adopted here gives up on the open-closed principle (although in theory it could have been achieved through functional tricks) because it's easier to do it this way. The point here is that the game developer (as opposed to the 'engine' developer) is the one writing the Entity module, and therefore should not need for that module to be closed. As such, the entity type will look something like:
type entity = Player  of player
            | Enemy  of enemy
            | Bullet of bullet
Additional entity types can be added here if necessary (besides, enemy and bullet are types that can belong in their own module and can therefore be themselves variants to allow even more polymorphism at that level. There are obvious advantages of the variant approach. For instance, collision response gets much simpler than if an inheritance-based solution involving visitor multiple dispatch was used (not to mention that introducing a visitor requires compile-time knowledge of the list of possible colliding subtypes, and thus also violates the open-closed principle):
let collide a b = match a, b with 
  | Player p, Enemy e  | Enemy e, Player p  -> player_enemy p e
  | Player p, Bullet b | Bullet b, Player p -> player_bullet p b
  | Bullet b, Enemy e  | Enemy e, Bullet b  -> enemy_bullet e b
  | _ -> no_collision a b 
Also, the lack of inheritance does not make things that complicated either, since it can be fairly easily emulated using pattern matching:
let think entity input = match entity with
  | Player p -> 
    ( match Player.think p input with 
      l, None -> l, None | l, Some p -> l, Some (Player p) )
  | Enemy e -> 
    ( match Enemy.think e input with 
      l, None -> l, None | l, Some e -> l, Some (Enemy e) )
  | Bullet b -> 
    ( match Bullet.think b input with 
      l, None -> l, None | l, Some b -> l, Some (Bullet b) )
Then, it's possible to have each of the player, enemy and bullet modules have their own completely independent interface that requires no knowledge of the other two, or of the entity module, or of the simulation module. They may also use a smaller subset of the available messages (both inbound and outbound) by using the corresponding functionality in Objective Caml (for instance, a bullet would not require any messages at all, and would simply be killed by its collision with either an enemy or a player. So far, only the underlying model has been explained. The interface with the user (displaying things on the screen, reading input, playing sounds) has not been expressed. This is a good idea (and in line with the typical model-view-controller pattern). To each model is associated a view:
  • The SimulationView module extracts the visible and audible entities and prepares their corresponding view using ...
  • ... the EntityView module: provided with the position and value of every entity, this module is responsible for selecting what to render, possibly using the variant type to require specific attention from ...
  • ... the PlayerView, EnemyView and BulletView modules.
The view keeps some internal data (for animations states, and the like) from one frame to another, and merges that data with the new simulation state every frame. Conversely, every frame, the top-level SimulationController module updates the simulation state based on the elapsed time, appropriately specifying the list of pressed keys (and other input data) for the simulation to work with, before passing the resulting simulation to the view and storing it for the next frame.

Share this post


Link to post
Share on other sites
Advertisement
I think what I'm wondering the most is how useful is this to game development? Does it make the design more flexible? Allow greater maintainability? Reduce coupling between components? It seems to me that even when you eliminate the use of provided object oriented syntax, the design still typically revolves around a concept of objects. That is to say, any mildly large program will be designed around objects, even if the language used to create it does not provide explicit syntax for it.

Share this post


Link to post
Share on other sites
ahh offering a solution to a problem in a language few people know using techniques fewer people appreciate.

Like Mike I dont think its object less, just class less. The objects kind of fall out of/are implicit in the semantics of your model.

I may be talking out of my face here but your model seems to be biased towards space games. In fact it looks like a dsl for them. It also looks like it will not scale or get out of hand when being used for an RTS or even an RPG. might work for a multiplayer FPS. But looks like, if the game is of the free roam shooter type, it can scale extremely well since you can easily add structures and operations on them.

It also does not scale downwards, it seems to add too much think overhead for a game like tetris.

Would be cool to see a high level overview of how these modules interact.

Something else that looks like might be a problem is using matching to simulate inheritance when the hierarchies are more than two levels deep.

Share this post


Link to post
Share on other sites
The Wikipedia article on what "object based" is is very ambiguous unfortunately, but I think the gist of it is that when there is no implementation inheritance, it's not fully object oriented, just object based.

Incidently, I implemented a scripting language (no longer in development) that uses pattern matching to archive methods and inheritance (and guess what language it "compiles" to!).

I wonder if you could implement inheritance the same way? That is, match what you can, and delegate the rest by a function call, ie.:


let parent_input entity = function
| `GetNearbyEntities q -> answer q (get_nearby_entities entity)
| `GetPressedKeys q -> answer q (keyboard # get_keys)

let input entity = function
| `GetSelfPosition q -> answer q entity.position
| `GetCurrentTime q -> answer q now
| e -> parent_input e


The last line delegates to "parent" or "super". I'm not sure how the typing for variants work in OCaml, but maybe it's worth a try.

I'm also not sure what advantages this have over OOP (or indeed, how it's isn't exactly OOP or a subset). I don't think the visitor pattern is that bad, especially not in a language with lexical scoping and anonymous objects. The obvious advantages you're talking about are not so obvious to me, so please elaborate ;-)

[Edited by - Ahnfelt on August 4, 2008 4:25:32 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Daerax
ahh offering a solution to a problem in a language few people know using techniques fewer people appreciate.


Still, that is how you think outside the box. Sometimes it's best to step away from the usual ways of doing things to see if there's a better way which you couldn't see from the inside.

Share this post


Link to post
Share on other sites
Quote:
Original post by Kylotan
Quote:
Original post by Daerax
ahh offering a solution to a problem in a language few people know using techniques fewer people appreciate.


Still, that is how you think outside the box. Sometimes it's best to step away from the usual ways of doing things to see if there's a better way which you couldn't see from the inside.


Heh It was not a jab. It was more of a sharing sympathy thing. Since I had just done something (talking in a non famous language) like that prior to posting.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement