Dev log: Demystifying movement collision detection

Help spread the word!Share on FacebookShare on TumblrTweet about this on TwitterShare on Google+Share on LinkedInShare on RedditFlattr the author

DemystifyingCollisionDetection1

In a previous dev log, we explored how movement is done and I provided a very bare-bones implementation of “pixel movement”, which allows you to move your character along a finer movement grid.

In this article, we explore how map movement collision detection is implemented in RMVX Ace and try to come up with a solution that will allow us to move less than one tile per step without walking into a wall, or into other sprites

Note that all code examples rely on the Pixel Movement script shown in the previous dev log.

Background

According to Wikipedia:

Collision detection typically refers to the computational problem of detecting the intersection of two or more objects.

So for example if you’re walking along a wall, if you try to walk towards the wall, the engine should detect that you are about to intersect with the wall and prevent you from continuing to move.

To review, RPG Maker uses a tilemap to represent its maps. Each tile is 32×32 pixels in dimensions. Coincidentally, character sprites are also 32×32 in dimensions, fitting exactly within one tile. Furthermore, each step that a character takes is measured in terms of tiles. When you take a step on the map, the engine determines whether that tile is passable. If it is not passable, you cannot move in that direction.

From this summary, there are two types of applications for collision detection

  • Map passability
  • Event triggering

Well, if you think about it, they are basically very similar, but I like to think of them as two separate cases.

How Movement Collision Works

To see how the default scripts handle collision detection for movement, we consider the case where the player wants to move to the right. Movement begins in the Game_Player class:

def move_by_input
  return if !movable? || $game_map.interpreter.running?
  move_straight(Input.dir4) if Input.dir4 > 0
end

Which leads us to the definition of move_straight in one of the superclasses, Game_CharacterBase:

def move_straight(d, turn_ok = true)
  @move_succeed = passable?(@x, @y, d)
  if @move_succeed
    set_direction(d)
    @x = $game_map.round_x_with_direction(@x, d)
    @y = $game_map.round_y_with_direction(@y, d)
    @real_x = $game_map.x_with_direction(@x, reverse_dir(d))
    @real_y = $game_map.y_with_direction(@y, reverse_dir(d))
    increase_steps
  elsif turn_ok
    set_direction(d)
    check_event_trigger_touch_front
  end
end

Now we see from the first line that moving is possible when the specified (x, y) position in the given direction is passable, so we see how passable? is defined:

def passable?(x, y, d)
  x2 = $game_map.round_x_with_direction(x, d)
  y2 = $game_map.round_y_with_direction(y, d)
  return false unless $game_map.valid?(x2, y2)              # (1)
  return true if @through || debug_through?                
  return false unless map_passable?(x, y, d)                # (2)
  return false unless map_passable?(x2, y2, reverse_dir(d)) # (3)
  return false if collide_with_characters?(x2, y2)          # (4)
  return true
end

There are basically 4 reasons why you can’t move to another tile.

  1. You will fall off the map (the RMVXA world is indeed flat)
  2. You can’t move from your tile in the given direction (one-direction passage settings)
  3. The other tile is not passable (apparently if you’re walking backwards)
  4. You will run into another character (such as an event that is not passable)

For the purposes of this article, the last reason is not relevant at this point, as we are focused strictly on map movement. We will re-visit it later. For now, we just want to be able to make sure our character does not walk into a wall.

Single-point Collision

One thing that should be pretty obvious from the way passable? is defined is that it only checks one point to determine whether you can pass or not. If you’re at (0, 1) and you wish to move to (0, 2), then all you need to do is check whether (0, 2) is passable or not.

That’s like saying if you want to move forward, all you need to do is check whether the center of your body will collide with whatever is in the direction you want to go, and if there is no collision, then you may move.

Well, that is acceptable in RPG Maker, because your character is the size of the tile and so if walking into the other tile will cause a collision to occur with any part of you, then the movement will not occur.

However, it no longer becomes acceptable once your movement grid size is different from the size of your characters, because now you can move inside a fraction of a tile and your sprite will appear to be walking into a wall before the engine determines that you have finally collided with the wall.

So, single-point checks don’t work. Is there anything we can do?

