Steve Jobs passed away today. A profoundly influential man, his work touched the lives of millions. Including mine. I wanted to reflect on his passing and, since I don’t really have an alternate forum, I’ll share my story here. In late 1991 I received my first machine: an Apple II/c. I remember a feeling of […]| Shortest Path
This is the second of my three-part look into symmetry reduction algorithms for speeding up grid-based pathfinding. In part one I introduced the notion of path symmetry: a property of uniform-cost grid maps which can significantly slow down optimal search. In this article I discuss Rectangular Symmetry Reduction (RSR for short): a new pre-processing algorithm […]| Shortest Path
In this article, the first in a three-part series, I attempt to explain path symmetry: a property of uniform-cost grid maps and other regular search domains which can significantly slow down pathfinding. I describe how symmetry manifests itself and briefly discuss some approaches that other people have tried to improve things. Finally, I introduce two […]| Shortest Path
I wanted to share this small piece of creative writing. It was cobbled together earlier this year while I was turning myself inside out trying to meet various submission deadlines. It’s a change of pace for this blog, but I hope you enjoy it nonetheless. I call it, The Paper: Tick, Tock. Tick, Tock. Steadily […]| Shortest Path
One of the (few) perks of being a research student is attending conferences. There are many reasons to attend a conference: you get to travel to places you probably wouldn’t otherwise visit, toss around ideas with other people who work in the same research area and get a glimpse into the state of the art […]| Shortest Path
I noticed recently that the Proceedings for the 2008 IEEE Symposium on Computational Intelligence and Games (CIG’08) are now available online. There were a number of interesting presentations at the conference, including a few neat pathfinding-related talks (which I discuss in an earlier summary) but the really cool thing is the other stuff the organisers […]| Shortest Path
In my last two articles I discussed HAA*, a clearance-based pathfinding technique applicable to grid maps that efficiently computes paths for agents of different sizes and with distinct terrain traversal capabilities. Such problems are common in many modern video games and particularly in the real-time strategy and role-playing genres (Figure 1). The basic idea behind HAA* is really […]| Shortest Path
In my last article I discussed Annotated A*, a search algorithm able to solve pathfinding problems for variable-sized agents with heterogeneous terrain traversal capabilities. Such problems are encountered in many modern video games which often feature different classes of units, each with distinct physical characteristics and navigational capabilities. The story so far Annotated A* operates […]| Shortest Path
Real-time strategy (RTS) games often feature a wide number unit types for the player to control. One of my favourite titles from the past, Westwood’s seminal Red Alert, had many classes of di…| Shortest Path
This is the final article in my three-part look at symmetry reduction algorithms for speeding up pathfinding on uniform-cost grid maps. Recapping the story so far: Part one introduces the notion of…| Shortest Path