B3: Final Interactive Narratives

Group: CG-F15-1

Members: Tolby Lew, Firas Sattar, Brian Ho

Documentation:

Part 1:

Story World Descriptions:

Our story takes place on a city street. Note the casual characters walking along the sidewalks, enjoying their day. However, one city man chooses the unwise choice of jaywalking and crosses the street, neglecting to look both ways to check traffic. He gets run over by a car! Trying to get up, he doesn’t notice as a second car runs him over! Neither car stops in this doubly disastrous case of hit and run.

Afterward, two bystander see the accident and rush to the man’s side. Depending on their level of panic (differing on each run through of the story), each bystander may point at the mangled man’s body in horror or call the police. As in real life, when an accident occurs, no one may call the police at all. Without user intervention, the man dies in the street.

Part 2:

(Controls:

W, A, S, D to move character

Mouse to look around

Once the jaywalker dies, get close and press R to revive

Then press D to make him bust a move)

You are the hero of the story, represented by the first person point of view camera, a trained EMT. After getting within a certain distance of the crime scene you can save the man! Press R to revive the man, who will get to his feet, but not move as he is in shock of his ordeal. More comedically, you can use the healing powers of breakdance to cause the fallen man to breakdance back to life by pressing D! Note, to do either of these actions, you must get close to the falling man. Alternatively, you can let the man die, and instead roam the city.

Part 3:

For the multi-agent control portion, we implemented a system where the player presses a button to switch the camera to a different agent. We used the same raycasting functions from B1 to enable and disable agent movement and their corresponding cameras upon switching to that agent.

Summary of characters:

Walkers:

Walk back and forth along the city street

Bystanders:

Call for help

Point in horror

Jaywalker:

Walk into Traffic

Struggle to get up

Revive self

Breakdance back to life

Protagonist (any controlled character):

revive fallen man

induce fallen man to breakdance

Videos:

Part 1 Behavior TreePart 2 Behavior Tree

Documentation:

Part A:

For this assignment, we extended and evaluated our previous work in SteerLite. We leveraged our previously made social force AI modules into a crowd simulation tool and subjected the program to a series of test cases. We then used the given performance rater script to measure the efficiency of our algorithms and compare our benchmarks to the rest of the class

To do this, we adjusted our social forces AI module from a past project and combined it with A* planning to form a crowd simulator with path finding capabilities. Social forces were initially comprised of a goal force, proximity force, agent repulsion force, and wall repulsion force. Our A* implementation, which calculates the shortest path to a goal using the Manhattan distance heuristic.

For Social Forces, we enhanced out previous project by adding calculations for a sliding friction force in both our Agent Repulsion Forces and out Wall Repulsion forces. Our idea behind this was to simulated pushing and shoving of members of a crowd. Consider the example of Black Friday shopping. Often shoppers congregate outside of closed stores waiting for the doors to open, forming what amounts to a bottleneck when they do. In this situation, people are pushed forward and backwards by other shoppers, up and down walls.

Adding A* to our social forces allows our agents to plan their paths, moving around obstacles that would previously block a straight forward approach to their goal. This mimics actual crowd behavior in the way that crowds are comprised of individual rational agents. Rational agents want to use the shortest path paths to their goal, thus so should all agents of the crowd.

Below are some test cases showcasing our crowd simulator:

maze 1:

office complex 1:

plane egress 1:

plane ingress 1:

wall squeeze 1:

doorway two way 1:

double squeeze 1:

hallway four way roundabout 1:

hallway two way 1:

bottleneck squeeze 1:

Part B

Here we were tasked with making a creative Steerlite crowd animation. We decided to use this as an opportunity to tell a story with the agents. The story is depicted is as follows:

In a world, a great wall separates the population. But after having separated the land for thousands of years, parts of the wall have collapsed creating three corridors. Though some groups, the cyan, wish not to change their way of life and act as if the corridors do not exist, others from both sides of the wall seek adventure and discovery. The red group ventures forward through the first corridor, but seeing the passing purple group, decide to make a hasty retreat west so as to avoid confrontation with the new strangers .The purple group pays no notice to the red, instead racing against the yellow group, with whom they had a long historic rivalry, to reach the other side of the second corridor. They push and shove each other before parting ways at the exit, desperate to claim their own territory. Meanwhile, a peaceful green group traverses the third corridor, then heads east to find their own home, not noticing the yellow group trailing behind.

Behavior trees

This project demonstrated 2 different aspects of character animation: Affordances and Behavior trees.

Affordances:

Affordances are specifically actions that can only be completed when a specific other thing is present. For example you can only open a door if a door is present.

Using the robot, you can try the 2 implemented affordances. One is to step on the yellow spring button, which will begin an animation depicting the spring expanding and contracting with motion (and simultaneously sending your robot into the air). The second affordance is triggered by colliding with the brick door to the maze. This will trigger the trap door which should cause the door to push you into the adjacent hallway if you don’t move out of the way quickly enough.

