Thursday, August 2, 2012

Day 45 - ECS & Behavior trees

Entity Component System - (continued)
After various attempts, careful considerations and long meditations under an authentic ancient japanese sakura from the naruto period... I decided to roll my own lolECS.

It does what I need, which is nice, though it is not internally as optimized as Artemis.

- Uses Universaly Unique Identifiers which auto-instantly solves the id problem mentionned in the previous post : it allows insertion of foreign entities without ids collision headaches.

- Uses a messaging system to communicate : strong decoupling - systems don't have to know each others, they just send and listen to messages they are interested in.

- Systems are abstract and treated like services you can plug concrete systems in a static/singleton class GameSystems : very easy to implement client and server - they have different implentations of the same set of systems. (eg: a client would not have the same physics system implementation than the server).

- Commands are special kind of messages  : they are actions that need to be executed in the game world - this will prove very useful for debugging, console commands, scripting (if need to) and more importanly networking (the server will send mostly commands to clients).

I could throw some UML diagram but the structure is pretty much like the in the previous episode.
The only thing interesting is the specialized Postman system which handles messaging and subscribing for other systems.

RS2 ECS in practice
I create entities with the EntityManager, then build them via an EntityFactory which is a registry of EntityBuilders. For instance the crate builder knows what component to add and how to set them up to make an entity that behaves and look like a crate. I prefer the factory approach to prototypes/clones/templates as you can more easily add variations or conditional building (eg: not all crates may look or weight the same). The concrete builders are specific to RS2, but the Factory, ECS and most components and systems are part of my engine which I hope to re-use for other awesome games.

In code, creating, building, spawning and shooting a crate from the camera look like this:

CrateBuilder : building crates since overused meme date.

Would someone please insert an original caption here? No caption no fun.

Note the use of command messages to spawn and shoot the entity.
And the result when I shoot a bunch of crates at a wall:

"Advanced Crate Shooting" game or "Blocky Zombies" game? Make up your mind damn it!

Note that the crates are savagely stacked, as we now have real ultimate physics(*) thanks to jbullet. It will be fun to collapse a bunch of crates on unsuspecting npcs :p
There is negligible fps loss when the crates are at rest, but a noticeable drop in fps when a lot of crates are moving and colliding. We'll see how it runs in a real game situation.

 If you don't know what BTs are you can find some articles there.
They are often presented like more advanced or specialized HTN/HFSMs, but to me they remind me a lot of LISP program trees. Which leads neatly to the idea of using genetic programming to evolve AIs. Surely someone will or has already catch on that!?

Anyway for RS2 AI I'm considering using behavior trees. So I designed and implemented a Behavior Tree package for my engine.

Behavior Tree. UML you see. Haiku captionee.

(Diagram made with DIA)
The only things of note are :
  1. the use of a generic IBtContext which :
    1. allows one instance of a behavior tree to be shared for many usages (similar to a flyweight pattern).
    2. allows to narrow the context for concrete uses.
  2.  a clear separation of Terminals (leafs) vs Composites (inner nodes) and Conditions (predicates) vs Actions.
A deeper hieararchy than really needed but its much cleaner and should make stuff like a visual editor or scripting more easy to do.

Since I implemented a generic BT package, I can use it for other purposes. For instance I could use BTs for scripting some entities (doors, levers, whatnot). This would fit nicely into a CpBehaviorTree Component :D

(*) which as you may know is functionaly equivalent to Real Ultimate Power but applied to games. Man, this gets me so pumped!

Day 47 update and exercise for the reader: There are two big flaws in this BT design, which I have now fixed. They would produce incorrect behavior at runtime. Can you spot them? Hint: context.

End of post.

Friday, July 20, 2012

Day 32 - Serious Problems, Serious Design

WARNING: complicated stuff ahead not properly explained but with pictures ok not really picture but diagrams and they are complicated too for non programmes sorry lol did you read this or not trololo :-)

