User:AaronR/Arbitrary direction melee surfing

I mentioned on my talk page a movement idea I was thinking up. I was trying to come up with various ways of doing bullet dodging in melee, and this was the only idea I could think of that would make any sense. The problem is, I don't know if it's been done before. (I hardly pay any attention to melee.)

First of all, this method wouldn't be used at all unless there were about 5 or less bots on the battlefield--as ABC has said, melee bullet dodging is useless if you dodge yourself into the center of the battlefield and there's 9 bots firing at you.

That said, the idea works like this. First, the bot tries its best to scan all the enemies and see if they fired a wave in the last couple ticks. It tracks all the waves on the battlefield at once.

Then, rather than picking a large number of points to consider like in Minimum Risk Movement, the bot picks a small number of directions--possibly fixed directions, in which case you'd get something like Tron.

The bot then precise predicts how far it could move in each direction before any wave hits it. This gives it a point for each direction, as well as the wave that would hit the bot if it moved in that direction. The movement then calculates the GuessFactor danger in the normal way (using separate data for each opponent, of course). In a practical implementation, this danger would be summed with a typical Minimum Risk Movement point danger factor.

Finally, the bot would move by directions rather than goto. It would constantly recalculate the direction to move in, relying on a "don't stay in one place" heuristic to get it moving.

So, has something really similar been implemented before? I see something kind of like this on Talk:Melee Strategy from the old wiki, but it isn't this specific. Gameplay-wise, do you think it would actually work better than plain-old MR movement?

P.S. One more idea that I have is a way to fix the "assume everyone is firing at you" problem with the implementation I just described--since most bots target the closest opponent, throw out any waves that pass "x" number of other bots before you.

« AaronR « Talk « 08:23, 2 October 2009 (UTC)

To my knowledge I don't think any robots have implemented this yet. Unless you count what I have been developing for a while now. One point that I think differently that you, is the decision on which direction to move. I think of choosing the point exactly same as Minimum Risk Movement, then predict each point, simulate the wave, and add the danger for any waves hit/passed between you and your target point. With some risk at center of the battlefield, I think you can use this as main melee movement. About directional-base versus goto, many MR-robot changes its destination point on-the-fly, they won't actually reached the destination (except HawkOnFire). But this method could be awfully slow, since it involve at least a hundred precise predictions per tick.

To your PS, many melee top bots, which you will want to dodge better, doesn't choose target at all =) --Nat Pavasant 08:51, 2 October 2009 (UTC)

When I was thinking about this algorithm, I was explicitly trying to design it to be as fast as possible. That's why it only picks a small number of directions instead of a large number of points, and stops as soon as a single wave hits. Your idea would probably actually work better, though, because it would account for multiple waves. Also, I know that most MR movement bots don't reach their destination every time, but I wanted to emphasize that my design works almost entirely with directions instead of points.

As for the "top bots don't choose a target" bit--top bots may not choose a target explicitly, but the effect is somewhat similar. For example, last I heard Shadow's gun weights possible target angles on inverse distance. With your multiple-waves method, you could effect this in reverse by weighting predicted waves on inverse travel distance or inverse travel time. Then you wouldn't have to throw out any waves, but it might be crazy slow. « AaronR « Talk « 11:27, 2 October 2009 (UTC)

Garm does something like this. It has 4 differen movement directions (0,90,18, and 270 degree), yes like tron... It predicts its movement for about 20 ticks in each of this directions. You shuld be able to see this in garms debug graphics (take a version which was entered in melee rumble: Garm 0.9u). But it was more of an extension to the 1on1 Surfing and is horrible slow. Using a differend movement for the first half of a battle would surely increase speed and score... Old versions surf every wave, weighted on distance. The newest one only close waves. I focused on the 1on1 part during my movement code cleanup, i removed some bugs and changed some elementary things. Therefor the melee part technically works, but it needs some new tuning.

If you are intrested we could start a teamwork, we could start with Garm as a basis and extend or replace its current melee movement. Garms design is quite modular and supports melee wave detection, scancode etc. I havent looked at the (melee) gun for some while, but it should be ok for now. What do you think? --Krabb 13:03, 2 October 2009 (UTC)

Sorry, I don't really have enough time for a collaboration right now. Maybe in the future? « AaronR « Talk « 18:13, 2 October 2009 (UTC)

Nice thoughts here. I know a couple people have some Melee bullet dodging in the works, but I'm not sure how similar their implementations are. My (unreleased) attempts at a Twin Duel surfer work a lot like you say here: precise prediction in 8 directions until a wave intercepts, like a variant of True Surfing. If we ever add a MegaBot division of Twin Duel, I think you could do some very effective Twin Surfing with something along these lines. --Voidious 14:01, 2 October 2009 (UTC)

