Páginas

terça-feira, 16 de dezembro de 2014

Santa Kitten will join the jumping!

Just sent to the Google Play a new version of Kitten Hopper. In this update I've added Santa Kitten and Persian Kitten. Happy jumping!


sexta-feira, 12 de dezembro de 2014

Space fighters! Deploy!


Hello! I am one of the Drifter's Last Stand programmers. As Allan is making the design, visual and gameplay parts of the game, I am doing some random code here and there attempting to keep the development process smooth - and an ugly UI.

These past weeks we decided that we wanted to have light spaceships fighting around the player. It is cool, adds some life to the game, and it is really fun to watch. But programming their fighting behavior wasn't so triffling!

I took on the task to implement those flying light spaceships. First, I used a plain dumb steering algorithm where the spaceship would take on a target and keep on trying to move towards them. The results were... well... painfully awful. The fighters would just wander around as clouds of flies, slowly circling around towards somewhere outside the screen.

Then, I decided to throw all of it away and use a physics based approach. The spaceships are simply attracted to their targets. It should work! But it didn't! They would either fly in an interesting circular motion (emergent behaviors are always awesome!) or collapse in small groups with spaceships slingshotting in and out. It was clear then that the best solution would be a steering algorithm with some brains to know where the possible targets are and dynamically decide what to do. For those more into AI, what I meant is that I started to build an steering algorithm inspired on Boids.

Many attempts came after, but here's my final spaceships movement algorithm:




A spaceship has its own acceleration, deceleration, max and min movement speeds. The min speed is needed to avoid "docking" on a stationary target - this is an undesirable behavior. To make the battles smooth and convincing, a ship has two turning speeds. The 'maneuver turn speed' is used when the spaceship is slow enough, and the 'hi-speed turn speed' us used otherwise.

The different turn speeds are very important to give a good visual feeling to the player. They won't allow a fast spaceship to do a sharp U-Turn, resulting in taking some distance before turning to attack an stationary target, and also allowing ships to dodge their pursuers (they won't be able to keep on the spaceship tail because it, being slower, will turn faster. The pursuer will then need more time to adjust it's own speed to be able to turn back to their target).

To keep the battles more chaotic, the spaceships will search for a new target every x seconds of time (or fragments) - even if the previous target didn't die. The new target is decided by the 'Distance Then Cone Target Fetcher Behavior', which will try to find the best target within an ideal distance from the ship, and closest to straight forward direction. This allows the ships to give up on some dodging target to aim at a new target that just happens to be within range and weapons angle.

The final challenge was to not allow the battles to move too far away from the player. This was solved with a guard position and distance. If the ships go too far away, they'll abort all engagement and come back within an ideal distance again.

Finally, Allan then fine-tuned the parameter so we could see fun battles. Phew. It was some work to do. But the results are neat! Here's a Web Build. Use left and right mouse buttons to spawn fighters! May the force be with you.

Web Build!

sábado, 6 de dezembro de 2014

Finding your art style when you can’t draw

As the first post of our newest project, I wanted to talk a little about choices and choosing.

First some introductions. The game name is Drifter's Last Stand. In short terms, your ship is always going forward (you can’t control), you have two cannons you can aim with your mouse to shoot enemies, and you can build turrets in your ship that will shoot enemies for you. And enemies are always coming (always!).


We have two persons in the team, both programmers “by nature”. Although one of us can draw

 
(like this)

for the limited time we have (until the end of the year), we preferred a simple solution.
My mind was “drifting” between Desktop Tower Defense and Geometry Wars. Two simple art styles that I was sure we could reproduce in time. 
Desktop Tower Defense
Geometry Wars
                                                                              


However, we thought that a great part of the idea of this game was to really recreate a space feeling (as in outer space). You know, like in Space Battleship Yamato 2199, when they jump out of a dimensional portal and there are thousands of enemies surrounding them? That’s the game we want!

If you are a fan of space operas, go watch Space Battleship Yamato 2199.


So after some search, (roll the drums) we settle on…tchan tchan tchan tchannnnn…this! (Thanks a lot Skorpio)


A modular ship construction pack!

Links:
http://opengameart.org/content/space-ship-mech-construction-kit-2

If you are an artist, check this tutorial by the author of the Space Construction kit http://opengameart.org/content/spaceship-tutorial


Anyway, with both packs it’s fast and easy to build your own space ship! So we did it, and so far these are the results:


This is the player's ship:


As commented before, the player will control two cannons, shooting with the left and right mouse buttons, and aiming with the mouse:



The best part about this modular art pack is that the pieces are fitting really easily and nicely. So, this is the ship, without and with the cannons highlighted:

 



 Now what we are missing are the turrets. The player will have 8 available turrets to build. These turrets will be placed over slots distributed in the ship. Slots and Turrets look like this:


Turrets 

Slots
         
In the ship, they will be positioned strategically (Slots have fixed position and you can only build Turrets on top of them). In this highlighted version, Slots are green and Turrets are blue, and we removed the main cannons:



Finally, putting everything together, the player ship will look like:




And now what? We still have to test this art style with players of course. 

Unfortunately we don't have a lot of time, so if this proves to be lame (through a few friends evaluation), will probably revert to triangles shooting squares. 

But if this gets approved, we already have some ideas for enemies (which we will improve depending on how fast we can complete our task list):





So far that's it. Again, many thanks to the author of this spaceship art pack, Skorpio http://opengameart.org/users/skorpio

Leave comments if you have them, and see ya next week

terça-feira, 11 de novembro de 2014

Unity and Components Orientation Tutorial - Part Three

This is the third part of this series about Component Orientation and Unity. In part two, I've made a very simple system so that things could automatically aim at anything tagged with a TargetableBehavior component. In this part, I'll make a very simple movement system, and add components that allow the player and AI to move their ships.

The movement I want is very simple. The object can be accelerated and decelerated, and asked to turn facing towards some angle. Of course, there's also attributes like current direction (or angle) and current speed.

To make things nicely separated in components, I will need three behaviors. The first one, and most important one, is a movement behavior. It will receive commands and move objects as needed. This behavior is the basis of our moving things. The other two behaviors the player and AI, that sends movement orders to this movement behavior. Even thought I could use inheritance here and make the player controller and AI inherit from the base movement, I won't do this. With components, it is easier to simply change the movement orders issuer for whatever need I might have (i.e give player control of another ship, changing the AI movement style at runtime, etc).

Naturally, to allow components to communicate with each other without needing to know their existence or types, SendMessage will be needed. As always, since SendMessage takes a string as the message to be sent, it is easy to make invalid code, or break some scripts when we rename methods. This time I'll go a little bit further in safety measures than I did in part two. I'll use C# Interfaces!

/// <summary>
/// Interface needed by moveable objects. Theres not much
/// sense for this Interface, since it is more likely there will
/// be one moveable behavior. The main reason for this interface,
/// in this case, is to make SendMessage less error prone. For
/// example, if we decide to rename or change parameters of these
/// methods.
/// </summary>
public interface IMovable {
    void TurnToAngle(float degrees);
    void Accelerate(float accelerationPower);
    void Decelerate(float decelerationPower);

    float CurrentSpeed { set; get; }
    float CurrentAngle { set; get; }
}

public class MovMsgs {
    public const string TurnToAngle = "TurnToAngle";
    public const string Accelerate  = "Accelerate";
    public const string Decelerate  = "Decelerate";
}