Alright I got that primitive prototype with some stuff going using a simple lolphysics.
But my lolphysics won't be able to do what I want it to do.
I want players to be able to stack random objects to form makeshift barricades, Zombies to smash said barricades, throwing crates at bikers from the rooftop to smash their heads by proxy and all that jazz. And possibly chopping zombies arms and heads off.
So no lolphysics. Sorry, I liked you, but you're not good enough. (acutally I'm not good enough to make it good enough eh)
So I'll use jbullet which by pure random luck conveniently comes wrapped in jme3. Omagad. It works fine I can very easily make crates stack and bounce around and its of course much faster than my lolphysics while doing more things.
Hey, didn't I also wanted multiplayer? Lol.
Time for some serious design. I coded relative crap fast to get things going and test if jme3 was suited for procedurally generated maps and if I could code threaded chunks and collisions in a box world, now onto more serious stuff.

Game Design : Serious Business

Example Standard OOP Design : game types ~ classes

This is more or less what I currently have.
And it won't work.
Or should I say it will work but will quickly become messy not doubt about that. I could insert more data-driven behavior like I did in RS1 to flaten the hierarchy and allow a bit more flexibility, but it won't just do it.
I also intent/hope /pray to re-use most of RS2 engine for another game, which won't necessarily have things as specific as Backpacks or Undeads. Nor Undeads with Backpacks.

It's all the craze. I won't write an article on that, there are plenty out there. This is a good start point, plenty of links. Here's my current take on it.

Example Entity Component System

I got my hands dirty by prototyping a couple of lolentitysystems to understand the challenges in designing and using one and then tried using established frameworks like Artemis.
They look good, but like most of these frameworks I could get my hands on it gets a bit less easy when you have a client-server architecture : how do you ensure one there is no duplicate entity ID between clients and servers, and more importantly you can't re-assign an ID to an entity once created, there is only once source of creation and you can't insert arbitrary foreign ID.

- Solution A : the server is authoritative and the sole source of IDs. When a client wants to spawn an entity, it must ask the server to get an ID. That's 100% reliable.
But: a player fires its bow, it must create a flying arrow, so it asks the server for an ID. That's 50-100ms latency at best before the arrow actually appearing on the client. The lag is for other clients, but not for the player who fired the shot. Image you play single-player and have a 100ms latency on all your shots. Ugh.

- Solution B : map client local entity IDs to server entity IDs. Allows clients to create entities when they need to, but only the server is a reliable source of global IDs and there must be a map between local IDs on the client and global IDs on the server. And on the other way too.

Then you have solutions in between. For instance, you could create a temporary entity on the client and ask for a proper ID to the server. In the meantime the client can shoot the arrow with no lag, but it exist only on this client. Then when you get a server answer the client must re-assign the arrow ID to the correct one provided by the server. Mmmh. But then what happens if in the meantime the server sends you an entity with an ID the client has assigned to his arrow? Mmmmmmmmh. Lots of re-allocation of IDs and ID collision management to do.

I'll try solution B. We'll see how it goes.

Entity UID between Clients and Server

Using classes diagram for what they are not supposed to be used for and that's a long caption hope you read it kthksbye

Good luck me.

PS: diagrams made with NClass. You have ArgoUML too, but I prefer NClass for rapid loldesign.
End of post.

Thursday, July 12, 2012

Day 24 - Debug Days with VisualVM and SVN

"I don't always profile in Java.
But when I do, 
I use Visual VM"

One of the advantages of a virtual-machine runtime like Java is easy debugging and profiling.
When developping you want to know :
- how much time is spent by your game doing what and how many memory does it take : cpu and memory profiling.
- when something goes wrong, find who or what is fucking things up : debugging.
Sure Java IDEs can do step by step debugging and you can write logs at runtime and do hand-made performane checks, but you can get so much more informations with a proper profiler.

It happens there is a really great free profiler for Java : Visual VM

Visual VM has several information panels and profiling tools you can launch.
The panel I spend most of my time anxiously looking at is the Monitor panel
You can see CPU and Memory usage at a glance, and in particular how much of a sneaky bastard the Garbage Collector is. When you get an old lag in game, look there and its propably the GC doing its thing.
In practice:
I C U GC!!
On this picture, you can see the GC event. Also notice the average CPU usage is above 25% on my quad core CPU. This is actually ok, the game is wrote to use multicores when available.

