Pathfinding Bouncing Ball through Generated Maze

By: Aaron Sanchez

Project Overview

This project aimed to create a pathfinding algorithm that can solve a randomly generated maze and animate a ball bouncing through along the solution of the path. In order to do this project there needed to be an aspect of animation from our Computer Animation, so I decided to use Blendshapes. Originally, I was planning on using Blendshapes and Keyframing, but after consultation on the project with Dr. Sueda I decided to solely use Blendshapes, but blend based off of height.

Ball Bouncing Animation

This animation of the bouncing ball was made by using blendshapes and a function that determines which point in the animation the ball needs to be based off of the height, which is determined based off of the time. This creates the basic animation, however, to use blendshapes, we need to first have blendshapes created. In order to do this we first had to use Maya Blender to create the shapes. The first shape that I made was the base pose, which is pictured below on the left, then making the stretched ball shape (for when the ball is in the fast motion of the bounce). Lastly, making the squished ball pose, for when the ball hits the ground. All of these combined make for our blendshapes.

Now once we had these blendshapes, we of course had to write code that would go between blends, for this we simply used the code that we had written in P3, however, we modified it to take in our exact shape and to go through the blends in a sequential manner, so that we could have the blends actually look like the ball is bouncing. In order to get that to happen, we pretty much just needed to change the weights that the blends would have based on a height calculation, which I created using the time. After that was completed all we needed to do was have the ball translate along the solution of the pathfinding algorithm to get something that looks like this:

Maze Generation

The simplest part of this project was generating a maze, in order to do this we used code from stack overflow, written by Jaden Peterson in 2016. This code uses a DFS algorithm to generate a random maze based off of the size the maze is. I had to adapt this code to send out the maze to the pathfinding algorithm, along with understanding and adapting a lot of the bad coding practices that were used in this code, so that I could find different variables. After all this was done, we came out with code that could create 91x91 mazes easily in Visual Studio Release mode, and 21x21 mazes in Visual Studio Debug Mode. In order to draw the maze, we created the 2 dimensional maze and in the render function, we translated the cube obj files by the x and z of the maze, creating a three dimensional look, even though the maze we are solving is two dimensional.

Pathfinding Algorithm

Lastly, to create the pathfinding algorithm we used an A* search function and took out the capability to go diagonally, as this would have resulted in a weird animation where the ball would be bouncing through the maze at points. In order to create the A* search function we used code from geeksforgeeks.org/a-search-algorithm/, however, this only worked so far. I had to make this into a class, which was able to interact with our maze class from before, and allow the maze to send start and end points, along with the actual maze itself, along with changing the functions of A* to interact with the format of the maze that was being sent to it. After this was done, I wanted to be able to see the path that the ball would take, so I created a draw function, which draws from the current points (x, 0.5, z), and goes through the entirety of the vector solution until we have a path drawn.

Final Solution

Once all of these things were put together we had a final working product, which you can pretty much see in the first video, but which I will now demonstrate with the 91x91 maze and the toggles to turn the maze and path drawing on and off.