Target selection algorithm

[abdula123]

at this moment my bot can "see" mobs around, select nearest (in terms of path lenght), go to it (with navmesh pathfinding), cast spells, use abilities etc. to kill it, and when - loot it.

but going from nearest target to nearest seems to be not optimal (in terms of xp/time) or even dangerous, if bot will approach to compact pack of mobs.

so next what I want - is to optimize target selection algorithm.

any ideas about?

maybe clusterize targets list (by distance between targets) and prefer targets in clusters, that is not too dense (packs) and not too sparse (more running, than killing) ?
for example, with Kohonen network.


EDIT: range, in that server sends mobs data is not big, so maybe it will be not good idea at all

[mnbvc]

Travelling salesman problem - Wikipedia, the free encyclopedia

[Robske]

Recognizing Strategic Dispositions: Engaging the Enemy - AI Game Programming Wisdom I

Well worth the read and fits your problem description perfectly.

[namreeb]

It depends how far out you want to plan. Doing a traveling salesman problem sort of implementation would allow you to plan your next few targets. However, I find this to be not only overkill, but flawed in the sense that by the time you kill one or two targets you may want to re-evaluate. It makes sense to concern yourself only with finding the presently optimal target, and repeat that process after you kill said target.

Hell, we re-evaluate every couple of frames, to allow for a scenario where we want to switch targets before the current one is dead (if, for example, it beings to flee and that fleeing is safe). What has worked okay for us is to do something like:

UpdateTargets()
{
  if (Me.InCombat)
  {
    TargetsList = select target from nearby mobs where
                  target.TappedByMe and target.InLineOfSight and !target.IsFleeing
                  order by target.RemainingHealthPercent asc;
    if (!TargetList)
      TargetList = select target from nearby mobs where
                   target.TappedByMe and target.IsFleeing
                   order by target.Distance(Me) asc;
  }
  else
  {
    list<mob, score> priorityList;

    foreach (mob in nearby mobs)
    {
       // this will check if pulling this mob will do anything bad (like pull more guys that we can handle)
       if (!SafeToPull(mob))
         continue;

       int score = 0;

       score += mob.Health*weight;
       score += mob.RelativeLevel(Me) * weight;
       score += mob.distance * weight;
       // .... and so on, different weights for each to play with as you see fit

       priorityList.add(mob, score)
    }

    TargetList = priorityList.sortBy(score, sort::ascending);
  }
}

This leaves the case of being out of combat and not having any safe pulls unaddressed as it's beyond the scope of this example.

Please forgive my somewhat haphazard pseudo-code. I've been working with c# and c++ at the same time lately.