In the script above, there is an Interface that will indicate all the methods needed by any “mover” component that might be done. The class bellow, MovMsgs, simply contains constant strings that are the ones to be used within SendMessage parameters. This way, if I ever need to rename the methods and messages, I'll do it in the Interface and change the related constant strings in the MovMsgs, thus reducing the likelihood of breaking things when bug-fixing or code re-factoring. I modified the “targetables” scripts to use Interfaces as well, but I won't list the code here, for space. You can try it as an exercise or download the source code.

Now, there's another trick I'll use for the movement behaviors. I plan to have a single movement behavior, but I can't be sure that this will always be true in the lifetime of this project. With this in mind, I'll do some “flexibility” code that will make it easier to add more movements in the future. I want all movement behaviors to be seen as the same type. I'll be using the generalization concept of Object Oriented Programming, where child classes are the same type of their parent.

using UnityEngine;
using System.Collections;



/// <summary>
/// Base component for movement behavior. The main reason for
/// this component to be inheritable is that I want that other
/// components can find any type of movement behaviors with a
/// simple GetComponent.
/// </summary>
abstract public class MovementBehaviorBase : MonoBehaviour, IMovable {
    abstract public void TurnToAngle(float degrees);
    abstract public void Accelerate(float accelerationPower);
    abstract public void Decelerate(float decelerationPower);

    abstract public float CurrentSpeed { set; get; }
    abstract public float CurrentAngle { set; get; }

    // Yes, no virtual or abstract methods for Unity methods such as
    // Awake or Update. This class is not meant to hold any behavior
    // or initialization by itself.
}


The MovementBehaviorBase is our model to any movement behavior that might be done. The component itself is abstract, blocking you from instantiating or putting it in GameObjects. Also, the abstract methods need to be defined on child components so, actually, this is a “model” component for future others to follow. If you don't know what abstract classes and methods means, or don't know about inheritance and interfaces, I advise to do some researching. These concepts are quite “big” and would require a some hours of study.

About the movement itself, it is coded on another component:

using UnityEngine;
using System.Collections;



/// <summary>
/// Basic movement simply mave forwards with the "current"
/// angle and speed.
/// </summary>
[AddComponentMenu("Scripts/Movement/Basic Movement Behavior")]
public class BasicMovementBehavior : MovementBehaviorBase {
    // Movement attributes
    [SerializeField] protected float m_MaxSpeed;
    [SerializeField] protected float m_MinSpeed;
    [SerializeField] protected float m_MaxTurnSpeed;
    [SerializeField] protected float m_MaxAccel;
    [SerializeField] protected float m_MaxDecel;

    // Movement variables
    protected float m_CurrentAngle; // Degrees per second
    protected float m_CurrentSpeed; // World units per second

    // Small optimization by caching
    protected Transform m_Transform;
    protected Rigidbody2D m_RigidBody2D;




    public override float CurrentAngle {
        get { return(m_CurrentAngle); }
        set { MoveRotation((m_CurrentAngle = value)); }
    }

    public override float CurrentSpeed {
        get { return(m_CurrentSpeed); }
        set { m_CurrentSpeed = Mathf.Clamp(value, m_MinSpeed, m_MaxSpeed); }
    }



    protected void Awake() {
        m_Transform = this.transform;
        m_RigidBody2D = this.rigidbody2D;
    }



    protected void Update() {
        // Move the object
        Vector3 pos = m_Transform.position;
        pos.x += Mathf.Cos(m_CurrentAngle * Mathf.Deg2Rad) * m_CurrentSpeed * Time.deltaTime;
        pos.y += Mathf.Sin(m_CurrentAngle * Mathf.Deg2Rad) * m_CurrentSpeed * Time.deltaTime;
        MovePosition(pos);
    }



    /// <summary>
    /// Turns the object towards an angle
    /// </summary>
    public override void TurnToAngle(float degrees) {
        m_CurrentAngle = Mathf.MoveTowardsAngle(m_CurrentAngle, degrees, m_MaxTurnSpeed * Time.deltaTime);
        MoveRotation(m_CurrentAngle);
    }



    /// <summary>
    /// Accelerate with the given acceleration power
    /// </summary>
    public override void Accelerate(float accelerationPower) {
        accelerationPower = Mathf.Clamp01(accelerationPower);
        m_CurrentSpeed += accelerationPower * m_MaxAccel * Time.deltaTime;
        m_CurrentSpeed = Mathf.Clamp(m_CurrentSpeed, m_MinSpeed, m_MaxSpeed);
    }



    /// <summary>
    /// Decelerate the specified deceleration power
    /// </summary>
    public override void Decelerate (float decelerationPower) {
        decelerationPower = Mathf.Clamp01(decelerationPower);
        m_CurrentSpeed -= decelerationPower * m_MaxDecel * Time.deltaTime;
        m_CurrentSpeed = Mathf.Clamp(m_CurrentSpeed, m_MinSpeed, m_MaxSpeed);
    }



    protected void MovePosition(Vector3 position) {
        if(m_RigidBody2D != null) {
            m_RigidBody2D.MovePosition((Vector2) position);
        } else {
            m_Transform.position = position;
        }
    }



    protected void MoveRotation(float rotation) {
        if(m_RigidBody2D != null) {
            m_RigidBody2D.MoveRotation(rotation);
        } else {
            Vector3 angles = m_Transform.eulerAngles;
            angles.z = rotation;
            m_Transform.eulerAngles = angles;
        }
    }
}


The code is straightforward and very simple to understand. It allows the object to be turned around, accelerated and decelerated, there's a maximum turning speed, and maximum and minimum movement speeds. Finally, some specialized code to treat rotation and movement differently if there was a RigidBody2D in the object at awake. As a rule of thumb, if your GameObject has one of either RigidBody or RigidBody2D component, you're better off moving it with physics or the rigid body methods MovePosition and MoveRotation, instead of directly changing the transform component of the object. Directly changing the transform in their presence might cause unexpected behavior, wrong or broken physics, and even miss collision detection.

The new stuff introduced in the code above is the AddComponentMenu attribute. It says to Unity where you want your component to be listed in the menus when trying to add it to a GameObject. This is solely to keep things organized, and help other team members (i.e designers) to quickly find components that they need and can use. The right ones, mind you! You should make use of the opportunities to make the non-programmers developers life easier.

The code to move the player is pretty straightforward now, too.

using UnityEngine;
using System.Collections;



/// <summary>
/// Detect input from the player and pass over to a MovementBehaviorBase
/// child instance.
/// </summary>
[AddComponentMenu("Scripts/Movement/Player Movement Controller")]
public class PlayerMovementController : MonoBehaviour {
    protected MovementBehaviorBase m_Movement;



    private void Awake() {
        m_Movement = this.gameObject.GetComponent<MovementBehaviorBase>();
    }



    private void Update() {
        if(m_Movement != null) {
            // TODO : GET RID OF MAGIC VALUES
            if(Input.GetKey(KeyCode.W)) m_Movement.Accelerate(1.0f);
            if(Input.GetKey(KeyCode.S)) m_Movement.Decelerate(1.0f);

            float currentAngle = m_Movement.CurrentAngle;
            if(Input.GetKey(KeyCode.A)) m_Movement.TurnToAngle(currentAngle + 90.0f);
            if(Input.GetKey(KeyCode.D)) m_Movement.TurnToAngle(currentAngle - 90.0f);
        }
    }
}


At Awake, I attempt to find a movement behavior within the same object. I do a component search for MovementBehaviorBase, but any component that inherits it will be returned – and right now, it can only be an instance of BasicMovementBehavior.

