Jump to content


Photo

Fast Platform Collisions


  • Please log in to reply
18 replies to this topic

#1 scotay

scotay

    GMC Member

  • GMC Member
  • 147 posts
  • Version:Unknown

Posted 13 October 2011 - 01:03 PM

http://www.yoyogames.com/tech_blog

With the launch of GameMaker:HTML5, there's one brand new factor that should be at the forefront of any game you now design; speed. You see, moving from a windows executable to HTML5 carries some performance issues, and sometimes, some pretty severe ones. JavaScript isn't as quick as native code, that's obvious, and this means you will have to produce more optimal, streamlined code. This in turn means that there is some adjustment required in the way we now do some things in GameMaker. Platform games are a case in point, for while they work fine under windows, due to the way the original examples demonstrated things, they are far from optimal enough for GameMaker:HTML5. Don't worry though, anything you learn here can be carried over to Normal Windows executables, and you'll still see a speed up there as well, so it's all good.

So, why is this? Why does the current crop of platformers suffer so much in JavaScript? Well, the issue is due to the way commands such as "move_outside_solid()" work. you see, what currently happens when you write a platform game, you ask the system to give you a collision event, and then you use commands like move_outside_solid() to move outside it. The problem with commands like this is the amount of code it has to run through in order to satisfy these seemingly simple actions.

Let's take the command move_outside_solid(), how does GameMaker do this? Well... first, have a read of my collision article, because you'll need to understand how precise collisions work, and how much effort it is for the CPU to do that work. Once you've read that, you'll realise that even one precise collision can take a pretty long time, and you might even now realise that move_outside_solid() will have to do this several times in order to "move outside" the collision that just occurred.

So let's follow through what happens.... First you move the player/object as normal, and then the system throws a collision event (probably using a slow collision test in the process), telling you that your instance has just hit something. You now workout the direction you've just come from, and use move_outside_solid() to "back out" of this collision. If you were deep inside the collision (say several pixels inside the collided block), then it may take several precise collision iterations to actually move your instance back out. Add to the fact that you may also be doing this to baddies as well as the player, then you can see that this is just burning CPU time - lots of it. So, how else could you do this? How could you run around on a platform, and stop the player (and baddies) jumping into walls, or falling through the floor?

First, why don't we have a look back at some old retro systems: NES, C64, Megadrive, SNES - all of these systems are well known for platform games, and did platform collision detection in the same way; tilemaps. Now, these aren't tilemaps as GameMaker defines them, this is because GameMaker uses a somewhat warped version of tilemaps. Most of these old systems used fixed character mapped screens, that is, a screen made up of X by Y characters. (i.e. the C64 had a screen of 40x24 cells, which it uses as characters, and games use as tiles). These characters were then used as tiles, and these tiles were then defined into platforms and background, and simple collisions would occur with them.



The game above (The C64 game, "The Great Giana Sisters") shows how the game would probably tile up it's level. The larger tiles would actually be multiple tiles, chained together to make a large object. This differs greatly from GameMakers tiles, because they aren't really tiles at all, but very simple sprites. This is a problem, because we can't easily detect which tile we've hit - at least, not without extensive checking. So, how did these old - and very slow systems, collide with the background so quickly? Easy, they used a fixed grid of tiles. This meant you could easily tell which tile you hit, simply by dividing down your coordinates (usually by 8, 16,32 etc. in fact, any power of 2 number) and then using these numbers they index directly into the grid of tiles.


10000001
10200101
11111111

So, lets have a look at a simple tilemap. Above you can see a very simple tilemap where 1 is solid, 0 is empty, and 2 is a pickup. This means all we need to do is test the tiles directly under the instance (in this case, the player). So how do we do that? Well, If we're using a 16x16 tileset, and our sprite is a 16x16, then when standing directly on a tile, it's x and y coordinate will be a multiple of 16. So, when checking the tile directly below, we would simply add 16 to Y, then divide the Y coordinate by 16, and flooring it. This gives us the tile index (on Y) for the tile under our feet. If the tile is 1, then we don't fall, if it's 0, we do.



