Gaming Your Way

May contain nuts.

Distance Based Broadphase

Collisions, they're always a part of my games that I'm never happy with. Not so much the actual this sprite has hit that sprite part ( The narrowphase of the check ), but the broadphase, ie deciding which checks are needed and which we can just ignore.

Different genres require different ways to test for collisions. For a long time now I've been using grid based checks ( As far back as this old beauty ) in arena based shoot'em ups. Simple enough, you split the screen up into overlapping sectors, and store each baddie in the sector it's occupying.
So let's say we've split the screen up into quarters, you check each baddie's position, and store it in one of the four arrays you've set aside for each sector. Then you can run through your bullets and see which sector they're in, so in theory you're only testing the baddies which are nearest to the bullet ( There's no point testing a bullet against a baddie which is on the other side of the screen ) which in an ideal world will reduce the checks by 75%. Not bad.

The problem I've always had with this is that it feels costly to maintain. I've always just cleared the sector arrays at the start of the baddie movement routines, I've never been clever enough to come up with a way to maintain it "properly". Therefore I could have baddies that have only moved a pixel or two since the last frame, there's no way they're going to have changed sectors, but I've had to treat them afresh.
That can't be good, but like I've said, I've never been able to come up with a clever way of negating that, so I've always just done it that big dumb way.

Recently quadtrees ( Check here for a great example, and an overview by the always excellent 8bitrocket can be found here ) and octtrees are very in vogue with Flash developers, so being a bandwagon jumper I thought I'd have a bit of that.

Again, I couldn't think of really good way to maintain the structure every frame, and it felt like you'd need a lot of objects to make it worthwhile ( Or just use it as a generic collision system for every game, but I'm not a fan of that. Collisions are a weird beast where very rarely does one hat fit all ).

One aspect that all the collision methods I mentioned above have, is shown below,

dbB1.png

I'm going to generalise a bit here, but let's say we've drilled down into the correct sector / node / whatever. Our bullet is travelling along that path ( Pick which ever direction you feel more comfortable with, in my head it's going up and right ). Chances are it's never going to hit that baddie ( I know the baddie could in theory move enough to come into collision with it, but we're generalising for a second ).
So we've gone to quite a bit of effort to narrow down our collision checks, and then we're still running a check per bullet every frame when most of the time it's not going to hit ( Think of your accuracy rating at any game that checks such things. 75% is pretty good in a game. That means that 25% of all the bullets are going to miss, yet we're having to test 100% of the bullets a 100% of the time ).

This all felt a bit sucky in my head. A lot of cpu time spent on something that wouldn't happen.

Let's talks about "Distance Based Broadphase". I made that up, it's more than likely already been around for years with a different name and I've just happened across a similar idea, but it explains what it is pretty well.

I've approached it in a different way than how I normally set up the whole bullets / baddies stuff. Using DBB every baddie has an array of all the player bullets ( Well a linked list for speed ), and every time the player shoots that new bullet is shoved into that array.
During the baddies main loop it runs through all the bullets it has in it's array and checks it's distance to it ( The narrowphase checks are just your bog standard circle to circle collisions ). If it's distance has increased, then the bullet is moving away from the baddie, and it won't hit it.

dbB2.png

So looking at that diagram above, lets say the bullet is flying up to the top left. The broadphase will keep checking as the distance from the bullet to the baddie is decreasing every frame, ie it's getting closer. It's possible that it could hit it, so it's worth checking.
Once the bullet goes past the sweet spot, it's moving away from the baddie. It'll never ever hit it, so we just remove it from the array and the baddie won't check for it again.

Whilst there's a possability of a collision it's worth checking, so it's not so costly ( If you're shooting at baddies from a distance then it's going to incur a cost until the bullet goes past the sweet spot, ie 'til the bullet gets to a point where it's not going to hit the baddie. The greater the distance the more the tests as it will take a while to actually get to the sweet spot ).
Going back to the first diagram, the bullet ( If moving to the top right ) is moving away from the baddie right from the start, so it's thrown away.
In effect we're checking the general direction until we get to the point of a hit, or a miss.