On Update I simply check if any movement behavior was found in the Awake and, if true, issue movement orders accordingly to the current user input. I could, of course, have reduced the coupling between the PlayerMovementController and BasicMovementBehavior components and used SendMessages instead, but my desire here was to show that the inheritance works as expected. This is important for components that might need more information about their movement, such as angle and speed (I.e an aiming AI that attempts to shoot where stuff will be, not where they are). To fetch data from other components, its really tricky to do so without a specific reference...

Lastly for this part, a very simple AI movement code for the enemy ships.

using UnityEngine;
using System.Collections;



/// <summary>
/// Simple AI movement behavior that attempts to circle around a target
/// at max speed. Please note that turn speed and max speed will affect
/// the result of this AI, as the movement attributes might or might not
/// make the desired movement possible
/// </summary>
[AddComponentMenu("Scripts/Movement/AI/AI Movement Circle Target Behavior")]
public class AIMovCircleTargetBehavior : MonoBehaviour, ITargeteer {
    public GameObject objectToMove;
    public SendMessageOptions messagesOptions;

    public float minDesiredDistance;
    public float maxDesiredDistance;

    [Tooltip("Position 'in circle' that the AI attempts to reach. " +
     "Different values might result in interesting behaviors")]
    public float angleLookAhead;
    
    private TargetableBehavior m_CurrentTarget;
    private Transform m_TargetTransform; // Small optimization.

    // Small optimization
    private Transform m_Transform;



    private void Awake() {
        m_Transform = this.transform;
    }



    private void Update() {
        if(m_CurrentTarget != null && objectToMove != null) {
            Vector2 dist = (Vector2) (m_Transform.position - m_TargetTransform.position);
            float angleFromTarget = Mathf.Atan2(dist.y, dist.x) * Mathf.Rad2Deg;
            float desiredDistance = Mathf.Clamp(dist.magnitude, minDesiredDistance, maxDesiredDistance);

            angleFromTarget += angleLookAhead;

            Vector2 desiredPosition = (Vector2) m_TargetTransform.position;
            desiredPosition.x += Mathf.Cos(angleFromTarget * Mathf.Deg2Rad) * desiredDistance;
            desiredPosition.y += Mathf.Sin(angleFromTarget * Mathf.Deg2Rad) * desiredDistance;

            // We want to move to the desired position
            Vector2 moveDist = desiredPosition - (Vector2) m_Transform.position;
            float moveAngle = Mathf.Atan2(moveDist.y, moveDist.x) * Mathf.Rad2Deg;

            objectToMove.SendMessage(MovMsgs.TurnToAngle, moveAngle, messagesOptions);
            objectToMove.SendMessage(MovMsgs.Accelerate, 1.0f, messagesOptions);
        }
    }



    public void SetTarget(TargetableBehavior target) {
        m_CurrentTarget = target;
        if(target != null) {
            m_TargetTransform = target.transform;
        } else {
            m_TargetTransform = null;
        }
    }
}


Now isn't this a plain simple AI? It is, indeed! It will wait for a SetTarget message to define a target object related to the AI movement – right now, it can only be the player. Then it will calculate the current angle and distance from this object to the target, and calculate a desired destination by offsetting a bit the angle either clockwise or counter-clockwise, and defining a min and max distance from the target. The movement itself is a problem to the movement behavior being used!

This AI is so minimalist and simple that the values for an interesting behavior is kind of like finding magic values by trial and error. Try it, and you'll find a few interesting patterns. A little more coding and I could have something boids-like, with emergent behavior. When planning for AI, you can often first try simple things and see how they behave in groups. Emergent “complex” behavior is always interesting.

Enough coding for this part! I did some quick artwork for the ships to make the testing more pleasant. Since now I have a movement behavior that rotates the objects, I need to restructure the player and enemies prefabs. I'll not get in details here, as this is very simple – but you can download the code for this part if you want to see how I did.

In this part I've introduced a way to use SendMessage in a less error prone way. By using C# interfaces and constant strings, I was able to drop the main reasons that I hated SendMessage and refused to use Component Orientation widely, attempting to use Objects Orientation in all possible situations. I'll say again. OOP is not bad. It's not evil. But in a components system, it makes it a lot easier to not choose optimal choices. Both paradigms can work together, but the programmer must not be biased to either one of them, and use the best tool that solves his problems!

So far, the components do still feel kind of meaningless. In the next part, the cannons will be able to shoot some placeholder bullets, concluding the basic framework for the game. From there, in part four and onwards, it's all about making some new behaviors to the existing systems.

The project for this part can be downloaded here.

sábado, 1 de novembro de 2014

Unity and Components Orientation Tutorial - Part Two

Infinite Sail part two: the turrets.

In part 1 of this series, I've introduced what it is about: trying to convince you that Component Orientation is a good way to go within Unity, and helping newcomers to think in component terms. And for this, I would make a game called Infinite Sail. In this part, I'll finally get some code! Please, do remember that I will consider that you already know the basics of the Unity and C#, as this is not a really “new programmers” tutorial series. Even though I don't think things will get so complex, I won't go on details about some things, and trust that you'll google or research when needed.

Sooooo... Let's get started! First, I created a new project in Unity, set it to default as 2D (I never used 2D collision system, so I'll adventure on this). Created the basic folders structures that I'm used to work, set up my Unity layout, and finally created a new empty scene.

I've set the background color to an ocean blue, the camera depth to 1000 and position z = -500, and the orthographic size to 100. In the end, I got something like this:


As in every new project, I have no idea on where to start coding... even more on a tutorial. To make matters worse, I have no idea of what this game will be, either! Since it's a tutorial and the game does not to be fun, let's go with something simple. Enlightenment Age ships sailing on a waveless ocean shooting each other with its cannons. Or shooting monsters... Let's stay with ships, for now...

I have a problem when starting new projects, that's my inability to make something playable right from the start, so it might be a while until we have “a game”. For this game, I want that a group of cannons can pick a target by themselves and start shooting without the player needing to issue an order. I can change this later. So for now, I'll do the initial automatic aiming system.

For this, I'll need one enumerator and a few components:

  • TargetTypes: PlayerShip or EnemyShip;
  • TargetableBehavior: means that something can be aimed at;
  • TargetablesLister: to keep lists of our targets;
  • TargetFetcherBehavior: fetches a target for shooting;
  • TargeteerFullRotationBehavior: aims at a target.

That's enough for part two, I guess! When I had my first contact with Components Orientation, I had the feeling that I needed to do much more code than needed to fulfill a task. Actually, this is often true! But there is a benefit that outweighs this cost really fast, as your projects grows more and more complex. It's low coupling between components and game objects. If you've already developed a game in OOP, you'll feel that later, this extra code now will have saved you from hundreds, if not thousands, of lines of code created or changed.

The aiming system will work in a very simple fashion. Any GameObject with a TargetableBehavior component is supposed to be a target that can be aimed at. Don't care what the GameObject is. It could be a barrel, an alien, the player, enemies, an immortal rock - anything. Components like TargetFetcherBehavior will search for appropriate TargetableBehavior instances and set them as a target. Then components like TargeteerFullRotationBehavior will try to aim at them.

Enough talking! First, we do the TargetTypes enumerator. Its fast!

// Types that a TargetableBehavior can be. Values are defined to avoid
// elements reordering to affect the Prefabs. It is ugly, but better safe
// than bug, in this case...
//
// As a game grows, we might reorder the enum to group elements and make
// it easier to know what exists and what does not. In this case is
// not likely to happen but again, better safe than bug
//
// Last Value: 2
public enum TargetTypes {
    None = 0,

