##### More path finding

###### December 1st, 2005

Path finding is coming along very nicely. I’m out of the prototyping stage and I’ve begun integrating the code into the game. I’ve written a function that takes a Boundary (and range at which to sample) and produces what’s best described as an ‘edge list’. An edge list is essentially a list of std::pair; it defines which vertices are connected to which other vertices. The ‘int’ denotes the index of the vertex in the vertex list. Doesn’t feel very OO… but I’ll withhold my judgement for the moment. This edge list is used to produce what the BGL describes as an adjacency_list.

Something that bothers me is that each vertex must have a ‘weight’ property in order for the astar algorithm to work. Given that each weight is simply 1, this feels wasteful. I considered writing a function, (ConstantWeight) that, you guessed it, always returned a 1, but Boost started whinging at me, so I’ll put that off for now.

So, given that I can now generate an adjacency_list from a Boundary, I can start tested out the algorithm on some Scene boundaries. I first of all tested it on the academic example of the **U** shaped path – getting the algorithm to path find from the top-left to the top-right. Seeing that work, (by plotting the results in Excel) was very rewarding.

All that’s really left is to integrate the path finder into the Director/Actor. Apologies if none of what I just said made sense.