Big Bucket Software you like to use
A* Search using the Boost Graph Library
November 28th, 2005

Lately, I’ve been playing with the Boost Graph Library, specifically the A* search algorithm. It didn’t require very much effort to get something working, albiet that working meant finding its way from the top-left corner to the bottom-right corner of a square. At first, I was a little put off that it doesn’t support implicit graphs, (graph’s that expand on demand) but after a bit of thinking, I realised that I didn’t really care for this behaviour anyway; if a search is going to happen every time the player clicks the mouse, its best keeping the whole graph in memory anyway.

I’m going to continue hacking prototyping until I become comfortable with the territory, see how difficult (and costly) its going to be to hook into the existing Boundary class I’m using at the moment. Maybe I should take a moment to explain…

Currently, an ActorModel is allocated a Boundary. A Boundary has a public method:

bool isInside(Vector2DF position);

Everytime the ActorModel tries to take a step, it will ask the Boundary if the place that it is about to step ‘isInside()’ and if it is, it will take that step. If not, it will become idle. The trick, as far as I can tell, is to sample the boundary at given intervals to build a boost::adjacency_list. This will only need to be done once for each scene. When the ActorModel is asked to walk somewhere, a suitable path will be found (if possible), boundary-checking will be disabled, (in case the sampling was too coarse) and the ActorModel will be directed to destination… almost. Just before reaching the final node, boundary-checking will be turned back on, to ensure that the ActorModel doesn’t come to rest outside of the boundary.

Sounds good in theory at least 🙂 Can’t be too hard.