The Shape of Search: Grid Worlds

Heuristic search algorithms such as A* are widely used for solving problems in artificial intelligence. The A* search strategy finds optimal solutions by prioritizing search through states that appear to lead to cheaper solutions. This interactive visualization demonstrates the dramatic effectiveness of A* over breadth-first search; a well-known uninformed search algorithm. Increase the weight on the heuristic to see what happens when A* becomes more like Greedy search.

The Shape of Search: Permutation Puzzles

Visualizing large search spaces can be challenging. Previous approaches, like the one above, have emphasized 2D maps where the search space and the physical representation have a natural correspondence. These approaches are not applicable to permutation problems like the Rubik’s Cube and the Sliding-Tiles puzzle; two toy problems commonly used in evaluating search algorithms. Here we propose an interactive Sunburst visualization for exploring the behavior of search algorithms on arbitrary search spaces. We used this technique to gain some insights on two commonly used A* heuristics for the Sliding-Tiles puzzle.

Ray Tracing

Ray tracing is a rendering technique whereby each pixel in an image is computed by tracing rays of light back to one or more sources of light in the scene and simulating their effects as they interact with the surfaces of objects in the scene. Ray tracing is computationally expensive but capable of generating visually realistic images, simulating effects like reflection, refraction, scattering and dispersion. I developed a ray tracer in C++ using OpenGL for a computer graphics course assignment. My raytracer was very basic by today's standards but capable of recreating the image on the cover of the course's text book! Check out a couple of my renderings here.