Abstract
Summarize your proposal to a paragraph or two with a link to a URL more details. Its recommended to use a wiki page that you can update over the Summer with diagrams, mockups, screenshots and statistics.
In games it is often necessary for the computer to find a path between two points. It needs to be able to do this quickly and will ideally find an optimal or near optimal path, and in some applications it will need to be able to adapt the path to an environment that can change, potentially blocking off the original path or making a shorter one available.

I plan on initially implementing a simple A* pathfinding algorithm, which is often used for its speed and ability to find good paths. I will use ant colony optimization to adjust the path should it get blocked, a more efficient path become available, and to provide slight variations on the optimal path as you might see in animal behavior.

Should the path get blocked and the ant colony take too long to repath, A* will be used again to rapidly find a new path. Options will be made available to the user to control how much effort the ant colony puts into the pathfinding, how much it can randomize the path, or to turn it off altogether.

Once the ant colony optimization works, I will use it to easily allow for actual ants(or other insects) to be added to the environment and be seen running around looking for food. This could be used simply aesthetically to create a more natural environment, or the ants could be incorporated into a game. I will also use them to create a simple game in which the player must protect a picnic basket from a very hungry ant colony(s).

Milestones
These are initial goals, students may work with their mentor over the Summer to update these goals as needed.



Start of Program (May 24)

Detail the preparation work you'd need to do before you can start working on code:
Familiarize myself with PySoy. This will be accomplished by acquiring appropriate reference materials such as... and reviewing sample applications.

Develop and document requirements for the project and incorporate them into a wiki.

Review and consider testing methodologies.

Learn Genie and any other languages I will need.

Midterm Evaluation (July 12)

List your proposed deliverables by the midterm evaluation:
Unit test plan.

Algorithm able to find paths through three dimensional space and update that path as objects move in that space.

Top level class implementing the algorithm and additional support classes.

Final Evaluation (Aug 16)

List your proposed deliverables by the end of the Summer:
An expanded algorithm able to find paths through three dimensional space and update that path as objects move in that space, while allowing for limitations and abilities of the object following that path, such as the inability to fly or the ability to climb walls.

Results from unit testing.

Simple working game demonstrating the pathfinding AI. Current expected scenario will be a player who has to protect a picnic basket(or some other food item) from hungry ants by placing obstacles in their path.

About Me
Tell us more about you and your experience, include references to your previous work where applicable.
I am a third year student majoring in Computer Science at the University of Maryland, Baltimore County. I know Python, Java, and C, as well as some Racket and assembly, and will gladly learn new languages as needed. Most of the code I've written so far has been for class projects or for games I've written for myself, including chess and a game similar to missile command.

Contact Info
Your blog URL, email address, and phone number are required. Your postal address is optional and is for sending swag (hats, tshirts, stickers, etc) from the Python Software Foundation.
Name: John LaCourse?

Blog:  http://gsocbuggy.blogspot.com/

Email: lacoursejohn@…

XMPP:

Phone: 301-498-8421

Postal Address: 16007 Jerald Rd.

City, State, Zip, Country: Laurel, MD, 20707, USA

Right now I'm planning on implementing a new class, I'm thinking under soy.widgets or soy.scenes. This would have a function that the programmer would call that would take a start point, an end point, the Scene object it should be working in, optionally some control options, and return a list of waypoints that have clear straight line paths between them. The programmer then just has to move their object from one point to the next. For additional control options, I would implement some common abilities and restrictions, such as the ability to fly or jump, and the programmer would just select the ones they want. I would like to implement some way for the programmer to define extra functions in their object that could be given to the AI to help it with more complex abilities, but I probably won't be able to tell how well that will go until I at least have basic pathfinding working.
Alternate idea: programmer calls the function, also passing the object that will follow the path. The pathfinding object creates an internal list of waypoints for that object, and returns just the first one. The programer then moves to object towards the first point, and when it gets there asks for the next waypoint, again passing the object so the pathfinder know which list of waypoints to check. this allows the path to be updated without the object following the path needing to know something has changed.