Post 11 – Done

Buddy got into town the other day, and brought my Park toolset, with which we finished the Schwinn. Or at lease, we have it as a single speed using the original cassette until we get to Boston later today and buy a cog and some jb weld to fix it. I’m pleased with the result:

I have a front break on it, and we’ll also be getting some bar tape. With this bike and the Raleigh I found on the road, we rode down to the scenery posted above. It was wonderful.

Also finished is the simple program I was working on. I ended up using Dijkstra’s shortest path algorithm which is essentially the same as A* except the heuristic is always set to 0. I did not, however, use boost’s c++ library as I wanted to implement the algorithm myself before I used an already made tool to do it. My program is a little slow, as it takes roughly 2 seconds to find a path from a random node at the top and a random node at the bottom of a 70 x 70 map. I was using STL’s containers to hold pointers which turned out to be a little to problematic so instead I had the container hold copies of nodes (when I say node I mean the object that holds all the information). I had to have a multiset hold the nodes because a set would only add one node object (it thought they were all the same for reasons I’m still not sure of, as I included overloaded == and < operators). Now I want to use boost’s property maps to associate these objects with a graph, because boost conveniently includes a wonderful standard graph library.
My updated challenges will be:

• Use the boost graph library to optimize my code and bring down the search time
• practice several different algorithms to search, including Ant Colony Optimization for searching for food where the ‘ants’ don’t know the location beforehand (as opposed to A* and Dijkstra which the goal is known) and place them into my procedurally generated map.
• develop more objects and use an interaction system between ‘creature’ objects

This is all heading towards a stronger understanding of AI and being able to efficiently program it. Unfortunately I have to wait until spring semester or even next year until I take any classes that delve into these topics. I’ll post some code you can make fun of soon.

~ by blitzgren on July 14, 2008.