Effective character/enemy programming

Aug 11, 2014 at 8:24 PM
Senior Member
"Wahoo! Upgrade!"
Join Date: Aug 11, 2014
Location:
Posts: 57
Hi guys, just joined the forums, so here’s a small amount of background: I've been programming game engines (or rather, "game engines" since I can't say I've made a successful game with them) for a while now and I'm recently trying to dedicate myself to making actual games as opposed to just tech.

The problem I seem to have, however, is settling my thoughts on the best way to program characters. I normally don't have any problem programming intrinsic engine behaviors like lighting, physics, graphics, ect. When I get to something like character programming, though, I start flopping like a fish out of water. I've tried everything from normal "update" based models to coroutines to finite state machines and all results just feel so verbose and needlessly complicated. The code always ends up with a ton of special cases that turn it into such a mess. That's what bothers me the most.

I want to deal with character and enemy code in an elegant way, and I would like to know if anyone here would like to share their methodologies and experiences for programming them. I chose to post on CS forums because, as practice, I would like to recreate some simple CS enemies in my own script system.

I realize this is kind of a vague question, something akin to "how do I program fun", but I hope I'm not alone in my feelings here.

Thanks in advance.
 
Aug 11, 2014 at 8:48 PM
In my body, in my head
Forum Moderator
"Life begins and ends with Nu."
Join Date: Aug 28, 2009
Location: The Purple Zone
Posts: 5998
Oh boy an actual thought-provoking question

Personally, I'm probably in the same kind of boat you're in because I also find coding in enemy behaviour to be an onerous task.
A lot of my experience comes from modding Cave Story and I can say that the way Pixel does it, at least, is every different enemy AI is a finite state machine. They have an int that defines which "type" it is, and each type corresponds to one entry in a big array of function pointers.
Yes, that's right, each of the 360+ enemies in Cave Story has a function dedicated to its behaviour and I'm pretty sure it makes up at least half of the executable's code size. Makes modding them easy, at least.. but, not exactly the most elegant solution, and you can tell a lot of them are copy-pastes of each other with minor changes (critters, for example).

This kind of behaviour could be likened to the Delegator pattern in OOP, if you wanted to pretend you're making use of that Software Engineering Principles and Practices textbook you got 3 years ago and haven't touched since. Really flat implementation of it but I think it still fits.

Now, as for what a more elegant solution would entail, I guess it would depend on what kind of behaviour you want them to have and how much control you want over that behaviour. There's a lot of room to abstract certain movement patterns into general behaviours that can be applied to different enemies (follow player, jumping, walk around an area, etc) but then you've got to decide how it figures out which to do when, so you could still end up having to write a number of specific cases.
 
Aug 11, 2014 at 9:14 PM
Senior Member
"Wahoo! Upgrade!"
Join Date: Aug 11, 2014
Location:
Posts: 57
Noxid said:
Personally, I'm probably in the same kind of boat you're in because I also find coding in enemy behaviour to be an onerous task.
I find this simultaneously comforting and discouraging (you seem to usually have all the answers on these forums; I been-a lurkin).

Noxid said:
Yes, that's right, each of the 360+ enemies in Cave Story has a function dedicated to its behaviour.
0_o

Noxid said:
A lot of my experience comes from modding Cave Story and I can say that the way Pixel does it, at least, is every different enemy AI is a finite state machine. They have an int that defines which "type" it is, and each type corresponds to one entry in a big array of function pointers.
I'm really curious how you found this out. I see that you decompiled some of CS's code, but does a decompiler maintain the overall program structure for a language like C++? My knowledge in this area is limited, but I have heard that while the algorithms remain in tact (obviously), most of the program architecture cannot be recovered.

Noxid said:
Makes modding them easy, at least.. but, not exactly the most elegant solution, and you can tell a lot of them are copy-pastes of each other with minor changes (critters, for example).
This is the sort of thing that scares me. I work with the game engine for [[NDAd]] and they do pretty much the same thing, except their underlying FSM is a lot more complicated (its a fighting game). Suffice to say its a nightmare and their company has suffered for it, with development times probably 4x longer than they need to be because every little change takes so much code re-writing.

Noxid said:
This kind of behaviour could be likened to the Delegator pattern in OOP
I suffer from the "god class" problem where there invariably ends up being a class like "MyEnemyC" that just ends up responsible for everything except a few small details. I try to delegate out the work as much as I can, but unlike programming "normal" systems, the helper objects end up requesting so much information from the main class that not only does it break encapsulation, but it gets prone to confusing bugs.

Do you have any theoretical insights as to why this might be if you experience the same thing? I've been trying to wrap my head around this question of "what is so hard about this?" and I just cant seem to come up with a solid answer of why its different than any other code.

Noxid said:
Now, as for what a more elegant solution would entail, I guess it would depend on what kind of behaviour you want them to have and how much control you want over that behaviour. There's a lot of room to abstract certain movement patterns into general behaviours that can be applied to different enemies (follow player, jumping, walk around an area, etc) but then you've got to decide how it figures out which to do when, so you could still end up having to write a number of specific cases.
It's been a tough job to try and balance aggregation and inheritance. Aggregation, imo, is usually the best software engineering practice for most things, but it creates a lot of overhead code dedicated to delegating out the work. There ends up being a lot of clutter and not a lot of substance. Inheritance on the other hand comes with all the problems of introducing a monolithic class hierarchy. It seems great because there's no delegation code, but want to change something too far into development and... well... pppttttpppttfffff


Thanks for the quick answer btw. The reason I chose to post on CS forums is that in a general dev forum the best answer I could get is "it depends". This is already starting to look more promising.
 
Aug 11, 2014 at 10:57 PM
In my body, in my head
Forum Moderator
"Life begins and ends with Nu."
Join Date: Aug 28, 2009
Location: The Purple Zone
Posts: 5998
Fluffball said:
I'm really curious how you found this out. I see that you decompiled some of CS's code, but does a decompiler maintain the overall program structure for a language like C++? My knowledge in this area is limited, but I have heard that while the algorithms remain in tact (obviously), most of the program architecture cannot be recovered.
It generally depends how it's written; Pixel's code is very C-like and he uses a lot of static structures and global memory objects, so with a little bit of experimentation and intuition it's possible to find patterns in how certain addresses are used and build up a pretty good idea of how the code could have looked. The structure is all there, it just takes a bit more knowledge than the machine has to make sense of it.

