Friday, March 18, 2016

Inheritance versus ECS Pattern Concerns

"Should these data members become the base class that this class inherits from?"  If you've ever heard this phrase, or had any discussion involving multiple inheritance, read on!

If you've read anything about the Entity Component System design pattern (ECS), you might have dismissed it as being only relevant to game design.  But ECS short-circuits the need for inheritance - so it's worth trying to understand as a tool in your belt.

I started writing this with processing architectures in mind, because it helps to visualize how the ECS pattern seems to work.  So I will first enumerate computer processing architectures I have encountered.


From The Main Event Loop to Multi-Threaded OS

If you go back to before operating systems offered multi-tasking, code was written in a loop which waited for events, and every event was then processed.  There were several weaknesses - but we don't care for this article.

Later came multi-tasked operating systems.  They allowed events to be queued up in one (or several) tasks.  Other tasks could process event handling.  Then finally we have multi-threaded operating systems.  As more processors are available, tasks can be assigned to other processors.


But all we really need to understand is the main event loop, as it mimics the processing needed to make ECS work on a per-object basis.


The Entity Component System Pattern

Lets say you've got a bicycle class.  It has a gear data member.  And you later decide it needs to have a location too, so you create a location base class and have the bicycle inherit from location.  Seems reasonable doesn't it?  Unless you aren't always concerned with location of the bicycle.

ECS allows attaching concerns to an object dynamically.  It might help to first look at how ECS is implemented and processed in time.

In terms of time organization, the ECS pattern processes concerns in a loop, just like the old main event loop processed events.  An entity can have multiple class instances attached to it, where each instance represents a concern, and those instances can, but don't have to be, attached at run-time.

For this to work, the entity has to process through a list of all attached instances and run an update method (and maybe others).  Common methods can be called directly using polymorphism, but message sending to custom methods may require reflection, or a more sophisticated approach.

Because this architecture organizes by concerns that entity is responsible for, the overall code organization tends to avoid class inheritance.  That seems like a really big deal, and if you've never had exposure to using ECS, might expose assumptions about how code needs to be organized.

Thus a concern (the location of the bicycle) is not inherited by a bicycle class, even if bicycles have location.  Instead a bicycle will have a location concern possibly attached to it.

There are always trade-offs, and workflow for architectural design might be affected.  If you don't have to worry about inheritance as much, writing code can be more straightforward.  Also it seems easier to learn new code by visually seeing which classes are attached to entities.  But the penalty is in the ECS processing at run-time.


Wednesday, March 9, 2016

Detecting Collisions in 2D

Introduction
Let's say a game object is in 2 positions over frame updates.  The 2 positions form a line L1.  To determine if the game object collided with a line L2, we look for the presence of an intersection.

