Sir Robin Bravely Ran Away - looked for a more elegant answer and received a class in using Vector

Adventurer
21

I was thinking a bit more about the fleeing algorithm, trying to keep it simple, but effective.

Weights

To make a difference between enemies, you need to assign different weights to them: a brawler is obviously a more serious threat than a munchkin.

J_F_B_M suggests some simple weights (distance, health, maxHealth), but it’s better to define something more specific. I compiled a small table of the most common units and their main stats:

|   type   | health | speed |  dps  | range |
|----------|--------|-------|-------|-------|
| munchkin |    14  |   12  |    4  |    3  |
| thrower  |     7  |   11  |   18  |   25  |
| shaman   |    60  |   10  |   33  |   30  |
| scout    |    75  |   12  |   24  |    3  |
| fangrider|   100  |   30  |   50  |   20  |
| ogre m   |   120  |    5  |   36  |    3  |
| ogre f   |   250  |    7  |   60  |    3  |
| skeleton |   300  |    7  |   38  |    3  |
| brawler  |   500  |    4  |  150  |    5  |

I guess that the dps is a good basis for the weight, but it should be combined with the distance, range and speed: a brawler at 20 meters is harmless, but a few shamans at the same distance can be deadly.

I couldn’t come up with a formula that incorporates all this, but I’m working on it :slight_smile: If you have any suggestions, share it with all of us! Probably a precalculated dictionary would be the best:

weightByType = {"munchkin": 4, "thrower": 18, ...}
weight = weightByType[enemy.type]

Walls

If you want to really flee, you should avoid walls too. As suggested above, you could give some weight to the wall, but I didn’t find an easy solution to do that. You could manually specify wall points on the map (e.g. every 5 meters) and assign a weight to them (=boring job), or you could try to detect walls with an algorithm (=probably an overkill). So what to do?

I think the easiest solution is to check if the calculated flee vector (let’s say 5…10m ahead) is “clear” (using isPathClear): if it’s clear - go! If not, try to “scan” what’s ahead:

(Awesome paint skills here, too :relaxed:)

  • green dot - hero
  • red dots - enemies
  • black arrow - calculated flee vector
  • blue arrows - test vectors for “scanning”
  • green arrows - possible flee vectors

This is still not fail-proof (e.g. corners), but I think it can be coded in a few lines (rotate the calculated flee vector 10…15 degrees until it’s “clear”), so it might be good enough.
[edit] Scanning in 0.2…0.3 rad steps (alternating left and right) seems to work OK.

If you have a more efficient and/or simpler solution, tell us!

To consider

  • Limit the calculation distance: anything further than 30 m could be safely ignored. For melee types this could go down to e.g. 10 m.
    [edit] A more precise way could be to ignore enemies that are further than their attackRange + speed/2 (see notes in next post)

  • [edit] Define escape points: defining a few safe “escape” points per map should be simple, and could make the fleeing algorithm more efficient. (see following posts)

  • Special types: witches, warlocks, etc. Hard to calculate a dps for those - but it’s probably best to stay as far from them as possible :smile:

More…

Finally, here are some starting points for reading, if you want to go deeper in the subject:



Please :heart: it if you find this post useful! Thanks

4 Likes
22

