Welcome, Guest. Please login or register.

Login with username, password and session length

 
Advanced search

1411283 Posts in 69325 Topics- by 58380 Members - Latest Member: bob1029

March 29, 2024, 01:07:35 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsDeveloperTechnical (Moderator: ThemsAllTook)Functional equivalent of an entity-component tree
Pages: [1]
Print
Author Topic: Functional equivalent of an entity-component tree  (Read 1142 times)
Layl
Level 3
***

professional jerkface


View Profile WWW
« on: March 17, 2015, 04:39:02 AM »

In many engines written in imperative languages, the world is represented by a tree of entities, each entity object having a series of component objects. This generally works well for representing complex worlds. Within a functional programming language however, methods let alone inheritance within a type are generally discouraged, if they even are permitted. What would be a good way to manage large and complex worlds in a functional language?
Logged
Netsu
Level 10
*****


proficient at just chillin'


View Profile WWW
« Reply #1 on: March 17, 2015, 04:51:17 AM »

I don't really understand your problem. What does a tree structure and having components have to do with inheritance and methods?

Trees are actually the most widely used structures in functional programming as far as I know.
Logged

Layl
Level 3
***

professional jerkface


View Profile WWW
« Reply #2 on: March 17, 2015, 04:58:41 AM »

Well generally in a entity-component tree, you would have components like this:

Code:
public class MyComponent : EntityComponent, IUpdatable
{
    public float Speed { get; set; }

    public void Update(TimeSpan elapsed)
    {
        Entity.Position += new Vector3(Speed * elapsed.TotalSeconds, 0, 0);
    }
}

This way a game engine can use reflection to find the components that want to be updated, any caller that needs to configure a component can set the property, and the component itself can access the parenting Entity.
Logged
Netsu
Level 10
*****


proficient at just chillin'


View Profile WWW
« Reply #3 on: March 17, 2015, 05:22:01 AM »

Oh, I see. Can't really help with that as I've never extensively used a language with reflection.

But I think the whole point of using functional programming is to use a different approach to OOP entirely. So for example instead of thinking about callers and components think about the process/function that translates the world tree of frame X to the world tree of frame X+1 and then design the whole tree in a way that simplifies updating the world through simple traversal.

Then again, I'm no expert at FP either, and have no idea how a functional game engine could work Shrug
Logged

Layl
Level 3
***

professional jerkface


View Profile WWW
« Reply #4 on: March 17, 2015, 05:32:05 AM »

Well a really important part would be that you can still plug in new update behavior without editing the core engine code.
Logged
Cheesegrater
Level 1
*



View Profile
« Reply #5 on: March 17, 2015, 06:42:28 AM »

You can still do it OO-style in a functional language. There are two main ways: One is to exploit that functions are data, and stuff your entity's logic into a list member as a lambda. This has the virtue of being quick to code at first, but it can be hard to refactor if you decide you need additional methods and/or data later.

The other way is to use message passing. In this case you have a 'constructor' function that itself returns a dispatch function. The first argument to the dispatch function is a message (typically a string literal), which is analogous to a Object method.

The implementation of the dispatch function is a conditional that performs different actions depending on the message you passed in. You can define these 'methods' as functions in the dispatch function's scope if you want.

Here's an example: http://community.schemewiki.org/?simple-object

I'm most familiar with Scheme. If you're using something else your mileage may vary.
Logged
Layl
Level 3
***

professional jerkface


View Profile WWW
« Reply #6 on: March 17, 2015, 08:53:13 AM »

I'm not looking for a system that mimics the way it's done in object oriented languages, but rather one that's idiomatic to functional languages. Unless this is an area where really objects just are the better approach in which case in my language of choice I still have objects available.
Logged
BorisTheBrave
Level 10
*****


View Profile WWW
« Reply #7 on: March 17, 2015, 02:23:35 PM »

