View source for Talk:Path Surfing

As-described this reminds me of what I was working towards back in 2012 or so for a new movement engine that I never quite completed. I'm not quite sure how far BeepBoop is going with it, but what had started on was intended to have extremely comprehensive coverage of all possible non-redundant paths a bot could be maneuvering. Seeing this page here got me looking at my old backup files. I thought I remember talking about it some on the wiki at least in passing but can't find it. The main thing I remember finding tricky was the optimization required to make it not be absurdly slow, while not compromising on the range of movement options available. Maybe I'll pick that back up again some time.

I remember this, you were discussing using a lookup table but running into file size limits.

I still want to go back to my idea of surfing future waves, so you don't just control how you react, but also proactively you control what the enemy sees at fire-time. This way you could dynamically 'discover' motion patterns like stop-n-go, which force even linear guns to shoot HOT. I'm sure many other classes of guns have similar weaknesses which we can't see...

BeepBoop uses something like a lookup table (actually a kd tree) for finding paths, but a pretty small one. Given a current velocity, desired distance to travel, and desired ending velocity it outputs a "path" (sequence of 1s/-1s/0s corresponding to calling setAhead(100/-100/0)) that approximately meets those criteria. When its surfing, BeepBoop sets the desired distance to one that will take it to a low-danger area of the wave (kind of like GoTo surfing) and sets the desired end velocity to 8, -8, or 0 randomly, which means it will try out a variety of ways of getting to that area. It then precisely predicts the looked-up paths along with the standard going forward/backward/stopping paths true surfers use.

My bots AgentSmith and Wraith do path surfing, but in a more generalised manner which in theory would work in melee although my bots have never been made to work in that mode. Its obviously not top tier and I always meant to do a write up but basically they generate a bunch of possible paths, estimate the danger of each path and then choose the least dangerous path. Its general because the bot does not get restricted to just forward/back around the target but can move anywhere within the max prediction ticks, including turning towards/away from the opponent. This means it uses no special anti-ramming code it just does prediction of the opponent path like we do for bullets and then just assign danger to the opponent. I might do a full write up at some point but it makes around 20 random paths each time it starts evaluation, and then uses run-time genetic algorithms (RHEA) to improve the path population over a few ticks. Its optimised like no-business in order to get it to run, and they are both still slow bots, but it does work pretty well. There are definitely improvements that can be made to it as well.

Sounds awesome!

I was always tuning bots against DoctorBob to get 100%, and a few ramming bots to get 80%+, however I always find it challenging and tricky. If random path & RHEA based approach can get better than that, I will regard it as the next innovation since 2005 ;)

Looks like that Path Surfing is one-step towards motion planning in phase space, where not only x, y but also velocity (momentum) is considered. And looks like finding path that minimizes wave danger can be reconsidered as weighted region shortest path, where distance is weighted in some region, e.g. wave region.