Behavior Trees

Animated story :
This is a story between two legends - Mr.Samurai Sama and Mr.Dead Shot. One day Samurai sama meets with Dead Shot and they talk about a lot of stuff for sometime. In the conversation, Dead shot did a mistake of insulting Samurai sama. Samurai sama shouts and Dead shot and they both leave that place angry.
Dead shot consumed by anger, plans to kill Samurai sama with his gun. Samurai sama notices Dead shot walking towords him with a gun. He senses that something is wrong and quickly hides behind a wall and draws his katana. When Dead shots walks in, Samurai sama slowly sneaks up behind him and swiftly slashes Dead shot. The End. Implementation affordance like sitting, drawing katana, holding on to something, attacking. Here is the YouTube link of our game.

The online deployment of the game can be found here. and the git repository here.

Pathfinding using A-star

In this assignment, we implement A-star algorithm for finding the path in a grid environment.

A brief discussion about the A-star algorithm (From wikipedia)

A* uses a best-first search and finds a least-cost path from a given initial node to one goal node (out of one or more possible goals). As A* traverses the graph, it builds up a tree of partial paths. The leaves of this tree (called the open set or fringe) are stored in a priority queue that orders the leaf nodes by a cost function, which combines a heuristic estimate of the cost to reach a goal and the distance traveled from the initial node. Specifically, the cost function is

.

Here, g(n) is the known cost of getting from the initial node to n; this value is tracked by the algorithm. h(n) is a heuristic estimate of the cost to get from n to any goal node. For the algorithm to find the actual shortest path, the heuristic function must be admissible, meaning that it never overestimates the actual cost to get to the nearest goal node. The heuristic function is problem-specific and must be provided by the user of the algorithm.

We first used two heuristics, namely  Manhattan distance and Euclidean distance as they both are admissible and consistent heuristic.  Then we proceeded to compare the results of weighted heuristics. Following are some video clips demonstrating our results.

Using Eucliedian as heuristic

                                      

                                                       Using Manhattan as heuristic

Next, we checked how different ways of resolving the ties(with same lowest f-value) would imapct the solution

                                      

Tie breaking in favour of smaller 'g'

Tie breaking in favour of larger 'g'

In the final part we dicuss how altering the weight of the heuristic function affects the optimality and speed of the search.  Please refer the follwing table which compares the pathlength/#nodesexpanded against various weights of the heuristic. 

We observe that with the increase in the weight of heuristic function, the number of nodes expanded decreases as evident from the table shown above. However, the path returned is not optimal as the path increases with the increase in weights. This is due the fact the heuristic is now no longer admissible. 

Social Forces Implementation

As a part of course assignment, the Social Forces model has been implemented for obstacle avoidance. The model is then tested in various bottleneck test cases.

The Algorithm :

The Social Forces model computes various forces exerted on a agent by the environment. It then adds the exerted force with the force  required by the agent to reach the goal(F_pref) .

F = F_goal + F_agents + F_walls

F_agents & F_walls includes the proximity force, repulsion force(in case of collision) and sliding friction force(in case of collision) by obstacles/other agents.

Code : https://github.com/CG-F15-10-Rutgers/SteerLite (Forked from SteerLite parent repo)

The model is run against several test cases and the results are recorded. Following are the video links :

(a) Hallway one-way

(b) Hallway two-way

(c) Hallway four-way

(d) Bottleneck evacuation

Futher improvements : The efficiency can be further improved by tweaking the constant parameters of the Social Forces algorithm as per  the use-case.

Collision Detection using GJK and EPA algorithm

For collision detection we implemented the GJK(Gilbert-Jhonson-Keerthi) algorithm. The Algorithm makes use of the concept of Minkowski-difference of two convex objects, i.e if two convex objects intersect, then the Convex Hull of the Minkowski difference encompasses the origin. 


We used SteeeLite API (​https://github.com/SteerSuite/SteerLite.git) and implemented the GJK algorithm in the collision AI module. For finding the collision depth for intersecting polygons, we implemented the EPA algorithm.

Here are some screen-shots of our implementation and results.

For the situation described in figure 1, the GJK algorithm gives us the collision results as expected.

                                                       Fig 2

For the situation described in Figure 2, the GJK reports a collision b/w the polygons, whereas in reality there is no collision. This is due the fact that the polygons are concave. To solve the problem, we decompose the concave polygon to the left into two convex polygons(two triangles) and then run the GJK.

After convex decomposition we get the result of no collision.

Navigation Meshes and Crowd Simulation

As a part of our course project, we were asked to  design a relatively complex environment using different obstacle configurations for crowd simualtion.

Our environment consists of a scene with two levels,  navigation static containers(on top of which agents can move/jump), multiple bottleneck areas.

We created an "Agent" prefab with NavMeshAgent component to allow agents to navigate in
the environment while using the navigation mesh and then created a script to select agents and specify which destination to navigate towards. For this we capitalized on the concept of Ray Casting.


The next part of the project, was to get a good grip about Unity's Mecanim Animation System and
create an animated human character using Mecanim.
This was done by taking a humanoid character, importing  its animation data onto the humanoid and then create an animation state machine to have him walk, run, jump. A controller script was created where a player can control the character using arrow keys,run modifiers (shift key) and SPACE to jump.
A “third person” camera is implemented and attached to the character to give an RPG feel.


In the last part, we integrated our prefab into our crowd simulator to create a crowd of directable animated characters. Double right clicking the destination will make the agent sprint towards it.

Please click the following link for the web deployed version of our Game,
https://dl.dropboxusercontent.com/s/dedu824xex8kdsw/builds.html

P.S Please use Mozilla Firefox for best results.