    PlayerShip = 1,
    EnemyShip = 2
}


Next, comes the TargetableBehavior, and it's related behavior, the TargetablesLister. The “lister”, in this case, is here only to make it easier to find instances of TargetableBehavior. I didn't call it “manager” because, in reality, it doesn't manage anything. For us, it will be better that way, since TargetableBehavior is not a key component for prefabs or objects pooling.

using UnityEngine;
using System.Collections;
using System.Collections.Generic;



/// <summary>
/// Keeps lists of TargetableBehavior. The behaviors themvelves are
/// responsible in keeping the lists updated. This Lister only
/// stores the lists.
/// </summary>
public class TargetablesLister : MonoBehaviour {
    // We want this to be a "singleton".
    static private TargetablesLister m_Instance;
    static public TargetablesLister Instance { get { return(m_Instance); } }

    // Lists for storing instances references. Could be a dictionary,
    // but I'll keep as separates variables for now
    private List<TargetableBehavior> m_PlayerShips;
    private List<TargetableBehavior> m_EnemyShips;



    private void Awake() {
        // "Singleton" setup
        if(m_Instance == null) {
            m_Instance = FindObjectOfType<TargetablesLister>();
        }
        if(m_Instance != this) {
            Debug.LogWarning(
                "Multiples instances of TargetableLister detected. Deleting this component instance.",
                this.gameObject
            );
            TargetablesLister.Destroy(this);
            return;
        }

        // Allocate the lists
        m_PlayerShips = new List<TargetableBehavior>();
        m_EnemyShips = new List<TargetableBehavior>();
    }



    /// <summary>
    /// Returns a list of targets by type.
    /// </summary>
    public List<TargetableBehavior> GetTargets(TargetTypes targetType) {
        List<TargetableBehavior> targetsList = null;
        
        switch(targetType) {
        case TargetTypes.EnemyShip:  targetsList = m_EnemyShips;  break;
        case TargetTypes.PlayerShip: targetsList = m_PlayerShips; break;
        }

        return(targetsList);
    }



    /// <summary>
    /// (Unsafe) Registers a new target in the lists.
    /// </summary>
    public void Register(TargetableBehavior target, TargetTypes targetType) {
        List<TargetableBehavior> targetList = GetTargets(targetType);
        ValidateRegisteredStatus(false, target, targetList);
        targetList.Add(target);
    }



    /// <summary>
    /// (Unsafe) Unregister a given target from the lists
    /// </summary>
    public void Unregister(TargetableBehavior target, TargetTypes targetType) {
        List<TargetableBehavior> targetList = GetTargets(targetType);
        ValidateRegisteredStatus(true, target, targetList);
        targetList.Remove(target);
    }


    

    #region Debug Methods

    /// <summary>
    /// Validates if a target is registered in a given list or not.
    /// Won't fix anything, but will emit errors if possible.
    /// </summary>
    [
       System.Diagnostics.Conditional("DEBUG_GAME"), 
       System.Diagnostics.Conditional("UNITY_EDITOR")
    ]
    private void ValidateRegisteredStatus(
        bool correctStatus, TargetableBehavior target, List<TargetableBehavior> list
    ) {
        if(target == null) {
            Debug.LogError("[Error] Registered validation failed. Target is null");
            return;
        }

        if(list == null) {
            Debug.LogError("[Error] Received null list!");
            return;
        }

        bool registered = list.Contains(target);
        if(registered != correctStatus) {
            Debug.LogError(
                "[Error] Registered validation failed. Expected [" + correctStatus +
                "] and found [" + registered + "].",
                target.gameObject
            );
        }
    }

    #endregion
}


As you can see, the code is very simple. New C# programmers might learn two new things in this code. The first one, is the Summary comments before the methods and class. These comments will appear on the code completion screen, and this can be quite helpful as the project grows with more and more lines of code, and we forget what “old” methods did.


The second one is the System.Diagnostics.Conditional. Conditional methods are normal methods with some limitation as in that they cannot return values. They are tied to compiling directives, as macros defined with #define. Conditional Methods will always be compiled, but if the needed directives are removed, the compiler will remove the calls for those methods as well. This is a clean way of calling methods to validate the game (in order to detect bugs) and easily remove these validations calls for the release build, and thus making the release build slightly faster.

In the code, I made a method to validate if a given reference exists or not within a list. This method will be called as long as either UNITY_EDITOR or DEBUG_GAME macros are defined. UNITY_EDITOR is defined by default while on the editor. DEBUG_GAME I have to define it myself, in case I want these validation methods to be called in stand alone builds of my game. You can find a lot more on Conditionals on google and in the MSDN C# Reference.

The TarbetablesLister component is supposed to behave like a “singleton”. The quotes are here because the singleton is actually a component. If you're new to the Singleton concept (in or out of Unity context), I'd advise some research on it. It's very simple but interesting pattern. The remaining of the class code is pretty straightforward, and I believe it doesn't need any explanation.

Next, comes the TargetableBehavior class. For now, this one will also be really, really simple.

using UnityEngine;
using System.Collections;



/// <summary>
/// Component used to flag that this object is a target.
/// </summary>
public class TargetableBehavior : MonoBehaviour {
    // Target type. Only change this with the correct method
    [Tooltip("Sets the target type to be used at OnEnable. Don't change on inspector at runtime!")]
    [SerializeField] protected TargetTypes m_CurrentType;



    /// <summary>
    /// Current type of this target. At runtime, it is advised to change its
    /// type by using this property.
    /// </summary>
    public TargetTypes CurrentType {
        set {
            if(this.gameObject.activeSelf && this.gameObject.activeInHierarchy) {
                if(m_CurrentType != value) {
                    Unregister();
                    m_CurrentType = value;
                    Register();
                }
            } else {
                m_CurrentType = value;
            }
        }
        get {
            return(m_CurrentType);
        }
    }



    private void OnEnable() {
        Register();
    }



    private void OnDisable() {
        Unregister();
    }



    // Methods for registering on lister
    private void Register() {
        TargetablesLister.Instance.Register(this, m_CurrentType);
    }

    private void Unregister() {
        TargetablesLister.Instance.Unregister(this, m_CurrentType);
    }
}


All that the TargetableBehavior component does is to register itself in the lister when enabled, and unregister when disabled. Beginners to Unity might notice I made a protected member variable, m_CurrentType with the SerializeField attribute. I made the member variable non-public so I, or any other programmer, will not attempt to change it directly on code. This might avoid some bugs in the far future. However, I still want to be able to set it up on Inspector and save its value in prefabs or scene objects. Public variables are serialized and set to appear on Inspector by default, but I need the SerializeField attribute to serialize a protected or private member.

There's a nice property to change the type at runtime. I can't guarantee it is bug proof right now.

Now, to tie up our “automatic targeting system”, we need the TargetFetcherBehavior. This behavior will be stupid and inefficient. Why? Because I am making it solely for testing purposes. I want that different objects have the ability to own a target fetching algorithm that matches its behavior. But I don't have any special object right now, so it doesn't make sense to go around making customized targeting algorithms yet...

using UnityEngine;
using System.Collections;
using System.Collections.Generic;



/// <summary>
/// Dummy component that will be removed later. Here for testing
/// purposes.
/// </summary>
public class TargetFetcherBehavior : MonoBehaviour {
    // Message sent when a target is fetched
    public const string MsgSetTarget = "SetTarget";

