Collision Detection Part-1

Introduction
This tutorial is an introduction about collision detection and in this first part we will see how to detect collision between two circles. I will be using Python programming language to write the code and hope you are already familiar with Python language 🙂

Collision between two circles
Here we will take two circles as our input, for each circle we will take the position and radius. Using this three values from each of the circle we can easily check the collision.

  • Calculate the horizontal distance between the circle centers
  • Calculate the vertical distance between the circle centers
  • Form a right angle triangle using the horizontal distance as base and vertical distance as height
  • Calculate the length of the hypotenuse using the base and height
  • Calculate the distance between the center of the circles
  • If hypotenuse calculated is less than the distance between the center of the circles we can say a collision occurred.

The below given image describes three different cases of collision between two circles

collision

How can we make use of the circle collision detection
Consider two objects having random shapes and you have to do some collision collision check between this two objects. Yes the exact collision detection between random shaped objects are not easy to achieve. But you can do the collision detection between this two with circles

  • Define a mask for each of the shapes. Let the mask be a circle of a specific radius. The radius selected should be enough to cover (at least 80%) the random shaped object. Do the same for the second object
  • Now all you have to do is processing this mask while checking collision. Since the mask defined for each object is circular in shape and cover 80% of the area, the collision checking will be easy and enough. 🙂

The Program
The below given program is written in Python language and the things that we saw above is written step by step.

import math

# Find the absolute value of a variable
def absolute_value(x):
    if x < 0:
        return 0 - x
    return x

# Read parameters of a circle, x_position, y_position and radius
def read_circle(number):
    radius = int(input("Enter circle " + str(number) + " radius: "))
    x_position = int(input("Enter circle " + str(number) + " x position: "))
    y_position = int(input("Enter circle " + str(number) + "y position: "))
    print()
    return (radius, x_position, y_position)

# Create a right angle triangle and check for collision
# Take two circles as arguments and do the calculation
def check_collision(circle1, circle2):
    base = absolute_value(circle1[1] - circle2[1])
    height = absolute_value(circle1[2] - circle2[2])
    hypotenuse = math.sqrt(base * base + height * height)
    center_distance = circle1[0] + circle2[0]
    if hypotenuse <= center_distance:
        return True
    return False

# The main method
# Print success message on collision
def main():
    circle1 = read_circle(1)
    circle2 = read_circle(2)
    
    collision_status = check_collision(circle1, circle2)
    if collision_status:
        print("Success")
    else:
        print("Failed")

main()

Hope this tutorial was helpful 🙂

Thanks for Reading

Game Development Season 1

Hello, today I am going to show you how to develop a computer game where character run continuously along a straight road collecting points and avoiding obstacles.

What are the things required while developing this type of game?

Character development

The game have a main character. We have to give a proper behavior.

  • Character can jump left or right, jump over the obstacles, slide under obstacles.
  • Character will die when hit the obstacles and so game will end.
  • Character can collect points from the road by hitting them.

World

World is where we have everything in picture. The road, points, obstacles and main character. The obstacles are vehicles and hurdles. The main character have to jump over vehicles and slide under the hurdles. Or simply jump left or right. The road will have three lines. Where vehicles move towards main character.

If you look close to such games you will see the main character is not moving forward or backward. That is the magic. The other things are actually moving. Got it?

Getting in to the Picture

The objects are created and placed in the world continuously in equal time interval in different patterns. This includes points or coins and obstacles. If you look at any such game you will find this pattern and the same pattern can come more than once.

Each time interval a pattern generator create patterns and based on the pattern objects will be placed in the world. At first the pattern is created for obstacles. Secondly the pattern is created for coins or points. While generating the second pattern we have to consider the pattern of obstacles. Got it?

The reason we are doing this is simple. When coins are placed in the world, ten or less coins can be placed in the line in an interval. We place coins continuously one by one. Say if the next position is occupied by an obstacle, we can place coin over the obstacle if it is a vehicle or do like this for hurdles by placing coins under hurdles. You got the picture right?

Once we finalize the patterns for the current time interval we can use the pattern to place the objects in the world and they will move towards main character 🙂 . In these type of games pattern generation is important. Patterns must be created without continuously repetition. If we generate same pattern continuously, it will be boring. We can customize the patterns on demand by giving behaviors and look and feel.

Hope this tutorial gave you a small idea about running games 🙂

Algorithm to insert words into a 2D Matrix

About
The following algorithm can be used to put some selected words to a matrix without a specific order. Initially the matrix will be empty. Once we put the selected words, we put random alphabets to the empty cells. So by doing this we can hide these words in random position. The same can be used to generate the Find Word puzzles

There are total eight possible directions possible, they are NORTH(0), NORTH-EAST(1), EAST(2), SOUTH-EAST(3), SOUTH(4), SOUTH-WEST(5), WEST(6), NORTH-WEST(7)

The algorithm is given below

global matrix[10, 10]

procedure insert_word_to_matrix(word)
  directions <- [0, 1, 2, 3, 4, 5, 6, 7]
  completed <- NO
  tries <- 5
  while not completed
    if tries reached 0
      exit this while loop
    (x_position, y_position) <- Locate an empty box randomly
    shuffle(directions)
    next_direction <- 0
    while next_direction is less than 8
      (x_increment, y_increment) <- get_direction_increment(directions[next_direction])
      if possible_to_insert((x_position, y_position), (x_increment, y_increment), word)
        do_insert_word((x_position, y_position), (x_increment, y_increment), word)
        completed <- YES
        exit this while loop
      next_direction <- next_direction + 1
    tries <- tries - 1
  if completed
    return YES
  return NO

procedure get_direction_increment(direction)
  if direction = 0 return (-1, 0)  
  else if direction = 1 return (-1, 1)
  else if direction = 2 return (0, 1)
  else if direction = 3 return (1, 1)
  else if direction = 4 return (1, 0)
  else if direction = 5 return (1, -1)
  else if direction = 6 return (0, -1)
  else if direction = 7 return (-1, -1)

procedure possible_to_insert((x_position, y_position), (x_increment, y_increment), word)
  word_length_counter <- 1
  while word_length_counter is less than length(word)
    (next_x_position, next_y_position) <- (x_position + x_increment, y_position + y_increment)
    if (next_x_position, y_position) is outside the matrix
      return NO
    else if matrix[next_x_position, next_y_position] have no value
      word_length_counter <- word_length_counter + 1
      continue while loop
    else if matrix[next_x_position, next_y_position] is not equal to word[word_length_counter]
      return NO
    word_length_counter <- word_length_counter + 1
    continue this while loop
 return YES

procedure do_insert_word((x_position, y_position), (x_increment, y_increment), word)
  word_length_counter <- 1
  matrix[x_position, y_position] <- word[0]
  while word_length_counter is less than length(word)
    (next_x_position, next_y_position) <- (x_position + x_increment, y_position + y_increment)
    matrix[next_x_position, next_y_position] <- word[word_length_counter]
    word_length_counter <- word_length_counter + 1
    continue this while loop

Note: Here we try to fit the word by taking each direction from the list for a selected position. This is some times time consuming. So we can try another method. First find the best fit directions (at least three) for the selected word using the matrix boundary and word length. Check if it is possible to fill in any of the selected direction.So by doing this we can improve the performance

Hope this tutorial was helpful 🙂

Thanks for Reading