Now that's all well and good, but what if we are falling, and what if we fall INTO a tile? How can we move out of it without commands like move_outside_solid()? This is where we use some old school tricks, and it's how these old 1Mhz systems were able to games like platformers and shooters so easily.

First; time to brush up on some binary maths. Binary is very handy, and you should be a fluent as possible with it and the tricks it allows you to do. Lets have a look at a couple of numbers.


%1 1
%10 2
%100 4
%1000 8
%10000 16

As each bit is set, it adds a power of 2 number to the total. As you can see from the above numbers, they have single bits set, and so are "pure" power of 2 numbers (1,2,4,8,16,32,64,128 etc. are all power of 2. As each number is multiplied by 2, it doubles.)

So, if we have some combinations of these bits... what does this mean?

%110 6
%1101 13
%11 3
%1001 9

Using the table above, you can see when you add the bits together, you get the resulting numbers. So, pretty straight forward so far. This is how computers store numbers, with each BYTE being able to hold 8 bits, allowing for numbers from 0 to 255. For larger numbers, the computer simply uses more bytes. 2 bytes allows 16 bits, and a number from 0 to 65535, and so on.

So... why this lesson in basic computing? Ah... well, now it gets interesting. What happens if we shift these bits around? Let's say shift them left or right by a number of bits? Well, %1 shifted left 3 would give %1000, and this gives 8. Also, if we had %1000 and shifted right 3, we'd get %1 (1). In other words, we can do simple multiplication and division by shifting the bits around. (this is again, how the computer does basic binary maths).

So... What would happen if we dropped OFF the lower bits...? Let's say we had %1011 (11), and we AND'd with %1000 (8), we would end up with...8. By removing these lower bits, we have effectively rounded DOWN to the nearest multiple of 8.



Now, that's handy.... What if our tilemap was made from 16x16s, and what if we were 4 pixels into one on Y. So the Y coordinate was 68. How could we move it back out of the tile? Well, since we know all tiles are on fixed pixel boundary's, we know that OUTSIDE the tile coordinate is 64. Using the binary tricks above, we can do a simple AND with Y coordinate (Y = Y & $fffffff0), and this will rid us of the lower bits making the value a multiple of 16, and placing it outside the collision, and back to 64; since %1001000 (68) & $fffffff0 = %1000000 (64).

So, let's look at this again. If we know we have a collision on Y (below), we can simply jump back directly into the empty space by ANDing with $fffffff0, and removing the offending bits.

This collision system is lightning fast, but to use it you must have a FIXED tilemap, not one that places tiles "anywhere". Future versions of GameMaker will remove that ability, but it will also give access to the map for use with collisions, because it's an invaluable tool. Once you collide with the map, you can collide with anything in the level. Pickups, traps, solid objects, triggers, pretty much anything you use an instance for in terms of collision, you can use tilemaps to do it faster. You do have the restriction that your object must be on a tile boundary, but for most things, this isn't an issue. After all, if you want to trigger something when the player walks over it, does it matter if it's a few pixels to the left? The same with power ups... You just get used to placing them in this manner, and then you can use the tilemap to actually collide.

GameMaker:HTML5 comes with a demo of this method, so you can now read over this and then poke around in the source till your hearts content!
  • 4

#2 ryguydavis

ryguydavis

    GMC Member

  • New Member
  • 277 posts
  • Version:Unknown

Posted 14 October 2011 - 01:46 PM

Excellent, stimulating read. Reminds me that many excellent minds have already struggled with these problems using far more crippling limitations. A couple points concerned me, however.

...you must have a FIXED tilemap, not one that places tiles "anywhere". Future versions of GameMaker will remove that ability


Am I right in reading that the Yoyo staff intends to remove the ability to use slow collisions, rather than assuming we are intelligent enough to choose for ourselves?

I also noticed that using a grid system for colissions is not something that needs to be built into the system--rather, every time a collision is detected, the instance can round its coordinates using much less complicated methods (ie, assuming 32x32 cells x=round(x/32)*32). The cpu usage is just as light without requiring the underlying structure of the level to be so static. Walls on a grid are fine--but need everything be so confined?
  • 0

#3 Adequate

Adequate

    GMC Member

  • GMC Member
  • 479 posts

Posted 14 October 2011 - 02:55 PM