    // Message target and options. We don't really need the option here
    // (could use DontRequireReceiver). But lets give this decision power
    // to our designers!
    public GameObject targetFetchedReceiver;
    public SendMessageOptions messageOptions;

    // Current type of this targeter
    public TargetTypes currentType;



    private void Update() {
        List<TargetableBehavior> targetsList = null;
        switch(currentType) {
        case TargetTypes.EnemyShip: 
            targetsList = TargetablesLister.Instance.GetTargets(TargetTypes.PlayerShip); break;
        case TargetTypes.PlayerShip:
            targetsList = TargetablesLister.Instance.GetTargets(TargetTypes.EnemyShip); break;
        }

        if(targetsList != null) {
            // We will simply search for the closest target
            TargetableBehavior currentTarget = null;
            float smallestSqrDist = float.PositiveInfinity;
            Vector3 pos = transform.position; // Small costless optimization

            for(int i = 0; i < targetsList.Count; ++i) {
                Vector2 dist = (Vector2) (pos - targetsList[i].transform.position);
                float sqrDist = dist.sqrMagnitude;
                if(sqrDist < smallestSqrDist) {
                    smallestSqrDist = sqrDist;
                    currentTarget = targetsList[i];
                }
            }

            // Send the target message. Yes, we will set a new target (even
            // if the same) every frame. This could be better, I know, but
            // this is a dummy class that most likely will be deleted later.
            // Or, at least, rewritten. Let me save some effort right now.
            if(currentTarget != null && targetFetchedReceiver != null) {
                targetFetchedReceiver.SendMessage(MsgSetTarget, currentTarget, messageOptions);
            }
        }
    }
}


The TargetFetcherBehavior simply searches for the nearest target available. Every frame. Don't place too many of them in the scene! Anyway, you can see that I added a constant string called MsgSetTarget. My constants starting with “Msg” means that they are messages used with SendMessage or BroadcastMessage. There're a few good things about making them a “named” constant instead of “magic values”, but the most important here is to make it clear to the coder that this object send this message.

Component Orientation works better when the component does not know about other components. The less each component needs to know about others, easier it is to reuse components on different objects. The problem then is how to call methods of other components, that you don't know what they are, or even if they exist? For solving this problem, Unity give us the SendMessage and BroadcastMessage methods. They are a blade that cut to either side, though. Any typo on the message or the receiving method name, and the message won't get through. When a component receives a message, it is very hard to know WHICH GameObject and component sent it – you'll need to use a stack trace and the Debug.Log ability of “flagging” objects (second argument). The MonoDevelop “FindReferences” won't help much, either.

You'll need to come up with small tricks and coding practices to reduce these errors. Things like SendMessageOptions.RequireReceiver for testing behaviors, making messages on code as named constants, and so on. Just like we need to know many “defensive” measures when programming inheritance and design patterns, we will also need to learn quite a few for components orientation.

Now, finally, our targeteer to aim at stuff!

using UnityEngine;
using System.Collections;



/// <summary>
/// Rotates the shortest distance to aim at a given target.
/// </summary>
public class TargeteerFullRotationBehavior : MonoBehaviour {
    // Related messages:
    // MsgSetTarget (in)

    // Targeting
    private TargetableBehavior m_CurrentTarget;
    private Transform m_CurrentTargetTransform; // Small optimization

    // Rotation settings
    [Tooltip("Speed of rotation, in degrees per second")]
    public float rotationSpeed;
    private float m_CurrentAngle;

    // Small optimization
    private Transform m_Transform;



    private void Awake() {
        m_Transform = this.transform;
        m_CurrentAngle = 0.0f;
    }



    private void Update() {
        // Aim at the target
        if(m_CurrentTarget != null) {
            Vector3 distance = m_CurrentTargetTransform.position - m_Transform.position;
            float targetAngle = Mathf.Atan2(distance.y, distance.x) * Mathf.Rad2Deg;
            m_CurrentAngle = Mathf.MoveTowardsAngle(
                m_CurrentAngle, targetAngle, rotationSpeed * Time.deltaTime
            );

            Vector3 currentRotation = m_Transform.eulerAngles;
            currentRotation.z = m_CurrentAngle;
            m_Transform.eulerAngles = currentRotation;
        } else {
            // Simple cleanup
            m_CurrentTargetTransform = null;
        }
    }



    /// <summary>
    /// Sets a target for this targeteer.
    /// [Possible Message]
    /// </summary>
    public void SetTarget(TargetableBehavior newTarget) {
        m_CurrentTarget = newTarget;
        m_CurrentTargetTransform = newTarget.transform;
    }
}


Very simple, right? This component receives a target with a SetTarget message sent by a target fetcher, and then takes the shortest turning angle to aim towards it. You'll see that I cached the targeteer owner transform, and the transform of the target as well. Every time you use “transform” (equivalent of this.transform, or somecomponent.transform), Unity will actually retrieve it as a GetComponent every time. So I just cached them since this is a very simple optimization. Lastly, if you look at the SetTarget method, I “flagged” it as “Possible Message”, so that I think it twice before renaming the method, or changing the parameters.

You can now place a few objects in the scene and move around to see their behavior.


This part got long already, so I'll do no more coding for now. As you can see, we created a simple targeting system that can work on its own. In the next part, we'll make some moving code for the player, as well as for the enemy ships. Again, we will try to make it component based. It will feel like we're writing more code than needed, but soon it will start to be worth it. Meanwhile, you can go on drawing a few nice sprites, heh? Till then!

The source of part two can be downloaded here.

Unity and Components Orientation Tutorial - Part One

Hello!

Ever since I've started to develop games on Unity, I've come across many tutorials here and there. Since I was already a somewhat experienced programmer by the time, I quickly outgrew them and started to use the manual and reference guide. After a couple of years, I knew a lot about Unity, but I lacked the knowledge to use its full power. And that's what this tutorial is about!

I've learned to develop on Unity by thinking as an Object Oriented programmer. The tutorials showed me how to do this. People around taught me how to do this. There was a glimpse of another paradigm that quickly I learned to recognize as “the round-about, bad style way of accomplishing something”. That paradigm was called Component Orientation.

Now, don't get me wrong. Object Orientation is not bad, but you CAN'T put Unity at its best if you don't use Component Orientation (Unity is a Component Based System, after all). And what's most troublesome, is that Objects Orientation and Components Orientation often does not get along well. If you're solving a problem with inheritance, for example, chances are that you're definitely wasting components potential!

So, I've decided to make this short series of tutorials in which I'll develop a top-down shooter game called Infinite Sail. In this series, I'll try to to convince you why Component Orientation is a good way to go, and how to think in this paradigm. However, I'm not a professional and even less a master in this paradigm myself, so I might not be able to use its full power.

Finally, I'll assume you already know how to program C# and the basics of Unity. I don't think things will get so complex, but I might omit things that I think that are too obvious, and you might need to research on them yourself if you're a newcomer (i.e Mathf.Atan2).

To keep things organized (in the blog), I'll finish this part here, and start the coding in the next post. See you there!

segunda-feira, 6 de outubro de 2014

Kitten Hopper has been released!



Released for Android, Koffee Bird is proud to announce a new game: Kitten Hopper! If you like kittens and the blue sky, you will definitely love this simple game! The game can be found in Google Play here. Hope you like it and have tons of fun!

segunda-feira, 26 de maio de 2014

Towards a Modified Simple Stupid Funnel Algorithm with Agent Radius

