FINAL PROJECT: Interactive Narrative

Computer Graphics 
Group 40 

Overview of Project: In this project we had three important parts. The first part included authoring a story with a crowd of characters. This is described in the Story Section below. The second part required transforming our story into an interactive narrative. We provide a video below to demonstrate this section. Lastly, the third part asks multiple character control, where the human user can control any character during the game and seamlessly switch to other character. 
Our Story (Part 1):

 Our story takes place in an ancient dungeon which has been set on fire. There are five men who are stuck in this dungeon, as the doors won’t open.

                                They convene to discuss methods of escaping the dungeon.

Unfortunately, they begin to all panic as they are frightened with the danger of their situation.

 One courageous man raises his hand and gives a speech saying that they must not give up. He remembers that there was a gold lamp on the upper floor that might be a secret key for the doors.

Another man steps up and goes upstairs to retrieve the lamp. Immediately after touching the lamp, the door to exit the dungeon opens

They all leave the dungeon, happy that they were able to escape.

Our Behavior Tree: 

Character/Object Capabilities:

Part 1: 

Our characters are controlled by the behavior tree and by human control. In this part, the character that raises his hand is completely random, and thus changes on every play. The character that bravely goes to the lamp is also random and changes on every play. 

Part 2/3: 

In Parts 2 and 3, the user can select which character goes to touch the lamp and thus open the door. Right clicking switches from the original character to the next character, making it possible to switch to any character in the middle of the game. Left clicking on the environment makes the selected character move to that location. Multiple characters can change their locations at the same time. The door is capable of opening only after the lamp has been touched. The lamp serves as a trigger for the characters escape. 

Part 1 Video: This video demonstrates our story. 

https://www.youtube.com/watch?v=RzK-FzLfU5g&feature=youtu.be

Part 2 Video: This video accurately shows the interactive narrative with the characters and our story. 

https://www.youtube.com/watch?v=3cX9XUSaP8g&feature=youtu.be

Part 3 Video: This video shows the multi character control functionality. 

https://www.youtube.com/watch?v=teoNnVSNa3o&feature=youtu.be

Play if you'd like on the web player!!! 

https://rawgit.com/CG-F15-40-Rutgers/UnityProjects/master/BAssignments/B3/Web_Build/Web_Build.html

Computer Graphics

Group 40 Documentation

A5: Crowd Simulation Challenge

Part 1: 
In this assignment, we created and evaluated an end-to-end crowd simulator in SteerLite by implementing A* algorithms and by enhancing the existing social forces module. One of the key changes we made to the sfAI module was enabling the useLongTermPlanning function, allowing our agents to plan their respective paths from the beginning of the test case. The projected paths were viewed by clicking on individual agents while the test case was running. Lastly, we also tweaked different constants in the social forces implementation file for specific test cases. 

Plane_Egress: 

Plane_Ingress: 

Crowd Crossing: 

Office Complex: 

Bottleneck Squeeze: 

Doorway Two Way: 

Double Squeeze: 

Wall Squeeze: 

Hallway Two Way: 

Maze: 

For Part B, we created our very own test case. We wanted to implement a more real life scenario, so we chose a crowd of people attending a huge event at MSG in NYC -  thousands of people swarm around buildings, onto roads, and into the entrance of the venue (red cylinder). 

NYC Crowd: 

Our YouTube Links for ALL our test cases!! 

plane_egress: https://youtu.be/Q8P9up6zsSo
plane_ingress: https://youtu.be/GCq_vpNXkzA
crowd_crossing: https://youtu.be/W5n35jEm_QA
office_complex: https://youtu.be/yvr2Fd5BOwg
bottleneck_squeeze: https://youtu.be/M1gFR6vfTd0
doorway_two_way: https://youtu.be/2Yp6MDcIJWQ
double_squeeze: https://youtu.be/IvGDcCaAQBI
wall_squeeze: https://youtu.be/cXGSkmNwa6k
hallway_two_way: https://youtu.be/YdlR2gEmMPI
maze: https://youtu.be/wUcvZn9ooIA
a5-testcase: https://youtu.be/g2Ll0k9Cjk4

Computer Graphics

Group 40 Documentation

A4: Path Finding 