Behavior Tree: (uses a modified MyBehaviorTree.cs script)

Behavior Trees model actions taken by characters and can account for user interaction and changes in the environment.

The story here is as follows. There are 3 random buttons and 3 characters. Two of the characters are racing to one of the three buttons, while the other cheers one of them on. When one reaches the button, the other stops, admitting defeat. In between the start and end, a character may find his path obstructed, and pause while the other character races on.

The  three branches here denote the different buttons the characters may head to.

Here the 2 participants racing are done in parallel, but separate from the cheering participant because if either participant is unable to read the destination, the cheerer still should be able to do his action.

User interaction:

You can click the steel metal drums and then use the arrow keys to move them around to obstruct a runner’s path or clear it.

Scalability:

The race could be scalable by adding more cheerers or runners. Runners would add extra nodes to the Selector in Parallel section of the second tree, but to add more cheerers, you’d have to add another Selector in Parallel part before the third character starts cheering.

A4: A* and Pathfinding

In this assignment we had to implement an A* algorithm with 2 heuristics: one for Euclidean distance and once for Manhattan distance.

Euclidean differences is basically calculated using something reminiscent of the Pythagorean theorem.

Manhattan distance is basically the sum of absolute values of the differences of the components of vectors.

Part 1:

Here was a bare-bones comparison of Euclidean distance vs. Manhattan Distance in A*

Case 1: Euclidean

Case 2: Euclidean

Case 1: Manhattan

Case 2: Manhattan

Here the videos all pretty much look the same and the paths are the same length, but the real difference is in the number of nodes expanded in each algorithm. Manhattan does significantly better in the number of expanded nodes, having a lower number expanded in both test cases.

Part 2:

Here we tested how to handle ties in f values in computing the best path. We have the choice of tie breaking using g scores. Here we tested what changed when the algorithm chose the node with a higher g score or the lower one.

Higher:

Euclidean

Case 1

https://www.youtube.com/watch?v=-vYfMW0nw_o

Case 2

https://www.youtube.com/watch?v=5UZJ_BXaa3I

Manhattan

Case 1

https://www.youtube.com/watch?v=zfZO6EJ7KDY

Case 2

https://www.youtube.com/watch?v=Lk2t93PB6l0

Lower:

Euclidean

Case 1

https://www.youtube.com/watch?v=pe4LNgLAZp0

Case 2

https://www.youtube.com/watch?v=C2Oa1dUpgQ8

Manhattan

Case 1

https://www.youtube.com/watch?v=EqiE18gcacw

Case 2

https://www.youtube.com/watch?v=BUPeH-fM-1c

Here we also observed a lower node expansion number using the Manhattan heuristic, though the number was a little higher when considering a lower g score.

Part 3:

Here we checked what happened when you increased the weight of a diagonal movement

Euclidean

Diagonal weight = 10

Case 1

https://www.youtube.com/watch?v=O87M_ftU7HI

Case 2

https://www.youtube.com/watch?v=WzMhxJCRI8A

Manhattan

Case 1

https://www.youtube.com/watch?v=8Rw6fImAyI8

Case 2

https://www.youtube.com/watch?v=KjgZCrgod-0

Once again, the case of Manhattan using a lower number of expanded nodes held for this part.

Part 4:

Finally, here we checked what happened when you changed the weight of the heuristic cost, doubling it in each run.

Heuristic Weight: 2

Euclidean

Case 1

https://www.youtube.com/watch?v=NWBZsijrrTU

Case 2

https://www.youtube.com/watch?v=WWZlI1i5hpE

Manhattan

Case 1

https://www.youtube.com/watch?v=9znW3Gtuprc

Case 2

https://www.youtube.com/watch?v=erex6lXe2G4

Heuristic Weight: 4

Euclidean

Case 1

https://www.youtube.com/watch?v=vdRH1PuK8gM

Case 2

https://www.youtube.com/watch?v=ozEIDnPl8Bs

Manhattan

Case 1

https://www.youtube.com/watch?v=yKt6xwyySTo

Case 2

https://www.youtube.com/watch?v=uDpzclYiCuE

Heuristic Weight: 8

Euclidean

Case 1

https://www.youtube.com/watch?v=_KARHtUDekw

Case 2

https://www.youtube.com/watch?v=XkdT0kvJYDw

Manhattan

Case 1

https://www.youtube.com/watch?v=JJizwpD5MK4

Case 2

https://www.youtube.com/watch?v=Ji3Y_7qQDKU

Here what was observed was less clear. The Manhattan heuristic seemed to expand more nodes in some test cases, but not others as the heuristic weight increased

A3: Social Forces

For this project we implemented the below social forces in order to run the listed simulations.

First, calcGoalForce calculated forces as follows:
      agent mass * ((preferred_speed*goaldirection)-velocity)/change_in_time

