This week’s accomplishments are mostly of the bug crushing variety. I reduced the likelihood that the ‘no more jumping for you error’ occurs. I’m not convinced it’s completely resolved. What exactly is this error you ask, well let’s start with a screen shot (finally) of physics body debug render. The player is represented by the small square on top of the circle on the bottom about 1/3 of the way in from the left side.
Since jumping is conditional on having something to jump off of at present, the circle fixture checks to see if it has contact points near it’s bottom. if yes then jumping is allowed if not no jumping for you. At various times during testing the player stopped responding to jump commands while appearing to be grounded visibly and with in a few thousandths when the numbers were reported. The cause of this phenomenon is it seems that when Box2D contacts are reported to a libgdx box2d contact listener only the most recent contact point is retained. So if the player is contacted from the side, by let’s say a box propelled by an explosion, the circle would record a side contact and decide it was hovering making jumping impossible. The solution I used was to shrink the size of the circle ever so slightly, so that the box now projects out past the sides of the circle slightly. This has eliminated current instances of this issue, but I’m not convinced all cases have been eliminated.
In other news Rho_Bot stopped by long enough to find a problem with the explosion system. Basically too many explosions (to put a number to “too many” somewhere 3-4 range) in rapid succession caused the program to hang while the physics calculations were completed. This was solved by limiting rocket ROF which was planned anyway.
I’m beginning to remember why I didn’t want to do a status update post every week when we started this website.
It’s that what gets accomplished in one week tends to be easily summarized in a few words. For example this week I got projectiles working completely and explosions working partially (unless being able to walk on compressed air waves is a feature in which case explosions are done), and while someone who does game development would think that’s a reasonably productive week when combined with bug crushing. Those of you who are not developers are likely thinking, ‘that doesn’t sound like much. Why didn’t he do more? And where are the screenshots.’
Well the screenshots are coming … eventually. I could post some box2D debug renders, but that’s just a bunch of rectangles outlined with different colors. Ahh the days when someone around here did artwork.
Speaking of Box2D I’ve got more things to say about it. Some good some bad.
The Good
I used Box2D to implement the explosion. I think it is fantastic and reasonably straight forward now that I’ve done it once.
The Bad
Things get stuck at the seams of butted objects; not always but often enough to be annoying. This is a known issue and is supposedly being worked on. Currently suggested is don’t place objects contiguously. This means that loading a world tile by tile is a no go.
On first implementations of things I frequently pass bad data or make inappropriate calls to the Box2D world. This is a normal part of the development process however since I’m developing on java and Box2D runs in native libraries I get lovely unhelpful error messages like.
Process finished with exit code 255 (Box2D, java, libgdx)
Which I got when I tried to add a new object while the world was stepping.
And
EXCEPTION_ACCESS_VIOLATION (0xc0000005), AL lib: (EE) alc_cleanup: 1 device not closed – (Box2D, java, libgdx)
[Update] which was caused by attempting to address(dispose of) a body that had been disposed of.
I also had an equally unhelpful error when I disposed of a shape before instantiating a fixture based on that shape. I’m too lazy to reproduce this error so no console capture for that one.
Since these crashes happen in native code that means that lost objects aren’t cleaned by the java garbage collector, and it’s entirely possible they sit around causing a memory leak. yay. Oh wait that other thing, booo.
Last week I mentioned screenshots for the platformer, and everyone here to see those will be disappointed, because instead of spending time adding content and updating graphics I decided to reorganize how level data is organized. Why exactly did I do this?
Because I could.
Also levels were defined in a combination of *.xml and *.json and I wanted to standardize it a bit. Now all level data is stored in a single *.json file. I also wanted to move level loading instructions into their own class. Previously level’s loaded themselves; however, the level class was getting long and moving the loading functionality seemed to be a logical way to split up the class.
So not a very exciting week when viewed from the easily demonstrated progress dimension, but streamlining level files and improving class compartmentalization should make things smoother going forward.
Contrary to all appearances. Since starting my new job I do have a substantial amount of time work on games. I’ve just been doing other things.
Currently I’ve decided to let Malwrath stay on hiatus, and work on something new over the next couple of months. I have three reasons for doing this
I’m out of practice reading and writing code. And since it’s always easier to start at the beginning than remember what’s going on in the middle. new project!
I wanted to experiment with level loading which is something that will be necessary for Malwrath.
I wanted to experiment with Box2d since it popped up on the list of libgdx options. And the idea of using a complete physics engine sounded neat.
So I’ve set about making a platformer (what better way to try out a physics engine?) about a small robot who jumps over aliens who are on fire.
I’ve been working on this for a couple of weeks and what have I learned so far. Maybe Box2d is not the best back end for a platformer. To start with this guy at GDC points out that jumping in platformers rarely if ever follows a consistent physical model. There are also some other articles around the web discussing other issues with using physics engines modeled on the real world as back ends for platformers. Frequently sighted is how to implement platforms that move without having them fall. Box2d, fortunately, has a work around for this by having an object (body) type that doesn’t respond to external forces. However after implementing all this I have a new issue which is the player sprite/physics object doesn’t want to stay on or ride platforms that move horizontally. And the solutions I’ve read for that all seem kind of kludgey.
There is no name yet, and maybe we’ll have some screenshots next week.
What did you miss. Well I quit my old job, got a new job, and moved. And during the adjustment period let this slide a lot.
Rho_Bot got a new job and is still deciding if he’ll be able to contribute on an on going basis. But dropped off a bunch of graphical assets for Malwrath before leaving.
Optimus Composite got a new job and discovered he had no time for writing. He might occasionally join us in the future but will not be a regular contributor.
Arnold Schwarzenegger Fun Fact: Terminator was the first time he’d ever say “Your clothes…give them to me” but it wouldn’t be the last, just ask the maid. (Image courtesy of the Terminator Wiki)
When you think of robots, you’ve got two kinds in pop culture: the helpful, friendly robots and the ones who want to kill all humans. The number nine entry on the Robot Round-Up started out in the second category and then kind of moved into the first. I mean, it still kills a lot of people, but it’s done to protect a very important human. That’s right, I’m talking about the T-800 Terminator….aka robo-Arnold.
Nothing strikes fear into the hearts of rebels like metal skeletons, apparently. (Image courtesy of the Terminator Wiki)
In universe, the T-800 model terminators were designed by Skynet and used as the basic foot soldier of their “kill all humans” army. For some reason, despite wanting to replace humans, Skynet thought the standard, bipedal human design was the best design for their robots and the T-800 is basically a walking skeleton that carries a big machine gun. It’s not the fanciest design, but it works. In the real world, the T-800 was designed by Stan Winston Studios. It’s a solid design from one of the premiere special effects houses. When we first meet the original T-800, it’s sent back in time to kill Sarah Connor. Skynet knows that the only way to stop the human resistance is to kill the man who would be their leader and what’s an easier way to do that than by killing him before he’s even born, eliminating his mother from the timeline. John Connor sends a man named Kyle Reese back in time to protect his mother (and possibly become his father—time travel in the Terminator universe is a bit confusing). In another bit of time travel confusion, the laws of time travel in the Terminator universe prevent Skynet from sending robots back in time unless they’re covered in flesh. So, Skynet coated the T-800 in synthetic skin and sent him back in time. For some reason, Skynet thought Arnold Schwarzenegger would blend in well enough in the 1980s, so that’s what the Terminator wound up looking like. (Funny behind the scenes story about Terminator: The casting director originally wanted O.J. Simpson to play the T-800 but James Cameron thought no one would believe O.J. as a homicidal robot.) Kyle Reese and Sarah Connor would work together and defeat the T-800 by crushing him in a hydraulic press (meaning we’ve got machine-on-machine violence), but that wouldn’t be the last time we’d see one in the movies.
The glowing red eyes are a nice touch, though it doesn’t exactly scream “stealth.” (Image courtesy of the Terminator Wiki)
The next time we see a T-800, John Connor has managed to reprogram one and send it back in time to protect his younger self from another Skynet assassin, the liquid metal T-1000. I don’t know how liquid metal gets around the “no robots unless they’re covered in flesh” time travel rule, but that’s how it happened. Still looking like Arnold, the T-800 finds John Connor and kills or wounds a lot of people protecting him. Seriously, there’s a pretty high body count in T2: Judgment Day, and it’s not all the T-1000’s fault. The T-800 eventually sacrificed itself at the end of the movie to prevent Cyberdyne from getting the technology from him that they use to create Skynet. Yes, I know, that doesn’t make much sense either. If the T-800 never goes back in time from a future where there is a Skynet, Cyberdyne can’t create the technology that would eventually become Skynet so then Skynet wouldn’t exist, but Skynet can’t exist without the T-800 coming back in time…sigh, sometimes I hate time travel.
However, the T-800 would come back in time one last time in Terminator 3: Rise of the Machines. This time, it’s clear that Judgment Day is more of an inevitability so all the talk of John Connor being able to stop it from happening in previous movies is rendered moot. One again, future John Connor sends an outdated T-800 back in time to protect his younger self from a more advanced cybernetic assassin. Even though Skynet developed liquid metal technology, which is really quite useful, they went back to the standard robotic endoskeleton model with a new after-market feature: boobs. The T-X model Terminator was a lot more dangerous because of the advanced technology inside, but it was still no match for a standard T-800 model reprogrammed by John Connor which begs the question of why Skynet keeps sending back new models when they apparently hit the pinnacle of killing with the T-800.
I wonder how Pops actually aged the meat on his frame. Does he smell like jerky? Is he teriyaki flavored? (Image courtesy of the Terminator Wiki)
We would see the T-800 one last time (sorry, I don’t count Terminator: Salvation because that really turns the timeline on its head and I’ve already burned enough brain cells trying to figure out the time travel here). This one was sent back in time by an unknown agent to 1973 to protect Sarah Connor. This Terminator, called Pops by Sarah and John, protected them many times and helped them travel through time to prevent Judgment Day. However, if Pops has been around since 1973, why didn’t he protect John or Sarah Connor in 1984 or 1992? Those seem like pretty important times to act as a protector but instead, John Connor had to send a different T-800 terminator back in time to do the protecting. Does that mean this one was just watching, saw another one of him kicking ass and just decided to sit this one out even though it was smarter due to the additional years of experience online and could better fight the T-1000? Again, time travel makes my head hurt…at least with robots, you don’t have to worry about aging, though Pops did age to blend in with humans better because we needed to find a way to justify old-ass Arnold Schwarzenegger playing the T-800 again since when they tried making a Terminator movie without him (Terminator: Salvation) it didn’t really work out all that well.
Let’s be fair, the T-800 was not a complicated robot design. However it was probably one of the earliest major pop culture examples of the robot as a relentless killing machine. Even losing is lower body in the first Terminator movie wasn’t enough to stop it from trying to kill Sarah Connor. It was that devotion to its job that allowed Sarah Connor to destroy it. However, it’s clear that the T-800 isn’t a bad robot. It was just programmed by an evil computer. When John Connor captured a few T-800s to send back in time, they were just as adept at fighting off robots as they were trying to kill humans. The T-800 endoskeleton is surprisingly resistant to a lot weapons and can take a lot of damage before failing. There aren’t any built in weapons systems, which seems like a bit of a design flaw for a robot soldier. Why wouldn’t you just build guns in so it could never get disarmed? Regardless, the T-800 is a robot that’s hard to stop and it was built that way. It’s nice to see some organization viewing robots as something other than disposable cannon fodder. Yeah, it was an evil super computer, but seriously, robot soldiers are a threat and they should be threatening. The T-800 definitely has that in spades.
It’s been a month of working on Malwrath’s Tower. and we’ve made a decent amount of progress if not as much as I’d like.
Somehow I got tasked with the exterior ground tiles. So the basic tiles are done, but they still need to be blended at the edges. And the more I look at the grass the more low frequency artifacts I see; so, we might have to revisit that one. We’ll see when we get some more decorations on top of it.
In terms of code I’ve got the monster and the character mostly set up. A basic AI that can move the monster around. A solid path finding algorithm. And if you whack the monster with your gray stick thing it dies and re-spawns immediately. Anyway enough of me babbling take a look at some screen shots with my awesome placeholder rectangles.
Monster using path-finding algorithm to navigate around the wallThe rectangle monster is dead, and the people rejoice
And that brings us to the schedule. Which is more or less on track although I did sop up a fair amount of buffer by reallocating it to extra blog posts I’ve done in April.
Oh God, the robots are coming to take our women! (Image courtesy of Wikipedia)
It should be no surprise that we here at Sarcastibots love us some robots (but not in that creepy we-want-to-have-sex-with-them way that some people do). Since our Scoundrel Round-Up was popular, we figured the next logical step was the Robot Round-Up (or as I like to call it “The Bender is Great! Bender is Great! Bender, Bender, Bender! Great! Great! Great!” list). We’ll be covering robots from all over pop culture, so we’re starting with an oldie, but a goody. First appearing in 1956, I figured I’d talk about the real star of Forbidden Planet—Robby the Robot.
Every super-scientist needs a good robot companion. (Image courtesy of Wikipedia)
Unlike a lot of entries in the Scoundrel Round-Up, Robby doesn’t have that much of an actual history to delve into. The robot was originally designed for the film Forbidden Planet. Robby was a mechanical man created by Dr. Morbius to be his servant. Dr. Morbius, apparently a bit fan of science fiction himself, ripped off Isaac Asimov rules of robotics when programming him—keeping him subservient but also, in an ironic twist, preventing him from saving Dr. Morbius from the Id monster because Robby was programmed not to harm humans and Robby understood the Id creature was just an extension of Dr. Morbius’s psyche. Destroying the Id creature would be tantamount to destroying Dr. Morbius, so he was unable to do so. Robby also originated quite a few modern movie robot traits since he does have his own personality and a rather dry wit. I almost see him as Marvin the Paranoid Android’s more optimistic grandfather. Unfortunately, Robby was a victim of anti-robot prejudice in the movie’s marketing campaign. Forbidden Planet posters showed an evil looking Robby carrying off a damsel in distress. However, Robby never looked that scary in the movie and the only time he carried a person (and it was a male crew member at that) was when it was to trying and save someone’s life. Even back in 1956, filmmakers realized they could make money by appealing to our typical anti-robot prejudices. That’s really all that can be said about Robby the Robot as himself, however, like any good robot, he had a long life and a history well beyond that of Forbidden Planet.
Robby still looks good after all these years. (Image courtesy of Wikipedia)
Robby the Robot was a fairly popular guest star or cameo in science fiction for a lot of years. Most of the shows he showed up in were during the 70s and not every appearance was the greatest (including on the Banana Splits Adventure Hour where he also apparently got a sex change as he was known as “Mildred the Robot”). Of course, any great robot from the 50s is going to show up in Lost in Space and Robby showed up a couple different times as different characters. Robby stayed busy for a lot of years, but sometimes, as a robot, you have to make ends meet and the last times he showed up on TV (as a robot and not just a prop) were on the short-lived Pamela Anderson vehicle, Stacked, in a nightmare and then in an AT&T commercial with WOPR (the computer from WarGames), KITT, and Rosie the Maid. Apparently, he and KITT became friends as they also did a GE commercial together a few years later. According to Craig Ferguson’s gay robot skeleton sidekick, Geoffrey Peterson, Robby is a frequent guest at robot parties, though C-3P0 is never invited because he’s a douche.
Robby may not have had a long history as himself, but the robot design definitely got around. Plus, a lot of the tropes of robot characters (like a dry wit and programming limitations affecting the outcome of movies) originated with him. Overall, Robby may have been portrayed in posters as a villain, but in reality, he’s a great robot and the granddaddy of them all.
In our second installment of Coder’s Corner we’ll discuss SpatialHashes. For those of you thinking, “This got intense fast… last month was IDE setup – shouldn’t this be some sort of libgdx ‘hello world’?” Tough. There are many, many tutorials for people (and robots) just starting out in coding and game development. There is less discussion on more intermediate and advanced topics. So that’s where Rho_Bot and I have decided to focus Coder’s Corner. To answer the other half of the initial question, we chose SpatialHashes specifically because I actually made one for Stoned in Space.
Which brings us to the question most of you may be asking: What is a SpatialHash? (Just to be clear we’re going to discuss the data structure used for accelerating collision calculations not the one for compacting loose spatial data.)
According to some eggheads: “Spatial hashing is a process by which a 3D or 2D domain space is projected into a 1D hash table.”
While this is probably true if you delve far enough into how the data is actually stored (It’s exactly how I backed my SpatialHash), I think it misses describing the concept in favor of describing the implementation.
At the most general level a SpatialHash is data structure where an object can be looked up based on its location in space. As a side effect, objects that are physically close together get grouped. Or to describe it in more computer science-y terms, a SpatialHash is a special case of a HashTable where an object can be referenced by its location. That means you can almost say SpatialHash = HashTable<multi-dimensional-point, object>. However, a salient difference between a HashTable and a SpatialHash is that HashTables almost always have unique key-value associations. For a SpatialHash this is not the case. Depending on your situation you might want a relation that links one key to many values or one value to many keys. If the SpatialHash is going to be used for collision detection, having a single key to a single value relationship defeats the point of grouping an object with things it is likely to collide with.
Figure the first. Graphical representation of a spatial hash
And collision detection was the reason that I created a SpatialHash for Stoned In Space. I originally anticipated there would be a lot more objects and, therefore, many, many potential collisions to check for.
You wish there were this many missiles in Stoned In Space
Having a large number of objects means that doing brute force collision detection would take up substantial computational time every frame and make the game unpalatably slow. So we needed a way to make the collision checks faster. I can hear the coders and cyborgs in the audience saying, “You want to partition space. Just use a QuadTree for that.” Maybe… But before we settle on a solution for the problem we should make sure we’ve accurately defined the problem scope. So, let’s round out our initial assumptions:
00. lots of objects (as previously mentioned)
01. uniform object distribution
10. uniform object size
11. Fixed world space (for example we’d always be working with 4 parsecs²; not sometimes 4 and sometimes 9 parsecs²).
Based on these assumptions it turns out that a quad tree would split down into the same number of cells as a SpatialHash. Which eliminates one of the major advantages of the QuadTree – fewer cells to check for collisions. And since the whole point of partitioning the collision space is to reduce the time spent doing collision checks, why not save additional time by sizing the cells in advance instead of splitting them every time collisions are checked?
Adding objects to a SpatialHash can be implemented two general ways. In what we’ll call “Method A”, each object can be consolidated to a point (finally we find an application for that whole center of mass concept from physics). In “Method B” we add an object to all cells intersected by its axis-aligned-bounding-box (aabb).
Method A has fast put and remove methods since it only has to deal with one cell. But since the information on the object’s size isn’t contained in the SpatialHash, all cells that might contain part of the object must scanned when looking for collisions. Assuming the object is placed in the cell that contains its center; the scan radius in cells should be “check radius = object radius / (cell size) + 1”. This method works well for uniformly sized objects with relatively low density. If all objects are approximately the same size it would be easy to size the cells to keep the number of cells scanned per object to nine. This also corresponds to the minimum safe scan number in this style.
Method B has slower put and remove methods since the aabb has to be found and then converted to hash space before the object can be placed in SpatialHash cells, but it results in faster collision detection since you’re only checking cells the object is in (minimum of one). This method is useful if objects vary dramatically in size.
Benchmarking the two styles is left as an exercise for the reader. Mainly because which performs best will depend on the particular application.
How did I implement a SpatialHash? Glad you asked. I used Method B and put together a pretty straightforward 2D SpatialHash (here’s the code). In addition to the SpatialHash object I also used a simple data structure called a HashRectangle. This structure could be replaced with class variables if desired. However I think it adds clarity to the code.
The meat of any hash is its hashing function. So I’m going to constrain my discussion to that section of code and the SpatialHash’s fields. Also I’m going to start referring to “world space” and “hash space”. In the first drawing world space is the area contained by the large rectangle and is addressable by (float, float); hash space is the subdivision of the world represented by the grid and is addressable by (int, int) or just (int).
Let’s start with fields
List<List<T>> cells;
The inner list is a list of objects in a cell, and the outer list is a list of the cells (you can probably tell from my imaginative name) in space. For reasons that have been lost in the mists of time, I chose a single list to contain all the cells in space rather than some sort of 2D array. Likely this was done for a combination of readability and to reduce memory overhead. The latter of which grows rapidly when adding extra dimensions to data structures in Java. That and you you also only need one loop to iterate over all of space when looking for collisions.
int numRows;
int numColumns;
The numRows and numColumns variables represent the extents of hash space. I’m going to discuss them together. Since I opted for a single list to represent all of the cells, we need to know the dimensions of the area of interest in hash space. The astute among you are already pointing out that I really only need one of these and cells to define the space (numRows = cells.size()/numColumns), and you’re right – one of these variables is a pre-calculated helper variable which is why I wanted to discuss them together.
float cellSize;
This is the size of a cell in world dimensions. In this case I assumed that cells would be square, but rectangular cells could be used if a specific situation called for it. This field is critical since it allows conversion between world space and hash space.
Continuing my trend of imaginative names, the hash method is called ‘hashFunction’. At first this method might appear misnamed since the actual hash conversion is done by the ‘hashFromWorldRect’ method. Which, if you haven’t read the code or guessed, converts the ‘worldRect’ to hash space by dividing the vertices of the worldRect by cellSize and truncating to form an integer. However, the second half of the method validates and constrains the raw hashRectangle returned by the ‘hashFromWorldRect’ method, and I consider validating and constraining to be part of the overall hashFunction.
At this point those of you who are still conscious and have been able to follow everything so far are probably thinking, ”ACMU, you used a dynamically resizable data structure (a list) to back the SpatialHash’s data; so you could resize this on the fly, but earlier you mentioned having a fixed world size as being part of the choice to use a SpatialHash over a QuadTree.” This is true. SpatialHashes can be resized on the fly but… one – if not the biggest – advantage of the SpatialHash is that it is pre-partitioned. If your world space is resized then it needs to be repartitioned, and partitioning early and often is where QuadTrees excel. If your world has an occasional resize a SpatialHash might still be more beneficial than a QuadTree, but that’s something you’ll have to benchmark in your particular application.
And that’s everything I know about SpatialHashes. I hope you found this mildly condescending and slightly informative.
If you’d like to read some additional views on SpatialHashing, take a look at these resources:
Some of you might have heard about Dominoes Robotic Unit (DRU) which was announced publicly a few weeks ago.
A mug only it’s designer and bugs could love. courtesy of Marathon Robotics
And while we can all applaud that humans are now one step closer to never leaving their couches.
However, until that day robots are in grave danger. Just last year the poor defenseless Canadian HitchBot (http://www.hitchbot.me/) was destroyed near Philadelphia. This makes the design of DRU highly concerning. It lacks an apparent righting system. We all know that robot immobilization can negatively affect the fate of whole planets in addition to the operation in which the robot is currently engaged.
DRU’s defensive design is also questionable. There has been some mention of DRU recording the images of assailants. It’s not confirmed if even this minimal level of protection will be implemented. However I feel compelled to point out that this system will be insufficient in light of HitchBot’s dismembered while carrying no cargo. DRU primary function will be transportation of goods which will dramatically increase the likelihood of ‘freak angle grinder accidents.’ so DRU clearly needs and active defense system.
You must be logged in to post a comment.