Monday, November 23, 2015

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.

Saturday, November 14, 2015

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

Wednesday, November 4, 2015

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