For starters did you know Google Chrome has an inbuilt game that is made visible when you are offline, but you can directly access it when you are online as well.
Let’s check it out, please open Google Chrome and then type “chrome://dino” in the browser URL or website bar on top
Next click on space to play the game.
If you played the game for sometime you must have figured it out that the rules of the game are very simple.
you see an obstacle in the form of cactus or bird you press space or up arrow and Dino jumps to avoid it.
But did you know that you can press down arrow key and the Dino will duck from the flying creatures !
So, how should we go about writing a program that can play this game.
- Let’s do some quick analysis:
After playing the game for some time, these are the things that I noticed
Dino is standing still, legs are moving but the position is actually fixed on the screen
Ground objects or obstacles are coming towards Dino
Ground objects or obstacles are sometimes in cluster (group of cactus)
Flying objects or obstacles are coming towards Dino
There is a fixed line indicating ground
There are clouds indicating sky
Sometimes the flying obstacles are in-line with Dino
Sometimes the flying obstacles are above Dino
Example:
- What are the things that we care about
The Dino’s position on screen
Ground objects or obstacles are coming towards Dino
Flying objects or obstacles are coming towards Dino
Ground or Flying object position on screen
Distance of Dino from Ground or Flying
- Let’s narrow down our focus
remove the Dino from the screen because as we can see the Dino position is fixed
remove the parts of screen that are below the fixed line indicating the ground, including the line
remove the parts of screen that are above the Dino face
Now we are left with
a very small section of image with cactus as ground objects/obstacles
Big cactus on the ground
Small cactus cluster on the ground
flying objects/obstacles that are flying inline with Dino’s face
Section of flying object that is in line with Dino
- Let’s do some basic solution design:
open browser
send space/up-arrow to start the game
Start Infinite Loop
take screenshot
trim screenshot such that we are left with only parts that we care about
identify if the Dino is still alive then
inspect the screenshot for any obstacle/object
identify if the obstacle/object is flying or is on the ground
if there is something on the ground
how far is the object
what is the width of the object
jump when object is close
if there is something flying
how far is the object
duck when object is close
if the Dino has hit an obstacle then stop the loop
Simple enough, so what do we need to implement the above solution?
- Let’s add some logic to the solution:
open browser
we will use Selenium to do this for us
send space/up-arrow to start the game
we will send the key press using Selenium
Start Infinite Loop (for or while loop)
take screenshot
We will use selenium to take screenshot of the game canvas
trim screenshot such that we are left with only parts that we care about
we will have to first manually inspect the image to identify how much to crop
once manual analysis is done we can then hard-code the X, Y, Width and Height
identify if the Dino is still alive then
inspect the screenshot for any obstacle/object
we will loop the image buffer looking for any grey pixel, presence of pixel means there is an obstacle
identify if the obstacle/object is flying or is on the ground
we will start from top left corner and move towards X axis if anything is found, we will inspect the position at the floor of that X axis if there is something on the top and bottom it means object is a ground object
if there is only grey pixel on the top and no pixel on the bottom is means object is flying
we will record the first grey pixel location
if object is on ground we will then continue move towards the X axis to identify the width of cactus to identify if it is a single cactus or a cluster
if there is something on the ground, how far is the object
This is the recorded first Grey pixel location
what is the width of the object
This is the recorded width of the object
when should we jump
We will chose a random value of how far the object should be when we jump and see what works for us
if there is something flying, then how far is the object
This is the recorded first Grey pixel location
when should we duck
We will chose a random value of how far the object should be when we jump and see what works for us
if the Dino has hit an obstacle then stop the loop
To do this we will save the screenshot buffer in a List and if a few consecutive screenshot buffers are same it means the Dino has stopped running which means it has hit an obstacle
Now try and think of Dino as a Robot, so how do robots work, they have sensors which they use to understand its surrounding.
So our Robo-Dino will have a master sensor that takes in the image as input and add it to a buffer, if there are images in the buffer then it will compare the new images with other images in buffer, if they are all same then that means environment is not changing which means end of game.
- Let’s think about some test cases that will cover the above solution logic:
Given a cropped screenshot image of flying object we should be able to correctly identify that the object is flying
Given a cropped screenshot image of flying object we should be able to correctly identify flying object distance from Dino
Given a cropped screenshot image of ground object we should be able to correctly identify that the object is on the ground
Given a cropped screenshot image of small ground object we should be able to correctly identify that the object is on the ground
Given a series of cropped screenshot images indicating a moving ground object we should be able to correctly identify that the object distance is reducing as it moves closer to Dino
Given a cropped screenshot image of ground object we should be able to correctly calculate ground object width
Given a cropped screenshot image of ground object we should be able to correctly calculate ground object width even if it is at the end
Given a cropped screenshot image of flying object we should be able to safely skip calculating flying object width
Given a series of cropped screenshot images
we should be able to correctly identify that the Game Over has occurred if all the images are similar
As explained above the parent Sensor will try and identify Game Over
Master sensor will pass the image to actual sensor that knows how to do image processing, this sensor will reduce the scope of vision and then analyze the buffer to identify the obstacles and decide when to jump or duck
So what next ?
We can use this code as a starting point and then use it to
1. replace the screenshot with a webcam feed
2. write image processing algorithm that checks the entire webcam feed and run connected component analysis to pickup the all the objects
3. use stochastic algorithm with input as distance, velocity, width of object to determine when to jump
4. or simply use basic physics formula and input the #3 values to get the distance and then run brute force to determine when to jump
Next I will use this code to write a very simple genetic algorithm chromosome that will try, and guess when to jump using the distance only.
The simple or dummy Genetic Algorithm code will help understand Stochastic Algorithm, and their use cases
Please star or fork if you liked the source code snippets.
Hope this article helped you to see some concepts in new light.
Please clap or write a few lines to let me know if you enjoyed reading this article , what do you think about my code and unit-test-cases.