In this assignment, we implemented the A* Search algorithm with both the Euclidean and Manhattan distances. The A* Search can be thought of as the following equation: f(n) = g(n)+ h(n), where g(n) represents the exact cost of the path from the starting point to any vertex n, and h(n) represents heuristic estimated cost from any vertex n to the goal. A* computes f(n) at every node to find the most optimal path. The Euclidean distance can be defined as a straight line between 2 points. The Manhattan distance between two points is the sum of the (absolute) differences of their coordinates. E.g. it only costs 1 unit for a straight move, but 2 if one wants to take a crossed move.

We ran our A* search algorithm across two test cases - Search 1 and Search 2. 

Search 1

Search 2

As can be seen from the images above, Search 2 is more complex than Search 2, in that it is longer in length and has many more diagonals/turns. 

There were four different parts to our project for this week. For Part 1, we executed the test cases under normal conditions. For Part 2, we implemented tie breakers for a larger g and a smaller g (separately). For Part 3, we implemented a higher cost for diagonals and used a larger g to break ties. And lastly, in Part 4, we weighted the heuristic by 2, 4, and 8. For each of these different parts, we documented our results (number of expanded nodes and the path lengths) for each search. 

Results

Table 1: Number of Expanded Nodes

Part	Description	Euclidean Search 1	Euclidean Search 2	Manhattan Search 1	Manhattan Search 2
1	Normal	2188	12106	2104	11887
2	Smaller g	2188	12107	2104	11887
	Larger g	2188	12107	2104	11887
3	Higher d cost; Bigger g for ties	2284	8952	1696	5406
4	h Weight 2	2165	11931	2157	11921
	h Weight 4	2081	11496	2086	11574
	h Weight 8	1938	10768	2002	11054

For Parts 1, 2, and 4, the path lengths are the following:

Search 1 Path Length = 3507.34

Search 2 Path Length = 10398.9

For Part 3, the path lengths are the following:

Search 1 Path Length = 5191.63

Search 2 Path Length = 12358.9

Discussion 

The Manhattan Distance has a higher cost for diagonals, and since our test cases mostly move up, down, left and right, it’s obvious that the number of expanded nodes in the normal condition is less for the Manhattan distance than the Euclidean. For these test cases, as we choose how to break ties based on smaller or larger g, there seems to be no change in the number of expanded nodes. It is also clear from the table that as the heuristic weight increases, the number of expanded nodes decreases for each search type. What’s interesting to note is that as the heuristic weight increases, the Euclidean distance expands less nodes than the Manhattan distance. Thus, as the heuristic weight increases, the shortest path expands less nodes than the path which moves only horizontally and vertically. This is because as h increases, the algorithm becomes greedier at each node, and looks for the next best node, rather than the best distance to the goal. Consequently, the Euclidian distance will provide equal cost for diagonals and find the next best node at the corners of the obstacles, while the Manhattan will move up and down rather than diagonal and use more nodes at the corners of the obstacles.

Additionally, the table shows that increases in the cost of diagonals drastically decreases the number of expanded nodes while increasing the path lengths. This is because the agent will avoid moving diagonally and thus expand much less nodes. And consequently, will increase the path distance as it prefers moving only vertically and horizontally. This is the only part that changed the path significantly since the path length increased; this can be seen in the videos provided above. ­­­­

Check out some of our videos! 

Part 1

·       Euclidean search 1: https://youtu.be/xVCbFbdH_rQ

·       Euclidean search 2: https://youtu.be/kdkg7oS9Pd4

·       Manhattan search 1: https://youtu.be/49dnRvyF-yY

·       Manhattan search 2: https://youtu.be/9SL1TpkhIYc

Part 2

·       Manhattan, smaller g search 1: https://youtu.be/llcDSHg8i5s

·       Manhattan smaller g search 2: https://youtu.be/4HFVgrteI-g

·       Manhattan larger g search 1: https://youtu.be/ijEQ9sZCz8g

·       Manhattan larger g search 2: https://youtu.be/M40jCsFxuXI

·       Euclidean smaller g search 1: https://youtu.be/UT7Vtf4_3Ag

·       Euclidean smaller g search 2: https://youtu.be/FZ1wxkJxmGs

·       Euclidean larger g search 1: https://youtu.be/5ADcxDi6T4U

·       Euclidean larger g search 2: https://youtu.be/RH9OVLHNSZY

Part 3

·       Euclidean search 1: https://youtu.be/Sa9uoKjolaM

·       Euclidean search 2: https://youtu.be/ffGKh3YtItA