If you wanted speed, why are you using GM on the first place?

Food for thought
  • 0

#4

  • Guests

Posted 14 October 2011 - 03:16 PM

Am I right in reading that the Yoyo staff intends to remove the ability to use slow collisions, rather than assuming we are intelligent enough to choose for ourselves?

I also noticed that using a grid system for colissions is not something that needs to be built into the system--rather, every time a collision is detected, the instance can round its coordinates using much less complicated methods (ie, assuming 32x32 cells x=round(x/32)*32). The cpu usage is just as light without requiring the underlying structure of the level to be so static. Walls on a grid are fine--but need everything be so confined?

No, the slower system will always be there, because there ARE cases where they are handy and useful. But we will be allowing more streamlined cases in the future, building things like "playfields" in natively, and allowing your to do collision to tile maps directly.

While we will be limiting TILES to fixed grids, but we will also be allowing you to place sprites, text, particles and the like directly into the map, meaning it should be much more flexible in the long run.

None of this has been set in stone, and we will be putting out docs with more information later, so for now...don't worry about it. It's a long way off yet. :tongue:

If you wanted speed, why are you using GM on the first place?

Unless you're wanting to make Unreal 10, your probably fine with GameMaker..... :dry:

#5 ryguydavis

ryguydavis

    GMC Member

  • New Member
  • 277 posts
  • Version:Unknown

Posted 14 October 2011 - 04:55 PM

Mike.Daily, thanks for your swift reply--that definitely answers my questions.

While we will be limiting TILES to fixed grids, but we will also be allowing you to place sprites, text, particles and the like directly into the map, meaning it should be much more flexible in the long run.


May I be the first to say, "FINALLY."

Unless you're wanting to make Unreal 10, your probably fine with GameMaker.....

Agreed. However, GM is a 2d engine at heart--and sadly even 2d games start to lag long before is reasonable. The dev world might take us more seriously if we got a speed boost. That said, for most things, GM is all you'll ever need.
  • 1

#6 round

round

    GMC Member

  • GMC Member
  • 165 posts

Posted 15 October 2011 - 09:38 AM

http://www.yoyogames.com/tech_blog

With the launch of GameMaker:HTML5, there's one brand new factor that should be at the forefront of any game you now design; speed. You see,.........

...........GameMaker:HTML5 comes with a demo of this method, so you can now read over this and then poke around in the source till your hearts content!


Hello,

This tech blog's article is too difficult. Please allow inexperienced GameMaker users(like me) to use the old ways to make platform games in the future version of GameMaker Standard. Thanks a lot.!!!

Edited by round, 15 October 2011 - 09:39 AM.

  • 0

#7

  • Guests

Posted 15 October 2011 - 11:24 AM

You can still use "the old way", but we can't limit articles to what everyone would understand, or you would never learn anything! This article is all about the fastest, and most robust way of doing platform games, not the only way. You also can't expect to read articles and understand them all right off, you need to think about them, play with the ideas, and let your brain work it out in it's own good time.

I disagree that GameMaker requires that much of a speed boost. Using techniques like this free up a LOT of cpu time, and thats what it's all about. Folk did games (like platformers) in a certain way before, and these weren't good or fast methods. Writing code using methods that commercial games use will give a huge boost, but it does require a shift in thinking. I've written for fast, and slow systems, and you change your coding style depending on the platform and what it's capable of.

#8 NakedPaulToast

NakedPaulToast

    GM Studio/Mac/Win

  • GMC Member
  • 8207 posts
  • Version:GM:Studio

Posted 15 October 2011 - 05:27 PM

Another huge benefit of this kind of collision processing is the reduction of Objects.

Typically in a Platformer, one would create invisible objects for floors, platforms and walls and place them into the room, one would also create objects for pickups.

This technique no longer requires objects to be used in this manner. Objects are expensive in GameMaker.

Granted objects used for floors, walls and platforms don't have events attached to them and don't need to be drawn, but there very existence causes them to participate in the game loop. They don't need to be drawn, moved or have gravity influence them, but they still need to be interrogated to see if they need to be drawn, moved or influenced by gravity.

