[RC5] Tree search algorithms and the next d.net

Greg Lee tatsu at tatsu.dynip.com
Thu Apr 22 19:13:25 EDT 1999


On Wed, 21 Apr 1999, Michael Bidzos wrote:

-oh man... a sore spot!
-yes i'm new at the lists, but i can't resist the opportunity to ask...
-have any of you played trade wars?  keep reading please!  =)
-there is a part of the game that involves calculating every possible move
-from your point to another point (part of the nav system).  This takes into
-account sectors that are one-way (can move into from a direction but not out
-of in the same direction, etc...) among other navigational obstacles such as
-starbases and enemy territory (it would be bad to end up there 'mkay?).  In
-the end it displays the fastest route (via a list of sectors to go through)
-to a sector that you wish to travel to.  Everything considered.
-Anyways, with talk of tree searches, do any of you know the best way to
-implement such an algorithm, that does NOT involve a 'branch to infinity'
-search, where if you are at point 1, you can get to 2,3,4, and 5, and from
-each of these, to 7, 12, 13, etc
-the game has in the neighborhood of 5000 sectors, and likely more.  An
-exhaustive search (exempting the creative efforts of d.net) is impractical,
-especially at run-time.  Any thoughts?  'tis been done... in the original
-game!  and with the power of today's personal 'puters over the old p-60, i
-can't get the search practical in under 2-3 minutes, or without using a
-reference 64MB dat file.  (ahem)
-it needs to take about 5 seconds max  ^_^
-thanks for listening,
-mbidzos at ufl.edu

[snip]

The algorithm for the game is a shortest path problem. It is solved using
graphs.  Each sector is a node on the graph and the paths between them are
the edges, which can have a direction and weight assosiated.  The weight
would just be the relative amount of time required for you to move between
the two sectors.

There are very well known methods for solving it to find the shortest
distance.
Basically you start at the one you are on, sector 1,  and say it takes 0
units of time to get there.
Then for each adjacent sector, say sector 3, if cost to get to sector
1 from 1 + time from sector 1 to sector 3 is less then the cost to get to
sector 3 from 1, which isn't know yet, put in the new cost and save the
current sectors number in the adjecent one.
And you keep repeating this until all sectors have been checked.

When you are done the sector you want to get to has the time required to
get to it and the name of the previous sector you needed to get to for the
shortest path, which has the next previous one and so on.

This is called Dijkstra's Algorithm and runs in order of(number of edges +
(number of sectors)^2) or just (number of sectors)^2 if there are lots of
edges. So even with 5000 sectors a P-60 should easily be able to check
them all quickly.

////////////////////////////////////////////////
   E-mail  : tatsu at tatsu.dynip.com              
   Web Page: http://tatsu.dynip.com/            
   PGP Key : http://tatsu.dynip.com/tatsu.asc   
   Uptime  : 0 days 0:26
   Load    : 2.00 2.01 1.67
////////////////////////////////////////////////

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/E/M d- s+:- a--- C++++$ UL++++ P+++ L+++ E--- W+++ N+ o? K? w-- O?
M- V? PS+ PE+(-) Y+ PGP+ t+++ 5 X+ R tv+ b+ DI+ D+ G e>++ h! r- y-
------END GEEK CODE BLOCK------

--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list