B26354 actually does what you described. I have a path-independent surfing algorithm that looks at all waves in the air and tries to find the safest point along a given path. To keep performance up, this bot starts out as MR then blends the two styles as the number of enemies drops, until it's doing pure surfing in 1v1. Right now the surfing won't kick in until the melee is down to 4 bots. I'm still trying to figure out how to surf even earlier but I don't want to limit the number of directions too early in the battle, and I'm already skipping too many turns as it is. --Darkcanuck 15:05, 2 October 2009 (UTC)

People talk about dealing with directions instead of points, but the approach I'm working on goes the other direction: use min-risk point generation, but with an extra-special point generation function. In Glacier, the min-risk point generation function I'm already using is very different than you find in any other min-risk bot I know of: Instead of choosing points at or within a certain radius at random, it uses a fancy algorithm to generate a fairly accurate polygon of points reachable within x ticks (I can't remember x off hand), and chooses random points from that polygon. What I specifically had in mind when I designed the polygon generation algorithm, was to in the future adapt it to different "end conditions". The current "end condition" is a number of ticks, but I can also generate a polygon of the area area reachable "before wave y hits". By using this special point-generation function for min-risk, I only evaluate points that are reachable before the wave hits, and all that needs to be done to evaluate each of a plethora of points is to check the danger of it's position on the wave, and tradition min-risk factors. There are other details (i.e. special condition when moving and there is not enough time to get back to the current position before the wave hits, or how to surf multiple waves), but my main idea is that a min-risk can be adapted to surfing without needing to do precise prediction for every evaluated destination point. --Rednaxela 15:22, 2 October 2009 (UTC)

Looking at Glacier code, you are already simulating all your VBs. What is the difference between checking for VBs and Waves? Btw, I used to think of direction, but after re-considering, I'm using points too. --Nat Pavasant 16:12, 2 October 2009 (UTC)

Ignore the VBs in Glacier's code. They're a temporary thing because they were the fastest way to do some handling of the fact that the exact firing tick is unknown. --Rednaxela 17:23, 2 October 2009 (UTC)

Your polygon idea sounds interesting, but I'm not sure why the fuss over directions vs. points. Every point implies a direction and every direction leads to a series of points, don't they? --Darkcanuck 16:42, 2 October 2009 (UTC)

They aren't that different I suppose, but with simulating multiple directions, you'd do a precise prediction for each. My reachable area algorithm is avoids that by tracing the boundary of the reachable area once. It also makes it less restricted to certain directions and such. --Rednaxela 17:23, 2 October 2009 (UTC)

My attitude when I was thinking about this was "simpler is better". The polygon thing might be really effective, but I object to it on principle. It just seems way too complicated for melee, since you can't know the exact timings of every wave anyway.

Come to think of it, I'm not really sure it's useful to do precise prediction with MR points at all. Given the potential discrepancy between a wave's detected position and the bullet's actual position, the number of waves in melee, and the inability to predict very far into the future on a constantly-changing battlefield, it might be better to just use geometric methods to estimate wave hits. « AaronR « Talk « 18:13, 2 October 2009 (UTC)

Well, the polygon method isn't actually that complicated. It's certainly rather different, but I see it as little different than precise prediction. In fact I consider it simpler than precise prediction because I don't need to simulate my own go-to movement and such and makes evaluation of points no more complicated than normal min-risk. As far as precision in melee goes: That's why I don't intend to try real surfing that learns until there are only 2 or 3 enemies remaining. With larger numbers, I simply intend to use it simply for somewhat enhanced dodging of head-on-targeting. --Rednaxela 19:06, 2 October 2009 (UTC)

Here's an idea I just thought of. What about doing precise prediction just like in True Surfing--predict one direction perpendicularly forward, and one direction perpendicularly backward. Except that you do that for every opponent. That would mean that you only have to do 8 precise predictions for 4 opponents, you can predict wave hits exactly, and the points you get are guaranteed to be good with respect to that opponent. Are there any bots that do something like that? « AaronR « Talk « 19:36, 2 October 2009 (UTC)

I don't understand what "the points you get are guaranteed to be good with respect to that opponent" would mean. It's no different than choosing different directions like you talked about before, except that it happens to use ones perpendicular one enemy, for no good reason I can see. For example, if you're fighting two remaining enemies, surfing along the orbit of one seems silly, and less optimal than other paths. --Rednaxela 19:48, 2 October 2009 (UTC)

It's just another way to reduce the number of points you have to consider. Might work, might not. Knowing my ideas, probably not. ;) Based on the description on the B26354 page, it looks like that bot does the same thing, but orbiting corners and other arbitrary points rather than the enemy positions. « AaronR « Talk « 20:30, 2 October 2009 (UTC)