Given the large numbers of wall, floor and platform objects, and the cumulative effect of saving processing for each one, the speed improvement can be significant.
  • 0

#9 ryguydavis

ryguydavis

    GMC Member

  • New Member
  • 277 posts
  • Version:Unknown

Posted 15 October 2011 - 06:42 PM

I disagree that GameMaker requires that much of a speed boost. Using techniques like this free up a LOT of cpu time, and thats what it's all about. Folk did games (like platformers) in a certain way before, and these weren't good or fast methods. Writing code using methods that commercial games use will give a huge boost, but it does require a shift in thinking. I've written for fast, and slow systems, and you change your coding style depending on the platform and what it's capable of.


Again, I agree. A programmer is only as good as his/her ability to work with his/her tools in an effective manner. My point about GM, however, is that if we have to move back several generations of hardware in our thinking to accommodate our system, it only follows that our system runs on a level which was consistent for hardware which, today, is several generations behind. NakedPaulToast got it right--instances are expensive, and so is drawing in general. Things can always be optimized--and should be--but there is a point where optimization needs to be at the ground level as well. We should all be Lance Armstrong programmers, using every scrap of code to our advantage in getting the best out of our system. But even Lance can't win a race on bicycle in need of a good oil.

I love to see what you guys are doing with GM. I've seen it flower into what it is today from version 5.0 eight-and-half years ago and it has come a long way. The love and tender care put into it shows in the ease of use and intuitive nature of the editor and system. I will always know hands-down it is the best way to learn and master game development. Speed issues are relatively minor in comparison to its array of fine qualities.
  • 0

#10 BorisE

BorisE

    GMC Member

  • New Member
  • 200 posts

Posted 16 October 2011 - 02:36 PM

I think there needs to be some careful thought before going down this route. We don't want Gamemaker turning into Mario-Clone-Maker.
Back in the 80s games were managing off-grid movement very effectively using a number of tricks.

One simple optimisation might be to enforce that solid items don't move, allowing a collision "supermask" covering the entire room. Another is to draw a distinction between the problem of precise collisions and that of random placement. In the case of a precise collision with grid objects the test is "expensive" but it only has to be performed a limited number of times, since the number of tiles that an object could have hit would be limited to adjacent grid cells.

Any collision with randomly placed objects potentially means testing every combination of collisions but even here someone pointed out that hashing techniques can reduce the scale of the problem.

I suspect that there are even optimisations to speed up move_contact style functions. Once you've "and"ed two maps together runs of bits indicate the degree of overlap, so it may be possible to back up successfully simply using the results of one test.
  • 0

#11 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Member
  • 15785 posts
  • Version:GM:Studio

Posted 16 October 2011 - 03:22 PM

Hello,

This tech blog's article is too difficult. Please allow inexperienced GameMaker users(like me) to use the old ways to make platform games in the future version of GameMaker Standard. Thanks a lot.!!!


You can check my implementation of the concept in my Simple Platform tut in my tools page. Then you can think about the array method mentioned here which is basically replacing the collision system with a less cpu intensive (especially in java) method
  • 0

#12 Gamer_Dude64

Gamer_Dude64

    GM Html5 Programmer

  • GMC Member
  • 169 posts
  • Version:GM:Studio

Posted 16 October 2011 - 08:14 PM

whats up with the hovering over the ground in the html5 demo then? you can stand above the ground if you inch off of the side of one of blocks.
  • 0

#13

  • Guests

Posted 16 October 2011 - 09:37 PM

It's just the "default" locations of the collision. You can certainly fine tune it if you like.If you go back and look at games like Mario World, you'll notice a similar thing....

#14 Gamer_Dude64

Gamer_Dude64

    GM Html5 Programmer

  • GMC Member
  • 169 posts
  • Version:GM:Studio

Posted 16 October 2011 - 11:23 PM

alright, will have to go do that....

Edited by Gamer_Dude64, 16 October 2011 - 11:24 PM.

  • 0

#15 BorisE

BorisE

    GMC Member

  • New Member
  • 200 posts

Posted 17 October 2011 - 10:56 AM

Also how about having the best of both worlds. A new "Grid" type is added, and object types may be added to a grid. Once a type has been added to a grid it may be placed in any number of grid cells, yet all are considered the same "instance" so the instance count goes down drastically and if the type has a box sprite filling the grid cell then simple grid collisions may be used.
  • 0

#16

  • Guests

Posted 17 October 2011 - 12:23 PM

We will be adding proper "playfields" in the future. These will allow tiles on a fixed grid, but will also allow collision to them - as well as reading/write to/from the MAP itself. Animated tiles are a great tool, and usually very quick for an engine to do.

#17 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Member
  • 15785 posts
  • Version:GM:Studio

Posted 17 October 2011 - 06:05 PM

Also how about having the best of both worlds. A new "Grid" type is added, and object types may be added to a grid. Once a type has been added to a grid it may be placed in any number of grid cells, yet all are considered the same "instance" so the instance count goes down drastically and if the type has a box sprite filling the grid cell then simple grid collisions may be used.


Yeah, on the same thought, I always found annoying the mpgrid offered not way to look at its data ourselves. The grid allows adding instances, objects, areas. and it's smart enough to flag multiple cells.

Perhaps it's a simpler matter to just add a feature to allow reading from that mp_grid like we do a normal grid.
  • 0

#18 BorisE

BorisE

    GMC Member

  • New Member
  • 200 posts

Posted 18 October 2011 - 08:37 AM

The other problem with this kind of "optimisation" is that at the moment it should boost the performance of HTML5 where I'm presuming GML is translated into javascript so the performance cost of doing something in GML is low relative to leaving it to the runner.

In an EXE build the runner is now compiled C++ and enjoys a ludicrous speed advantage over GML. Therefore an improvised grid should speed up HTML5 but may even slow down the EXE.

Incidentally I think there was a way to read mp_grid cells, but it was something nasty like trying to find a path from the cell to itself. Cell empty=path found, cell full=no path.
  • 0

#19 Oracizan

Oracizan

    Mutant Dreamer

  • GMC Member
  • 543 posts
  • Version:GM:Studio

Posted 29 October 2011 - 04:20 PM

Hey all. Below is the code that I use for my tile collisions. I use an array, but any other data structure could easily be used.

var tile_x1,tile_y1,tile_x2,tile_y2;
var ix,iy,tx,ty;

//FIND THE CORNERS OF THE OBJECT
tile_x1=max((x-offset_x) >> 5,0)
tile_y1=max((y-offset_y) >> 5,0)
tile_x2=min((x-offset_x+width),room_width) >> 5 
tile_y2=min((y-offset_y+height),room_height) >> 5

//GRAVITY
if vspeed<10{vspeed+=1}

//LOOP THROUGH ALL TILE COLLISIONS
for (ix=tile_x1; ix<=tile_x2; ix+=1){
for (iy=tile_y1; iy<=tile_y2; iy+=1){
if global.Tile[ix,iy]=1{
tx=(ix << 5);
ty=(iy << 5);

{
    if y-offset_y+height-vspeed < ty and iy>0{ //IF OBJECT COLLIDES FROM ABOVE
        if global.Tile[ix,iy-1]=0{y = ty + offset_y - height;jump=true;vspeed=0};break;
    }
    if y-offset_y-vspeed > ty+32{ //IF OBJECT COLLIDES FROM BELOW
        if global.Tile[ix,iy+1]=0{y = ty + 32 + offset_y;vspeed=0};break;
    }
    if x-offset_x+(width >> 1)-hspeed < tx+16 and ix > 0{ //IF OBJECT COLLIDES FROM LEFT
        if global.Tile[ix-1,iy]=0{x = tx + offset_x - width;hspeed=0}
    }else{ //IF OBJECT COLLIDES FROM RIGHT
        if global.Tile[ix+1,iy]=0{x = tx + 32 + offset_x;hspeed=0}
    }
    

}

}
}
}


The grid is made of 32 x 32 tiles, and the difference here is that I allow for an object of any width x height to interact with the grid. This is useful for player, enemy, and movable item objects, because they are often not the same size as the platform tiles. This also eliminates the 'hovering' issue when players are still colliding with the very edge of a platform when they ought to have fallen. Hopefully some people find this useful.

Edited by Oracizan, 29 October 2011 - 04:22 PM.

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users