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
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
