Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (499)
Games in Android Showcase (118)
games submitted by our members
Games in WIP (567)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Checking a LARGE tilemap for collisions  (Read 3467 times)
0 Members and 1 Guest are viewing this topic.
Offline Xardov

Senior Newbie





« Posted 2012-07-12 05:33:45 »

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. =/

1  
2  
3  
4  
5  
6  
7  
for(int i = 0; i < tilemap.size(); i++)
{
    if(tile is within a 16 pixel radius of the player)
{
checkForCollision();
}
}
Offline Ultroman

JGO Knight


Medals: 25
Projects: 1


Snappin' at snizzes since '83


« Reply #1 - Posted 2012-07-12 05:46:50 »

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.



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:
1  
2  
3  
4  
5  
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.

- Jonas
Offline Xardov

Senior Newbie





« Reply #2 - Posted 2012-07-12 05:50:24 »

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.



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?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Ultroman

JGO Knight


Medals: 25
Projects: 1


Snappin' at snizzes since '83


« Reply #3 - Posted 2012-07-12 05:56:51 »

I thought you'd ask that, so I edited my last post to further explain

- Jonas
Offline philfrei
« Reply #4 - Posted 2012-07-12 06:37:12 »

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:

http://hexara.com/pond.html

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.

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline Cero
« Reply #5 - Posted 2012-07-12 13:37:50 »

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

Offline Ultroman

JGO Knight


Medals: 25
Projects: 1


Snappin' at snizzes since '83


« Reply #6 - Posted 2012-07-13 02:08:19 »

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:
<a href="http://www.youtube.com/v/EKv1zT_2O6s?version=3&amp;hl=en_US&amp;start=" target="_blank">http://www.youtube.com/v/EKv1zT_2O6s?version=3&amp;hl=en_US&amp;start=</a>
Well, it seems the forum isn't prepared for underscores in the Youtube-links.
Here's a link to the video

- Jonas
Offline Cero
« Reply #7 - Posted 2012-07-13 03:20:19 »

Well, it seems the forum isn't prepared for underscores in the Youtube-links.

Yeah I noticed that.

Offline Ultroman

JGO Knight


Medals: 25
Projects: 1


Snappin' at snizzes since '83


« Reply #8 - Posted 2012-07-13 03:48:27 »

This video is more relevant to the OP.

Video of my RPG, which demonstrates this method for both horizontal and vertical collisions:

- Jonas
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 801
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2012-07-13 12:54:52 »

Well, it seems the forum isn't prepared for underscores in the Youtube-links.
Thanks for reporting! Fixed.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline marcuiulian13

Senior Member


Medals: 5
Exp: 3 years



« Reply #10 - Posted 2012-07-14 07:23:24 »

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

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?  Stare

Getting a project done is by far the most hard thing in game development.
Offline jdgamedev

Senior Newbie


Medals: 1


Chillin Like a Villin


« Reply #11 - Posted 2012-07-14 15:48:31 »

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'm on a quest to become a better game developer, check it out.
Offline UprightPath
« Reply #12 - Posted 2012-07-18 07:52:14 »

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.

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Pippogeek (39 views)
2014-09-24 16:13:29

Pippogeek (30 views)
2014-09-24 16:12:22

Pippogeek (19 views)
2014-09-24 16:12:06

Grunnt (44 views)
2014-09-23 14:38:19

radar3301 (27 views)
2014-09-21 23:33:17

BurntPizza (62 views)
2014-09-21 02:42:18

BurntPizza (32 views)
2014-09-21 01:30:30

moogie (39 views)
2014-09-21 00:26:15

UprightPath (50 views)
2014-09-20 20:14:06

BurntPizza (54 views)
2014-09-19 03:14:18
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!