We can detect the presence of an intersection (we don't care where it is) by only looking at the slopes between L1's start point and L2's endpoints, and between L2's start point and L1's endpoints.  If L1's slope is between the 2 slopes of L1's start point and L2's endpoints, and also if L2's slope is between the 2 slopes of L2's start point and L1's endpoints, a collision occurred.


Caveats
I have not compared efficiency to other methods.  However this requires no dot product calculations thus no need for taking the cosine.  [If you know of other methods and would like to share - please post a comment!]


Process


Detect the presence of any intersection between line L1 from x1,y1 to x2,y2, and L2 from x3,y3 to x4,y4.


Figure 1, Two Lines L1 and L2



In Figure 1 above, the slopes of the lines are:

For L1, slope m1 = (y2-y1)/(x2-x1)

For L2, slope m2 = (y4-y3)/(x4-x3)

----------------------------------------------------------------------------------------------


Now we can calculate the slopes between x1,y1 and x3,y3, between x1,y1 and x4,y4, and between x3,y3 and x2, y2, as shown in Figure 2 below:



Figure 2, Additional Lines L14, L13, and L32


In Figure 2 above, the slopes of the lines are:

For L14, slope m14 = (y4-y1)/(x4-x1)

For L13, slope m13 = (y3-y1)/(x3-x1)

For L32, slope m32 = (y2-y3)/(x2-x3)

We also added L31, slope m31 = (y1-y3)/(x1-x3)


An intersection exists (and thus a collision occurred) if:

( m14 > m1 > m13 ) || (m14 < m1 < m13 )

&&

( m31 > m2 > m32 ) || (m31 < m2 < m32 )



Monday, February 22, 2016

C# Reflection - It's What Allows The Entity Component System Pattern At Runtime.

Here is the C# Language Specification 5.0.

From the introduction:

C# is an object-oriented language, but C# further includes support for component-oriented programming. Contemporary software design increasingly relies on software components in the form of self-contained and self-describing packages of functionality. Key to such components is that they present a programming model with properties, methods, and events; they have attributes that provide declarative information about the component; and they incorporate their own documentation. C# provides language constructs to directly support these concepts, making C# a very natural language in which to create and use software components.

If you had never used components, you might walk away from this paragraph scratching your head "well what is component-oriented programming?"

Sadly, this is all the specification spells out specifically about component-oriented programming.

-------------------------------------------------------------------------------

Enter the Entity Component System design pattern.  Apparently there are multiple flavors, and many discussions and purists concerned with how to implement the ECS pattern, and one of those flavors is implemented in Unity, which allows components to be added to game objects in the editor, and at runtime:


// add a script foo to the gameObject
gameObject.AddComponent ("foo");


// add a collider to gameObject
gameObject.AddComponent("SphereCollider");



Unity must be taking advantage of C#'s Reflection feature to find out which components have been added to a gameObject.  I believe Reflection opened the world of component-oriented programming in C#, which is quite wonderful!  Yet searching the C# Language Specification for "reflection" only lightly discusses the reflection feature, and you might not grasp the significance by reading.

Where is the ECS pattern used?  So far I'm only aware of games.  I'm guessing Galactic Civilizations (ship editor), Fate, Reassembly, probably Skyrim, probably Trackmania, Robocraft, and WazHack among many others.

I say "probably Skyrim" and "probably Trackmania", because some features might still be implemented without ECS, but it's cleaner to add components rather than trying to anticipate every possible feature that may ever need to be added to an object.  Thus a modding feature might be best implemented with ECS, but there are other ways to allow a game to be moddable - they just won't be as future-proof.

For example, if you wanted a collapsible wall which responded to impacts, it could be coded without ECS, but it would be a nightmare.  With ECS, a collapsible wall is trivial to implement, as each section of the wall can independently respond to impacts and distribute damage to adjoining sections.

There is also some discussion that Unity "breaks" the ECS pattern by allowing code to reside in components.  Some people want the components to be data only with no methods.  My impression is they have overlooked other messaging features and Unity does it fine; it's a rabbit hole I'm not interested in digging into right now.  The way Unity implements ECS is to divide concerns into individual components.

The ECS pattern in Unity organizes the software in such a way that components can be attached to initial objects without much emphasis on inheritance.  I've written applications without ever deriving from anything other than monobehavior.

Also, if you want to understand Reflection by itself, watch C# Reflection to the Max, and thanks Jamie King for helping me grasp the concept!

Tuesday, February 9, 2016

Using C# Expression Trees for Compiling Run-time Code

This is a follow up on the Genetic Algorithms Used to Search Solution Space post several years ago.

I just became aware of C# Expression trees.  The common application is for SQL database queries.

More exciting: Expression trees can also be used to compile arbitrary code, the first step in implementing the genetic algorithms as described in the post above.

For excellent tutorials on expression trees, see Jamie King's C# Expression Trees youtube video playlist.  If you like his videos, consider supporting him in some way.


Consider the following code for Unity:

using UnityEngine;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq.Expressions;
using System.Reflection.Emit;

public class Test : MonoBehaviour {

// Use this for initialization
void Start () {
int myC =

UnityEngine.Random.Range(0,30);


int myTI =

UnityEngine.Random.Range(-5,50);


ConstantExpression cE =

Expression.Constant( myC, typeof(int) );


ParameterExpression iP =

Expression.Parameter( typeof(int), "i" );


List<BinaryExpression> exps =

new List<BinaryExpression>(3) 
Expression.GreaterThan( iP, cE ), 
Expression.LessThan( iP, cE ), 
Expression.Equal( iP, cE ) 
};


int indexExp =

UnityEngine.Random.Range(0, exps.Count );


BinaryExpression myExp =

exps[indexExp];


Expression<Func<int, bool>> testRand =

Expression.Lambda<Func<int, bool>>( myExp, iP );


Func<int, bool> dele =

testRand.Compile();


Debug.Log ( "myC="+myC);
Debug.Log ( "myTI="+myTI);
Debug.Log ( "myTI " + myExp.NodeType + " myC = " + dele(myTI) );


}

}



Attach this script to an object in Unity (I used the main camera) and run, and you should get output something like this over several runs:

