Wednesday, December 2, 2009

Pacman!

Been a bit busy (and lazy) recently...

Winter break is almost here and as soon as finals are over DIY gift-making will follow.

For now though I've been trying to pick up the introductory topics of AI. With some help and a borrowed copy of Artificial Intelligence: A Modern Approach I'm getting started. The project files are part of an assignment from a course whose resources I got access to.

The project is Pacman. The first problem is to help Pacman find the single food dot. The highlighted paths indicated nodes explored by the AI. The nodes that are most red are the nodes explored earliest. Once a path to the goal state is found, Pacman begins to move, and moves only along that path.

Depth First Search: Pacman searches along one path until he reaches a dead end before going down a branching path. Uses the Stack data structure (LIFO: last in, first out).





Breadth First Search: Pacman searches in layers--first he looks at nodes one step away from his starting position, then at nodes two steps away, and so on. This uses the Queue data structure (FIFO: first in, first out).





I have to take a break from this to study for finals, but there's a lot more of the assignment to complete, involving mazes where Pacman must avoid the ghosts, find all the food dots in a maze, so on...

Happy holidays! Those are coming up, aren't they...

No comments:

Post a Comment