This is the sort of thing that scares me. I work with the game engine for [[NDAd]] and they do pretty much the same thing, except their underlying FSM is a lot more complicated (its a fighting game). Suffice to say its a nightmare and their company has suffered for it, with development times probably 4x longer than they need to be because every little change takes so much code re-writing.
mm, hand-crafted FSMs can become monstrous to maintain since your complexity just goes through the roof once you start adding more and more states, and it's easy to make the whole thing fragile as heck by introducing dependencies between different states and inter-state contracts that can't easily be guaranteed or even found.

I suffer from the "god class" problem where there invariably ends up being a class like "MyEnemyC" that just ends up responsible for everything except a few small details. I try to delegate out the work as much as I can, but unlike programming "normal" systems, the helper objects end up requesting so much information from the main class that not only does it break encapsulation, but it gets prone to confusing bugs.
Do you have any theoretical insights as to why this might be if you experience the same thing? I've been trying to wrap my head around this question of "what is so hard about this?" and I just cant seem to come up with a solid answer of why its different than any other code.
I think they key issue is that, the AI accounts for a lot of different things that can be different to encapsulate effectively. Consider the case of a critter - it's got a simple behaviour, sit and hop. But then, you want to animate it and it needs to know what frame to use at a given stage of its behaviour. So, you add delegating its frame in with the state logic. And, you want it to be aware of its surroundings, so you've got to add something to determine how its behaviour changes based on where the player is, if it's taking damage, what kind of environment it's in, etc.

you essentially have to build a decision-making engine tailored for each behaviour you want. With a physics system, or rendering, it's fairly straightforward - you have a set of inputs and given the same set of parameters it should always produce the same result. But, imagine if you had to design a physics engine where its behaviour had to change arbitrarily (but predictably) at any given time based on your user input, and then have someone say that they want 20 different implementations of it.

One way a lot of games seem to deal with the issue is by simply not having a whole lot of "different" enemy types. Hotline Miami, for instance, only has a few fundamentally different types of enemies (skinny guys, fat guys, dogs, and the boss fights) with a few parameters and the ability to equip weapons that also change their behaviour. Enemies in SHMUP-type games have very simple behaviours that usually don't react to the player or environment (which is usually the same every run), unless it's a boss. And Shovel Knight, a good retro-style game that is pretty comparable to Cave Story in this regard, only has maybe as many distinct normal enemy variants as it does bosses.
Actually I forget. But I know it recycles several of them.
the point is, that Cave Story is a bit of an anomaly for how many different behaviours it has, I think.

It's been a tough job to try and balance aggregation and inheritance. Aggregation, imo, is usually the best software engineering practice for most things, but it creates a lot of overhead code dedicated to delegating out the work. There ends up being a lot of clutter and not a lot of substance. Inheritance on the other hand comes with all the problems of introducing a monolithic class hierarchy. It seems great because there's no delegation code, but want to change something too far into development and... well... pppttttpppttfffff
In general I think the balance lies in the deciding where you want the scope of your project to lie. For a small one-off game like Cave Story (relatively speaking), going for straight inheritance can be reasonable because you want to be able to produce something relatively quickly without too much hassle. You can invest time into planning what you'll need and sticking to it, rather than building a whole framework.
However, if you want to build an engine that will be reusable, maybe even extensible, then the extra time spent futureproofing your code might be worth it to you.

Keep in mind that, in this sort of industry and the way technology and customer expectations can change so quickly, you may end up investing a lot of architecture in a product you'll discard after one release. Games aren't like building software for business processes, where something from the 80s can still live on and be maintained today.

Thanks for the quick answer btw. The reason I chose to post on CS forums is that in a general dev forum the best answer I could get is "it depends". This is already starting to look more promising.
no problem. CSTSF is the number one place to go for hastily written, one-sided posts.

And as well, if anyone disagrees with what I've written here, please call me out because I promise you I don't REALLY know what I'm doing. I've only been mucking around with this stuff for like 4 years and nobody ever really told me what to do so I just make it up as I go along.
 
Aug 12, 2014 at 1:19 AM
Senior Member
"Wahoo! Upgrade!"
Join Date: Aug 11, 2014
Location:
Posts: 57

The thing about the FSM explosion is so true. In that game I work with, one character can have hundreds of states and thousands of transitions. Thankfully, the transitions themselves are actually not a big deal because they don't actually do anything. One state simply declares that it can transition to another. They don't explicitly code states in C++, either. However, their system is very fighting game specific and assumes more or less the same behavior for all entities. Such is life in the data-driven approach.



So I think I initially misunderstood what you meant by the function pointer thing and what you said about the delegator pattern. Beforehand I was trying to delegate work out to different aspects of interaction such as physics, graphics, AI, ect, but that clearly doesn't work because sort of the point of a character is to bring all those aspects together.



If I'm understanding this correctly now, I think what is supposed to be done here is delegating states. This is like you were saying where a state could be "follow enemy while flying" and a specific class could be dedicated to just performing that kind of action. That would then make the definition of a character an FSM, where each state is a reference to one of these behavior modules. Then it would be a matter of developing each behavior algorithm in isolation (much better than all in a big clump) and making sure each works well. If you wouldn't mind, I'd like some feedback on this idea and anyone else reading is certainly welcome to chime in.



Lets take a small study of what I think is the simplest non-trivial case: the critters, specifically the big ones, I just call them "Bouncers".



We can map out what I think is their FSM structure, correct me if I'm wrong please.



p187001-0-dnfahe3.png


While it could be a lot worse for other classes, it seems like the state structure of most enemies stays around this complexity level. If anyone has taken time to map out these behaviors, I would love to see it.



