BerryBots demo
The highlighted comment was created in this revision.
Figured I'd take this to a separate thread. =) Posted another couple of vids with progress on the Raspberry Pi game I'm working on.
Still a lot to do but I think it's coming along pretty well.
Man, you are totally of the hook :). Looks indeed very neat. The race looks and sound as it could provide a lot of fun and maybe some nice pathfinding programming.
Well done!
(Sorry, gotta take this back to LiquidThreads.. =))
If anyone's curious, here's some TPS measurements (with graphics off) of Lua vs LuaJIT on the Raspberry Pi and my 2009 MacBook Pro 2.8 GHz. RandomBot is a trivial bot like sample.Crazy, BasicBattler is a slightly non-stupid bot with a simple Minimum Risk movement and random linear gun.
- 2x BasicBattler
- Rpi Lua: 343
- Rpi LuaJIT: 632
- MBP Lua: 5967
- MBP LuaJIT: 19101
- 8x BasicBattler
- Rpi Lua: 44
- Rpi LuaJIT: 88
- MBP Lua: 766
- MBP LuaJIT: 2377
- 2x RandomBot
- Rpi Lua: 782
- Rpi LuaJIT: 1053
- MBP Lua: 17781
- MBP LuaJIT: 28154
- 8x RandomBot
- Rpi Lua: 119
- Rpi LuaJIT: 182
- MBP Lua: 2429
- MBP LuaJIT: 4159
Obviously the LuaJIT is far superior in speed.
LuaJIT vs Lua
- 2xBB
- RPI: x1.84
- MBP: x3.2
- 8xBB
- RPI: x2
- MBP: x3.1
- 2xRB
- RPI: x1.35
- MBP: x1.58
- 8xRB
- RPI: x1.53
- MBP: x1.71
Even considering a margin of error, it seems the x86/amd64 version is either more mature or has a more leverage-able machine code (assuming your mac book is intel rather then PPC based).
It seems to scale up on complexity. Be it more bots or more complex bots.
I think there might be a fixed, constant overhead each time you call the Lua code, so the actual advantage within the Lua code is actually much higher. From the results with RB, it seems that LuaJIT also has a smaller overhead constant.
About the difference between AMD64 vs ARMv6 instruction set, one is CISC other is RISC, so the CISC will benefit more from the pure assembly components that were part of LuaJIT because more suitable instructions can be used to do multiple steps in one instruction. At least, that's my guess.
Oh, definitely the advantage is much higher in the pure Lua code. The more time being spent in Lua code, the more you'll gain from LuaJIT. I wouldn't be surprised to see more like 10x-20x gains with really complex bots. Some of the benchmark comparisons on luajit.org go as high as 50x.
I'm a little surprised 8x RB has a higher gain than 2x RB. The game engine is pretty fast, but some of it is <math>O({n^2})</math> (the line of sight and ship-ship collision detection), so for something like 8x a trivial bot, the engine is using a lot more CPU, which obviously gains nothing from LuaJIT. But I guess it's also sending more event data to the bots each tick, too (even if it's going unused here), which is sped up by LuaJIT.
Good point on RISC vs CISC, I hadn't thought of that. It could also indeed just be more mature on x86.
Interesting results.
Regarding some of the O(n^2) time things, I wonder if it would be worth trying to improve those via methods that subdivide the area (either tree or grid), to avoid having to do a check for each bot, for each bot. Of course, the question is how many bots does it take for the cost of maintaining the data structure to be made up for. I suspect more than 8 unfortunately.
It also depends heavily on the stage configuration - the above tests were on empty battle fields with no walls for checking line of sight. It's fairly well optimized as it is - for line of sight, it ignores the outer walls, doesn't re-calculate AxB and BxA, and line intersections involve no trig at all. And circle/line and circle/circle intersections, for collisions, will short-circuit quickly most of the time.
I considered trying some fancy improvements to the line of sight stuff - sorting the walls by how frequently they obstruct vision would be a big one - but as it will probably be quickly dwarfed by the CPU power required by bots, I figured it was better not to waste time on it and to keep the code simple.
One question just came to mind. Are you using floating point positions in BerryBots? If so I wonder if integer based (but still with better resolution than display pixels) would be much faster.
Yeah, it's all floating point. That's an interesting thought... Just with integer math being faster than floating point? And I guess it might enable some algorithmic optimizations if I knew it was a grid of fixed size, but I'm not sure.
But I think folks like floating points (I know I do in Robocode). And while it might speed up the physics engine significantly, it wouldn't necessarily speed up bot algorithms. And I think it might make bot programming more complicated having to round everything in your code, at least with the current game rules.
I honestly don't feel it makes bot programming any more difficult really. Bots could still use the floating point if they want to and won't suffer being less accurate in a significant way. Consider that current robocode fields are measured with a size no bigger than 1200x1200 or so units, and that a 32-bit integer can store 1200 times one milion just fine. In robocode I doubt being one millionth of a unit off has ever mattered. Is more resolution really needed? When dealing in absolute coordinates it's more resolution than 32-bit floating point would give (24-bit mantissa).
Well, as a bot author, I like everything modeled in my code exactly as it is in the game physics. (I know you of all people can appreciate that. =)) But actually you're right, with high resolution and doing all conversions on the host side, it could be transparent and it would be faster. I'm just not sure how much faster, and it might be a fair amount of work. So I'll consider it and do some investigation, but it's probably not high priority for now.
I think the bots will quickly outweigh the game engine in terms of CPU time and that the users who care most about uber-fast TPS are probably the same users with pretty complex bots. I do want the game engine itself to be really lightweight and fast, but at some point it becomes more a matter of personal pride than actually adding value to the game. =) And I'm trying to curb my whims and stay focused on a nicely prioritized to-do list.
What would really make things faster is if the game rules didn't require bots to ever do trig or sqrt's. But it's too late for that at this point. Maybe in the next game... ;)
Actually, speed in bots has more to do with game tree size (complexity) than number representation. i.e. chess has an 8x8 discrete (integer) board and the top AIs in the world are incredibly complex and slow.
Want to make bots run fast? Add a real-time constraint (skipped turns), like Robocode has.
Sure, I understand that. I more mean that at least your CPU time can be spent on game related strategy stuff instead of doing trig and sqrt's. :-)