Visual VM can hump the deap mmmh head the bump aaaaah dump the head for you.
You can see everything that is in Java VM memory, how much memory individual objects take, how many instances of each classes there are etc...
Hey you! Dump your heap! Now!
You can also examine each instances and see where they are referenced.
Very useful to fix "false" memory leaks : the memory keeps getting eaten and you can't seem to find the rationale behind that. You probably kept somewhere a reference to "old" object that you thought you got rid of. But it still linger there, referenced somewhere, and with a chain of reference it eats a lot of memory.
Believe it or not, it happened to me zomg! When moving around the world in game, in the heapdump I spotted entities and chunks that should not be there anymore. They were not active, but still in memory and couldn't be GCed. By looking at references in Visual VM, I found out the culprit : my debug ray tracer always kept a reference to the last entity traced. So the entity and all referenced objects could not get GCed even when my camera was now a million chunks away. DOH.

Visual VM can profile CPU and memory.
You have two kind of profiling :
- incurrate but lightweight and painless : sampler.
- proper profiling which of course kills your framerate : profiling.
Beware of using only sampling, it can be misleading.
Too lazy to profile...
Pro profile.
There are also other tools, such as monitoring threads and exploring call trees.
So, if you develop in Java and want a good and free profiler : GO GET IT!

* * *

"I don't always use source control,
But when I do,
I use SVN."

I keep a "devlog.txt" where I write daily what I do. I also do daily backups on my trusty USB key. It quickly gets messy, and while I know my code I can sometimes forget when and why I did what I did.
So in addition to that I now use proper source control with SVN.
"Oh... I did that..."
It very nicely integrates with NetBeans. You can see directly in the file you code you added, deleted or modified since your last commit. And of course, when you commit you can add a message explaining what you did. Helps when you commit a "MOD optimized physics for this entity works like a charm no possibility of a bug at all" and later stumble upon a brand new and bizarre physics bug :D

End of post.

(*) I keep reading this as "Headbump" trolololo

Friday, July 6, 2012

Day 18 - Entities LoD

Earlier I talked about "Entity Level of Detail", something that allows RS2 to handle more active entities than it be able to without.
So wtf is that. 

First let's see the most simple case, we do not perform LoD computations on entities.
No LoD
This is a simplified schematic top-down view of a game situation
 The green filled rectangle represents the portion of the world that is active, centered on the player.
"P" is the player.
"E" are entities, can be crates, zombies, whatever.
 With no LoD, everytime the world is updated, every entity is updated and there is no difference between a player or another entity.

This is fine and moraly satisfying to know the NPCs are as active and accuratly simulated as the player, but as discussed earlier we do not really need to do that and we can't do that if we want a large number of active entities around the player.
Some entities do not really need to be updated as frequently as others,  respective to the player.
So we introduce the LoD metric.
For each entity, we can compute a LoD with some formula, giving a number from 0 to 1.
LoD=1 means we want everything computed each frame.
LoD=0 means we will not update this entity at all.
In between values means we can simplify or skip some computations done on this entity.
More on what that means concretly later.
The less CPU time we spend on low LoD entities, the more entities can be active at the same time in the world.

The first idea that comes to mind is to give low LoD to entities that are so far from the player that they are culled by the rendering. Since they are not visible at all, why bother having smooth animations or accurate physics?
You can set this range to the camera far range, but since in RS2 I have a fog effect I set this range to the fog far range. Which is nice, since fog will be thicker at night and there will be more zombies at night. Nice coïncidence.
Distance LoD
Green circle : view range.
Orange : outside of view range.
Any entity inside or partially inside get full LoD. Entities outside the view range get lower LoD the farther they are.

