Bresenham Line Algorithm & Chase ‘n Ate:

To see the animation – Click Image Below

demo_anim

Chase ‘n Ate is a simple survival game.  The object of the game is to eat as many green and blue dots as you can while trying to stay away from the red dot that is chasing you.  Artificial Intelligence is applied using the Bresenham’s Line Algorithm (details below).

Features:

  • The green dots are worth 1 point each.
  • The red dot is constantly chasing you.
  • If the red dot eats any green dots, the red dot will move faster.
  • The blue dot is constantly chasing the red dot at a slightly slower speed.
  • The blue dot is worth 5 points.
  • If the blue dot eats any green dots, the value will increase by 5.
  • The purple dot will randomly appear at random times.
  • The purple dot is not worth any points, but will make the red dot run away for a short time if you eat it.
  • There is an easy way to increase your score – can you find it?

Download Chase ‘n Ate
(for any Windows PC)

 

The Bresenham’s Line Algorithm:

In 1962, Jack Elton Bresenham developed a simple line algorithm while working at IBM. Thus, the Bresenham line was developed and today is one of the easiest forms of artificial intelligence (AI) to code.

When it comes to designing a “chase” script for AI in a tile or pixel environment, a simple approach is to draw a straight line from one point to another, even if those points are constantly changing.  Visualize looking down at an empty room. The player stands in one corner, and the predator (the computer) stands in the other corner. In the diagram below, one can imagine the player (represented by an “P”) and the computer (represented by an “C”) trying to reach the player on a simple 2D 6×6 grid:

grid1

Right away one may think this is easy enough; however, how do we tell the computer to get from the coordinates (0,0) to (6,6)?

In this example, we use the simple slope formula:Slope_formula_2 a programmer can use this formula to tell the program to “walk” along the coordinates of (0,0)(2,2)(3,3)(4,4)(5,5)(6,6) to reach the target, or the player. You may remember this formula from basic math using the “rise over run” method to find a slope.

At the base, the Bresenham’s Line Algorithm simply uses the slope formula to draw a line on a grid, in which we tell the computer to draw the predator frame by frame, while following the line drawn from the slope formula.

If the grid was not such a perfect square as the example above, how would it work?
Take the next example of a 7 x 13 grid:

Bresenham_Line_example1

Our computer is now located at (1,5) and our player is located at (12,1).  Again, using the slope formula, we would get the computer to walk along the coordinates  (1,5) (2,5) (3,4) (4,4) (5,3) (6,3) (7,3) (8,2) (9,2) (10,1) (11,1), which will give us a kind of “jagged” look while the computer is walking.

Bresenham_Line_example2

 

When playing the game Chase ‘n Ate, sometimes you can notice this imperfect movement when the red dot is chasing the white square in a straight line.  This is due to your computer’s screen and the game using pixel coordination instead of a square grid.

When it comes to programming the Bresenham Line in just about any language, one can think of taking the approach of:
“If –  the predator’s (x/y) location is a higher value than the player’s (x/y) location,”
“Then –  subtract the predator’s (x/y) location by a small value.”
Or Else:
“If – the predator’s (x/y) location is a lower value than the player’s (x/y) location,”
“Then – add the predator’s (x/y) location by a small value.”

Imagine your predator moving around the screen, constantly drawing a straight line to the player, and moving along that line at the “small value” you assign it.  If you increase that “small value,” your predator will move faster!  This is the logical approach we take with the predator (or red dot) in Chase ‘n Ate.  When the game starts, both the player and the red dot are located at a distance apart from each other, and the red dot immediately starts moving towards the player at a “small value.”  We set up another “if” condition that tells the red dot the following:
“If – the predator crosses the coordinates of an existing green dot,”
“Then – increase the value of the “small value.”
By doing this, we now have a situation where the player can’t avoid the red dot forever.  Eventually the red dot will increase it’s movement value to where it moves faster than the player.

Let’s think about this approach in reverse.  In the game Chase ‘n Ate, there is a randomly appearing purple dot.  When the player comes in contact with that purple dot, the red dot will “run away” from the player for a short period of time.  This is accomplished by simply reversing the logic we have for chasing the player:
“If –  the predator’s (x/y) location is a higher value than the player’s (x/y) location,”
“Then –  add the predator’s (x/y) location by a value.”
Or Else:
“If – the predator’s (x/y) location is a lower value than the player’s (x/y) location,”
“Then – subtract the predator’s (x/y) location by a value.”

Lastly, our blue dot in Chase ‘n Ate is following the exact same logic as the red dot for chasing the player.  The only difference is that the movement value is set to be slightly lower than the red dot.  This gives the player the opportunity to maneuver around the play area in a way that will force the blue dot to gain enough distance from the red dot that the player can reach the blue dot without coming in contact with red.

In conclusion, Chase ‘n Ate gives you three good examples on how some simple artificial intelligence can be created by use of the Bresenham’s Line Algorithm.  One last thing to keep in mind when actually programming your AI is that our examples shown in this article are using coordinates as it would be found in any mathematical graph, meaning that (0,0) will be the bottom left of the graph.  In the computer world, however, the actual coordinates of (0,0) will be the top-left corner of your screen!

wikiExample