The first thought I had was to loop through each tile in the map, check to see if it is within a certain distance of the player, and then check for collisions. This still seems slow though, I was wondering if anyone had any other ideas? I’m also going to have a lot of entities (200 - 400) on the map doing this check, so it seems like it will slow down the game a lot. =/
for(int i = 0; i < tilemap.size(); i++)
{
if(tile is within a 16 pixel radius of the player)
{
checkForCollision();
}
}
Are all these entities on the screen at the same time?! If not, you could limit you code to only move and check collisions for entities within the screen-size.
Also, you should definitely not check collisions for each entity against all tiles on the map! That would be terrible, and I’m happy you thought that too.
What I always do, is calculate some points around the entity that makes sense. For a top-down RPG I chose 8 points (see drawing). Then I check for horizontal collisions on the ones furthest to the left and right, and then I check for vertical collisions using the points furthest to the top and bottom.
http://img534.imageshack.us/img534/3953/collisionthingy.jpg
Then just make a method that can get a tile from an x,y position on your map. It’s easy for tiled maps if you have same-size tiles. Ex: if all your tiles are 40x40px, then it would look like this:
public Tile getTileFromCoordinates(int tileCoordX, int tileCoordY){
int tileX = (int)Math.round(tileCoordX/40);
int tileY = (int)Math.round(tileCoordY/40);
return tileList.getTileList().get(currentMap.getGround()[tileY][tileX]);
}
My tileList-class holds a HashMap of all tiles, with their ID as key. My map ground is a 2D-array of these IDs, so I get the ID from the map from the location I pass it (remember, the Y is the row, and X is the column), and the tileList returns the Tile-object from that ID. Then I can check if it’s a passable or impassable tile.
Hmmm, i’m not sure I quite understand what you’re saying. To check for collision on the points, shouldn’t you have to loop through the entire tilemap?
I thought you’d ask that, so I edited my last post to further explain
How large are the Tiles? Do the Tiles overlap? How many per screen?
Can you track which Tile or Tiles your entity is currently in? if so, then you only have to check for collisions with other entities in those Tiles or maybe contiguous Tiles rather than all of them.
I think this is sometimes called a “bin” method for doing collision checking. There is some other term as well.
I was recently playing around with an extreme version of this: I made a replica grid of all the pixels and tracked all the entities on this grid. Before moving into a space, I check whether the space is occupied or not. If it is free, I erase my location from the previous and place it in the new location. If the spot is occupied, I have a link to the occupier in the grid location. Make sense? I’m not sure if this is the most efficient, but it worked for this silly experiment:
The stuff I mention on that post about locking is unnecessary if you are doing your moving and collision detection on a single thread. The data structure for this sort of system can probably be made less dense than the actual screen. What is lost in terms of maintenance is compensated by the gains in the collision test itself: one only looks at the space where one is going, no where else.
Bin system is more common, or if needed, quad trees, in certain situations.
you basically have a range around an entity.
tiles within that range are checked.
I do this by calculating the position of the entity and then do a x, y loop which starts with the first interesting tile and stops with the last.
so its only like, size of the entity plus 1*tilesize of radius to check
Yeah, I just want to add, my method is only applicable if everything you’re colliding with is bigger than the range between those points. I used it for the worldmap in an RPG in which the player only collided with tiles bigger than him, as well as for the tile-collisions in my Mario-platformer, in which all collisions with projectiles are handled with intersecting rectangles of variable sizes instead.
The method is applicable for low-cost collision-detection, with separated horizontal and vertical collisions, for simple movement. Here’s a video. Look at the points around the player. They’re used for horizontal collision. The green pixel at his feet is the player position, which is used for vertical collision detection. This is a very different approach to vertical collision detection compared to the method described above, which doesn’t apply to side-scrollers, save for the horizontal collisions.
Video of my sidescroller using this method for horizontal collisions:
EKv1zT_2O6s
Well, it seems the forum isn’t prepared for underscores in the Youtube-links.
Here’s a link to the video
Yeah I noticed that.
This video is more relevant to the OP.
Video of my RPG, which demonstrates this method for both horizontal and vertical collisions:
Thanks for reporting! Fixed.
So you mean hat it’s faster to make an array with the “possible” tiles in range for each entity than making only one array with “onscreen” tiles and check collision with all of them? 
This post helped me out quite a bit. As a placeholder, I was just iterating through my array and checking collision on ever tile. Now I’ve made a method to calculate the exact index of the tile I’m attempting to move onto and checking collision that way.
Thanks for the help guys.
I had (something) of the same problem in one of the games I posted recently. Basically, instead of just doing an ‘exact index of collision’ style thing, I figure out a range of possible tiles that the character could collide with depending on the direction of the motion. This allows you to have variable sized entities, with little worrying about tunneling/missing edge collisions.
If it’s falling/jumping I iterate through the horizontal tiles (left most tile to right) first, then move up or down depending on the direction in question and for some predetermined ‘limit’. The only ‘important’ tile in such checks is the highest/lowest (depending on which direction you’re moving), and it’s fairly easy to construct the loop for this.
If it’s moving horizontally, I iterate through the vertical tiles (From top to bottom) starting from where the entity’s head is down to the tile its feet are located, then iterate left/right to some limit. If the tile’s bottom is located below the entity’s top, it’s a possible collision object or if its top is located above the entity’s bottom (Like regular AABB style collisions, hah).
In both cases, only the most extreme object in a given direction typically matters for the purposes of a collision. The limit is predetermined based on maximum speed of the entity in question. After you find the tile in question, you either move the entity or calculate where the entity will move to, if it’s further than the object’s extreme edge then you’ve got a collision to handle.
For the most part, this’ll help to avoid the whole fun of ‘tunneling’, and if you should only have to check a small (Relatively, based on size) number of tiles for the collisions. I know that it means very little, but I tested it out with the platformer that I made, and just dumped numerous semi-randomly moving entities into it and didn’t detect any sizable difference in the frame rate (Though that might be more of a “You’ve got an alright computer” than “Your algorithm was good” sort of dealy).
This method was done resolving X then Y collisions, if you want to try to resolve them together, you can use a line algorithm to plot the player’s path through the air in a straight line, then create a path through that line (Find the line, then figure out the tiles you’d move through to follow that line) for the limiter.