Demo Video
Unfortunately, I did not manage to implement all the features below correctly in time. The demo video only shows a successful implementation of
the maze navigation section.
Project Overview
I attempted to create a 2D spider that would automatically navigate a maze towards a goal while positioning its legs using IK so that it looked
like it was walking.
Maze Navigation
For the maze navigation, I first create a grid over the maze and sample points on it to determine where acceptable positions
to place the spider's main body would be. This is done to prevent the spider from ever clipping into the maze. Using these
positions, I then construct a graph in adjacency list format where each vertex is a position and the edges are the valid neighboring
positions. Either DFS or BFS is then used to obtain a valid path from the spider's current position to the target position. The points
along this path are then used to create a spline curve, and animate the spider's body as it moves towards a target position.
End effector positioning
To determine the what angle the legs should be at, I decided to use an IK solver. The start of the chain was attached to the body and the end effector
was attached to a target. These targets would move with the spider every frame. However, the end effectors would not. They would remain at their current
position until the targets had moved moved far enough away from them that they were no longer within an acceptable range of the target. Once this occured,
the new end effector position would be placed at the edge of the target in the direction of the spider's motion. This was done instead of placing the
end effector at the center of the target so that the spider would "reach" along its direction of motion and thus have a more natural looking walk animation.
This concept is demonstrated in the following images.
However, just having the end effector teleport to its new position would still usually cause a very rough animation. To make it smoother, it would be a
good idea to interpolate between the end effector's prior and new position over some period of time.
Target positioning
Because the maze is not flat ground or a connected surface, If I simply maintained my targets at a fixed relative location from the spider, it was possible
they would not be located anywhere near a platform. An example of this is demonstrated in the image below.
I needed a way to ensure that the new targets would always be near maze geometry so it would not appear as if the spider was walking on air. To determine
where maze geometry existed and thus where I could place a target, I decided to use ray casts. I decided to cast rays in various directions from an offset
of the spiders current position in the direction of its motion and use the location of the first hit as a reference of where to put the new target. To try
and ensure the spider would keep walking on its current platform instead of radidly alternating between nearby platforms, I decided on a fixed order for
the directions of my raycasts. They would start in a direction perpendicular to the spider's motion and gradually become more parallel in an order similar
to the following image.
Areas For Improvement
Some improvements that could be made include:
- Finishing the logic for creating new leg targets as the spider moves
- Finishing the logic that controls the interpolation for the end effector after selecting a new position for it
- Modifying the IK solver to prefer more "spider-like" rest angles instead of straight lines
References
- Initial stater code and IK solver:
- Adapted from Assignment 4 code
- Maze navigation spline creation and animation code:
- Adapted from Assignment 1 code
- Pair hash function used in maze navigation path and path searching:
- Hash struct format: https://stackoverflow.com/questions/32685540/why-cant-i-compile-an-unordered-map-with-a-pair-as-key
- Hash function steps: https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes/27952689#27952689
- BFS/DFS psuedocode:
- Artificial Intelligence A Modern Approach Third Edition - Chapter 3, Solving Problems by Searching, page 84, Figure 3.14, Uniform-cost search
- Leg targetting and inspiration for project concept
- https://youtu.be/AhywDyu0EGw