Friday, November 24, 2006

Projects

Here is a list of some the projects I have been working on this semester:

Maze Solver: A program for Tablet PCs that allows the user to draw a maze on the screen using a stylus, and then finds the shortest path through the maze using A* search. For a simple maze the program only takes a few seconds to solve, but for more complex mazes it can take up to a few minutes (depending on processor speed). One advantage of using A* search for this problem is that it guarantees both completeness and optimality (it will find a path if it exists, and that path will be the shortest one possible). One of the best things about working on this project was the fact that our group got to borrow a Tablet PC from the CS department for the semester.

Text Adventure: A game called "Amnesia" written in Prolog. Text adventures are particularly easy to implement using Prolog because of built-in grammar support for processing natural languages. Although our game only used a very simple grammar system, it shows how powerful Prolog can be at natural language processing. Here is a copy of the game's source code (you will need a Prolog interpreter in order to play the game).

Parenting Lab Website: I redesigned the website at work. Check it out at http://www.psych.ubc.ca/~cjlab. The old version of the website can be found here.

Keyboard Optimization: This program generates keyboard layouts by minimizing the total finger travel distance required for a piece of text. We used three different local search configurations (hill climbing, random step, and simulated annealing). For relatively small pieces of text, the program can produce keyboard layouts that are significantly better than both QWERTY and Dvorak layouts. However, the program is also very computationally expensive, so it would take too long to find a layout for any substantial piece of text.

Chatterbot: This program is still in development. We are using Haskell to make a chatterbot based on the character Marvin (from The Hitchhiker's Guide to the Galaxy). Since this project involves natural language processing, I think it would have been much easier to implement using Prolog. Haskell is a functional programming language, so even basic tasks which would have been easy to accomplish using Prolog become unnecessarily confusing!

11 comments:

Anonymous said...

Can you please tell me the heuristic function you used for the implementation of A* search in the Maze solver? I am trying to implement the same...

Byron Knoll said...

The heuristic function was just the Manhattan distance to the goal.

James said...

Dear Byron,
can you implement a maze solver using prolog for me, I'm very need it. And I don't know how to start

Byron Knoll said...

No, I will not implement it for you. A good way to start is to choose a search algorithm such as depth-first search (see http://en.wikipedia.org/wiki/Depth-first_search). DFS should be easy to implement in prolog.

James said...

No, no :d
I know nothing about prolog, lecturer just tech it in 2 day and give the assignment. This sunday will be dead line.
The assignment tell us to solve maze in java (I've already done using A*) and prolog is last level (!0% of project). But I know nothing about it, so If you can please tech me how

Byron Knoll said...

http://lmgtfy.com/?q=learn+prolog&l=1

James said...

:((
I can't I still have the final exam (Other subject). I 've implement something but won't work. Just need to study.
Anyway thanks

James said...

I just need something to reference, please

Byron Knoll said...

Found on Google: http://www.iro.umontreal.ca/~vaucher/XProlog/path.pro

Good luck!

James said...

Thank you

James said...

Hey, at last I can make it implement with A*. Thank you very very very much. Without your help can can't make it work.