Bounding-box Collision

Imagine an imaginary box around you that perfectly contains you. That is the bounding box. Or rectangle. Whichever works. This is a very easy way to check for collision, but it is very crude and doesn’t take into consideration the actual shape of the object that it contains.

But, one thing you may (or should) have noticed is that RTP characters tend to be fairly box-shaped.

DemystifyingCollisionDetection2

 

 

So it should be acceptable if we just stick to these boxes.

Extending a point to a box

Let’s go with the assumption that our sprites are boxy. The problem we have right now is that our sprite sizes no longer match our movement grid size.

DemystifyingCollisionDetection3

To solve the problem, I introduce a little trick to make the passage checks align with the size of the sprite (assuming it’s 32×32):

class Game_CharacterBase
  include TH::Pixel_Movement

  def map_passable?(x, y, d)
    x_hi = x + 1 - Tiles_Per_Step
    y_hi = y + 1 - Tiles_Per_Step
    return false unless $game_map.passable?(x, y, d)
    return false unless $game_map.passable?(x, y_hi, d)
    return false unless $game_map.passable?(x_hi, y, d)
    return false unless $game_map.passable?(x_hi, y_hi, d)
    return true
  end
end

Which increases the collision checks to the 32×32 grid. Now the results:

DemystifyingCollisionDetection4

The left image shows simple movement. The center shows the player trying to move down, but unable to. The right shows the player trying to move down again. It looks like you should be able to, but due to the fine pixel movement, you can’t. If this is an issue, we can make the collision box slightly smaller into the sprite, so that the box itself might be smaller than 32×32.

class Game_CharacterBase
  include TH::Pixel_Movement
  
  # 4 pixels per step
  def map_passable?(x, y, d)
    delta = Tiles_Per_Step * 2
    x_lo = x + delta
    y_lo = y + delta
    x_hi = x + 1 - delta
    y_hi = y + 1 - delta
    return false unless $game_map.passable?(x_lo, y_lo, d)
    return false unless $game_map.passable?(x_lo, y_hi, d)
    return false unless $game_map.passable?(x_hi, y_lo, d)
    return false unless $game_map.passable?(x_hi, y_hi, d)
    return true
  end
end

And this should make movement somewhat more flexible!

Note that this assumes you’re moving 4 pixels per step. You will need to fine-tune these calculations for different movement grids. For example, if you’re using 8 pixel per step, you’ll find yourself walking through walls. You’ll need to change the calculations a little:

# 8 pixels per step
def map_passable?(x, y, d)
    delta = Tiles_Per_Step 
    x_lo = x + delta
    y_lo = y + delta
    x_hi = x + 1 - delta
    y_hi = y + 1 - delta
    return false unless $game_map.passable?(x_lo, y_lo, d)
    return false unless $game_map.passable?(x_lo, y_hi, d)
    return false unless $game_map.passable?(x_hi, y_lo, d)
    return false unless $game_map.passable?(x_hi, y_hi, d)
    return true
  end

Closing

At this point, we have accomplished two things:

  1. We can specify how many pixels we move per step.
  2. We can move around the map without walking into walls or other obstacles

It assumes a lot of things about our collision area (eg: they are 32×32, just like most of the RTP sprites), but this should be a very simple and compatible pixel movement script.

There are still several issues that need to be addressed, the most important being event collision and interaction with objects, both of which require you to perform collision detection between two objects. It also does not properly check whether you collide with another character, which could be considered part of “movement” I guess, but one step at a time.

Spread the Word

If you liked the post and feel that others could benefit from it, consider tweeting it or sharing it on whichever social media channels that you use. You can also follow@HimeWorks on Twitter or like my Facebook page to get the latest updates or suggest topics that you would like to read about.

Help spread the word!Share on FacebookShare on TumblrTweet about this on TwitterShare on Google+Share on LinkedInShare on RedditFlattr the author

You may also like...

1 Response

  1. October 6, 2014

    […] grid from 32×32 pixels to alternative sizes such as 16×16, 8×8, or 4×4. In the second part, we explored how our new movement grid could be integrated with the tilemap system using a new […]

Leave a Reply

Your email address will not be published.

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax