EnderBotV2

EnderBotV2
This next iteration of EnderBot is much better - it has aggression and defensive options. It chooses whether to fight or stay focused on the objective based on its current status and the other player's/bot's status.
It still only supports CTF, but that is easily changed.
Shielding is still bugged, but is better than it was.
WARNING: THIS BOT IS CPU INTENSIVE. It took up both of my cores at 80%, and I have an insanely fast CPU.

Format of arguments:
<Skill Level [0-1]> <Agression [0-1]> <Defensive [0,1]> <Max Speed [0-1]> <Switch Threshold [0-1]>

Definition of arguments:
Skill Level - 0 is impossibly bad, 1 is very good.
Agression - 0 means that it only focuses on its objective, and 1 means it goes after any enemy ships.
Defensive - 0 means that it is an offensive team member and 1 means that it is a defender.
Max Speed - 0 means that it won't move, 1 means that it will go as fast as possible.
Switch Threshold - How often the bot switches orbit direction when fighting with a ship. 0 means it is always switching and 1 means that it only switches when its shield is constantly on for 20 steps.

Implementation (Creates 2 bots per team, one defense and one offense. All are easier bots.):

  Code:

1. Robot 1 EnderBot.lua .25 .5 1 1 .25    # difficulty, aggression, defense, speed, dodging
2. Robot 0 EnderBot.lua .25 .5 1 1 .25
3. Robot 1 EnderBot.lua .25 .5 0 1 .25
4. Robot 0 EnderBot.lua .25 .5 0 1 .25

[karamazovapy]

The bot really only needs to check gametype once per game, right?

You might be able to reduce the CPU load by having the gametype detection in doObjective run once in the Main block as opposed to every tick.

Similarly, (for now anyway), the arguments you set for defense/aggression/etc aren't going to change mid-game. There's no reason to eat up CPU and run tests on those values every tick if they're not really dynamic.

I also wonder if there's a way to reduce the number of tests called in the compare Priority block. Is it really necessary to check for asteroids every tick if there aren't any asteroids in the level to begin with? Do spybugs merit a test on every tick? Technically, you're checking each of these things TWICE thanks to the first and second priorities...

I have to assume the high CPU burn is a result of the massive number of tests each iteration of the bot computes on every tick. The only reason I even bring it up is that most of the VPSes are pretty low-powered and won't be able to sustain high-burn bots.

[watusimoto]