myC=17
myTI=-4
myTI LessThan myC = True

myC=20
myTI=9
myTI GreaterThan myC = False

So what is this code doing?  It's generating a random BinaryExpression at runtime, then compiling and running the expression at runtime.

When I found this I was overjoyed!  This is a relatively straightforward way to compile algorithms at runtime to search any random algorithm space.

Friday, January 22, 2016

Linux App Pt. 2




Here  I've added a few uGUI elements and optional disabling of the animation and an FPS count.

With the animation turned off (the culling mask of the animation is off in the camera), the draw calls drop to 6, which can be lowered still further to 4 without the toggle button (shown in the screen-shot above), or 3 if the buttons don't have the white backgrounds.  Still with no graphics card and the animation turned off my Mac ran 40 FPS.



Tuesday, January 19, 2016

Linux app

Today I got advice that Linux drivers are not that high in demand, and I'd do better to work on making apps for Linux.

Here's an animation program for fun.





It is big for what it does.  10MB.

All I did was take a previous Unity3D project of mine and built it for Linux (on my Windows machine).  Anyone can get the latest or older versions of Unity for free for Windows, OSX or by now almost certainly for Linux, and build an app for a Linux target.

Builds tend to be bloated (at least that was what I saw with iOS apps compared to similar iOS apps built only with XCode), and the only other tool I've heard of as a standard is Qt, which comes already installed in Linux Mint 17.3.

-------------

Also, it might be interesting to look at libusb.sourceforge.net to build USB access into a Unity3D app.  I found nothing for libusb in the Unity asset store.

For example a use case might be a USB dongle that has to be plugged in to let the app run.


Postscript
On my iMac which is running Linux, I have the GPU disabled due to missing drivers.  So this app runs unbearably slow.  This begs the question if a Unity app with no hardware support would still be okay if it was just comparable to a Qt app - i.e. just UI elements and not much 3D.

Sunday, January 10, 2016

Building the Kernel

Many years ago when I worked for a receipt printer company, I was given the opportunity to write a USB driver for Windows.  It was one of those very fast conversations "anybody want to do this?" and I watched the opportunity pass by as someone else wanted to.  Honestly, it didn't sound very appealing at the time, but ever since then I always wondered what it would take to talk to USB devices.

So I've taken up trying to learn how to do this in a Linux environment.  There are many reasons I believe this is the best use of my time at the moment, not worth going into here.  But the biggest reason is: Stayin Alive.

