Re: [Algorithms] agent pathing to renewable resources

[John R. A. \(2K Boston\) <Joh...@2k...>]

I think you could just do (as you suggest) the search outward from a
starting location within a bounded distance, and keep track of the
resources found.  Obviously you need to find at least n resources (maybe
1) within the maximum distance searched (and keep searching outside of
the distance if you don't find n),  and if you deplete the "found"
resources the agent might need to do a search again for the non-depleted
resources.  

 

If you could do this over multiple frames (more difficult and more
memory required) or staggered agents searches where there are a limited
number of searches allowed each frame (much easier) it might be doable,
and since you already have the quadtree ready to use it might not take
much time to get running.

 

Although it's a brute force approach, I imagine it's worth trying first
before trying to get elegant.

 

-crombie

 

 

From: Heath Copeland [mailto:cop...@tr...] 
Sent: Wednesday, October 29, 2008 7:15 PM
To: gda...@li...
Subject: [Algorithms] agent pathing to renewable resources

 

Hi all,

 this is my first post, so excuse me if I'm a little verbose; you'll
probably get what I'm talking about very quickly, but I figured more
detail is better than too little (so feel free to skim!):  

 

 I'm working on a simulation in which, amongst other things, AI agents
must navigate from a fixed reference point (think a workplace, for
instance) to a location on a map at which they can gather resources
(imagine woodcutters heading off to chop down trees, for example).  At
such locations, the resource they gather might be either temporarily
depleted before gradually regenerating, or else might simply run out.
The points in question can never move, though they might be temporarily
invalid if they happen to run out of the resource (until it
regenerates.)  The agents might be tasked to gather their resource
(several types of such resources exist in the simulation) perhaps as
often as once every twenty or thirty seconds real time, so this isn't
something that would occur every frame for a given agent, but there
might be hundreds of agents, so potentially at least one of them might
be looking for a resource point as often as once per frame.

 

 The algortithm agents must use to locate their resource needs to work
on a map where there can be an arbitrary number of such resource points
at arbitrary positions.  Obviously, the agents should navigate to the
nearest such point that currently has the resource available - errors
that aren't obvious to an observer are acceptable, but those which are
noticeable are not, even if small.

 

 Some maps could be quite sparse, with only a few widely distributed
resource points, so a pathing algortihm that analyses the map in real
time would be much less efficient than simply storing all the resource
locations (and their current resource availablility) in some sort of
list or quadtree which can then be sorted by navigation distance to
select the nearest resource point with resources available.

 

 On the other hand, some maps might be quite dense, with resource
gathering points never very far away, so that a pathing approach would
quickly locate a nearby point whilst a search through the points in a
list would potentially be expensive, since there might be dozens or
hundreds of points with the required resource available, which then need
to be sorted by distance (and this is navigable distance, not simply
straight-line distance, since some points might require navigation on
the map that makes them expensive to reach even if they are close by, so
some sort of relatively expensive distance heuristic would need
evaluated for all points even to decide that they should be excluded).

 

 I tried a quadtree, in which I analysed the map prior to starting the
simulation, and then this information was cooked into the map.  The
implementation stored the points sparsely in the tree, with only
terminal leaves containing resource points, up to some threshold number
of points at which point the quad was subdivided.  That allowed any
reference point on the map to quickly be mapped to the corresponding
leaf quad containing only this threshold number of resource points (or
fewer) which could then be sorted by navigable distance by even a fairly
expensive algorithm without too much impact.  

 

 The weakness here is that since the quadtree is static rather than
being dynamically generated from the agent's starting location, if
resource points happen to be close together near the corner of
neighbouring quads then running this algorithm from a leaf quad
containing one such point considers only points in *that* leaf, before
any of the ones in neighbouring quads which might actually be closer;
particularly once terrain navigation is taken into account.  My mileage
varied according to different maps and quadtree thresholds, but it was
frequently obvious that agents were navigating to a point at which
resources were available while ignoring other candidate points that were
(to a human obvserver) "obviously closer", which is unacceptable.  

 

 It also raises the question, since there are generally fairly few
resource points in a leaf (the whole point), of what happens when -
inevitably - they are all harvested to the extent where they need time
to regenerate.  At this stage, the quadtree leaf containing the
reference point where the agent starts their search contains no resource
points that actually have any resource, so we need to work back up the
quadtree to find larger or neighbouring quads that still do.  Parent
quads automatically contain no points if I store them sparsely (in
leaves only) so I would have to consider "sibling" or "aunt/uncle" quads
- if that makes sense.  How would I choose which?

 

 The only other useful piece of information is that agents always start
their search from the same place (their workplace).  Although it is
inelegant brute force, I considered running an A* pathsearch or similar
from every workplace once to every resource point workers from that
workplace might need to go, and caching the resource points sorted by
navigation distance.  This could, for maps with lots of resource points,
be *really* expensive, but only needs to be done once.  For workplaces
on the map at the start of the simulation this can all be precalculated
and cooked into the map, but part of the simulation is to allow new
workplaces to be added in real time, so whatever technique along these
lines is used would have to be defered over many frames.

 

 This is where I decided I needed advice.  So... it strikes me that
situations comparable to this can't be all that uncommon, and one of you
might well know of an algortihm - possibly completely different to what
I have considered - that provides a good solution.  Can you recommend
for or against any of the suggestions I've offered, or suggest anything
else, please?

 

Thanks,

 Heath.

DISCLAIMER:
This e-mail and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to which they
are addressed. If you have received this email in error please notify
the sender or system administrator. This email message has been checked
for the presence of computer viruses. Trinity College Gawler Inc.
reserves the right to filter and delete inappropriate, offensive or
unsolicited e-mail.

Please consider the environment before you print this email