Second, calcProximityForce calculates forces by creating a vector that is the aggregate of the position of all other agents in the area as well as any walls.

As such, calcAgentRepulsionForces is a sub procedure of calcProximityForce only taking into account nearby agents.

Likewise, calcWallRepulsionForces calculates forces only using the vectors of walls in close proximity.


Bottleneck Evacuation

Hallway-One-Way

Hallway-Two-Way

Hallway-Four-Way

GJK & EPA

Description:
For this assignment we had to implement a GJK and EPA algorithm to detect collisions between convex polygons.

GJK works by creating a simplex from Minkowski differences and checking within the created shape for the Origin.

EPA works to calculate penetration depth and the penetration vector of the colliding polygons.

Part A
Demonstrated here is the output running Steerlite using Polygon1

Part B
Demonstrated here is the output running Steerlite using Polygon2

Part C
Notice how part B erroneously detects a collision between polygons where none exist. This is because the GJK algorithm used in this project assumes all shapes input are convex, whereas in the case of the polygons tested in part B are most certainly not. To remedy this error, simply reorder the vertices in the xml file containing the polygons. SteerLite reads in the vertices in a way in which order matters, thus by reordering vertices we can make a set of points that output as a concave or complex polygon a convex or set of convex polygons. Below is the result of reordered vertices in the xml.

Notice that the output is the same in the terminal

Assignment B1

Part 1: Navigation

User Guide:

Agents (White Capsules):

Click agents (can click more than 1)

Click movement destination

Obstacles (Blue Cylinders)

Click Obstacle

Use up, down, left, right arrow keys to move across simulation

Clicking anything else with the mouse will disable user controlled movement of selected obstacle.

Link to Part1 download:

Webhosted:

http://gamebucket.io/game/b959c6ed-5472-4120-a6f2-33ffe1d290c8

Summary:

Here a complex environment was created to demonstrate the uses of NavMeshes, NavMeshAgents, and NavMeshObstacles. Agents exist as white capsules which can be moved around the environment by clicking agents (multiple can be clicked in a row), then clicking the destination. The selected agents will move together as a crowd to the selected destination. There also exists obstacles in the form of the blue cylinders. The obstacles carve paths in the NavMesh and can be moved by clicking on them and directing them with the arrow keys. Clicking anything else will end player control until they are clicked again. Offmesh links also exist, enabling agents to cross distances over seemingly empty space to equal level planes or jump down from higher planes to lower planes if the differences are not too high.

Misc. Questions:

Explain the differences in behavior between carving and not carving for NavMestObstacle.

Having a noncarved obstacle makes the default behavior of the obstacle like a physics collider. This means the agents will only avoid local obstacle, making it inefficient since an agent might not be able to get around a set of obstacles. Carving changes things by creating a hole in the NavMesh, thus will be factored in to the bigger path an agent takes.

When and why should the carve checkbox be active/deactive?

You should use carving for things obstacles that can block navigation, but should be able to be moved. For example, a door, or boulder are good examples of objects that should be carved.

However, if you have constantly moving objects like cars or other characters, carving should not be used.

Problematic situations:

1) Carving all obstacles

Carving all obstacles might not be a wise choice if your obstacles are frequently moving. If a moving obstacle does not have “carve when stationary” checked and if in constant motion, this will eat up computer resources as the nave mesh will be continuously updated for the changing holes in the mesh. This is especially true if the carving move threshold is low and the obstacle moves very fast.

2) Not carving any obstacles

If you don’t carve any obstacle, then movements of agents will not be along an efficient path. In fact a path to a goal point may not be reached at all. Consider an agent surrounded by four walls. Creating a goal point outside those walls would cause the agent to move directly towards the goal point and collide with a wall. It would possibly try moving around the box, but would not be able to register that no path exists to the clicked point. This is because, without carving, an agent tries to sidestep an obstacle rather than avoid it entirely.

How an agent can avoid obstacles with non-carving options.

For non moving obstacles, you could put them on another NavMesh layer by declaring the objects unWalkable before baking them in Navigation. You could also adjust the settings under Nav Mesh Agent, such as the obstacle avoidance settings and pathfinding settings.

Part 2: Animation

User guide for animated character:

Move around (arrow keys or ‘w’, ‘a’, ‘s’, ‘d’ keys

Jump (‘space’)

Summary

We implemented a animated human character that can walk forwards and backwards, run, and jump in the environment we created. You move around with the arrow keys and jump with ‘space’. We also added the camera to be third-person to follow the character and is located on its shoulder.

Download: Link to part 2

Webhosted:

http://gamebucket.io/game/c37e37e1-b731-4428-9be7-9e485fe53375

Part 3: Combine Animation & Navigation

Here we put part 1 and 2 together. Now, instead of white capsule agents, we have the animated robots in part 2. Assume the controls of the agents, even though you are using robots (i.e. click to move instead of using the arrow keys).

Download:

Webhosted: