AStar Game

Recently, I learned how to implement the super-awesome pathfinding algorithm called A*. Given a start point and a goal, A* will find the shortest possible path to the goal while evaluating as few paths as necessary.

Not satisfied with leaving such a juicy algorithm to rot in a classroom, I set out to build a game.

I chose to create a Cat and Mouse game where the player tries to reach a goal while running away from evil baddies. Sound familiar? Well I've made it before:

Warp Chase was the first videogame I ever made. And by "made", I mean copy-pasted from a game programming book and added some levels. Oh shame. At the time, I did my best to add some personal spirit to the title, but didn't know enough concepts to program any of the gameplay that I had imagined.

Lucky for me, this kind of game lends itself perfectly to A*, since baddies need to be pretty movement-efficient to chase the player effectively. I set forth to fully realize the gameplay I couldn't quite grasp before.

Implementing A* was an interesting exercise in itself. I spent a few days experimenting and optimizing my implementation. Ultimately, I cut my processing time for a long A* search from 117 milliseconds to under 4. The biggest gains came from two places: First, I evaluated visited nodes by looking up values in a 2D array, rather than wastefully looking through each nodes list of visited previous nodes. Second, I implemented my own priority queue using a heap, which saved a lot of time on sorting.

From a gameplay standpoint,  the escape mechanic was fun for a while, but I quickly grew bored of it. A* was just too intelligent to waste on such shallow gameplay.

I wanted strategy.

While finishing the implementation for the Escape part of the game, I stumbled upon a very interesting bug. Effectively, the bug allowed the player to create walls that could trap unsuspecting baddies. Very interesting indeed.

A few experiments and 9 levels later, I found that the trap mechanic allowed me to make some modestly interesting puzzles. I won't spoil the levels here though. Go play the game!

http://kwarp.com/portfolio/astargame.html