What follows is a super-hand-wavy C++ pseudo-code type of thing that tries to get the basic code structure across. I don't try to get the actual code precise because reading a bunch of lines that say std::bind(std::ptr_fun(&Func), *this) doesn't really do anything to get the concept across
Code:
//hand-wavy algorithm parent
class Algo{
  virtual void Update() = 0;
};

//my hands are waving all over the place
class FlyTo : Algo;
class Sleep : Algo;
class Stare : Algo;
class Jump : Algo;


class Bouncer{
public:
  //state machine to provide dynamic behavior
  FiniteStateMachine fsm;
  //components used for intrisic behaviors (collider stores our position)
  Collider 	*col;
  Sprite   	*sprite;
  SoundEmitter	*sound;   
  //updated with the position of the player every frame
  Vec2 player;
  
  bool GetPlayerClose() const{
    return (col->pos - player).Length() < 10;
  }
  bool GetPlayerCloserOrHurt() const{
    return (col->pos - player).Length() < 5 || (GetHealth() != 100);
  }
  bool Always() const{
   return true; 
  }
  bool HitWallOrOverPlayer() const{
    return 	col->GetHittingWall() 
	  || 	abs(col->pos.x - player.x) < 2;
  }
  
  Bouncer(){
      //declare the states we can be in
      uint sleep = fsm.state(new Sleep(sprite));
      uint stare = fsm.state(new Stare(sprite));
      uint jump = fsm.state(new Jump(sprite, col));
      uint fly = fsm.state(new FlyTo(sprite, col, &player));
      uint slam = fsm.state(new Slam(sprite, col));
      //set up predicates to approve transitions
      fsm.trans(sleep, stare, &GetPlayerClose);
      fsm.trans(stare, jump,  &GetPlayerCloserOrHurs);
      fsm.trans(jump,  fly, &Always);
      fsm.trans(fly, slam,  &HitWallOrOverPlayer);
      fsm.trans(slam, stare,  &Always);
      //NOTE: im excluding binding "this" to the functions for readability
  }
  //update the state machine, get the current state and run it
  void Update(){
    Algo *currstate = fsm.Update();
    currstate->Update();
  }
};
The idea is that each algorithm has a goal behavior that it wants to implement and requires a set of tools to achieve it. The bouncer itself holds the tools and data and simply lends these tools to each behavior to prevent data redundancy. A behavior state runs until one of it's predicates for a potential transition returns true, and then the fsm transitions to the connected state.



Obviously, I'll need to see how this plays out while eating a cold, stale reality sandwich, but what are your initial thoughts on this?


 
Aug 12, 2014 at 1:34 AM
The Preacher
"Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-BLEIUP"
Join Date: Feb 20, 2011
Location: lost in translation
Posts: 336
Age: 31
Fluffball said:
in a general dev forum the best answer I could get is "it depends".
Noxid said:
It generally depends how it's written;
hahahaha

Okay I'm gonna try and answer this because it's the first interesting thread I've seen in a while, suck it No Shitposting Game

I haven't been working on Cave Story nearly as much as Noxid, so I'll take what he says about it for granted. Pixel seems to have a pretty unusual way to do things.
Also, I'm gonna assume we are working with statically-typed object-oriented languages (such as Java and C#) because most of these problems don't appear in other paradigms. If the language/paradigm isn't a requirement, then downright switching to another one is a viable option.

Fluffball said:
I suffer from the "god class" problem where there invariably ends up being a class like "MyEnemyC" that just ends up responsible for everything except a few small details.
Are you describing an abstract superclass "MyEnemyC" which all enemy classes extend? If so, then it isn't a god class, it's just normal inheritance. If not, then I guess that is a problem yeah

Fluffball said:
I try to delegate out the work as much as I can, but unlike programming "normal" systems, the helper objects end up requesting so much information from the main class that not only does it break encapsulation, but it gets prone to confusing bugs.
I would like some examples of what you're describing. The point with inheritance is that subclasses possess the attributes and methods of their parent class on top of their own as if everything was coded into the same class (except it's far from always being the case, especially when generics come into play because it does weird things, but that's not really the point), so there shouldn't be any problems with encapsulation.
If you're using composition(/aggregation?) in order to bypass the limitations of simple inheritance, then it might be wise (if you aren't doing that already) to make the reference mutual (or, better, to make the dependency circular with a third object that serves as a link between the two, kinda like this) in order to make sure the composition acts as an "inheritance" in the original sense of the term: "an inclusion of features from one class to another".

Fluffball said:
Do you have any theoretical insights as to why this might be if you experience the same thing? I've been trying to wrap my head around this question of "what is so hard about this?" and I just cant seem to come up with a solid answer of why its different than any other code.
Without examples, it is hard to answer, as a *lot* of different theoretical situations could lead to complex code structures. My advice would be to force yourself to think of your problem in a different way; to reformulate it, not at the implementation level ("how can I code this"), but at the design level ("what am I doing, why am I coding this, what is 'this' in the first place").
For example, imagine someone who goes in a store and asks to buy an iPhone. If you think at implementation level ("how"), you're gonna sell him an iPhone for a lot of money and that'll be the end of it. But if you think at design level ("why"), then you might figure out that he wants to buy a handheld device that does calculations and someone told him to get an iPhone. So you'll sell him a little calculator instead and everyone will be happy. Except your boss because you could have made a good affair and you chose to sell him a cheap thing instead shit this wasn't the best example after all forget it

Fluffball said:
It's been a tough job to try and balance aggregation and inheritance. Aggregation, imo, is usually the best software engineering practice for most things,
I don't see how

Fluffball said:
but it creates a lot of overhead code dedicated to delegating out the work.
That's partly why it's not

Fluffball said:
Inheritance on the other hand comes with all the problems of introducing a monolithic class hierarchy. It seems great because there's no delegation code, but want to change something too far into development and... well... pppttttpppttfffff
You just stumbled upon one of the reasons why Java- and C#-like languages are bad.
Although usually, ways to factorize the code are made to prevent one from having to redo everything everytime there's a change to make (even though, again, this is technically far from always being the case) so I dunno what your actual problem is.
 
