# Constrained/penalized distance function

Assume a character is located on a n by n grid and has to reach a certain entry on that grid. Its current position is (x1,y1). Also on the same grid is an enemy with coordinates (x2,y2). Each step algorithm randomly generates new candidate locations for the hero (if there are k candidates then there is a kx2 matrix of new potential locations.

What I need is some distance objective function to compare the candidates. I'm currently using d1 - c * d2, where d1 is distance to the objective (measure in terms of number of pixels for each axis), d2 is distance to the enemy and c is some coefficient (this is very much like a set-up for Lagrangian). It's not working very well though. I'd be quite keen to learn how what constrained distance function are used for similar cases.

Any suggestions are very much appreciated.

• I'm not sure I understand what your problem is. Is that an AI problem, i.e. is your "character" or "hero" located in (x1,y1) computer-driven? If so, are you trying to make this AI both go to its goal, let's say in (xg,yg), and avoid its enemy in (x2,y2)? Please try to clarify this a bit. Commented Apr 6, 2012 at 11:03
• Maybe you should just skip all the maths and tell us in plain words what behaviour you are trying to achieve. Commented Apr 6, 2012 at 15:02
• You need to say, at minimum, what you consider "not working very well." Commented Apr 6, 2012 at 15:58
• OK, here's the challenge: the character needs to et to some entry on the grid without being killed by an enemy which performs a random walk. For this purpose the step that the cahracter takes has to account for 1)distance to the target 2)distance to the enemy. What's the best way of doing it? Commented Apr 8, 2012 at 1:09

## 1 Answer

Based off your comments on the original question, what you are describing are two basic steering behaviors:

1. Avoidance (or flee): the character has to maintain as much distance as possible from the enemy.
2. Seek: the character needs to get closer to the entry point on the grid.

For each, generate a separate movement vector for the character. With avoidance, find the vector to the enemy and negate it (flip it 180 degrees). For seek, simply find the vector to the entry point.

Now the trick is to blend the two vectors. If both behaviors are equal priority, then add the two vectors. If you are moving on a grid, then you'll need to find the grid square closest to where the vector points and set that as the destination. Obviously if constraining movement speed is required, normalize the final vector and multiply by the character speed before determining the destination.

• I'd add a distance-based falloff for the enemy vector, since the character needn't worry much about the enemy if it's far away; and conversely, if the enemy is coming near, the character should avoid it even by moving away from the goal if necessary. Commented Aug 31, 2013 at 20:03
• As Nathan suggested, a judicious transition function between the "seek goal" and "avoid enemy" should be employed. For example, a sigmoid (en.wikipedia.org/wiki/Sigmoid_function) might do the trick for blending between the two behaviours in terms of the distance from the enemy... Commented Oct 1, 2013 at 7:36