TSP Forum
Study assignment for *:94, Internet programming course
Martin Rimka
2000-10-23
Description
TSP Forum is a network game, based on the Travelling
Salesman Problem (TSP). Users can choose new sets of
cities, search for the best solutions, share their
solutions with other users, view solutions created by the
TSP server. TSP Forum contains a chat client and a
server.
To maintain a communication between clients, TSP Forum uses a specific server-client protocol. The protocol and the graphical interface are designed to support a quick exchange of images between the users. Users can request images from each other at any time (except when participating in the game).
TSP
- Travelling Salesman Problem
One has to find a shortest possible route
through a number of randomly placed cities. Each city has
to be connected with two other cities. A connection
between two cities is called an edge. There must be as
many connections as cities.
Connecting
cities
To connect two cities, drag a mouse pointer from
one city to another, or simply click once on each city.
To disconnect a city, double-click on it. Every time user
connects or disconnects cities, a new route distance is
calculated. Cities can be connected only according to the
TSP rules.
Game
The idea of the game is taken from the quick
chess parties. You have to consider both the position and
the time. The goal is to find a shortest possible route
through 20 cities in 1 min.
To initiate a new game session, click 'Start game'. Server will ask you and other users to join the game. You can always quit the game by pressing 'Cancel'. To change game settings, choose different number of cities or minutes in the 'Game' menu.
Game results are displayed after the game session if finished. Each player receives an equal amount of time, no matter when he or she joins the game. The game can be played alone, against the server, or with a group of users.
TSP
Solver
To make a search, server has a build-in module,
called TSP Solver. TSP Solver implements the Simulated
Annealling technique. This technique proves to be fast
and efficient for the game purposes. It offers quite good
solutions with 10 or 20 cities, but has some obvious
flaws (crossings) when playing with 30 cities.
