Im making a game in Java with a few other people but we are stuck on one part of it, making the collision detection. The game is an RPG and I know how to do the collision detection with the characters using Rectangles, but what I dont know how to do is the collision detection for the maps. What I mean by that is like so the character cant walk over trees or water and that stuff but using rectangles doesnt seem like the best option here.

Well to explain what the game maps are gonna look like, here is an example: enter image description here

Now I could use rectangles to get bounds and stop the player from walking over the trees and water but that would take a lot of them.

But is there another easier way to prevent the player from walking over the trees and obstacles besides using Rectangles?


3 Answers 3


Your map looks like a 2D grid so why not have a boolean[][] lookup table for the map? Or even int[][] if you want different grid cell types. For smoothing movement around corners you can look up the target position and make a smoother animation, e.g.

if (movingUpRight && myGrid[playerPosX + 1][playerPosY + 1] == TILE_EMPTY) { /* smooth animation */}

Judging by your question you don't need anything more complicated than that.

If you do need something more fancy take a look at Recast/Detour project [1][2] but it doesn't seem to have a Java binding or port (apart from CritterAI but it's not a straight port) so far but someone's got to do the work sooner or later :) If you choose to go that route please get in touch as I plan to support it in my game at some point so we can coordinate the efforts.

[1] http://code.google.com/p/recastnavigation/

[2] http://digestingduck.blogspot.com/

  • \$\begingroup\$ This is a very performant solution. Looking up to see if a tile walkable is basically O(1) \$\endgroup\$ Commented Mar 7, 2011 at 16:36

You use something called a nav mesh. This is basically (in this simple case) a texture with just one bit for each square- collidable or not. When the player tries to move, you check the texture.


Ok, I think I understand your problem and you have a few options that I can think of, the best I don't want to write the code for, but I will give a metaphor for the algorithm I am suggesting. imagine your map as colored entirely black and white, where black pixels are not allowed to be collided with and white pixels are. then imagine your hero (or any character) to be a shape cut out of that map. if any of the pixels in the shape are black, then you have collision. this is similar to what the folks above were suggesting but it does not assume that your character moves on a grid (well it does, but not the same way). some things that might help you speed this up. if your character moves one pixel at a time, then you only need to check the boundary of the shape for black pixels, if he moves two pixels at a time, you need to check two pixels in etc. and if you imagine this as boolean trues and falses instead of black and white, then collision is just everything in your test space ORed together. what's nice about this method, is that since you're only testing the boundary, you can make your collision resolution really fine and the amount of checks you have to do goes up as the square root of the number of pixels, which increases pretty slowly. Some ideas for optimization are to only check a small subset of the pixels in the border of your character since this check is going to occur very often, and this is a good approximation of the whole border.

another idea, you can actually do this by drawing, and then converting the color data into boolean data.

hope this helps.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .