2D map collision detection

see title

  • (2 Pages)
  • +
  • 1
  • 2

19 Replies - 30210 Views - Last Post: 31 July 2009 - 04:44 PM Rate Topic: -----

#1 jyth  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 29-June 09

2D map collision detection

Posted 29 June 2009 - 05:36 PM

First post here, seems like a large community. fun fun.
Anyways, the dealio here is i'm working on this game in my free time just to kind of learn some basic stuff of how games work, collisions, graphics, what have you. I had absolutely no idea how games were actually programmed and structured a month ago and am heading into a CS major in the fall.
So, i'm working with a 2D map, essentially the same as one from a 2D zelda game. Cliffs, trees, water, most of you probobly know what I mean, and I'm having trouble getting my head around how I will do collision detection between a moving entity/sprite and the map.
As of now the basic map is just one big image, while anything that is animated or changes is to be created as an object on top of it. How would I do collisions in this context? I thought of breaking down the map into tons of sprites and constructing the map out of objects using a file for locations of things, which would make collisions easy, but I'm thinking that would be wildly inefficent.
One other idea i've had is to make a second imaginary map of rectangles constructed much like the above idea, except it would just be a layer of unshown rectangles used for collisions. Is this a good idea?

Image is an example area.

Anyways, questions/comments appreciated, even if they are to let me know i'm starting too big :D

EDIT: forgot to mention i'm working in java, although I don't think this will really matter.

Attached image(s)

  • Attached Image

This post has been edited by jyth: 29 June 2009 - 05:40 PM


Is This A Good Question/Topic? 0
  • +

Replies To: 2D map collision detection

#2 bobjob  Icon User is offline

  • D.I.C Head

Reputation: 23
  • View blog
  • Posts: 163
  • Joined: 29-March 08

Re: 2D map collision detection

Posted 29 June 2009 - 05:45 PM

I also tend to program in Java.

if the map is top down. you can make a 2 dimension array of blocks. and each block contains a boolean state (to show if its occupied). So when the character/sprite moves out of the block it occupies: it will check to see if the next block is occupied before entering. And if it enters then it will un-occupy its last block position.


If you are doing a platform game. I find the best way is to do line collision tests.
Was This Post Helpful? 0
  • +
  • -

#3 bobjob  Icon User is offline

  • D.I.C Head

Reputation: 23
  • View blog
  • Posts: 163
  • Joined: 29-March 08

Re: 2D map collision detection

Posted 29 June 2009 - 05:51 PM

If you want you could always have the two dimension block array independant of graphics and set each block manually.

But I personally think its best to have images grouped with the blocks (TileMap).
If you decide to use a TileMap Layout, You can save alot of space, as all images will be relatively small and re-usable.
Also you can have images with alpha channels for trees/rocks/sign_post/characters on top of the tile, stored in the same tile block object.

if you want a Java example of an efficient Top View Editor Check out:
Tile Map Editor

You could even use this to edit your own custom maps for your game.

This post has been edited by bobjob: 29 June 2009 - 09:03 PM

Was This Post Helpful? 0
  • +
  • -

#4 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1503
  • View blog
  • Posts: 8,249
  • Joined: 07-September 06

Re: 2D map collision detection

Posted 29 June 2009 - 06:00 PM

Quote

How would I do collisions in this context? I thought of breaking down the map into tons of sprites and constructing the map out of objects using a file for locations of things, which would make collisions easy, but I'm thinking that would be wildly inefficent.

I have no idea about effeciency here, but I would think you are correct in it being innefficient. One other thing you could do is create another image which has only 2 colors on it, blak and white and place black squares over everything you don't want to allow movement on. For instace, a collision map for your current image may look like so:
Attached Image

Then you ignore all the white, and use the black as a collision zone.

HTH
Was This Post Helpful? 1
  • +
  • -

#5 SixOfEleven  Icon User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: 2D map collision detection

Posted 30 June 2009 - 12:11 AM

How are you actually drawing the map? Did you make one large bitmap and you are scrolling that or did you make a tile engine? If you are using a tile engine, the normal way to do this is with a collisoin layer. Like what bobjob was saying. Tile engines are typically far more efficient than just loading and scrolling one large bitmap because the bitmap takes up huge amounts of memory. You can design your tile engine so that it only draws the visible part of the screen, plus a few extra tiles around the edges to keep it from disappearing off the screen. As I said, using tiles reduces the amount of memory needed for the map as if you have one large field of grass you can use 1 tile to make up the field of grass. You can also add what chuckb refrences as 'splatter tiles' which would break up the monotany of a large field of grass. A 'splatter tile' is a tile that would be mostly trasparent that would add to the image.

Typically tile maps are made up of 2D arrays of integers where each integer represents a tile. You could make a class to represent a tile though. In the class, you would have the tile and other information about the tile. Such as the player can't pass through it. The player takes damage passing through. The player walks more slowly. The sky is the limit here.

There are even isomertic tile engines. Games like Civilization, Age of Empires, Star Craft, Warcraft(not WoW mind you) all use isometric tile engines. Isometric tile engines give the illusion of depth.
Was This Post Helpful? 0
  • +
  • -

#6 Fib  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 163
  • View blog
  • Posts: 554
  • Joined: 12-March 09

Re: 2D map collision detection

Posted 30 June 2009 - 07:50 AM

Hi Jyth,

Did you create that map yourself? If you did then with what software? I'm just curious because it is a very well drawn background. I usually have trouble creating backgrounds/sprites because I don't have much artistic talent.

If you used a certain kind of software then maybe I can try it out!

:D
Was This Post Helpful? 0
  • +
  • -

#7 jyth  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 29-June 09

Re: 2D map collision detection

Posted 30 June 2009 - 04:07 PM

Some interesting suggestions. Wouldn't the tile map have to be 800x600 because Im thinking an object can have a (x, y) position in any pixel. Maybe that is unneeded detail though. I'll look into the isometric tile system suggested, although i'm not looking for 3D.

View PostFib, on 30 Jun, 2009 - 06:50 AM, said:

Hi Jyth,

Did you create that map yourself? If you did then with what software? I'm just curious because it is a very well drawn background. I usually have trouble creating backgrounds/sprites because I don't have much artistic talent.

If you used a certain kind of software then maybe I can try it out!

:D


As to your question, GOD NO! I wish I could =P
It's an image of an area in LoZ: Minish Cap B)
Essentially i'm looking for the way nintendo may have handled the map in the game.
Was This Post Helpful? 0
  • +
  • -

#8 SixOfEleven  Icon User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: 2D map collision detection

Posted 30 June 2009 - 09:03 PM

Quote

As to your question, GOD NO! I wish I could =P
It's an image of an area in LoZ: Minish Cap B)
Essentially i'm looking for the way nintendo may have handled the map in the game.


Like I and others said, Nintendo would definitely have done that using a tile engine. Try a google search for Java tile engines as I think I remember you saying you were doing this with Java. There are plenty of source code examples around in other languages so I'm sure you will find one in Java.
Was This Post Helpful? 0
  • +
  • -

#9 stayscrisp  Icon User is offline

  • フカユ
  • member icon

Reputation: 1040
  • View blog
  • Posts: 4,325
  • Joined: 14-February 08

Re: 2D map collision detection

Posted 01 July 2009 - 07:32 AM

SixofEleven is right they would have used a tile engine, a map like that could be done using a simple solid or not solid tile structure. Adding depth could be achieved by the order you draw objects in, for example when you walk under a tree, you can draw the tree after you draw your player.

I wrote a basic tile engine that used a pair of ints to signify a tile, like this

// a 5x5 tile map
1:1 1:1 1:1 1:1 1:1
1:1 1:1 1:1 1:1 1:1
1:1 1:1 1:1 1:1 1:1
1:1 1:1 1:1 1:1 1:1
1:1 1:1 1:1 1:1 1:1



The first number is the bool to check whether a tile is solid or not and the second is for the graphic to draw.

Something like this might suit your needs quite well :^:

This post has been edited by stayscrisp: 01 July 2009 - 07:33 AM

Was This Post Helpful? 0
  • +
  • -

#10 jyth  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 29-June 09

Re: 2D map collision detection

Posted 01 July 2009 - 02:59 PM

View Poststayscrisp, on 1 Jul, 2009 - 06:32 AM, said:

SixofEleven is right they would have used a tile engine, a map like that could be done using a simple solid or not solid tile structure. Adding depth could be achieved by the order you draw objects in, for example when you walk under a tree, you can draw the tree after you draw your player.

I wrote a basic tile engine that used a pair of ints to signify a tile, like this

// a 5x5 tile map
1:1 1:1 1:1 1:1 1:1
1:1 1:1 1:1 1:1 1:1
1:1 1:1 1:1 1:1 1:1
1:1 1:1 1:1 1:1 1:1
1:1 1:1 1:1 1:1 1:1



The first number is the bool to check whether a tile is solid or not and the second is for the graphic to draw.

Something like this might suit your needs quite well :^:


Would it be inefficent to make a class for a tile, as i can think of some more booleans that would have to be made, swim/walk, new area entrance, i dunno.

Thanks for all the tips and ideas so far.
Was This Post Helpful? 0
  • +
  • -

#11 stayscrisp  Icon User is offline

  • フカユ
  • member icon

Reputation: 1040
  • View blog
  • Posts: 4,325
  • Joined: 14-February 08

Re: 2D map collision detection

Posted 01 July 2009 - 03:22 PM

No I wouldn't think that to be inefficient, in fact thats exactly what I did. You could also create a struct to hold your tiles in your map class.

I created an enumeration to hold types of tiles

TILE_TYPE_SOLID = 0,
TILE_TYPE_PASSABLE,
TILE_TYPE_SLIPPY,
TILE_TYPE_WATER,
TILE_TYPE_EXIT



Then when you move your character and check for whether a tile is valid or not

bool GameObject::ValidateTile(Tile* Tile)
{
   if(Tile == NULL){
	 return false;
   }
   if(Tile->TypeID == TILE_TYPE_SOLID)
   {
	  return false;
   }

   if(Tile->TypeID == TILE_TYPE_WATER)
   {
		 player->swimming = true;
		 return true;
   }
   return false;
}



This is just an example but I hope you get my meaning.
Was This Post Helpful? 0
  • +
  • -

#12 SixOfEleven  Icon User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: 2D map collision detection

Posted 01 July 2009 - 03:24 PM

View Postjyth, on 1 Jul, 2009 - 03:59 PM, said:

View Poststayscrisp, on 1 Jul, 2009 - 06:32 AM, said:

SixofEleven is right they would have used a tile engine, a map like that could be done using a simple solid or not solid tile structure. Adding depth could be achieved by the order you draw objects in, for example when you walk under a tree, you can draw the tree after you draw your player.

I wrote a basic tile engine that used a pair of ints to signify a tile, like this

// a 5x5 tile map
1:1 1:1 1:1 1:1 1:1
1:1 1:1 1:1 1:1 1:1
1:1 1:1 1:1 1:1 1:1
1:1 1:1 1:1 1:1 1:1
1:1 1:1 1:1 1:1 1:1



The first number is the bool to check whether a tile is solid or not and the second is for the graphic to draw.

Something like this might suit your needs quite well :^:


Would it be inefficent to make a class for a tile, as i can think of some more booleans that would have to be made, swim/walk, new area entrance, i dunno.

Thanks for all the tips and ideas so far.


No, making a class for the tiles would not be inefficient. It would actually be a good idea. The efficiency is in the rendering process. That is where your program will be bogged down the most. Transferring data to the screen will probably be your biggest bottle neck for a 2D game. You can get around this by only drawing a portion of the map or splitting the map into smaller sections. You could use a portal system for splitting the map. When the player reaches a portal, you could switch to a new map. For the other part, you can try and only draw what part of the map the player is on and one or two tiles around it to keep the map from scrolling off the screen.
Was This Post Helpful? 0
  • +
  • -

#13 mono15591  Icon User is offline

  • D.I.C Regular

Reputation: 12
  • View blog
  • Posts: 406
  • Joined: 05-November 08

Re: 2D map collision detection

Posted 10 July 2009 - 11:20 PM

View PostSixOfEleven, on 1 Jul, 2009 - 02:24 PM, said:

No, making a class for the tiles would not be inefficient. It would actually be a good idea. The efficiency is in the rendering process. That is where your program will be bogged down the most. Transferring data to the screen will probably be your biggest bottle neck for a 2D game. You can get around this by only drawing a portion of the map or splitting the map into smaller sections. You could use a portal system for splitting the map. When the player reaches a portal, you could switch to a new map. For the other part, you can try and only draw what part of the map the player is on and one or two tiles around it to keep the map from scrolling off the screen.


For loading the map couldn't you just have the player always be in the middle of the screen and just have it draw tile so far out from the center of the screen. I've never made a 2d game so I don't know how efficient this actually is.

XXXXXXXXXXX
XXXXXXXXXXX
XXXXXOXXXXX
XXXXXXXXXXX
XXXXXXXXXXX<- like that.

just have the surroundings drawn and when he moves it erases the stuff off screen and draws the new things coming onto screen. I would say make the area where things are drawn to go a tile or two off screen so you don't see anything when the map is loading. idk my idea

This post has been edited by mono15591: 10 July 2009 - 11:25 PM

Was This Post Helpful? 0
  • +
  • -

#14 stayscrisp  Icon User is offline

  • フカユ
  • member icon

Reputation: 1040
  • View blog
  • Posts: 4,325
  • Joined: 14-February 08

Re: 2D map collision detection

Posted 11 July 2009 - 03:53 AM

Well that is basically what you would do if you where to draw a large map, you would have to write a camera that would follow you and keep you centered on the screen.

This would only work on an RPG exploration type of game, I found this out when making a platform/side scroller, remaining center meant if you jumped the whole map followed you, it looked terrible. :lol:
Was This Post Helpful? 0
  • +
  • -

#15 SixOfEleven  Icon User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: 2D map collision detection

Posted 11 July 2009 - 09:18 AM

View Postmono15591, on 11 Jul, 2009 - 12:20 AM, said:

For loading the map couldn't you just have the player always be in the middle of the screen and just have it draw tile so far out from the center of the screen. I've never made a 2d game so I don't know how efficient this actually is.

XXXXXXXXXXX
XXXXXXXXXXX
XXXXXOXXXXX
XXXXXXXXXXX
XXXXXXXXXXX<- like that.

just have the surroundings drawn and when he moves it erases the stuff off screen and draws the new things coming onto screen. I would say make the area where things are drawn to go a tile or two off screen so you don't see anything when the map is loading. idk my idea


Well, like staycrisp said, that doesn't always work so well in all cases. You can pad the map so the player will never be able to walk off the side of the map, using tiles that the player can't walk through. It was done like in several games. Using the camera to control scrolling it will also work for other types of tiling, like isometric where the map is a diamond, not a square, like in the first Age of Empires. Also, if you wanted to have the player be able to scroll the map using the mouse by having the mouse at the edge of the screen, like in popular RTS games, centering the map on the player wouldn't work all that well.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2