Open types (i.e. subclassing where you don't list all the possible subsclasses up front), is not really idiomatic for many functional languages. This is the entire premise of components, so I don't think they translate well. Likewise, reflection is not a thing. Functional languages tend to prefer static typing.

The easiest reasonable implemenation is to just definite all components in a gigantic union. (and likewise make an update function that is a gigantic pattern match).

But I think a better approach would be to replace stateful components, with stateless behaviours, where each behaviour is a function World -> Entity -> World. The game engine is responsible for invoking every behaviour on every object each tick. Move all the state into the Entity object itself, which becomes a fairly large record, where it can be better managed.

Note that behaviours as described *can* contain private state (as they can replace themselves when updating the world), but anything you want to be "shared" goes into the entity. But the design strongly encourages immutable behaviours.
Logged
Layl
Level 3
***

professional jerkface


View Profile WWW
« Reply #8 on: March 17, 2015, 03:42:29 PM »

Could you give a (psuedo)code reference implementation of such a system? I think I'm getting the idea but I'm not entirely sure.
Logged
BorisTheBrave
Level 10
*****


View Profile WWW
« Reply #9 on: March 18, 2015, 03:26:49 PM »

I don't really know functional languages that well and I've been drinking, but here goes. I've wussed out and toned down the scope of behaviours, because i'm not good enough to write the "step" procedure otherwise.

Code:
-- Entity is a record with various bits of data, and a list of behaviours
data Entity = Entity {
 position :: Point,
 speed :: Point,
 name :: String,
 behaviours :: [World -> Entity -> Entity]
}

-- World is a list of entities (though it could also be a record if you needed global data)
type World = [Entity]

-- Runs every behaviour on a every entity
-- NB: I've written this with no cleverness for simplicity but
-- there are better ways to achieve the same result.

step :: World -> World
step w = tickInner [] w
  -- tickInner recurses over the list of entities in the world
  where  tickInner processed [] = processed
         tickInner processed (current:remaining) = tickInner (processed ++ [runBehaviours processed current remaining (behaviours current)]) remaining
  -- runBehaviours runs each behaviour in turn
  where runBehaviours _            currentEntity _             []                                     = currentEntity
        runBehaviours prevEntities currentEntity afterEntities (currentBehaviour:remainingBehaviours) =
           runBehaviours prevEntities (currentBehaviour (prevEntities ++ [currentEntity] ++ afterEntities) currentEntity) afterEntities remainingBehaviours

-- Now to define a few behaviours to demonstrate

-- Inertia is responsible for moving objects by speed each tick
inertiaBehaviour w e =  e { position = position e + speed e}

-- Gravity changes speed by a constant each tick
makeGravityBehaviour g w e = e {speed = speed e + g}

gravityBehaviour = makeGravityBehaviour Point 0 -9.81

-- Some utility methods
explodeEntity e = e {name = "explosion"}
isNearby e1 e2 distance = length ((position e1) - (position e2)) < distance

-- explodesNearbyBehaviour causes objects to explode if near the player
explodesNearbyBehaviour w e =
  if any (\other -> name other == "player" and isNearby other e 1.23) w
  then explodeEntity e
  else e

-- Behaviour with private "mutating" state. I'm pretty sure this doesn't work without some refining?
countdownBehaviour timer w e ->
  if timer == 0
  then explodeEntity e
  -- return entity, replacing the old countdownBehaviour with a new one with a smaller timer
  else e { behaviours = (countdownBehaviour (timer-1)) : delete (countdownBehaviour timer) (behaviours e)

Really, not very good code, but perhaps it gives you the idea.
Logged
Layl
Level 3
***

professional jerkface


View Profile WWW
« Reply #10 on: March 19, 2015, 04:46:17 AM »

Though a bit hard to read it does give me a general idea of it, thanks.
Logged
Boreal
Level 6
*


Reinventing the wheel


View Profile
« Reply #11 on: March 24, 2015, 10:26:22 PM »

I wrote this up for fun, ended up teaching myself the importance of applicative functors in the process  Evil

First you have your components.

Code:
type Position = Float
type Velocity = Float
type Name = String

Now, your systems.

Code:
position :: Position -> Velocity -> Position
position x v = x + v

velocity :: Velocity -> Velocity
velocity v = v - 9.81

draw :: Position -> Name -> String
draw x n = n ++ "@" ++ show x

All pretty basic.  Next we add our entity type as well as a couple of convenience functions.

Code:
data Entity = Entity {
    x :: Maybe Position,
    v :: Maybe Velocity,
    n :: Maybe Name
}

makeStatic :: Position -> Name -> Entity
makeStatic x n = Entity (Just x) Nothing (Just n)

makeDynamic :: Position -> Velocity -> Name -> Entity
makeDynamic x v n = Entity (Just x) (Just v) (Just n)

Hopefully this is still pretty straightforward.  Here's where things start to get a bit hairy.

First, I made a convenience operator that basically works the same as or in Lua.  My Haskell standard library knowledge is very shallow so I may have accidentally used a name that another module defines.  Droop

Code:
(<?>) :: Maybe a -> Maybe a -> Maybe a
Just x <?> _ = Just x
Nothing <?> x = x

I then broke the tick function down into two discrete parts.

Code:
tick :: Entity -> IO Entity
tick e = do
    render e
    return (update e)

The update function is pure and makes the changes to each component out-of-order.  In a real implementation you would probably want to bucket things to reduce latency.

Code:
update :: Entity -> Entity
update e = Entity
    (position <$> (x e) <*> (v e) <?> (x e))
    (velocity <$> (v e) <?> (v e))
    (n e)

Here you can see the usage of the operator I defined.  Let's analyze the calculation of the position.  It basically reads: "If both the position and velocity are Just values, make the new position the result of the position system function.  Otherwise, copy over the old position."  The render function is a bit simpler.

Code:
render :: Entity -> IO ()
render e = maybe (return ()) putStrLn (draw <$> (x e) <*> (n e))

If it has both a position and a name, it prints a line.  If not, it doesn't do anything.

I didn't bother to make an actual game loop, but it should be pretty straightforward.  You would just map the tick function over a list of entities to get the next frame's entity list.



Here's the full, runnable source file if you're interested.

http://hastebin.com/fusenunawa.hs
« Last Edit: March 24, 2015, 10:32:22 PM by Boreal » Logged

"In software, the only numbers of significance are 0, 1, and N." - Josh Barczak

magma - Reconstructed Mantle API
Pages: [1]
Print
Jump to:  

Theme orange-lt created by panic