To get started, the Linux Device Drivers book is free for download (and there's also apparently a 4th edition).  I'm using the 3rd edition for now:

http://free-electrons.com/doc/books/ldd3.pdf

The book wouldn't let me go any further until I had built my own kernel.  And so here we are.


Hardware

Presumably building the kernel can be done on a virtual machine or an AWS ec2 instance or a raspberry pi, but for now I'm using my old dusty iMac, because it already runs Linux Mint (see Recovering Files From A Crashed Mac), and it will build faster than the rPi.

The only downside with using my iMac was a nagging sense of doubt - that it might not work.  I also noticed the Mint distributions are all odd numbered kernel versions, so I assumed they are heavily modified from the main tree.  But I found I was able to actually build the kernel and switch to it and it actually ran fine on this hardware.

For this I got Mint 17.3 32-bit Cinnamon "Rosa", just to try getting the latest.

The process for building is fortunately spelled out: How to: Compile the latest kernels (Classic Mint & LMDE).  This is an excellent guide, even though I ran into some kinks.


The First Kink
Mint 17.3 32-bit Cinnamon Rosa runs vmlinuz-3.19.0-32-generic.  Just look in /boot, or run uname -r.

So browsing to kernel.org, the closest subsequent version was 4.1.15, so I tried downloading and making this, and the make crashed.

At this point, it really helps to have no sense of dignity or pride, no feeling of "am I wasting my time" or "this is clearly not my fate in life".  It really helps to be sort of... dumb.  You know?

So what would a dumb person do?  Follow the example on the forum verbatim of course!

By following the example to the letter, which uses 3.8.7, everything built fine.  Here's my history output which should be exactly what they posted on the forums.

      Note these aren't included but updating everything can't hurt (run as root):

    3  apt-get update
    4  apt-get upgrade
    5  apt-get dist-upgrade


    8  apt-get install build-essential kernel-package libncurses5-dev fakeroot wget bzip2
    9  apt-get install qt4-designer qt4-dev-tools qt4-doc qt4-linguist-tools qt4-qmake
   10  export CONCURRENCY_LEVEL=2
   12  export CFLAGS="-march=native -O2 -pipe"
   13  export CXXFLAGS="$CFLAGS"
   14  export CHOST="x86-pc-Linux-gnu"



     Note: These I ran as a regular user:

   29  wget https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.8.7.tar.xz
   30  tar -Jxf linux-3.8.7.tar.xz
   31  cd linux-3.8.7
   32  cp /boot/config-3.19.0-32-generic ./.config
   33  make oldconfig
   34  make xconfig
   35  menuconfig
   36  make menuconfig

   40  fakeroot make-kpkg --initrd --append-to-version=-mint-17.3-x86-32-16-01-09-2246 kernel_image kernel_headers
   41  ls ..
   42  cd ..
   43  sudo dpkg -i linux-image-*.deb linux-headers-*.deb
   44  sudo update-grub


Note: I think xconfig never worked for me, so menuconfig was okay, and I changed nothing in it either.

Also the build process (fakeroot make-kpkg...) took well over an hour.


The Second Kink

After rebooting, running uname -r showed the old kernel was still running.  This is because the grub apparently will run whatever the most up-to-date kernel available is.  To fix this, I ran:

  gksudo gedit /etc/default/grub

and commented out the hidden timeout references so it looked like this:

  GRUB_DEFAULT=0
  #GRUB_HIDDEN_TIMEOUT=0
  #GRUB_HIDDEN_TIMEOUT_QUIET=true
  GRUB_TIMEOUT=10
  GRUB_DISTRIBUTOR=`lsb_release -i -s 2> /dev/null || echo Debian`
  GRUB_CMDLINE_LINUX_DEFAULT="quiet splash"
  GRUB_CMDLINE_LINUX=""


This allowed a selection menu to show up at boot.  The "advanced" menu allowed selecting the older kernel I had built.

Display Driver Issues
Lastly, just booting into that kernel didn't work because the iMac's nVidia drivers don't run.  So instead, select the "recover mode" version of the kernel, and after that boots up run the first option (something like "resume") which bypasses hardware video support altogether.  I'm writing this blog post from that build right now.  Note that the forum also explains in the same thread how to run the nVidia driver after first running:

   update-initramfs -k `uname -r`

(note the ` character not ' as the forum says).  I started to try this, didn't know where to get the nvidia driver and more importantly, I don't care.  This is adequate functionality to move forward with the Linux Driver book.

Thanks!


PostScript

Right after posting this, I tried hybernating the machine, which resulted in severe problems with booting up that kernel (even when it had already booted twice).  Specifically, the initrd.img* file for the built kernel is somehow missing.  I was able to fix this by running dpkg and update-grub again (after renaming things dpkg complained about) - but I have no explanation how the initrd.img* file got deleted.   So this whole approach is somewhat unstable for now.


Wifi Drivers


For a Mac, to get Wireless working, try this.  Namely, connect via an Ethernet cable, and run these commands:

 sudo apt-get purge bcmwl-kernel-source broadcom-sta-common broadcom-sta-source
 sudo apt-get install linux-firmware-nonfree b43-fwcutter firmware-b43-installer

and then reboot.

Thursday, January 7, 2016

Unity Versus Sencha for Mobile App Development

This whole discussion is mostly academic for me.  I post it for whoever might have an interest in these tools.


Recently I looked into the Sencha development environment.  It reminds me a lot of Maqetta, specifically the sliding UIs it generates.

I've looked into whether similar UI is available off-the-shelf for Unity (especially for workflow), and so far it looks like it's not.  I wrote a UI from the ground up using uGUI, but this adds extra weight which isn't present in the Sencha UX, and the workflow isn't anywhere close to as streamlined.

All I can say is Unity still thinks of itself as a game engine, rather than a mobile app engine.

It has not yet matured in the direction of rapid UI development.  I have this nagging feeling I want to create a Sencha-like UX in Unity, which only animates going between scenes while not actually using a Unity uGUI scroll-rect to hold them all.  Mostly I want to do this to improve the whole game development workflow, of which UI design can be a good starting point.

But again... this discussion is mostly academic.

Live and learn.  Unity is still more efficient than going through multiple target learning curves (i.e. Xcode for iOS + Android API).

Will I switch to HTML5?  Only if three.js or other tools can bridge the gap.  Push notifications look like they are available at least for Chrome (and possibly exclusively to GAE).

Google may kill Unity altogether eventually.