Aug 12, 2014 at 2:01 AM
Senior Member
"Wahoo! Upgrade!"
Join Date: Aug 11, 2014
Location:
Posts: 57
Hiino said:
Also, I'm gonna assume we are working with statically-typed object-oriented languages (such as Java and C#) because most of these problems don't appear in other paradigms.
I work with C++ because I'm doing a great deal of computational heavy lifting and need very low level access to DirectX and (evnentually) openGL. On top of the C++ engine is a script system written in Lua. Sadly, that has not helped because I have not found this issue to be affected by how a language is typed at all. The only thing language typing has reduced for me is the need to use template tricks and fuctors in programming, which I have no problem with.

Besides, programming characters in a dynamic language can introduce pretty large speed problems. For some games it wont matter. From stress tests on mine, it most certainly will. Scripts are great for configuration, but they can really drain the CPU fast if used for updating.

Hiino said:
Are you describing an abstract superclass "MyEnemyC" which all enemy classes extend? If so, then it isn't a god class, it's just normal inheritance. If not, then I guess that is a problem yeah
I was just using that for a generic enemy name. By god class I just mean a class that tries to do far, far too much by itself.

Hiino said:
I would like some examples of what you're describing. The point with inheritance is that subclasses possess the attributes and methods of their parent class on top of their own as if everything was coded into the same class (except it's far from always being the case, especially when generics come into play because it does weird things, but that's not really the point), so there shouldn't be any problems with encapsulation.
Inheritance is usually the "obvious" choice early in the project, because of the reasons you mention. Indeed it seems like a great deal. The problems tend to hit later when you want subclasses that break constraints their parents have, or when you want to combine the attributes of two classes on different branches (which has happened a lot for me). There's also issues like bubble-up effectthat make more and more god classes which can unexpectedly break classes which inherit from them. There's also the yo-yo effect which makes me nauseated fast. Most any software engineering book I've ever opened speculates that you need a good amount of justification for using inheritance, and they are right. I've experienced how fast a project can fall apart if their warnings are not heeded.

Hiino said:
If you're using composition(/aggregation?) in order to bypass the limitations of simple inheritance, then it might be wise (if you aren't doing that already) to make the reference mutual (or, better, to make the dependency circular with a third object that serves as a link between the two, kinda like this) in order to make sure the composition acts as an "inheritance" in the original sense of the term: "an inclusion of features from one class to another".
Circular dependence can be very problematic because it severely decreases code reuse and makes both classes more fragile to change. You generally want classes to be as unidirectional in their relationships as possible. Doing this simple practice has eliminated most bugs for me (I would guestimate around %80). That being, I found most of my bugs arose from integration of system parts and more complicated relationships meant more opportunity for error.

Hiino said:
Without examples, it is hard to answer, as a *lot* of different theoretical situations could lead to complex code structures. My advice would be to force yourself to think of your problem in a different way; to reformulate it, not at the implementation level ("how can I code this"), but at the design level ("what am I doing, why am I coding this, what is 'this' in the first place").
That's what I'm currently doing. A mix of both, really.

Hiino said:
You just stumbled upon one of the reasons why Java- and C#-like languages are bad.
I don't see how inheritance (or inheritance-like pattern) problems are unique to those languages. As opposed to what? Non-OOP?

Also, if problems with inheritance are hit on the large scale (sometimes they aren't, but I haven't ever witnessed that), yes, you can certainly re-factor and there's no need to re-derive your old algorithms in a mathematical sense. However, when your inheritance tree gets to be 300,000 lines of code, that's still a pretty big chunk of time lost.
 
