A* Pathfinding with Skinned Character

Overall Idea

Animating a character is great, but watching him run in place is not very interesting, so I wanted to give an animated character a little life by giving him the opportunity to run around a nice piece of terrain.
Of course running around a flat plain is not very interesting either, so there will have to be some obstacles for him to dodge. Utilizing the A* pathfinding algorithm I set out to have an animated character dynamically pathfind around a procedurally generated world.

Map Generation

The maps are loaded in from a bitmap image, where a white pixel is walkable tile and a red pixel is an obstacle. The terrain mesh is then procedurally generated.

Map to be loaded into the scene

Animation Techniques

I utilized the vertex skinning that we learned in class, with the vertices influenced by the model skeleton.
Each mesh vertex is influenced by several bones, which drive the animation. As the bones move, the vertices they influence move with it, allowing the entire mesh to animate without having to painstakingly animate every vertex.

Big Vegas running animation	Wireframe view of the bones that influence the vertex skin

Demonstration

External Libraries

The third-party libraries I used to make this project:

• GLFW/GLEW - Used to create a OpenGL context and retrieve OpenGL bindings.
• FBX-Extractor (Dr. Sueda) - Used to extract usable .obj models and animations from .fbx files.
• EasyBMP (Paul Macklin) - Lightweight BMP library for C++ to load and read pixel data from bitmap images.

What to Fix

Transitioning between animations

As of now there is only the one running animation that is played while the character is moving to the destination, and he returns to the T-pose once he arives.
Given the time, I would like to have him play an idle animation instead of standing still. Since the models and animations are abstracted into their own classes this would be very easy to implement, just with a little bit of extra work.

Idle animation

Prefer Linear Paths Over Diagonal Paths

In some cases the A* algorithm will prefer a diagonal path instead of the more visual pleasing linear one.
As far as A* is concerned, both of these paths cost the same, so it will choose whichever one it stumbles across first.
But humans prefer straight lines over zig-zags, so it would be nice if the linear path was always chosen when possible.
This can be fixed by changing the order in which tiles are pushed to the priority queue or the order that neighboring tiles are checked.

A* taking the diagonal (blue) path over the linear (red) path

Varying Movement Costs

As of now, every walkable tile has a movement cost of 1 and every obstacle has a movement cost of -1, indicating that it is unwalkable.
In this case, A* is not much better than bread-first search. It skips checking a few tiles which saves so computation time but BFS will still return the same path as A*.
The magic of A* comes in when tiles have different movement costs. In this case there is more to the optimal path than just the length of the path, it must also take into account the weight of each tile.
Currently, movement costs are stored as an integer and are taken into account in the A* implementation, so the only change needed would be to create a map with differing tile types.