So, you have your pathfinding working. It returns a channel (series of polygons, edges or portals) that you can execute a funnel algorithm on to return the shortest path from start to end in that channel. If you are using a navmesh, its is often (if not nearly always) a better idea to simply grow your obstacles (shrink the navmesh) with a simple convex polygon that represents your agent size. Of course, there is the need of a navmesh specifically to each desired agent radius.

That being said, there is the famous Simple Stupid Funnel Algorithm posted by Mikko Mononen in the Digesting Duck blog. You won't need to account for agent radius since your channel already has it calculated for you, assuming that your navmesh has been shrunk by the agent radius beforehand. Even if it doesn't, there are ways to "fix" the path by using steering movements or other techniques. The internet is full of ideas.

Now, lets say you truly want your funnel algorithm to use the agent radius "on the fly". Things got really trickier, and chances are that have already read "Efficient Triangulation-Based Pathfinding", by Douglas Jon Demyen. In that thesis there is the pseudocode for the Modified Funnel Algorithm that uses agent radius, but if you are like me, you will have a hard time to understand and implement it from that. Another version was posted by jack_1313 on gamedev forums (http://www.gamedev.net/topic/548610-modified-funnel-algorithm/#entry4538426). Its pretty neat and should work fine - as long as your language allows using booleans as integers. There are some neat ways to solve this problem if it does not, but that is not important here.

Truth is, I found it really hard to find more examples of funnel algorithms that consider the agent radius. Based on the funnel algorithms cited above, I decided to try to make a version of my own. I used the Simple Stupid Funnel Algorithm as a starting point, and came back to the Modified Funnel Algorithm and jack_1313's code every time I hit a problem that I didn't know how to solve. As a result, I ended up with an algorithm that seems to work properly. I am unable to think in more tests situation in which it might break, right now. The code will be posted here in the hope that it helps other people to find different ways to solve this problem and share their code and/or ideas, so that this technique won't be such a "secret" anymore.

First I assume that the channel is always valid to that agent radius - that is, the pathfinding already has returned a channel where the agent is able to move. Since I am using pathfinding on a Constrained Delaunay Triangulation, I used the pseudocodes given by Demyen in his thesis during the pathfinding to know if the moving agent could or could not walk into a triangle from a given edge.

My channel is structured as an array of portals, or edges. Every (triangle) edge that the agent must cross to travel from starting position to destination is a portal. Portals are stored in pairs of consecutive elements in the array: even elements are 'left' vertex of the edge, and odd elements are the 'right' vertex of the edge. Left and right here are in channel's viewpoint. Since my edges are stored as counter-clockwise, it is easy to build this channel. The first portal (array indexes 0 and 1) are equal and the starting position of the channel. The last portal (last two indexes) are equal and the final position of the channel. I allow repeated vertices for channel building and traveling simplicity (as with the original Simple Stupid Funnel Algorithm).


List<HalfEdgeVertex> portals


The next problem is the return data of the funnel algorithm. It seems that many people desires that the funnel algorithm itself returns a path. I have no strong opinion on this matter, but I decided that my version won't return a path - it will return the apexes from the channel that the agent will "touch" while traveling the path. I then use this information to process the path the way I want. This gives some flexibility such as using the same funnel algorithm (with different paths processing, e.g flock movement or steering algorithms) for different objects types. With this information, it is entirely possible to plot an exact path while keeping a "radius" distance from the walls, too!

My return data is an array of instances of a data class:


public enum ApexTypes { Point, Left, Right }

public struct Apex {
    public HalfEdgeVertex vertex;
    public ApexTypes type;
}


The apex type flags if the touched apex was on the left or right side of the channel. The 'Point' type is special, used for the first and last apexes in the array (the starting and ending points of the channel). As the apex position, I store the navmesh vertex itself. Not really elegant, but...

First, I will post a direct conversion of the Simple Stupid Funnel Algorithm to my project, so that the changes made to force up agent radius in this becomes easier to spot.


// Using lists since they can be cleared, and will not need
// reallocation of size until it grows bigger than it ever
// was during the game execution. End position is added twice (left and right). Note
// That the first two and last two elements of the portals list are NOT valid mesh vertices.
// Portals format: for a portal i
//     portal[i] = left side
//     portal[i+1] = right side
//
// This algorithm is basically the Simple Stupid Funnel Algorithm posted by
// Mikko in the Digesting Duck blog.
static public void 
Funnel(List<HalfEdgeVertex> portals, ref List<Apex> contactVertices) {
    HalfEdgeVertex portalApex = portals[0];
    HalfEdgeVertex portalLeft = portals[0];
    HalfEdgeVertex portalRight = portals[1];
    
    int portalLeftIndex = 0;
    int portalRightIndex = 0;
    
    // Put the first point into the contact list
    Apex startApex = new Apex();
    startApex.vertex = portalApex;
    startApex.type = ApexTypes.Point;
    
    contactVertices.Clear();
    contactVertices.Add(startApex);

    Vector2 previousValidLSegment = Vector2.zero;
    Vector2 previousValidRSegment = Vector2.zero;
    
    
    
    for(int i = 2; i < portals.Count; i += 2) {
        HalfEdgeVertex left = portals[i];
        HalfEdgeVertex right = portals[i+1];
        
        Vector2 currentLSegment = left.position - portalApex.position;
        Vector2 currentRSegment = right.position - portalApex.position;
        
        
        //Right side
        // Does new 'right' reduce the funnel?
        if(MyMath2D.CrossProduct2D(previousValidRSegment, currentRSegment) > -MyMath2D.tolerance) {
            // Does it NOT cross the left side?
            // Is the apex the same as portal right? (if true, no chance but to move)
            if(
                portalApex == portalRight ||
                MyMath2D.CrossProduct2D(previousValidLSegment, currentRSegment) < MyMath2D.tolerance
            ) {
                portalRight = right;
                previousValidRSegment = currentRSegment;
                portalRightIndex = i;
            } else {
                // Collapse
                portalApex = portalLeft;
                portalRight = portalApex;
                
                Apex apex = new Apex();
                apex.vertex = portalApex;
                apex.type = ApexTypes.Left;
                contactVertices.Add(apex);
                
                portalRightIndex = portalLeftIndex;
                i = portalLeftIndex;
                
                previousValidLSegment = Vector2.zero;
                previousValidRSegment = Vector2.zero;
                
                continue;
            }
        }
        
        // Left Side
        // Does new 'left' reduce the funnel?
        if(MyMath2D.CrossProduct2D(previousValidLSegment, currentLSegment) < MyMath2D.tolerance) {
            // Does it NOT cross the right side?
            // Is the apex the same as portal left? (if true, no chance but to move)
            if(
                portalApex == portalLeft ||
                MyMath2D.CrossProduct2D(previousValidRSegment, currentLSegment) > -MyMath2D.tolerance
            ) {
                portalLeft = left;
                previousValidLSegment = currentLSegment;
                portalLeftIndex = i;
            } else {
                // Collapse
                portalApex = portalRight;
                portalLeft = portalApex;
                
                Apex apex = new Apex();
                apex.vertex = portalApex;
                apex.type = ApexTypes.Right;
                contactVertices.Add(apex);
                
                portalLeftIndex = portalRightIndex;
                i = portalRightIndex;
                
                previousValidLSegment = Vector2.zero;
                previousValidRSegment = Vector2.zero;
                
                continue;
            }
        }
    }
    
    // Put the first point into the contact list
    Apex endApex = new Apex();
    endApex.vertex = portals[portals.Count - 1];
    endApex.type = ApexTypes.Point;
    contactVertices.Add(endApex);
}


If you actually had read this code and the original Simple Stupid Funnel Algorithm, you will see some differences. First, I use a "2d cross product", to know if a vector is clockwise or counter-clockwise from another. Second, I use vectors as in jack_1313's code. This is probably slower than using direct coordinates, but it made the code easier to debug.

Now, to put agent radius in this, its as simple as "considering each apex a circle". It was a long way until I got convinced of this. Really. Pure math fun. We need a way to calculate the tangents from one apex to another. Basically, let A and B be circle center positions, and P a point, you will need the following math methods:
- Inner tangent from A to B
- Outer tangent from A to B (this one is easy)
- Tangent that touches circle (A or B) and passes through P (start and end of channel).

I put all these hours of pure fun using vector math (to avoid using atan2, though vectors normalization can pile up and be as slow) in a single mighty method called GetTangentPoints. The rest of the algorithm is basically the same as the original one, but now double-sized to consider each special case that the agent radius brought to us. Naturally, this algorithm is slower than the original one, too.


// This algorithm is basically the Simple Stupid Funnel Algorithm posted by
// Mikko in the Digesting Duck blog. This one has been modified to account for agent radius.
static public void Funnel(float radius, List<HalfEdgeVertex> portals, ref List<Apex> contactVertices) {
    // In some special cases, it is possible that the tangents of the apexes will
    // cause the funnel to collapse to the left or right portal right before going to
    // the final position. This happens when the final position is more 'outward' than
    // the vector from the apex to the portal extremity, and the final position is
    // actually 'closer' to the previous portal than the 'current' portal extremity.
    // If that happens, we remove the portal before the last from the list. I have no
    // proof that this guarantees the correct behavior, though.
    if(portals.Count >= 8) {
        // This seems to be possible to happen only when there are 4 or more
        // portals (first and last are start and destination)
        int basePortal = portals.Count - 6;
        int lastPortal = portals.Count - 4;
        int destinationPortal = portals.Count - 2;

        // First, check left
        Vector2 baseLast = portals[lastPortal].position - portals[basePortal].position;
        Vector2 baseDest = portals[destinationPortal].position - portals[basePortal].position;
        if(baseDest.sqrMagnitude < baseLast.sqrMagnitude) {
            portals.RemoveRange(lastPortal, 2);
        } else {
            // Now check right
            baseLast = portals[lastPortal+1].position - portals[basePortal+1].position;
            baseDest = portals[destinationPortal+1].position - portals[basePortal+1].position;
            if(baseDest.sqrMagnitude < baseLast.sqrMagnitude) {
                portals.RemoveRange(lastPortal, 2);
            }
        }
    }


    HalfEdgeVertex portalApex = portals[0];
    HalfEdgeVertex portalLeft = portals[0];
    HalfEdgeVertex portalRight = portals[1];
    
    int portalLeftIndex = 0;
    int portalRightIndex = 0;
    
    // Put the first point into the contact list
    Apex startApex = new Apex();
    startApex.vertex = portalApex;
    startApex.type = ApexTypes.Point;
    
    contactVertices.Clear();
    contactVertices.Add(startApex);
    
    ApexTypes currentType = ApexTypes.Point;
    Vector2 previousValidLSegment = Vector2.zero;
    Vector2 previousValidRSegment = Vector2.zero;
    
    
    
    for(int i = 2; i < portals.Count; i += 2) {
        HalfEdgeVertex left = portals[i];
        HalfEdgeVertex right = portals[i+1];

        ApexTypes nextLeft = ApexTypes.Left;
        ApexTypes nextRight = ApexTypes.Right;
        if(i >= portals.Count - 2) {
            // Correct next apex type if we are at the end of the channel
            nextLeft = ApexTypes.Point;
            nextRight = ApexTypes.Point;
        }

        // Build radius-inflated line segments
        Vector2 tempA = portalApex.position, tempB = left.position;
        GetTangentPoints(
            tempA, tempB, currentType, nextLeft, radius, out tempA, out tempB
        );
        Vector2 currentLSegment = tempB - tempA;

        tempA = portalApex.position; tempB = right.position;
        GetTangentPoints(
            tempA, tempB, currentType, nextRight, radius, out tempA, out tempB
        );
        Vector2 currentRSegment = tempB - tempA;
        
        
        //Right side
        // Does new 'right' reduce the funnel?
        if(MyMath2D.CrossProduct2D(previousValidRSegment, currentRSegment) > -MyMath2D.tolerance) {
            // Does it NOT cross the left side?
            // Is the apex the same as portal right? (if true, no chance but to move)
            if(
                portalApex == portalRight ||
                MyMath2D.CrossProduct2D(previousValidLSegment, currentRSegment) < MyMath2D.tolerance
            ) {
                portalRight = right;
                previousValidRSegment = currentRSegment;
                portalRightIndex = i;
            } else {
                // Collapse
                if(currentRSegment.sqrMagnitude > previousValidLSegment.sqrMagnitude) {
                    portalApex = portalLeft;
                    portalRight = portalApex;
                    
                    Apex apex = new Apex();
                    apex.vertex = portalApex;
                    apex.type = ApexTypes.Left;
                    contactVertices.Add(apex);

                    currentType = ApexTypes.Left;
                    
                    portalRightIndex = portalLeftIndex;
                    i = portalLeftIndex;
                } else {
                    portalRight = right;
                    previousValidRSegment = currentRSegment;
                    portalRightIndex = i;

                    portalApex = portalRight;
                    portalLeft = portalApex;
                    
                    Apex apex = new Apex();
                    apex.vertex = portalApex;
                    apex.type = ApexTypes.Right;
                    contactVertices.Add(apex);
                    
                    currentType = ApexTypes.Right;
                    
                    portalLeftIndex = portalRightIndex;
                    i = portalRightIndex;
                }

                previousValidLSegment = Vector2.zero;
                previousValidRSegment = Vector2.zero;

                continue;
            }
        }
        
        // Left Side
        // Does new 'left' reduce the funnel?
        if(MyMath2D.CrossProduct2D(previousValidLSegment, currentLSegment) < MyMath2D.tolerance) {
            // Does it NOT cross the right side?
            // Is the apex the same as portal left? (if true, no chance but to move)
            if(
                portalApex == portalLeft ||
                MyMath2D.CrossProduct2D(previousValidRSegment, currentLSegment) > -MyMath2D.tolerance
            ) {
                portalLeft = left;
                previousValidLSegment = currentLSegment;
                portalLeftIndex = i;
            } else {
                // Collapse
                if(currentLSegment.sqrMagnitude > previousValidRSegment.sqrMagnitude) {
                    portalApex = portalRight;
                    portalLeft = portalApex;
                    
                    Apex apex = new Apex();
                    apex.vertex = portalApex;
                    apex.type = ApexTypes.Right;
                    contactVertices.Add(apex);

                    currentType = ApexTypes.Right;
                    
                    portalLeftIndex = portalRightIndex;
                    i = portalRightIndex;
                } else {
                    portalLeft = left;
                    previousValidLSegment = currentLSegment;
                    portalLeftIndex = i;

                    portalApex = portalLeft;
                    portalRight = portalApex;
                    
                    Apex apex = new Apex();
                    apex.vertex = portalApex;
                    apex.type = ApexTypes.Left;
                    contactVertices.Add(apex);
                    
                    currentType = ApexTypes.Left;
                    
                    portalRightIndex = portalLeftIndex;
                    i = portalLeftIndex;
                }

                previousValidLSegment = Vector2.zero;
                previousValidRSegment = Vector2.zero;

                continue;
            }
        }
    }
    
    // Put the last point into the contact list
    if(contactVertices[contactVertices.Count - 1].vertex == portals[portals.Count-1]) {
        // Last point was added to funnel, so we need to change its type to point
        Apex endApex = new Apex();
        endApex.vertex = portals[portals.Count-1];
        endApex.type = ApexTypes.Point;
        contactVertices[contactVertices.Count-1] = endApex;
    } else {
        // Last point was not added to funnel, so we add it
        Apex endApex = new Apex();
        endApex.vertex = portals[portals.Count - 1];
        endApex.type = ApexTypes.Point;
        contactVertices.Add(endApex);
    }
}


That's it. A channel special case treating (right at the start of the method), new conditionals to know if we are arriving at the end of the channel, two new "collapsing" codes (one for left apex, another for right apex) and a final correction if the last point is or is not in the contact list, that I don't know what causes it to sometimes be there and other times not.

Finally, my method to build the path with agent radius. Yeah, I calculate the tangents all over again...


static public void BuildPath(float radius, List<Apex> contactVertices, ref List<Vector2> path) {
    path.Clear();

    // My channel actually goes from path end to path start, so I need to
    // invert all the apexes sides...

    // Add first node
    path.Add(contactVertices[contactVertices.Count - 1].vertex.position);
    
    for(int i = contactVertices.Count - 2; i >= 0; --i) {
        Vector2 positionA = Vector2.zero, positionB = Vector2.zero;

        ApexTypes invertedA = contactVertices[i+1].type;
        ApexTypes invertedB = contactVertices[i].type;

        if(invertedA == ApexTypes.Left) invertedA = ApexTypes.Right;
        else if(invertedA == ApexTypes.Right) invertedA = ApexTypes.Left;

        if(invertedB == ApexTypes.Left) invertedB = ApexTypes.Right;
        else if(invertedB == ApexTypes.Right) invertedB = ApexTypes.Left;


        GetTangentPoints(
            contactVertices[i+1].vertex.position, contactVertices[i].vertex.position,
            invertedA, invertedB, radius, out positionA, out positionB
        );
        path.Add(positionA);
        path.Add(positionB);
    }
}


This post got quite long already. Way longer than I intended it to be. In the next post, I will write about the special situations that appeared while trying to make the funnel algorithm to use the agent radius, and relate them with the code posted here. As I said previously, this algorithm is not guaranteed to be fail proof as there might be special cases that I didn't cross or think while testing. I hope that this helps someone to come up with different funnel algorithms and maybe share through the internet.

segunda-feira, 19 de maio de 2014

Why would we like dot product? Part 3

Finally, this is the third part of things you can do with dot product. I had some difficulty in deciding what to post here. Most tricks would either be slight variations of what has been said in part two, or dot product would be only a helping tool in a complex set of calculations (take Separating Axis Tests, for example). As a result, I have a feeling that this post will be the last post about dot product alone.


Closest point of a line segment to another point


Sometimes, you will find a problem that can be solved (or reduced) by knowing the point of a line segment that is closest to another point. With this information, you can build up usable data as distance and direction between the points. Suppose, for example, a 2d top view game. As long as obstacles can be modeled as line segments, you can calculate the distance from an object (i.e the player) from the obstacle. If the object is too close, you move it a little so the object and the obstacle do not overlap.

There are numerous way of calculating the closest point of a point to a line segment, and one of them is with dot products. I will post here code for 3d checking, as converting it to 2d, if needed, is really simple. What we will need to find the closest point is:

 - Vector3 testPoint: the point that we will check the segment against.
 - Vector3 segmentStart: starting position of the line segment. This is one of the segment extremity points.
 - Vector3 segmentEnd: ending position of the line segment. This is the other segment extremity point.


Since the calculation is simple, the requisites are also simple - however the magic behind them can be rather tricky to understand. When you calculate a dot product between two normalized vectors, the resulting value is the cosine between them. If the vectors aren't normalized, you don't have the cosine, but you can still get some useful information about their relationship:

 - Product is a positive value, so the angle between the vectors is less than 90 degrees.
 - Product is zero, so the angle between the vectors is exactly 90 degrees (aka never in computer calculations).
 - Product is a negative number, so the angle between the vectors is more than 90 degrees (not bigger than 180 degrees).


So, what we do is calculate the dot product between the line segment against two vectors created with the test point and each of the line segment extremities. If, when calculating, the dot product is zero or negative, then we know that the segment extremity currently being used in the calculations is also the closest point to the testing one. If both dot products are positive, then the closest point is somewhere between the the two points that defines the segment.


We first calculate our line segment as a vector, to do the calculations:

Vector3 segment = segmentEnd - segmentStart;


Next, we create new vectors with the testing point and the segment extremities, in order to check if any of them is also the closest point:

Vector3 pointToSegmentStart = testPoint - segmentStart;
float dotPointToStart = Vector3.Dot(pointToSegmentStart, segment);
if(dotPointToStart <= 0) return(segmentStart);

Vector3 pointToSegmentEnd = segmentEnd - testPoint;
float dotPointToEnd = Vector3.Dot(pointToSegmentEnd, segment);
if(dotPointToEnd <= 0) return(segmentEnd);


Notice that none of the vectors are normalized. This is important when the closest point actually is between the two segment extremities. Now curse the math. You can actually use the dot products (that came from non normalized vectors) to calculate the closest point, by means of a interpolation.

Vector3 resultingPoint = Vector3.zero;

resultingPoint.x = segmentStart.x + ((segment.x * dotPointToStart) /
    (dotPointToStart + dotPointToEnd));
resultingPoint.y = segmentStart.y + ((segment.y * dotPointToStart) /
    (dotPointToStart + dotPointToEnd));
resultingPoint.z = segmentStart.z + ((segment.z * dotPointToStart) /
    (dotPointToStart + dotPointToEnd));

return(resultingPoint);


The interpolation will return the point of the line segment that is closest to our testing point. The full code follows:


static public Vector3 ClosestPointToSegment(
    Vector3 testPoint, Vector3 segmentStart, Vector3 segmentEnd
) {
    Vector3 segment = segmentEnd - segmentStart;
    
    Vector3 pointToSegmentStart = testPoint - segmentStart;
    float dotPointToStart = Vector3.Dot(pointToSegmentStart, segment);
    if(dotPointToStart <= 0) return(segmentStart);
    
    Vector3 pointToSegmentEnd = segmentEnd - testPoint;
    float dotPointToEnd = Vector3.Dot(pointToSegmentEnd, segment);
    if(dotPointToEnd <= 0) return(segmentEnd);
    
    Vector3 resultingPoint = Vector3.zero;
    resultingPoint.x = segmentStart.x + ((segment.x * dotPointToStart) /
        (dotPointToStart + dotPointToEnd));
    resultingPoint.y = segmentStart.y + ((segment.y * dotPointToStart) /
        (dotPointToStart + dotPointToEnd));
    resultingPoint.z = segmentStart.z + ((segment.z * dotPointToStart) /
        (dotPointToStart + dotPointToEnd));
    return(resultingPoint);
}



Efficiency wise, this way of calculating distance can be pretty fast on gpus, since they are magical with dot products. However, if you are truly worried with performance and/or precision, testing and profiling is strongly advised.