Those are all valid possibilities for the high CPU consumption, and it's definitely good practice to make the bots as efficient as possible. However, I suspect the real problem is with getWaypoint(), though I don't yet know why. Try commenting that line out (I know the bot won't work), but I would expect the CPU consumption to fall precipitously.

If one of you would actually try that, I would appreciate it.

Did anyone actually bother to try using the bot rather than discussing the reasons why the bot is somewhat slow? It's not the fact that it uses A* though. I think it is the game in general.

[watusimoto]

I've played around a bit with the earlier EnderBot, and it has the same problem, as do every bot I've done myself that uses pathfinding. There is a lot of stuff going on before it even gets to the A* code -- line-of-sight checking, searching for which zone an item is in, etc., that are pretty expensive. There are some optimizations I can make to reduce some of that processing, (e.g. if the target hasn't moved, I can skip figuring out which zone it's in, and use a cached value; maybe only do the waypoint processing every second frame; etc.). Maybe I'll make a pass at that tonight. I've found that when I have several bots using getWaypoint(), things get pretty slow. When I don't, performance is much better, though there are still occasions where things get bogged down for reasons I don't yet understand.

[karamazovapy]

Sorry - didn't mean to be such a turd. I only have the mildest passing interest in bots right now and don't do much more than scan through the code. I'll keep my thoughts to myself.

It's fine, I was being kind of a jerk too. I think though that this is the first bot that I would actually bother to play against and it annoys me to see it untested by others.
Actually, for all of your testing fun, I'll put up a server with them.
EDIT: Er, never mind. It crashed when I tried to join my own server.

[karamazovapy]

I think though that this is the first bot that I would actually bother to play against and it annoys me to see it untested by others.

I just tried to load these guys up in 012a and it crashed.

I'm sure the younger players would LOVE to test the crap out of your bots...if they could figure out how. You'd have a captive audience if you could make it easy enough for them.

Sidebar: What happens if you load a bot that uses waypoints into a level with no navmeshes? Is that what caused my bitfighter to asplode?

[watusimoto]

If people want to test the bots, they should really use 013. There's so much new stuff going on that I gave up backporting to 012.

Not sure what would happen if you used getWaypoint() with no navMeshZones. It might crash, but what it should do is fall back to line-of-sight navigating; i.e. if it can see the target it will go there, else it won't.

If you're motivated to do some meshzoning, I can try to prioritize some tools for creating them. You can already hide the zones to look at the other stuff in your level. Obviously the zones need to be added to the dock, and I'd like to get some sort of convexity test and perhaps some custom snapping rules to make creating them easier.

[watusimoto]

Well, I figured out what a huge part of the performance problem is by, yes, playing with EnderBot. I'm not sure how to fix it.

The problem is the HUGE number of point objects being created during the shield analysis. The allocation, deallocation, and garbage collection of these objects just overwhelms the system.

Try commenting out the call to shield(), and you'll see performance improve dramatically.

So. Either I figure a way to make this more efficient, or we get rid of point objects, and do all the math using good ol' x and y variables and traditional functions.

[watusimoto]

OK, so I rewrote parts of EnderBot2, here: http://bitfighter.pastebin.com/dqJ4MRUs

This will only work with the latest version of Bitfighter, which I will upload shortly. While there are many minor (trivial, probably) optimizations I could make, the only real change I made was to not use the point object at all. The modified version of Bitfighter returns a pair of numbers wherever it previously returned a Point, and I wrote a couple of local functions to handle various point functions. I was a little sloppy in places, but you'll definitely get the idea.

The result? About 10x better performance.

There's still some things I can do on the C++ side, but it looks like the strategy of using lots of small, disposable objects (i.e. Points) to pass values back and forth just isn't worth the overhead, especially with things like Points where handling the raw coordinates isn't too bad.

Take a look, and let me know what you think.

Note that it may be possible to encapsulate some of the x,y stuff into a simple table; that should hide some of the complexity, but still yield pretty good performance. I may try that tomorrow.

[watusimoto]

Or, if you prefer the more object oriented flavor of the original, you could do something like this. This also seems to perform very well: http://bitfighter.pastebin.com/gQ1YfTgi

Note that this also requires last night's build, and could be enhanced by having the C++ code return actual Lua point objects rather than creating them on the script side... i.e. instead of:

  Code:

1. local botVel = Point:new(bot:getVel())

we might be able to write this:

  Code:

1. local botVel = bot:getVel()

That would take a minor modification to the C++ code, which I'll try tonight. Also, with another mod of C++, instead of this:

  Code:

1. function canSeePoint(pt)
2.    return bot:hasLosPt(pt[1], pt[2])
3. end

we could write this:

  Code:

1. function canSeePoint(pt)
2.    return bot:hasLosPt(pt)
3. end

and get right back to the original.

One other advantage of this approach is you can easily add your own methods on the point class if you want. At the bottom of the file, you'll see the implementation of the lua-based point class. If we go this route, we would simply put that code into one of the lua init files, so it would be available to all bots.

Note I made a few edits to increase efficiency and clarity.

Sweet! That's good to know that point objects aren't in Lua and are in fact faster if done directly in Lua. Can't you just add the point objects you demonstrated in your version to the lua_helper_functions.lua file?

[watusimoto]

Yes, and I probably will... I want to do a little more research, but I think I found the main bottleneck.

[watusimoto]

Aslo, I made a few more efficiency modifications to the bot. Things like getting the bot's location once in getTick() and storing it for use elsewhere, rather than regetting it several times, and pulling some calculations out of loops and getting rid of unused variables and the like.

I haven't actually tested it yet, so it's possible I broke something. Use the pastebin diff function to see what I did.

http://bitfighter.pastebin.com/5GM6Ktux

[watusimoto]

Fixed some bugs in the latest version:

http://bitfighter.pastebin.com/PbadNP0k

[watusimoto]

Just one more thing: going back and trying the different approaches again, the non-object oriented version seems to perform significantly better (at least tonight ) than the more object-oriented one... that is, tracking x & y manually is faster.

This kind of makes sense, as putting them into a table requires some real overhead that dealing with primitives does not. On the other hand, it really puts more burden on programmers and creates more complex looking code.

So... this is what the best performing code looks like:

http://bitfighter.pastebin.com/dqJ4MRUs

Not pretty.

[karamazovapy]

Not pretty.

Loi...that code looks like a freaking algrebra class...!

Eh. I've done worse in my own programming before I understood OOP.

[watusimoto]

I had a new idea on the way in to work this morning that might give us OOP without the overhead of creating so many point objects. We'll see if I can make it work!