BerryBots demo
The highlighted comment was edited in this revision. [diff]
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. :-)
Just wanted to say this hasn't died... I've been working on it a lot and it's actually in a pretty stable and releasable state. I'm mainly waiting on clearance from work that I can release it. I don't expect that to be a problem (gone through the same for Robocode bots / WaveSim before), but you never know...
A couple weeks ago I ported the graphics to SFML and I've got it building / running on Mac and Linux now. I want to make a full GUI for the “real computer” version, but right now each match is just launched from the command line like the Rpi version. Teams, both weapons ;), all the events, security stuff, stage-loaded ships, graphics, packaging and loading bots/stages with or without source, and bot / stage APIs are all fleshed out and working smoothly. I tried writing a slightly decent gun today and it's definitely not at all a straight port of concepts from Robocode-land. I think the team setup is pretty sweet, and with one more feature to the stage API you could write a pretty legit CTF stage, which I think would be pretty cool.
SFML supports Windows too, but my use of Unix tar for packaging/extracting bots doesn't. So it will be a little work to support Windows, probably using zlib for zip stuff. Main issue though is that I don't even have a Windows machine to work with. Maybe I’ll grab a copy of Windows later if I’m feeling really dedicated to this project. :-)
Yay! Finally got permission to release this. It's pretty complete as far as game play and what features I wanted for the Raspberry Pi version, and all the same is working on Mac/Linux. So I'll get everything together and release that version first. Folks could certainly start making bots and stages, sharing them, and having fun with it. But there are still a handful of pretty important things I want to get done soon:
- A cross-platform GUI version. Working on this now, about halfway done. Before this, individual battles are launched from command line.
- CPU time limits. I have CPU tracking in place and I know how I want to do the calibration / enforcement, just haven't finished it yet.
- Windows support. Nearly everything should compile/run fine on Windows, including all the libraries I'm using. The main blocker is I don't have Windows. Now that I know I won't be flushing this down the toilet, I may just cough up the dough to buy a copy of Windows for this project.
Hoping to have it up on GitHub / new web site / some new YouTube vids soon. :-)
Unless it gets really complicated, I can try to get the Windows version working. (I use Linux, but have a copy of Windows). I'm pretty busy for the next few days, but I should be able to work on it starting this weekend. Also where can I download the source?
Hey thanks... It's not anywhere yet. :-) Gearing up now for a first release, probably around this weekend. I'd be curious to hear how it goes, but it would be a bit more than just a simple compile. For a fully functional binary release that supports un/packaging bots, I need to replace my use of the mkdir and tar Unix commands. You'd also need to build SFML 2.0 from source because it's not officially released yet.
And of course I need a permanent solution for future versions, too. My main concern is whether I need Visual Studio, or if I can do it with free tools like g++ as I use on Mac/Linux.
Windows has MingW you could use, which is a gnu compiler, meaning using it would likely be more compatible then using VS. However you can get the express edition of VS for free (which has 32 bit c/c++ compiler). It even has an IDE.. which actually I think you 'have' to use, at least for building.