·       Manhattan search 1: https://youtu.be/xdNKSOZvPEE

·       Manhattan search 2: https://youtu.be/BPWrqGuVUjM

 Part 4

·       Manhattan weight 2 search 1: https://youtu.be/ltyMCohuT-s

·       Manhattan weight 2 search 2: https://youtu.be/8GcWHVwrOIo

·       Manhattan weight 4 search 1: https://youtu.be/k_BgeZkeo44

·       Manhattan weight 4 search 2: https://youtu.be/4YU_0kH26JQ

·       Manhattan weight 8 search 1: https://youtu.be/ZCerTgYp4IU

·       Manhattan weight 8 search 2: https://youtu.be/zj1PbMcdlC4

·       Euclidean weight 2 search 1: https://youtu.be/zZseKH5Cc8o

·       Euclidean weight 2 search 2: https://youtu.be/RLjyouXTHQk

·       Euclidean weight 4 search 1: https://youtu.be/ZJ0gcqv3czs

·       Euclidean weight 4 search 2: https://youtu.be/Y0xI0_TK-Ss

·       Euclidean weight 8 search 1: https://youtu.be/VeaOjwvfmPc

·       Euclidean weight 8 search 2: https://youtu.be/e2eV9VTSW0E

                                                    

Computer Graphics

Group 40 Documentation

A3: Social Forces

                         
Description: In this assignment, we implemented four important function for social forces - calcWallRepulsion, calcAgentRepulsion, calcGoalForce, and calcProximity.

We define social forces as forces that we exert on particles to drive them towards their destination while avoiding agents and obstacles. 

Each of these functions provides the components for the equation: 

social force = collision avoidance + non-penetration + sliding force

We treated walls as obstacles and other agents as agents and solved social force equations for each of these. For agents and walls, the collision avoidance component is considered the proximity force and the non-penetration component as the repulsion force. These are applied back into the social force equation, along with the calcGoalForce which directs the force for the goal destination. 

For each of the following test cases, we applied a scoring script that gave us the overall score for the scene.  

One Way Hallway: 

One Way Hallway Scores: 

total number of agents: 200
avg. number of collisions per agent: 0
    average time spent by one agent: 84.3662
  average energy spent by one agent: 1501.66
 sum of instantaneous accelerations: 9.28161
(alpha, beta, gamma, delta) weights: (50,1,1,1)
                       weighted sum: 50*0 + 1*84.3662 + 1*1501.66 + 1*9.28161 =
1595.31
                        final score: 1595.31

Two Way Hallway: 

Two Way Hallway Scores:

total number of agents: 200
avg. number of collisions per agent: 0
    average time spent by one agent: 73.5943
  average energy spent by one agent: 1213.45
 sum of instantaneous accelerations: 244.974
(alpha, beta, gamma, delta) weights: (50,1,1,1)
                       weighted sum: 50*0 + 1*73.5943 + 1*1213.45 + 1*244.974 = 1532.01
                        final score: 1532.01

Four Way Hallway: 

Four Way Hallway Scores: 

total number of agents: 400
avg. number of collisions per agent: 0.015
    average time spent by one agent: 83.8544
  average energy spent by one agent: 1291.23
 sum of instantaneous accelerations: 487.834
(alpha, beta, gamma, delta) weights: (50,1,1,1)
                       weighted sum: 50*0.015 + 1*83.8544 + 1*1291.23 + 1*487.833 = 1863.67
                        final score: 1863.67

Bottleneck Evacuation:

Bottleneck Evacuation Scores: 

total number of agents: 200
avg. number of collisions per agent: 6.115
    average time spent by one agent: 99.9456
  average energy spent by one agent: 1256.3
 sum of instantaneous accelerations: 2121.33
(alpha, beta, gamma, delta) weights: (50,1,1,1)
                       weighted sum: 50*6.115 + 1*99.9456 + 1*1256.3 + 1*2121.33 = 3783.32
                        final score: 3783.32

Here are some links to view the simulations! 

One Way Hallway: https://www.youtube.com/watch?v=LLyWknD17gk
Two Way Hallway: https://www.youtube.com/watch?v=3zrMY31haKI
Four Way Hallway: https://www.youtube.com/watch?v=JW5SpJrBHBI
Bottleneck Evacuation: https://www.youtube.com/watch?v=cIEwulbXuGU