MUD-Dev
mailing list archive
[ Other Periods
| Other mailing lists
| Search
]
Date:
[ Previous
| Next
]
Thread:
[ Previous
| Next
]
Index:
[ Author
| Date
| Thread
]
[MUD-Dev] Re: mobile movement
On 1/6/99, at 3:34 PM, Caliban Tiresias Darklock wrote:
>>1) Doing some sort of real-time search (BFS or DFS maybe?) everytime
>>movement was to take place, to find the best room to move to from the
>>current one. Advantages of this, to my mind, are that it allows for the
>>most intelligent movement. The disadvantage of course is that this is
darn
>>slow (how slow, I don't know. I code on Achaea, but I would not really
>>consider myself much of a coder. Maybe one of you could enlighten me as
to
>>just how slow such a routine is likely to be, given that we could limit
>>how many rooms away to search, etc).
>
>
>Ultimate Universe can perform a 30-deep search of a weightless directed
>graph (it costs the same to move from any room to any connected room, and
>moving from room A to room B does not necessarily mean you can move from
>room B to room A: just like most MUDs which use rooms) with no more than
>32,000 exits across the entire graph --- in less than ten seconds.
A nice method of speeding up this sort of thing (that was suggested to me
by Mike McGaugerty of Shattered World) was to make up clusters of rooms.
Then do a path find through the clusters and then a path find through each
cluster. This significantly reduces the number of searches you need to do
at a fairly minimal memory cost. This is especially good if you do route
finding quite often. A cluster of rooms would be a connected set of rooms,
up to some random cut off number, say 12 or so. You then keep track of the
connections between clusters and any pre-determined routes through a
cluster. Makes everything a lot faster and is quite a neat solution.
Wombling down the fluffy path,
David.
- Thread context:
- [MUD-Dev] Keegan's MUD Tree,
J C Lawrence claw#kanga,nu, Thu 07 Jan 1999, 05:24 GMT
- [MUD-Dev] OT: Mike Sellers needs some help load testing,
J C Lawrence claw#kanga,nu, Thu 07 Jan 1999, 03:11 GMT
- [MUD-Dev] [RRE]MediaMOO annual birthday symposia: 1/20,
Bruce Mitchener, Jr. bruce#puremagic,com, Thu 07 Jan 1999, 02:02 GMT
- [MUD-Dev] Re: mobile movement,
Caliban Tiresias Darklock caliban#darklock,com, Wed 06 Jan 1999, 23:25 GMT
- <Possible follow-up(s)>
- [MUD-Dev] Re: mobile movement,
Caliban Tiresias Darklock caliban#darklock,com, Wed 06 Jan 1999, 23:38 GMT
- [MUD-Dev] Re: mobile movement,
Koster, Raph rkoster#origin,ea.com, Wed 06 Jan 1999, 23:49 GMT
- [MUD-Dev] Re: mobile movement,
Kylotan kylotan#globalnet,co.uk, Mon 11 Jan 1999, 07:25 GMT
[ Other Periods
| Other mailing lists
| Search
]