[Cixelyn]

Yeah navigation via A* / other traditional algorithms is almost always a no-go in Battlecode because of the way the bytecode limitation works. You almost always have to create some extremely custom pathfinding algorithm tuned to the constraints of the engine.

The simple algorithms are stuff like bugnav (walk in your desired direction until you see a wall then attempt to trace around it), but you'll find that even in something as simple as bugnav, there are a _ton_ of edgecases you have to account for in a discrete implementation that results in robots tracing around each other / stuck in infinite loops, etc.

Our 2012 bot uses a special implementation of the discrete tangentbug algorithm that allows us to precompute squares during rounds which we have extra bytecodes to spare[1]

It's probably _the_ most complex part of our codebase, and the person who wrote it doesn't even really understand how it works anymore.

[1] https://bitbucket.org/Cixelyn/bcode2012-bot/src/default/team...

[dthunt]

I think the last time we played, one of my teammates came up with 'detractors'; i.e. 'stay away from here, it's bad news', once a bot was sure that a place was not good for pathing, they would drop one and it would make its way around to the other bots.

That actually worked surprisingly well. Our implementation had briefly stupid behavior in a few scenarios, but after a lot of testing it was clearly our winner.

It looks like this year isn't as big on the pathing, as 'every square on the map is traversable, and there is no longer any distinction between ground and air units.'

That's mighty unfortunate. I thought that was one of the more interesting challenges.