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

Adam C Luter gryn at gryn.dyn.marko.net
Fri Apr 23 22:36:33 EDT 1999


> -<clip> 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  ^_^

> 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.

Right! However, his question is, how the heckfire did it run on a 386sx25
in less than 5 seconds?  :)  This particular graph was interesting,
because sometimes there would only be maybe 1-3 ways from whole groups of
sectors to the next.  I know this game cause I played it, and hosted it :)
, it was pretty kewl.

Anyway, it -did- make database, I think.  However you don't need a 64mb
data file.  All I think you need to do to optimize this is keep a list of
'groups' of sectors.  What I mean by group, is a relatively isolated area
on the map.  Depending on the map, the size of the datafile, and your
speed constraint, the definition of this would vary.  I would define a
group initially as an area that has X or less sectores "out", where X
would probably low, like 2-4.

I would suggest assigning each group a number, and then putting that
number on the sector in the main database.  Then you might want to add to
each group the maximum distance to any 'exit' from anywhere, and from any
other exit. Now your problem is reduced from 5000 sectors, to Y groups
(hopefully much smaller! :) ).  Oh another good thing would be the actual
shortest path from each exit to another.

With a little modification you can do the problem straight from your
original code that does it with sectors.  Anyway good luck :)  please
email me if anything interesting happens or you want more info :) .

(however I'm not a happy fan of dijkstra [whom i can only spell because of
the previous post :) ])

Again gluck, and Cheers!

Gryn

p.s. I promise not to email anymore about this subject to the list :)

--
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