Newsgroups: comp.ai.games
Path: cantaloupe.srv.cs.cmu.edu!das-news2.harvard.edu!news2.near.net!howland.reston.ans.net!swrinde!ihnp4.ucsd.edu!news.encore.com!jbates
From: jbates@encore.com (John W. Bates)
Subject: Re: "The Shortest Route"
Organization: Encore Computer Corporation
Date: Thu, 16 Mar 1995 17:26:12 GMT
Message-ID: <JBATES.95Mar16122612@pinocchio.encore.com>
In-Reply-To: tormy@stud.unit.no's message of 14 Mar 95 12:44:52
References: <1995Mar13.231632.13723@blaze.trentu.ca>
	<TORMY.95Mar14124452@signy11.stud.unit.no>
Sender: news@encore.com (Usenet readnews user id)
Nntp-Posting-Host: pinocchio.encore.com
Lines: 21

In article <TORMY.95Mar14124452@signy11.stud.unit.no> tormy@stud.unit.no (Tor Andre Myrvoll) writes:
> In article <1995Mar13.231632.13723@blaze.trentu.ca> basselstine@ivory.trentu.ca writes:

> The easiest way to calculate shortest-path in a graph is the classic
> Dijkstra algoritm. I recommend looking it up in a decent textbook on
> the subject (some graph-theory or a plain book on algorithms should do).
> The problem with this algorithm is the cost of calculating the
> shortest path. It has an upper bound of o(n^2), which is a bit to much
> when one considers an average sized games board. Some clever
> heuristics should take care of this though.

Actually, it might not be unreasonable to do an all-pairs shortest
path calculation during initialization (o((V+E)^3)), provided
that the map will be reasonably static. That way, you avoid delaying
the game to continually calculate shortest paths. You can just
do a lookup on the pre-computed table.

Even if it is a dynamic map, you can then use your clever heuristics
to update your table.

John