Aug 12, 2014 at 2:33 AM
The Preacher
"Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-BLEIUP"
Join Date: Feb 20, 2011
Location: lost in translation
Posts: 336
Age: 31
Fluffball said:
This is like you were saying where a state could be "follow enemy while flying" and a specific class could be dedicated to just performing that kind of action. That would then make the definition of a character an FSM, where each state is a reference to one of these behavior modules.
That's basically how I would go:
- first, implement a set of predefined behaviours, that take a character (and possibly some additional variables) and apply a move to it.
- then, implement a set of general-purpose triggers, that use a character's perception of its surroundings to check for something (like "is the protagonist less than 140 pixels away from me?") and return a boolean.
- implement a set of meta-behaviours, that are structures composed of the first-level behaviours and triggers previously implemented; for example, if you have a behaviour A, a behaviour B and a trigger Z, then one meta-behaviour could be "A until Z, then B".
- you can also make meta-behaviours that use other meta-behaviours, obviously, why not
- finally, implement characters which possess a starting meta-behaviour, and possibly other custom-made behaviours and triggers, but only if they are the only characters that are going to use them for actual "physical" (in terms of the ingame physics, not the game physics, I'm not sure how to say it) reasons. For example, if a behaviour is "launch missiles" and this character is the only one who has missiles, then it's not a good idea to add the behaviour as custom available only to the character because what if you add another character that can launch missiles? However, if the behaviour is "launch Mister Cat missiles" and you have a character that's called Mister Cat and has missiles and you want to make sure that he's the only one who can do that and that no other character will ever have Mister Cat missiles, THEN you can add it to your character. You can think of it as "if someone mods my game, should they be allowed to create a character that uses this behaviour?" maybe, I dunno if that'd help.
- you can also, obviously, implement perception-based functions, like "how far is the protagonist?" instead of "is the protagonist farther away than X pixels?"

Fluffball said:
This is a cool graph, although iirc, they can go back from staring to sleeping if you go too far.

This, expressed in the previous terms of behaviours/triggers, could be implemented this way:

Triggers:
TPNr(X) - Protagonist is within X pixels
TSec(X) - X milliseconds have passed

Behaviours:
BSlp - Sleep
BStr - Stare
BJmp - Jump
BFly - Fly
BSlm - Slam

MSlp - BSlp until TPNr(80), then MWkp
MWkp - BStr until [TPnr(50), then MAct] or [!TPNr(80), then MSlp]
MAct - BJmp, then BFly until TSec(3000), then BSlm, then MWkp

And for the critter:
Starting behaviour: MSlp

(keep in mind that i have no idea of the actual values for the flying time or the distance at which critters act, they are random numbers)

You could also change it slightly like this:
Behaviours:
MSlp(X) - BSlp until TPNr(X), then MWkp

Critter:
Starting behaviour: MSlp(80)

Or like this:
Perceptions:
PDir: returns the direction in which the protagonist is
PTime: returns current time

BChk:
Behaviours:
BFly(X) - Fly in the direction X.
MFlySlm(X, Y, Z=Y) - BFly(X) until [(PDir != X), then MFlySlm(PDir, Y, Ptime)] or [(Z - Y >= 3000), then BSlm]
MAct - BJmp, then MFlySlm(PDir, PTime), then MWkp

You're free to do as you please. And it's not very hard to edit. I'll try and do a basic implementation of that later.

As for your code, it's too low-level for me to read at 3:31 am so I'll come back to it tomorrow maybe, but I guess the general idea of what I just described is there. You just gotta generalize all those functionalities a bit.
 
Aug 12, 2014 at 2:39 AM
Senior Member
"Wahoo! Upgrade!"
Join Date: Aug 11, 2014
Location:
Posts: 57
I like that notion you're using. What's that called? It would have a pretty straightforward implementation into a system that used coroutines.

Also thanks for the correction with them going back to sleep. I'll keep that in mind.
 
Aug 12, 2014 at 3:09 AM
The Preacher
"Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-BLEIUP"
Join Date: Feb 20, 2011
Location: lost in translation
Posts: 336
Age: 31
Fluffball said:
I work with C++ because I'm doing a great deal of computational heavy lifting and need very low level access to DirectX and (evnentually) openGL. On top of the C++ engine is a script system written in Lua. Sadly, that has not helped because I have not found this issue to be affected by how a language is typed at all. The only thing language typing has reduced for me is the need to use template tricks and fuctors in programming, which I have no problem with.
Well, your problem doesn't actually come from typing in your case, but from low-levelness. I hardly have ever done any C++, but I'm pretty sure it doesn't handle higher-level structures such as Ocaml modules, Scala traits or Ruby mixins. You might be lacking some tools to make your work easier.

Moreover, the real, humongous advantage dynamic typing has over static typing for OOP is meta-programming. Static typing for the OO paradigm is absolutely not a good idea because the only thing that could ease up the stupid complexity of OOP is meta-programming, and static typing basically prevents you from doing any of that in an easy and efficient way.

Fluffball said:
Besides, programming characters in a dynamic language can introduce pretty large speed problems. For some games it wont matter. From stress tests on mine, it most certainly will. Scripts are great for configuration, but they can really drain the CPU fast if used for updating.
Well that's true, but also kind of cheating, since you are using C++. Other statically-typed languages are slower than that, I'm pretty sure they're closer to dynamically-typed languages than to C++ in terms of speed.

Fluffball said:
I was just using that for a generic enemy name. By god class I just mean a class that tries to do far, far too much by itself.
Oh. Well yeah that's bad I guess

Fluffball said:
Inheritance is usually the "obvious" choice early in the project, because of the reasons you mention. Indeed it seems like a great deal. The problems tend to hit later when you want subclasses that break constraints their parents have, or when you want to combine the attributes of two classes on different branches (which has happened a lot for me). There's also issues like bubble-up effectthat make more and more god classes which can unexpectedly break classes which inherit from them. There's also the yo-yo effect which makes me nauseated fast. Most any software engineering book I've ever opened speculates that you need a good amount of justification for using inheritance, and they are right. I've experienced how fast a project can fall apart if their warnings are not heeded.
That's why I dislike inheritance yeah. Composition is the way to go.

Fluffball said:
Circular dependence can be very problematic because it severely decreases code reuse and makes both classes more fragile to change. You generally want classes to be as unidirectional in their relationships as possible. Doing this simple practice has eliminated most bugs for me (I would guestimate around %80). That being, I found most of my bugs arose from integration of system parts and more complicated relationships meant more opportunity for error.
"Circular" isn't the word I should have used. If you read the article I linked you will see that there is no circling, just two classes A and B that both use a class C, and B uses A.

Fluffball said:
I don't see how inheritance (or inheritance-like pattern) problems are unique to those languages. As opposed to what? Non-OOP?
Firstly, as I said earlier in this message, as opposed to other OOP solutions such as Ruby, that possess a good deal of other solutions to replace inheritance and interfaces, and especially the limitations of single inheritance.
Secondly, yes, as opposed to non-OOP (like the functional paradigm).

Fluffball said:
Also, if problems with inheritance are hit on the large scale (sometimes they aren't, but I haven't ever witnessed that), yes, you can certainly re-factor and there's no need to re-derive your old algorithms in a mathematical sense. However, when your inheritance tree gets to be 300,000 lines of code, that's still a pretty big chunk of time lost.
In that case, the problem comes from the fact that the project went into a bad direction right from the start. So yeah, oops I guess? Obviously I won't ask you to redo everything from scratch, but it has to be understood that any solution that doesn't fundamentally alter the structure of the program is going to be kludgy.
Fluffball said:
I like that notion you're using. What's that called? It would have a pretty straightforward implementation into a system that used coroutines.
I don't know if it has a name? I guess it's just like a regular FSM state/event table.
 
Aug 12, 2014 at 4:15 AM
Senior Member
"Wahoo! Upgrade!"
Join Date: Aug 11, 2014
Location:
Posts: 57
I'm gonna try to type this on my phone, please excuse horrific typos.

I think you may have misunderstood my intent. I don't need to redo anything yet. I'm doing some investigative work before diving in to prevent getting myself into trouble.

While c++ is a superset of c, c++ comes with a ton of tools that effectivly make it a high level language. The lastest versions even implement basic forms of garbage collection via smart pointers. C++ does have metaprogramming, and it can be used to make algorithms and classes, not dynamically typed, but type agnostic. What ive found trading off between lua and c++ is that lua is a wonderful tool for data processing, file I/o, and rapid prototyping due to being able to modify code while the game is running. However, when I'm working with pure logic on a single actor, as unintuitive as it sounds, it usually takes about half the code to implement things in c++, and I think that's mainly because of the STL.

Imo, if stl and templates did not exist, I would be right there with you that c++ would be an awful language choice.

Also, it seems ive been using the wrong word. I did mean to say composition, not aggregation. Sorry about that, I get those terms mixed up constantly. Though aggeragation can be really great when an engine is based around subsystems, especially in multithreaded environments where cores can have affinity to object types.
 
Aug 12, 2014 at 10:46 AM
The Preacher
"Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-BLEIUP"
Join Date: Feb 20, 2011
Location: lost in translation
Posts: 336
Age: 31
Fluffball said:
I think you may have misunderstood my intent. I don't need to redo anything yet. I'm doing some investigative work before diving in to prevent getting myself into trouble.
I know, I was just answering the theoretical case you mentioned earlier, "Also, if problems with inheritance are hit on the large scale (sometimes they aren't, but I haven't ever witnessed that), yes, you can certainly re-factor and there's no need to re-derive your old algorithms in a mathematical sense. However, when your inheritance tree gets to be 300,000 lines of code, that's still a pretty big chunk of time lost."

Fluffball said:
The lastest versions even implement basic forms of garbage collection via smart pointers.
If a language's garbage collector is still in a state that could be qualified as "basic", it doesn't sound very much like a high-level language...

Fluffball said:
C++ does have metaprogramming,
Yeah, like Java and C#. I didn't say there wasn't any, just that it was horrendous to use.

Fluffball said:
and it can be used to make algorithms and classes, not dynamically typed, but type agnostic.
This is like the basics of polymorphism though, I mean even C can do that to some extent, thanks to the preprocessor notably. It doesn't make C++ as high-level as other modern languages.

Fluffball said:
Imo, if stl and templates did not exist, I would be right there with you that c++ would be an awful language choice.
Well C++ is still an awful language choice tbh but I'm not gonna go there

Fluffball said:
Also, it seems ive been using the wrong word. I did mean to say composition, not aggregation. Sorry about that, I get those terms mixed up constantly. Though aggeragation can be really great when an engine is based around subsystems, especially in multithreaded environments where cores can have affinity to object types.
Heh it's k, maybe as a mnemonic you can think of the fact that "aggregation" implies the idea of an already existing X clinging to a Y that also already exists (Y takes a X), while "composition" makes it sound like the X comes from the Y and thus didn't exist beforehand (Y makes a X).
 
Aug 12, 2014 at 1:52 PM
In my body, in my head
Forum Moderator
"Life begins and ends with Nu."
Join Date: Aug 28, 2009
Location: The Purple Zone
Posts: 5998
I think we're getting a bit sidetracked in discussing the tools rather than the problems we gotta solve with em

the behaviour system outlined earlier looks like a good start and I'll provide a better post once I've had time to digest it, I just arrived at work so naturally I need my morning cat-nap before I can get rolling
 
Aug 12, 2014 at 4:58 PM
Senior Member
"Wahoo! Upgrade!"
Join Date: Aug 11, 2014
Location:
Posts: 57
Right, I'm pretty sure Hiino and I have now hit the magical land of opinions and need to agree to disagree. I guess the conversation was somewhat relevant because the suggestion seemed to be that the problem was a result of language use, and I'm pretty certain that's not the case since all the same problems seem to pop up in all paradigms I've tried.

I will say that one thing I have found dynamically typed languages wonderful for is abstracting other actors to precepts that then get fed into C++ code. That indeed does solve a huge problem, but not really the one I'm asking about.
 
Aug 12, 2014 at 5:07 PM
In my body, in my head
Forum Moderator
"Life begins and ends with Nu."
Join Date: Aug 28, 2009
Location: The Purple Zone
Posts: 5998
Alright, so I think this approach is going in a good direction. I guess I don't really have too much to add onto the idea of composing actors by linking behaviours together, but something that is nagging at the back of my mind is how you link an animation system into this. Animation states are pretty closely related to behaviour states - show the flying frames while it's flying, close the eyes when it's sleeping - but the timings could vary from character to character for instance.

So, would the animation have its own state implementation too, where each animation is like a behaviour? Where is the right place to say "go from doing this animation to this one"?
 
Aug 12, 2014 at 6:21 PM
Senior Member
"Wahoo! Upgrade!"
Join Date: Aug 11, 2014
Location:
Posts: 57

Well, I' currently working on a more complete demonstration to show that might address that, but you are right, it does an awful lot of hand-waving over how animations link to sounds and states. I am still struggling with the problem of making a scalable, stable system that links animation frames to soundplaying and events that doesn't break encapsulation or result in code-bloat.

I'll hopefully have this next iteration typed out soon, and if it works ok, that might be the next issue to think about.

Ok, very, very large wall of text inbound.



I tried to get much closer to an actual C++ implementation this time, though its not totally accurate and would not compile quite yet. There are not too many gaps to fill in, however.



The core idea, as mentioned before is that state behaviors can be shared between potentially many different enemies, and the enemy class just needs to choose what parameters to set and what data to provide. For this implementation, i left out parameters for now just to make the code simpler to read, but i don't think it takes much imagination to see how they could be abstracted to use more settings and different constants.



A few notes on this:


-- I'm assuming a number of utility data structures that are not any different
from what you'd expect from standard implementation. If you think it does
something, it probably does it.

-- I would not use raw pointers in a real implementation, something like
wrapped, self initializing references would be much safer

-- I don't like the way slam works. It's code runs on the rather strong
assumption that we are waiting to hit a wall. I know that's...
technically desired... but something just feels wrong about it.

-- I don't like how timeInAir is linked into jump and fly. That variable
refers only to predicate operation and should be handled exclusively
by the class itself. It might be worth it to call do kind of
pre/post call system where we make initializing calls to the bouncer
class itself to reset variables like that

-- There is probably a much better way to group components than I am doing.
Passing in each data reference individually will grow to be quite a
pain and hard to read.



State Algorithm Code:
Code:
class Algo{
public:
  //pretty much all algorithms on all enemies require a sprite
  Sprite* sprite;
  
  Algo(Sprite* s):sprite(s){}
  
  virtual void Init() {};
  virtual void Update() = 0;
  virtual void End() {}
  
  //set the sprites direction based on sign of x
  void SetDirection(float x){
   if (x > 0){
    sprite->SetHorizontalFlip(false);
   }else if (x < 0){
    sprite->SetHorizontalFlip(true); 
   }
  }
  
  //returns -1 if left, returns 1 if right
  float GetDirection () const{
    return sprite->GetHorizontalFlip() ? -1.0f : 1.0f;
  }
  
};


class BounceAlgo : public Algo{
public:
  //not all bouncer algorithms need a collider, but enough do to justify this
  Collider *col;
  
  BounceAlgo(Sprite* s, Collider *c):Algo(s), col(c){}
  
};

//Note: Assume SetClip works be automatically caching and seeing
//files by name and "automagically" figures out how to  load the 
//clip and animate it. The actual structure operates much like this.

class FlySeekPlayer : public BounceAlgo{
public:
  SoundEmitter *sound;
  float *timeInAir;
  Vec2	   *target;

  FlySeekPlayer(Sprite* s, Collider *c, SoundEmitter *snd, Vec2 *t, float *tia):
    BounceAlgo(s, c), 
    sound(snd),
    timeInAir(tia),
    target(t)
  {}
  void Init(){
    sprite->SetClip("fly.png");
  }
  void Update() {
    //loop the flying sound over and over while in this state
    sound->Loop("fly.wav");
    //increase the time we have been in the air (assume fixed time step)
    *timeInAir += 1.0f/60.0f;
    //<waves arms around>     ~~~o_o~~~
    /*Magical code that makes us hover towards player in that
    /*sine pattern*/
  }
};

class Sleep : public BounceAlgo{
public:
  //algorithm only needs a sprite
  Sleep(Sprite* s):BounceAlgo(s, NULL){}

  void Init(){
    //set the bouncer to randomly face left or right
    SetDirection(Math::UnitRandom()-0.5);
    sprite->SetClip("sleep.png");
  }
  
  void Update() {}
};

class Stare : public BounceAlgo{
public:
  //pointer to the positon of the current target (usually the player)
  Vec2	   *target;
  
  Stare(Sprite* s, Collider *c, Vec2 *t):BounceAlgo(s, c), target(t){}
  
  // staaaaaarrrreeeeee 0_0
  void Init(){
    sprite->SetClip("stare.png");
  }
  
  //set it so the bouncer is always looking at the target
  void Update() {
    SetDirection(target->x - col->pos.x);
  }
};

class Slam : public BounceAlgo{
  SoundEmitter *sound;
  float *timeInAir;

  Slam(Sprite* s, Collider *c, SoundEmitter *snd, float *tia):
    BounceAlgo(s, c), 
    sound(snd),
    timeInAir(tia)
  {}
  
  //Set the initial velocity so we are jumping up and towards 
  //the previous facing direction
  void Init(){
    //we are fine to keep our previous velocity
    sprite->SetClip("slam.png");
  }
  //let the physics component move itself with respect to gravity,
  //velocity and acceleration
  void Update() {
    col->Update();
  }
  //at the end of the state when the ground is hit, we do a camera shake effect
  void End(){
    sound->Play("slamjam.wav");
    global->camera->Shake(5);
    *timeInAir = 0;
  }
};

class Jump : public BounceAlgo{
  SoundEmitter *sound;
  Jump(Sprite* s, Collider *c, SoundEmitter *snd):BounceAlgo(s, c), sound(snd){}
  
  //Set the initial velocity so we are jumping up and towards 
  //the previous facing direction
  void Init(){
    col->SetVelocity(Vec2(GetDirection() * 5, 25));
    sprite->SetClip("jump.png");
    sound->Play("boing.wav")
  }
  //let the physics component move itself with respect to gravity,
  //velocity and acceleration
  void Update() {
    col->Update();
  }
};
And here's the code that runs the state updates and transitions:
Code:
typedef unsigned int uint;

//Assume definition of Pred is a standalone functor that we can call without parameters and inquires about some state within the current object

template <class Pred>
class FiniteStateMachine{
private:  
  //graph data structure to manage nodes and edges
  GraphC<Algo*, Pred> g;
  //current state of our entity
  uint currState;

  //each node holds a refernece to an algorithm in its custom data pack,
  //this function gets that reference to the current state
  Algo *GetCurrentAlgorithm(){
    return g.GetNode(currState).GetData();
  }
  
  //set the current state node
  void SetState(uint state1){
    assert(g.HasNode(state1));
    currState = state1;
  }
  
public:
  //create a new state and assign a unique state id to it
  uint state(Algo *a){
    uint id = g.GetNumNodes();
    g.AddNode(id, a)
    return id;
  }
  
  //create a directed transiton from one state to another 
    //Note: underlying graph structure will throw an error if
    //state1 or state2 do not exist, or if state1 == state2 
    //(no loop constraint)
  void trans(uint state1, uint state2, Pred p){
    g.AddEdge(state1, state2, p);
  }
  
  //called once at the beginning of usage to initialize the first state
  void Start(uint state1){
    SetState(state1);
    GetCurrentAlgorithm()->Init();
  }
  
  //Note: edge data is kept in a hash map, 
  //so the iterator type is std::unordered_map<uint, Pred>::iterator,
  //where the first element is the id of the node to be transioned to
  
  //Note: we also assume that an actor cannot transition between more
  //than one state per frame
  
  //perform automatic transitons and return the current state for use
  void Update(){
    //Get the current state node
    auto &n = g.GetNode(currState);
    //for each potential transition, eval whether we should transition over
    for (auto e = n.edgeBegin(); e != n.edgeEnd(); ++e){
      //if the predicate for this edge returns true
      if (e->second() == true){
	//end the old algorithm
	GetCurrentAlgorithm()->End();
	//then we need to set the transition as the current state
	SetState(e->first);
	//initialize the new algorithm
	GetCurrentAlgorithm()->Init();
	//do not try to transiton to anything else
	break;
      }
    }
    //Now we can update our current state
    GetCurrentAlgorithm()->Update();
  }
  
  //Proof of state validity by induction (for me to double-check my work):
    //Base: At time 0 we start at a valid state due to the assertion on 
    //SetState(id). This case clearly holds.
    //
    //Inductive: At time n, assume we are in a valid state. We can either
    //transiton to a new state or not. If not, then at time n+1, we are 
    //clearly still in a valid state.
    //
    //If we do transition, the edge we take is certain to lead to another
    //valid node since the underlying graph does not allow linking to non-
    //existant nodes. Therefore at time n+1, we are still in a valid state.
  
};

 
class Bouncer{
public:
  //state machine to provide dynamic behavior
    //Note: the definiton of Pred is a functor bound to an instance
    //of Bouncer, I dont want to resolve the definition here
  FiniteStateMachine<Pred> fsm;
  
  //components used for intrisic behaviors (collider stores our position)
  Collider 	*col;
  Sprite   	*sprite;
  SoundEmitter	*sound;   
  //updated with the position of the player every frame
  Vec2 player;
  //the time we have been flying, in seconds
  float timeInAir;
  
  bool GetPlayerClose() const{
    return (col->pos - player).Length() < 10;
  }
  bool GetPlayerCloserOrHurts() const{
    return (col->pos - player).Length() < 5 || (GetHealth() != 100);
  }
  bool Always() const{
   return true; 
  }
  
  //if we hit a wall, OR are close to the player, 
  //OR we have reached the fly time limit...
  bool HitWallOrOverPlayer() const{
    return 	col->GetHittingWall() 
	  || 	abs(col->pos.x - player.x) < 2
	  ||	timeInAir >= 4;
  }
  
  bool GetOnGround() const{
    return col->GetOnGround();
  }
  
  Bouncer():timeInAir(0)
  {
      //declare the states we can be in
      uint sleep = fsm.state(new Sleep(sprite));
      uint stare = fsm.state(new Stare(sprite, col, &player));
      uint jump = fsm.state(new Jump(sprite, col, sound));
      uint fly = fsm.state(new FlyTo(sprite, col, sound, &player, &timeInAir));
      uint slam = fsm.state(new Slam(sprite, col, &timeInAir));
      //set up predicates to approve transitions, binding to the current object
      fsm.trans(sleep, stare, bind(ptr_fun(&GetPlayerClose), this));
      fsm.trans(stare, jump,  bind(ptr_fun(&GetPlayerCloserOrHurts), this));
      fsm.trans(jump,  fly, bind(ptr_fun(&Always), this));
      fsm.trans(fly, slam,  bind(ptr_fun(&HitWallOrOverPlayer), this));
      fsm.trans(slam, stare,  bind(ptr_fun(&GetOnGround), this));
      //set the starting state to sleep
      fsm.Start(sleep);
  }
  
  //update the state machine, get the current state and run it
  void Update(const Vec2 &_player){
    //update the current state of the player which also 
    //updates all algorithms that are reading from it
    player = _player;
    //Update the state of the bouncer
    fsm.Update();
  }
};
I feel like this is getting closer to a decent solution, but it's not quite there yet. I feel like there needs to be a cleaner way to pass and manage data to the algorithms rather than passing raw components and variable addresses. I would say the obvious choice is some sort of interface, but I could easily imagine that you would need about one interface per algorithm, which would double the size of the code and add so much clutter.



I also an not keen on the idea that the code to evaluate when a state is done is *outside* of the state itself. I get that that's kind of the point, but something just feels... really icky about doing that and I feel like it could create some very confusing situations.



Thoughts on this so far? I'll try to be thinking of ways to make it cleaner and more abstract.



EDIT: One aspect that still escapes me is the implementation of the critter movement in the air, which is why I kind of just fudged it. Do you think the critter code could be decompiled and we could get a look at the algorithm for that?
 
Aug 12, 2014 at 6:23 PM
The Preacher
"Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-BLEIUP"
Join Date: Feb 20, 2011
Location: lost in translation
Posts: 336
Age: 31
Here's how I manage animation:
I have two threads, the former calculating states and the latter displaying graphics.
A state object is shared by the two; modified by the first thread and read by the second one.
An animation has a starting time, a list of frames, and a framerate.
Characters associate an animation to each state they can have.
Then, for every character, the graphics thread checks their state, then fetches the corresponding animation, and displays the current frame (known with (currentTime - startingTime) % framerate).
 
Aug 12, 2014 at 6:23 PM
Senior Member
"Wahoo! Upgrade!"
Join Date: Aug 11, 2014
Location:
Posts: 57
Wait what? How did I just edit my last post instead of posting a new one... very strange....
 
Aug 12, 2014 at 6:24 PM
The Preacher
"Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-Wacka-BLEIUP"
Join Date: Feb 20, 2011
Location: lost in translation
Posts: 336
Age: 31
This is because the forum system prevents double-posting by automatically merging the new post inside of the previous one.
 
Aug 12, 2014 at 6:28 PM
Senior Member
"Wahoo! Upgrade!"
Join Date: Aug 11, 2014
Location:
Posts: 57
Hiino said:
Here's how I manage animation:
I have two threads, the former calculating states and the latter displaying graphics.
A state object is shared by the two; modified by the first thread and read by the second one.
An animation has a starting time, a list of frames, and a framerate.
Characters associate an animation to each state they can have.
Then, for every character, the graphics thread checks their state, then fetches the corresponding animation, and displays the current frame (known with (currentTime - startingTime) % framerate).
By thread, do you mean a coroutine or actual preemptive thread? Preemptive seems a a bit overkill in that situation imo, but if you can get the system to work fine, more power to you I guess.

Your solution is pretty much what im doing as well, but the problem goes deeper than that for me. I need to tie sound, logic, hitboxes, callbacks, physics events and AI to specific frames of animation, and sometimes the same animation can be used for multiple, subtly different states. This is nor really something I'm inquiring about yet though because I think the solution would probably greatly depend on engine architecture.

EDIT: Ah, I see. Just making sure I wasn't gong crazy
 
Top