You can get some really odd errors with .isPathClear, unfortunately. I have another topic on this board describing them. My current theory is that you may need to check to make sure you’re not testing .isPathClear when the resulting vector puts you outside the playing field. I’m currently leaning towards another direction:

  • create an array of “run-points”.
  • Use self.findNearest(array) to identify the closest run-point (any hints how to get from the point to the array # btw? I’m going to have to look into that. :wink:
  • Evaluate the 2 run points on either side
  • Move towards the safer run point
    I haven’t coded it out yet, however.
23

I coded my version and it seems OK-ish. Tharin - who is not a speedy guy (current maxSpeed = 8) - can survive 30 seconds on Backwoods Brawl level 5 (with 1600 health), only by fleeing. Not a bad start, but I think I would need the ring of speed and/or a faster hero to get better results :slight_smile:

About your points:

  • I didn’t have any problems so far with isPathClear, although I tested my code only on Backwoods Brawl. Are you sure it’s bugged?

  • “run-points”: it’s a good idea. Defining a few safe “escape” (run) points should be simple, and could make the fleeing algorithm more efficient. I will add this to my previous post for completeness.

  • finding the closest escape point: I’m not sure I understand you correctly, but it pretty easy:

escapePoints = [Vector(10, 20), Vector(50, 70), Vector(60, 10)]
targetPos = self.findNearest(escapePoints)
self.move(targetPos)
  • If you want to evaluate the “risk” of getting to each escape point, you could do the following:
  • calculate the vector from your position to the escape point
  • calculate the “center of mass” of the enemies on the map
  • compare the calculated escape vector with the vector pointing from you to this “center of mass”
  • if their directions are close (small angle difference), then it’s risky, otherwise it should be OK
    (I will try to put a sketch here)

Some notes to my previous post:

  • I decided to ignore enemies that are further than their attackRange + speed/2: this should be safe enough, as it would take 1/2 a second for them to get into attack range, but by that time I should be in a different place :slight_smile:
  • when the calculated escape vector hits a wall, scanning for new escape vectors in 0.3 rad (~17 deg) steps - alternating left and right - seems to work OK
24

I actually envisioned the escape point concept a little differently. I’m looking to kite in circles and/or potentially irregular shapes, depending on the level. The trick would be identifying the nearest point on the escape track … and then NOT heading to it but rather heading towards either the point before it or the point after it on the track depending on an evaluation function. If you let the escape point pull you directly to it, it could become a corner in the middle of the field (IMO … will be interested to see how you handle it).

My comments on isPathClear can be found here:

http://discourse.codecombat.com/t/backwoods-brawl-in-python-error-ispathclear-is-not-defined/5208

The good news is I actually am now on Backwoods Brawl 5 (1600+ hp and a ring of speed helped, yes). The bad news is I can get the “isPathClear” undefined error when surrounded in the middle of the screen now. :frowning:

25

You can dynamically generate run-points by abusing that flags don’t need to be collected:

#Init with one point and use wrapping access-logic to target-candidates
runPoints = [Vector(10, 10)] # Arbitrary chosen run-point
minAddDistance = 5           # Minimum Distance change for a run-point to be added

loop:
    flag = self.findFlag()
    
    if flag and flag.distanceTo(runPoints[-1]) > minAddDistance:
        runPoints.append(flag.pos)
    
    # Logic for fleeing
    nearest = self.findNearest(runPoints)
    index = runPoints.index(nearest)
    #wrapping logic. (-1%10 = 9)
    previous = runPoints( (index-1) % len(runPoints) )
    next     = runPoints( (index+1) % len(runPoints) )
    
    # Decide between previous and next

This assumes that you moved your flag in a path around the map. If you do big jumps or even crossovers this may not produce the correct result.

Is there any interest in an algorithm that automatically generates a path at the outer edge of the field? I have an idea, but it would need some time to make it work and would only implement it if there is an actual need for it. It depends on isPathClear though.

If yes send me a PM via the flag symbol below this post and I’ll edit this post or post a new one here.

26

The code in that link above re Backwoods Brawl - once corrected (thank you ant!) and some of the parameters tweaked slightly - actually can do just that for kiting purposes. Apparently, the isPathClear errors I was generating were actually because I #@$! up in generating the test target and created some Infinite vectors. (Oops! ^2 != **2 in python and computers still hate division by very close to zero.)

27

With the ring of speed, my updated fleeing algorithm and a few summoned soldiers, Tharin now survives 59 seconds on Backwoods Brawl level 5! Yahoooo! :smile: I’m gonna make it!

…and with a bit more tweaking he easily finished the level with 500+ hp!