> Well, we have over 15,000 rooms. So if we apply this to a few mobs (lets
> say 50, if there were around that many annoyed mobs and nearly that many
> players), wouldn't this get a wee bit CPU intensive?
It's not so bad as you may think. For the most part you're just
doing a couple of hundred loops with at most two reads and one write + a
few more for the recursion. The array based nature of the rooms, and their
non-directed graph like behavior does make this a difficult problem to
optimize though. In the end running through 15,000 data items is still
rough, but not unreasonable.
> Wouldn't there be a better method to FIND the shortest path to a victim
> ? And secondly, what about terrain? can that be thrown in to the
> equation? eg. WEIGHTS to get their now - sorta like the Travelling
> salesman problem way back in the uni days .. *cringe and smile*
I can't think of one off hand, but due to the fact that the ones
that I'm thinking of all require a foreknowledge of the world layout. In
a 3-D world, if you know the endpoints, tracking is pretty easy.
The best solution I can think of would be to make it so that when
a character enters a room, it sets a timed (maybe 1-3-5? minutes) mark
saying that that character had been there. Then, your BFS search can hit
either the character, or the trail. If it hits the trail it can limit its
search to along the trail. Really, I don't like this solution, but I'm
just trying to think of the 'right' way to do this.
As far as adding terrain, well, you've got a simple graph theory
problem. Pick up the CLR algorithm book and find something like weighted
non-directed graph traversal. I know the exact algorithm you're looking
for is in there.
PjD
+------------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
| http://qsilver.queensu.ca/~fletchra/Circle/list-faq.html |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 04/10/01 PDT