We can push the idea further. Since we are in 3D the player views the world through a camera. Anything that is outside the camera frustum is not visible, even if in view range.
Distance and frustum LoD
In this picture the player is looking south.
Light green : the frustum.
Dark green : the view range.
Orange : outside of view range.
In this situation, only one entity is currently visible and will get full LoD.
Entities in range but out of the frustum will get moderate LoD, since even if not visible they could still potentially interact with the player : chasing him, throwing something at him...
Entities out of range will get distance based LoD.

We could find other ways to improve the LoD metric.
  1. Occlusion : an entity in range and in frustum but occluded by the world geometry could get a lower LoD.
  2. Prediction : increase LoD of entities that appear to be coming closer to the player, and conversely decrease LoD of entities appearing to move away. 

Every game frame, the world is updated and rendered.
During a world update frame we update the entities.
With no LoD or full LoD, an entity is always updated on a world frame.
With partial LoD, we can skip an entity update frame during a world frame.
But remember the game runs in realtime, so we have to accumulate time between entity frames so they are still moving and behaving at the same speed than full LoD entities.

LoD and Frames
The green bars are world updates. Since the game frame rate is variable, we can't predict when the next frame will happen so all computations have to be time-based and we accumulate time between two frames. This accumulated time between frames is called "elapsed time".
At full LoD, you can see an entity is running at the same frame rate than the world.
At half LoD, an entity will skip one frame every two frame. For this entity, the elapsed time between frames will be longer. Its animations and movements will appear more jerky and less smooth or its AI will appear less responsive. Its ok since if we attributed this entity a low LoD it means we don't care about that. Since we accumulate elapsed time, it will still move the same distance as a full LoD entity of the same speed.

In practice, we have to put some safeguards. We can't let LoD go below a threshold, or the physics will break, especially the collisions as I implemented a naïve physic system that respond badly to high elapsed times. As the player gets closer to an entity, its LoD increase and the physics glitches tend to fix themselves.

End of post.

Wednesday, July 4, 2012

Thursday, June 21, 2012

Day 3 - TechBlah

Stuff done under the hood not interesting to see in a video, so heres some text.


Added a console to  allow me to input commands to help me find problems or test stuff.
- Wireframe : shows the world in wireframe. Useful to check the geometry is ok and to see through everything.
- Timescale : freeze, slow down or speed up the world physics and ai. Freeze in particular is very helpful, I can stop things from moving and go check a problem I spotted away with my magic flycam.
- Loadrange : allows me to change ingame the distance at which chunks are loaded/dropped. Good for stress tests or testing persistence.
- Fog : toggle fog on/off. I use fog in LoD computations, see below.

LoD optimization is a classic in 3d computer graphics. The idea is that for a 3d object far from the player, you don't have to draw everything in detail. It doesn't have to have as much details as a mesh right under the player nose. This improves framerate and also may help fixing some display bugs. If done right the player won't notice the difference.
You can use this concept elsewhere. I use it on entities. The farther away an entity is from the player, the less accurate the physics and the ai is. I constrain the physics so while they are less accurate they do not become insanely un-physics.
I need this optimization as I want RS2 to have as much entities active as possible. Focus in RS2 is entities/actors, like RS1. Without LoD even with the simple random walker ai make the game crawl to 30fps when there is 1000 entities active. With entity LoD is a respectable 150-200fps.
I refined the idea by incorporating fog. Distance for LoD is measured relative to fog far range, as this is the farther the player can see. I will refine the idea further by using the camera frustum : low LoD for anything that is out of the player view cone. This should really help a lot. As long as my lolphysics don't break on low lod :(
I'm still not decided on what kind of lighting to use. Depending on that, I will or will not implement LoD on the cells (=3d tiles) mesh. Right now there is no LoD optimization on chunks, but there are already optimizations in the rendering such as octtree and texture batching.

WHY U 3D??
3D graphics for me is a mean to convey the gameplay and the atmosphere and not an end.
I don't go 3d realtime because it's cool or something but because it will allow me to do stuff I can't in turnbased 2D gameplay wise. Both are fine btw.

RS1? :(
Don't worry, again it's not dead until I say so. If it is, I'll release the sources.

End of post.