Now I've done some generalisation here. In real life your baddie will be flying around throwing some great shapes. For that, you just increase the size of the sweet spot to take it into account. If you have a fixed speed for a baddie you could work out exactly the sweet spot's size ( That is you'd work out if the baddie moving at it's max speed in a straight line to the bullets path how big the area to check would be ), or if you're lazy like me you just increase the size of the sweet spot by subtracting some pixels from the distance and testing it til it stops breaking.

Hopefully I've made some sense, it's proved to be quite a fair bit to explain. As always please feel free to post a comment if you have any questions or if I've got anything wrong. I'm sure I'll be editing this soon enough to clear things up.

Squize.

Game AI for dummies - or making the enemy see.

Sorry folks yet again no image ... but some code :)

The current game (let's call it CC for the sake of it) is getting close to the point where I would declare the main game engine done, most of the events are processed now and the final enemies are going to be done today (hurray!).

As the title suggests (wow it's something post related) I want to write about the dumb ass AI one, nope rather 4 of the enemies in CC use, if you were so bold to call it AI.

While reading up the docs about the original game I read this:

"goes around objects to the left"

And there are 3 more which go around things to the right.

HA!

I first simply ignored the fact of "going around" and just coded a simple "if enemie hits wall turn left".

cc_ai_00.gif
(ok, I lied, there are some images)


So after noticing my mistake I removed the old code and started to write the one that should allow my enemy to move around things. Sounds easy enough.

cc_ai_01.gif
Oh, that's easy.


"Go ahead as long as there is something to the left, if not, turn left ..."

After a while I really lost my temper and just coded something that could deal with right turns as well, by checking 3 tiles + one, as you can see in the next image.

cc_ai_02.gif
Well that is stupid, isn't it?


Jein, it's a dummy approach. (jein is a pseudo German word, combining "ja" and "nein", yes and no).

cc_ai_03.gif
Some of the common situations, the green arrow shows the next direction
and in "D" shows the use of the 4th check.


In order to simplify (though, yet unoptimised) the checking of the tiles I set up an array of points, holding the offset for each of the checks. To make my life even easier I just numbered the directions (which is used all over the game):
0 = north, 1 = east ...

So the array for 0 (north) looks like this:

this._aTest.push( [new Point(0, -1), new Point( -1, -1), new Point( -1, 0), new Point(1, 0)] );

And because this one should move to the left I added a second array that holds the next direction to go to:

this._aDirNext = [3, 0, 1, 2,  1, 2, 3, 0];

(You might wonder why it has eight entries instead of the needed four, I'll come to that later)
I now could just lookup the next direction I need to face by simply checking with the current direction:

this._iDir = this._aDirNext[this._iDir];

Now, with that in place checking the movement was easy:

private function checkMoveBug ():void {
            
    var strTest:String = "";
    var i:uint;
    var xx:int;
    var yy:int;
    
    for (i = 0; i < 4; i++) {
        
        xx = this._pPos.x + this._aTest[this._iDir][i].x;
        yy = this._pPos.y + this._aTest[this._iDir][i].y;
        
        if (this._refChipsGame.getTile(this._refChipsGame.aMapGame[xx][yy][0]).objProperties.bMonster && this._refChipsGame.aMapGame[xx][yy][1] == -1) {
            strTest += "0";
        } else {
            strTest += "1";
        }
        
    }
            
    switch (strTest.substr(0, 3)) {
        case "000":
// "C"
        case "100":
        case "110":
            this._iDir = this._aDirNext[this._iDir]; // turn to the next dir
            break;
        case "111":
// "A"
        case "101":
            if (strTest.charAt(3) == "0") {
                this._iDir = this._aDirNext[this._iDir + 4];
// this one uses the second pair for "A"
            } else {
                this._iDir = this.getOppositeDir(this._iDir); // this one is used vor "D"
            }
            break
        /*
        case "011":
        case "001": // "B"
            these are not needed because we can just move ahead
            (there is something to the left)
            break;
        */

    }
    
}

The final version has the 4th check removed from the loop and just checks it for "111" and "101".

And because we use an array to store the test offsets, we can make the enemy around things to the right by just changing the values (north):

this._aTest.push( [new Point(0, -1), new Point( 1, -1), new Point( 1, 0), new Point(-1, 0)] );

and changing the aDirNext array to face right:

this._aDirNext = [1, 2, 3, 0, 3, 0, 1, 2];

Vioal. Done.

I hope this is quite understandable (the code is, my writing might not)

nGFX