Steganography: Hands-On approach

Stumbling upon Steganography (Inspiration behind this post):

Have you heard about the site called 300 Mechanics?

Well, I guess, many have heard about it. It’s on the first page of Google search for terms like “game mechanics” and it’s quite a class of its own. I have hunted this website often for game ideas and though I am not a great admirer of turn-based and card mechanics (which is a considerable portion of the mechanics posted there), there is a lot of food for your thoughts.

And there was this one post, about saving game save files as images.

I liked the idea, though I wanted to generalize the idea like this : Saving any file as image (not just changing the extension, actually making a picture out of it) and restoring the original file from that image alone.

Now, you are going to shoot me, I know: This is almost what Steganography is, though the original file is hidden in another innocent picture.

But unfortunately, until one of my friend (to whom I described the idea) told me about this “Steganography” thing, I believed it was one of my new ideas and I was super-excited about it.

So, here it is: It is not really an original idea, so I decided to make a “How-to” tutorial on it using Gamemaker ...

Concept Briefing: Saving the file as image

Once you get started, you can easily see how easy the concept is:

Let’s say there is a file “xx.xxx”. At first, somehow we need to draw it to the screen and save the screenshot. This screenshot will be our stand-alone image (instead of the file) and we can restore our original file from this image (using the algorithm I will describe later).

The process we will use

So, lets come to the most important term here: “somehow”.

How exactly are we going to draw a file to the screen? 

Here is my approach: 

At first, read the file byte by byte (so, it doesn’t matter what type of file it is as every format is similar in binary) and return in decimal format (for e.g. “A” should be read as 65, its ASCII value and not as the binary equivalent of 65 ). 

[Now. Let’s talk about RGB colours a bit. Every colour in RGB format (HSV format is also possible) consists of a value of Red, green and Blue (in the range 0-255) because red, green and blue are three primary colours and every colour can be made using a variation of these.]

Our primary task, now, is to convert this number returned in ASCII format to a unique colour, which is to be drawn on the screen. One of the facts, which might appear astonishing at first, is that extended ASCII table has 256 values (0-255) and range of value of red, green and blue each in RGB format is also 0-255. [This is probably due to the fact each of them is allotted one byte (8 bits) of memory space. So, there are (2^8)=256 possible values.] So, now we have to choose any one-to-one function which has equal range of domain and co-domain to convert ASCII value to RGB value. For sake of simplicity, we are choosing a easy relation between the two: Blue value of RGB=ASCII value of the character, Green value=0 and Red value=0. What it simply means is that we use the ASCII value as the blue value in RGB colour format and we use the value 255 for both red and green in the RGB colour.

Now for each byte of data, we have one specific colour. Next, we decide to draw these colours on the screen. It is quite simple: Just as in notepad, we start from the top-left corner of the screen  by drawing a pixel with the colour corresponding to the ASCII value of the first byte and then we move towards right (1 pixel at once) by considering the next byte of data and so on. There is just one thing- Similar to text wrapping, we have to use a wrapping function so that this drawing function moves to the next line when it is about to go out of view.

So, here we have our file drawn to the screen. The final task is to take a snapshot of this drawn screen and save it as the stand-alone picture instead of the file. Our next section deals with how to restore the original file from it.

 Concept Briefing: Restoring the original file from the screenshot

The actual process of Steganography

We are almost finished with our steganography tutorial. This part is easier than the earlier and shorter too.

So, we already have our screenshot. Let’s get the original file back from it…

Here, we need to have a function which will help us pick any colour from the screen and tell its red, green and blue values. Fortunately, Gamemaker has the draw_getpixel()  and colour_get_blue() functions to help us with this situation.

Initially, we need to clear the screen and load the screenshot as the background.

Then, we will need to start from the top-left corner of the screen [(0,0) in Gamemaker], pick the colour  at that point, get its blue value, convert it to its ASCII equivalent (which is actually equal to the blue value here),write the character equivalent of this ASCII value to a “new” file,  move towards the right one pixel at a time and continue this process until there is only the background left. [Also, we will need to use the aforementioned wrapping function to make sure that we move to the next line of the screen when the colour-picking function is about to go out of view.] To identify the background, I used black colour as the background. As the R, G and B values of black are 255,255,255 respectively, we can easily identify the black colour by getting just the red or green value (as we are using red=0 and green=0 for our drawn points).

So, when this whole process completes, we will have the content of our original file back in the “new” file. Just make sure to give it the same extension as your original file to access it properly.

Problems and suggested improvements:

 

Two most important drawbacks of this tutorial is that it will support only small files (about 350KB) and the process is very slow in Gamemaker.

To increase the file size limit, there is an easy solution: use surface (applicable with Gamemaker only) to draw instead of the screen, because the maximum possible dimension of any surface is much more than the screen size. There will still be a limit in the file size because surfaces do have dimensional constraint (due to memory constraint), but still it is a lot higher. Also, you may use multiple surfaces wisely to get rid of this drawback. Theoretically, this problem can be solved.

The sloppy performance you’ll experience is only due to the slow performance of the draw_getpixel() function. Unless you can re-create a faster version of this function with an external DLL or extension written in a faster programming language, you’ll have to live with it.

As always, here are the links: .GMK file and .EXE file

Few Facts:

What we just did isn't real steganography, it's just a part. Steganography involves the removal of a particular sequence of pixels of an image with other pixels which contain the hidden data. We created this pixels which contain the hidden data, but we didn't do the removal part. The removal part isn't that hard, and you can easily try that. Also most of the times, a password is used to vary the sequence of removed pixels.

Storing two integers in one integer: Encoding and decoding

Intro:

 

Let's start with what a basic understanding of how integers are stored in the computer ....

Whatever programming language you use, in almost all cases,  there is a range of the value you can store in an integer variable. But, in practical cases, this range is quite high and it is not reached with optimized calculations.

And the most interesting fact is that, irrespective of the value of the integer, it is internally converted into a binary number of a fixed length (32 or 64, depending on the system and mechanism of conversion). In case of relatively small integers, their binary equivalents are much smaller in length than that fixed length and hence, these binary equivalents are filled with zeroes in the left to make them of that fixed length (filling with zeroes is done to keep the decimal equivalent  same). Now this binary number, always being of a fixed length, consumes the same amount of memory space.

This is where the process described in this post will come to use...

This process takes benefit of the fact (described earlier) that small intgers are also converted into a binary of larger length (than optimally required to store it). We will try to convert two integers into one bigger integer which retains the both numbers in the order supplied (referred to as encoding, I really like that term :D) and later recover both the integers from that bigger integer in the order supplied (no prizes for guessing.. referred to as decoding).

Just for those interested, the approach I describe in the later section, was originally inspired by the use of the escape character, \  in JavaScript.

 

Encoding logic:

Note: I will be using zero as the "separating" number in this example and referring to the two original numbers as numb1 and numb2.

So, the rules for encoding goes below:

1. Whenever one of the digits in numb1 or numb2 is zero, one extra zero is added before (or after, it doesn't really matter) that original zero. But, what is important is that this newly added zeroes should be just left as they are and should NOT be subjected to the previous part of this rule, as that will cause an infinite loop.
Also, this step should be done only once for the whole number.
In short, whenever there is a zero in the original number, they become a pair of zeroes in the modified number.
For e.g. after applying this rule on 1203, it becomes 12003 and similarly, applying on 1002 makes it becomes100002.

2. To get the final encoded number, the modified first number is to written side by side to the of the modified second number and a single zero is to be inserted between those two. (The whole thing can be done more easily in the form of a string but remember, no spaces anywhere.)
For e.g. if numb1=202 and numb2=0, the encoded number becomes 2002000. (The bold zero is the single zero inserted between the two modified numbers 2002 and 00).
Similarly, if numb1=120 and numb2=5, the encoded number is 120005.

 This is how we get the encoded number and to be true, this final encoded number makes little sense to anyone. So,we need to decode it now to get back those original integers.

Decoding logic:

 

So, you think it'll be quite easy right?

Well, I can't disagree more.

Let's deal with the most easy case first and the harder next:

1. In the encoded number, there are no 3 successive zeroes and there is one and only one single zero.

A:  This is actually the case where numb1 and/or numb2 contains non-zero digit in the terminal position (the front terminal position doesn't count because a number can't start with zero. Even if you write 012, it is considered as 12 by the compiler).

This case can be decoded by the following logic:

• 1.1 The encoded number is separated into two separate numbers at the position where a single zero is found, such that this zero is not considered within any of the separated numbers. The respective position (which number was in the front and which was in the back in the encoded number) of these two separated numbers must be remembered for the later step.
• 1.2 Now, with both of these separated numbers separately, whenever there are two zeroes in a number side-by-side, one of them is removed. This process will leave us with the two original numbers.
• 1.3 To get the original numbers in the order specified, the logic is that, whichever number was in the front in the encoded number leads to numb1 (after the previous two steps) and the other one is numb2.

• Example: If the encoded number was 12001023, then the numb1 and numb2 decoded in this process should be respectively 1201 and 23.

2. There is no single zero in the encoded number or there are more than 2 successive zeroes.

A: This is actually the case where numb1 and/or numb2 contains zero in the terminal position (again, only the last position i.e. digit's position counts). For eg., numb1=20 and numb2=0.

So, in this case, numb1  and/or numb2 can be equal to zero.

Logic for decoding:

• 2.1 When there are more than two successive zeroes in the encoded number, moving from left to right, the first two are considered as a pair and one of them is removed and this process continues for the rest of the digits of the number. 

•     2.1.1 If a single zero is left out after completing this process and it is not in the terminal position, then apply logic 1.1, 1.2 and 1.3 to get numb1 and numb2.
•     2.1.2 If a single zero is left out after completing this process (logic 2.1) and it is in the terminal position, then numb2=0 and numb1 is equal to this processed number.
•     2.1.3 If no zero is left out after this process (logic 2.1), then this processed number is equal to numb2 and numb1 is equal to zero.
• 2.2 When there are no zeroes, then numb1=0 and numb2=encoded number.

 

Conclusion:

 

That is pretty much the end of encoding-decoding logic, but there are some more things to say. 

First of all it's better to use the number with the least number of total appearance in numb1 and numb2 as the "separating" digit instead of zero.

And secondly, this whole process will work fine only when you are working with relatively smaller numbers, because else the encoded number may get bigger than the highest possible value that can be stored successfully in integer variables.

And thirdly, as you might have guessed, I have made a small app for this with Gamemaker : GML link and Exe link

So, till the next time, good bye.

Arrays in GML : 5 things you probably don’t know

What is GML?

You have most probably heard of Gamemaker, the popular game design software.

Along with Drag-and-Drop (D&D) feature, it also features an extensive coding language, which is formally called “The Game maker Language (GML)”.

According to Mark Overmars, the original creator of Game Maker (which has been recently re-named as Gamemaker), “Game Maker contains a built-in programming language. This programming language gives you much more flexibility and control than the standard actions. This language we will refer to as GML (the Game Maker Language).”

Why this article?

The only official documentation of Game Maker is the help file included with the software. This help file, though complete, documents only what happens when something is used and the correct syntax to use it. But, it leaves out necessary details in some cases.

Among the many features of GML, I find the “Array” portion of the help file least detailed, which is (probably) supposed to be known by the user. Though this is acceptable, it often causes a lot of confusion when using arrays extensively for the first time in a new project. A lot of things have to be guessed. Now the problem lies with this guessing: Everyone with prior programming knowledge tries to think in terms of their previous concepts and experiences. Unfortunately, this often differs considerably due to the different approach of different programming languages.

This problem is concentrated further by the fact that compiled languages like C/C++ (which are most popular among programmers) support only fixed length arrays (without using dynamic memory allocation, of course) compared to GML which supports dynamic arrays (so, practically their lengths are not fixed and can be changed whenever required). Thus, for many programmers, previous concepts have to be tested in GML. This article tries to solve this problem, testing and publishing the result of every exceptional situation that may arise with arrays in GML. I have tried to answer every weird question about arrays that popped up in my head and thus, exposing some of the lesser-known facts about it. But on other hand, you are expected to know what is written in the help file.

Just a word of caution: You probably won’t find anything worth experimenting with arrays after you complete reading this.

So, let’s start…

1.     What does arr refer to when arr is an array? 

A: In GML, nothing is practically defined as a variable of some specific data type. The data type is instead implied based on the value assigned to it at any time. A variable is implied to be an array only when it is assigned a value in this format:

• a)      arr[ind]=value;   /* in case of 1-D arrays or */  variable_local_array_set(name,ind,value);

• b)      arr[ind1,ind2]=value; /*in case of 2-D arrays*/variable_local_array2_set(name,ind1,ind2,value);

Now that it is implied as an array, arr actually refers to the arr[0,0] ( which is the same as arr[0] ) position. 

1.      

2.     How are the 1-D and 2-D arrays related when a 1-D array is converted into 2-D array and vice-versa? 

 A: After a lot of experimenting, this is the final decision I came to: arr[ind1] is the same as arr[0,ind1] for all practical purposes. The value of arr[ind1] changes to the new value whenever the value of arr[0,ind1] is changed to a new value and vice versa.

3.     Is there any relation between numbers, strings and arrays? 

A: Two-dimensional arrays can be considered as the general data type for both numbers and strings as well as 1-D arrays (Hence, these are the special cases of an 2-D array).

      They are related in the following way:

• Any number or string variable (let’s say,the variable  named numb_or_string , usually used in code like this:  numb_or_string=something;) is actually the [0,0] position of the 2-D array of the same name(i.e. numb_or_string[0,0] ). Thus, numb_or_string can be alternatively called as numb_or_string[0,0] and vice versa . 

• Any 1-D array (for eg. arr[ind], used in code like this:  arr[ind]=something;) essentially refers to the [0,ind] position of the 2-D array with the same name(i.e.  arr[0,ind] ).

This answer generalizes the answers given in the first and second question.

As a side note, this is the reason why the same variable name can’t be used for two variables even when they are of different data types.

4.     Which elements of an array are filled with the default value?

 A: This idea is quite simple: I’ll explain it in terms of a 2-D array, though it can be easily applied with 1-D arrays (following the previous rules). The first and second index of a 2-D array is referred to as row and column respectively, for visualization purpose.

   The rules for filling up the elements of an array with the default value (zero) are:

•   If it’s a global 2-D array, then the [0,0] element is filled with zero.

•   In both local and global arrays, for any row, all the undefined elements between any two defined element is filled with the default value, zero.

5.     Is there always an error when a negative index is passed to an array?

 A: In terms of 2-d array, an error is always thrown when you use this type of syntax: “arr[ind1,ind2]=value; “ (where atleast one of the values among ind1 and ind2 is negative), to set or get a value. But only in one exceptional case, when you use variable_local_array2_set(name,ind1,ind2,value)  to set a value, such that ind1 is positive but ind2 is negative, no error is thrown. 

     I found out this last exception just out of curiosity. Though practically it is not of much use as the memory is ultimately leaked and so, the value can’t be accessed. IMO, it is some sort of a unimportant bug, so you should probably check if ind2 is negative, before using it in that function.

Neon BBXD HD : A review

Intro:

So what happens when you hunt the Gamemaker Community (GMC) forum for a game to review?

Well, you come across 4 types of games:

               1. WIP (Work-in-progress)

[ These are the guys I don’t have much to comment on: 

While some of them are pretty good games on the rise, others have a lot of room to improve upon]

         2.Novice games

[ These are mostly first or second-time projects. 

 Actually, most of the novice games are usually in WIP section, but a small number of them make it to 

 the  ”Finished Games” section.

 Now this finished ones are  playable, but usually buggy or easy projects. 

 Not really the kind of stuff you’ll like playing.

 They are usually very small in number, and are not continued for sake of better projects.]

     3. Intermediate games

[ These are the most in number. 

 While a lot of them are interesting, they are usually not totally bug-free.

 Most popular genres remain RPG, tower defense and platformers.

 Many of them are “just another game” and are not quite polished, but they are usually continued/updated for a reasonable amount of time.

A few of these games, which have interesting content, through continuous development, evolve to the next section of games. ]

            4. Jewel Games

[ The rarest kind and the ones worth waiting for- usually made by GMC veterans and becomes very 

 popular. 

 Highly polished games (not in term of graphics, but in term of game design), usually with quite 

 innovative  gameplay and intelligent level design – the ones you’ll always be coming back for.

 Many of the GMC Jam winners (usually continued even after the jam ends) fall in this classification.]

The first look:

 As this is my first review, I wanted to clarify how I classify most games in the GMC so that I can refer to the class of game whenever I review one.

So, let’s  come to the real stuff …..

When I decided to write a game review, I had the lucrative offer of choosing one of the ( recently ended) GMC Jam 6 games.

But I decided to act otherwise: 

I think those games have fair amount of spotlight on them and so, it will be justified enough to review one of the “not-so-popular” games from the “Finished Games” section.

So, by quite random choice, I picked up this game called “Neon BBXD HD” : 

I wanted to see how MisuMen49  (the creator of this game) have changed the classical Brick-breaking game. Also the description read “2 years in the making” – so that kind of interested me.

Frankly, at this moment,  I expected the game to fall into the Elite class of “Jewel games”. So, let’s see how it fares finally…

The moment you start the game you see a screen shake and some 3-D boxes thrown at your face followed by the name of the company (or group, maybe). 

This effect does look professional when you run the game for the first time; but when you come back at it later, you may find it a bit annoying and long (in duration).

Then, when  you finally start in the “Normal” mode, you get a screen filled with bright, colourful and outline-based brick arranged in a fashion, as you normally expect it to be.

 Those bricks get a lot of your attention due to their sleek and beautiful look.

 Now, when you start playing the game, you just wish that you knew each of the “power-up”s and “power-down”s  showing up on the screen (some of them may look similar).

They are broadly classified into good and bad category, recognizable from the colour of the bubble around them, so you don’t get confused. 

This is a nice addition to the concept of “power-up”s,  I suppose.

This is how your journey starts in this 100-level game….

To be true, it wasn’t possible to play the whole game, but I tried my best to get the whole picture and below are my opinion on specific elements in the game:

Graphics:

This is where this game really rocks!!

Neat attractive sprites and beautiful particle effects gives a edge to this modern-day version of Brick-breaking game.

I just wish that there were different backgrounds for different levels.

 The background is good enough, but it may get repetitive to the player.

 Also, the “Death screen” (when the player misses a ball) in which the colours were apparently just reversed, looks like a cheap effect – could have been done better.

Verdict: A (Very Good)

Gameplay:

Clearly, not the best gameplay I have experienced.

The game is perfectly playable, but there are some problems under the hood.

These are a few bugs which can make the whole gameplay experience bitter:

1.  The real "bugs" in the game get stuck among themselves as well as the wall.

 2. The "bat" goes outside the screen:

a) if you move the mouse hard towards one wall, 

b) also at times with the keyboard.

The frustrating part is that both of this either kills you directly or freezes your bat, which is again

( effectively) going to kill you.

       3. In "mouse mode", if your cursor is on the side brick walls, when you are reborn due to your 2nd or 3rd 

           life, the new bat is also created there and so it practically means one more unjustified death.

Verdict: B (Average)

Level Design:

I will be super-cautious about my comments here:

As a whole, this game takes a new take on the old “Bick-breaking” genre.

I didn’t go through even 50% of the game, so it’s not justified for me to give a rating here.

But from whatever I experienced, I liked the varying number of power-ups and attacks and specifically, how they can make a long level, a lot easy.

Sound:

The sound effects did make the whole experience more awesome, but the background music was kind of repetitive, so that should be changed.

The collision sound effects were quite  energetic and I loved them.

Also, the sound accompanying the screen shake was pretty good.

So, in short, whatever sound is present in the game is lovable, but I expected some more variations for the background music.

Verdict: B+ (Good)

Overall recommendation:

This game is more than worth downloading: definitely a lot better than average games, but still a “Intermediate level game”.

You are surely going to love the flashy neon graphics, but watch out from those nasty bugs.

I recommend not using the “Mouse Mode” due to the bug told earlier.

Finally, I am just hoping that all the problems of this game gets addressed by MisuMen49

and we have one more perfect game to play.

Verdict: B+ (Good)

Generating smooth roads for top-down racing games on-the-fly

Prologue:

I am making a fake 3D racing game (like a lot of flash games you have seen). It looks like a first-person racing game, but doesn't use any 3D functions. Why not real 3D, you may ask and the answer is quite simple:

a. Not every game development tool has 3D support

b. It will be lot faster if designed correctly.

When I was creating the tracks, I was a lot bored and it was a tiring task to lay long tracks by hand just for testing. So, I decided to code for dynamic random road generation, so that I will never run out of road :D

The beginning:

At first, I thought it would be quite easy, you know like:

 Generate random points within a small distance and join them to make a road.

But the major flaw that surfaced quickly was that the road was not at all smooth, it was like throwing away some chunk of concrete at places.

My thought was like:

This is not how roads really look like :(

So, I decided to come up with a new approach to tackle this problem and
the next day, I came up with this solution.

Main concept

 The idea is pretty simple. You'll need to have a knowledge of how sine curves are drawn on graphs.
We won't need any transformation matrices for this.

Note: 
1. The co-ordinate system is same as traditional, but the origin is at the bottom-center of the page.
   So, Y is always positive and X can be both be positive and negative upto a certain extent.
2. Co_eff is a constant value which constrains the maximum X co-ordinate of the road in order to
    fit it within the view. It is used as the amplitude of the sine curve.

First of all, I decided that that only full sine curves (one total period) will be used to avoid complexity.

 This also gave me one added advantage of smoothness of the curves even when one sine curve ends and a new one is drawn.

This are the steps for generating the first curve … The rest will follow similarly...

Steps:

1. Generate a random value  (within a  suitable range) and store it as y1
    This y1 value is the (relative) height (distance in the y direction) at which one full sine curve
    terminates.

2. Now, as we know, sine curves have a period of 2⊼ radians.
   But, in our case, the sine curve should start exactly at the current point and terminate exactly at the next
  point (0,y1) [relative to the current point].
  So, we need to find a variable named "value" such that y1=2⊼*value
  We will use a factor of (1/value) with the independent variable [here y-coordinate]
  (as the curves are drawn along y-axis, so the x-coordinate of the initial and final
   point doesn’t change. So, we don’t care about the x-coordinate)

3. Now, draw the curve “ x=co_eff*sin(y/value) ” starting from the initial point.

It will look like this:

Last words...

When I was first thought of this whole dynamic road generation thing, I asked one my friend on Facebook for his view on this matter. From what I could make out, he had a better but not-so-simple approach in mind. So, we decided to make a shared  Google Doc about this and I wrote about this concept there.

As of now, he's working on his version of this solution and hopefully, he will soon be done with it, and we can have a better version in this blog...

Using arrays for better analysis of nodes in a tree

Prologue

Let's start with the basics..

This post is written with the pre-supposition that the readers know about the theoretical concept of trees, storage of nodes of trees using lists and Depth-first search (DFS) used for analyzing those nodes...

[ If you are not aware of this terms, I suggest you read this book on Algorithms 

Also, keep Wikipedia handy if it appears a bit advanced...

Even if you know about these, still it's a good read..

As far as I can remember, it was allowed to be freely distributed; so you shouldn't hesitate downloading it. 

For quick learning, you may start with 3rd chapter named " Decompositions of graphs" and after completing page 95, I think you'll get the context...]

Context

As we all know,  "tree" is a theoretical concept in Computer Science and hence, 

data structures like lists or matrices are used for storing these trees.

Now, all that is fine, but how can you find the relation ( like parent, child, descendant) between two nodes?

For eg. consider this -> 

A company has about 500 webpages in their website.

The webpages are inter-connected among each other, 

but without any looping, for easy browsing of the reader.

Consider that they have maintained a site map as a list.

Now, someone needs to find (separately for each) if 100 of those pages (Group.A) links to another 100 pages (Group B).

So, using a normal DFS search, it'll take 100x100 searches which is not all feasible.

Even an optimized DFS search, which checks the relation between one webpage of say Group.A, with all the webpages in Group.B takes 100 DFS search and each of them needs to loop through many of the 5oo pages to find the required relation..

Can the process be optimized further?

Of course, we can...

Actually, we don't need that much of DFS search (or, just DFS, whatever)...

Whenever  DFS is used a good number of times times,it is bound to search through the same nodes which has been already searched in a previous DFS.

This optimization, on the other hand, increases the speed of the whole process, by sacrificing some storage space.

Ok, just show me how to optimize it... (The main concept)

What I plan is to run the DFS through the whole list  (i.e. all the nodes) only once..

And use a 2-D arrays (with the number of elements being equal to number of nodes) to speed up the later searches...

The DFS search is to be customized such that for every level, when the explore() function :gets called

1. The node address is used to fill up the positions of the first column array sequentially
2. The corresponding second column (of the same row) is filled up with an integer which is decided by the
    following rule:

• If it is the source, then the number used is 1.
• For every next level of the tree, zero (0) is apprehended to the end of the number that its immediate parent/ancestor was given.
• For every node, a number is added (in the end of the number previously obtained), which is equal to the sequential order of that node in that level in which it is accessed, taking only those nodes in account which have the same parent (not ancestor).

For eg, see the below  illustration:

1. The head node is given 1.

 

2. When the next level is accessed, a zero is added. So, it becomes 10.

 

3. Now, for the first accessed node in the second level, 1 is added at the end of 10; for the second accessed node in the second level, 2 is added at the end of 10;  and so on...

 

4. Now for the node in the third level which is the child of the node marked "102", at first zero is added to signify the next level and then 1 is added to show that it is the only child of "102" and hence it the child 

    which is accessed first... So, the number becomes "10201"

 

This continues similarly...

   

How is it gonna help me?

Now that the variable is assigned to each node, let's see how this numbers are gonna help us:

Note: This method is applicable only when the number of child of any parent is less than 100, which is acceptable for general purposes... Also, here acceptable zero refers to that zero which doesn't have zero after it and also isn't the last digit of the number... For. eg, if the head node had 40 sub-node, then the 1st child of the 30th sub-node will have a number "103001" : Here the coloured zero is not acceptable zero by definition, which actually signifies 0 of the 30th node..

1. The number with higher number of acceptable zero is of a higher level.

2. The numbers of same number of acceptable zero are of same level.

3. If between two numbers, all  the digits of the smaller number are same as the corresponding digits of the 

    larger number and 

    a) the larger number has no more acceptable zeros than the smaller one ->

        then the smaller number is the parent of the larger number.

    b) the larger number has more acceptable zeros than the smaller one ->

       then the smaller number is the ancestor of the larger one.

Thus, we can get all this information which are required for any type of relation between two nodes, without running the DFS multiple times, and using only one variable per node.

The End

Actually, I was reading that book called Algorithms (I mentioned at the Prologue) and I thought that this topic will bring a change of taste and so, here it is...

If you have any suggestions or want to have a small debate, feel free to comment.....

A bit more advanced motion planning ... Revenge of the zombies

Some words on the blog  (You can ignore this)...

Before I start this post, I am taking these opportunity to write something about the blog itself..

No one will like to read this, so let's keep it short..

 

In short, I made a banner for my blog using GIMP which you can see on the top instead of the text.. 

You can download the banner here if you wish and use anywhere, but don't remove the blog link..

Actually this is a stripped down-version of this image I made today using free GIMP brushes and fonts...

If you didn't notice, this image has a secret word hidden in the title itself !! Did you get it?

 You can get it here and also you can share it freely...

That's all about it, the real post starts here...

The post starts here...

FYI, this post is a continuation of the previous post on Easy Motion Planning made yesterday..

You must read the previous post, if you already haven't, to understand the context of this post..

I told something about optimization on the last post, but instead what I came up with is an algorithm for finding shorter route (compared to the previous one)...

But, unfortunately, this shorter route comes with a lot of sacrifice in terms of memory usage ..

I have always sticked to my philosophy of adding one example game to every theoretical concept offered in this blog and this one isn't a exception too, but, as I already said the game can slowdown a lot, specially if you move away from the zombies to a greater distance in a condition where there are numerous obstacles in between...

The example game is present here in .gmk format and here in .exe format..

Theoretical Concept (A better zombie arrives in the scene..)

 The main concept is a bit more detailed this time and so, it needs to be elaborated from the start...

Remember the previous zombie-human hide-and-seek game ??

Well, they unfortunately couldn't take down the lonely human that time because they weren't intelligent enough ....

So, they decide to learn from a human-vs-human hide-and-seek game and learn their strategy..

Zombies learn a thing or two :

They notice a few wonderful things :

• Humans don't change their direction of motion only when they hit an obstacle..

       They become aware of the obstacle from a distance and plan their motion before-hand before hitting an 

       obstacle and are usually able to avoid it...

       So, in a hide-and-seek game with obstacles, they are planning their motion virtually at every moment..

• Humans move in curved paths..

          They were confused how humans can move in curved paths !!

 

          After all, till now, they could move only in straight line...

 

          But in the end a wise zombie came up with this:

 

          Why not make small linear movements such that it appears curved as a whole??

 

           They already knew linear motion and so it wasn't hard for them to grasp the concept...

• Humans are ugly (What!! I am serious!) 

          After all, the zombies saw only their male counterparts :D

Learn and evolve:

As soon as they noticed how humans perform well in Hide-and-Seek game, 

they were bent on imitating all those good things to better their performance ....

A better strategy:

The zombies change their strategy for good and here's what they come up with:

1. If there's a linear motion possible towards the human from your current position, always take that route...

    (After all, those fancy curved motion ain't the least-distance paths in this case)

2. If there's no linear path available,

    A. At first, you'll scan your nearby places (like the previous strategy)

       starting from closest places and gradually moving to far away places with the help of a (hypothetical) 

       instrument which can tell you if you'll be able to see that human if you move to a certain point or not 

       (without  physically moving to that place) and also check if the path to that point is obstruction-free

    B. Now, if you don't find such a point, you just hope that some other zombie will find him...

        But, as in most cases, you'll find one, which is your "local goal".

        So, when you have that point, you just don't start moving towards that point and stop when you reach 

        it...

        Instead you take only a single step towards it and reanalyze the situation starting from point 1.

So, what's the big deal?

Well, you have to do a lot of analysis for sure, because you decide your next step wisely in every instant..

But, as a reward, you get all this:

1. You'll always know the position of your enemy, and you don't follow any obsolete "local goal" 

   (As the player is usually always in motion, your local goal is bound to change every instant..

     There was this problem with the previous approach that you continue to move towards your "local goal"

     even when it isn't the best motion possible, as the player changes position...)

2. You don't ever collide against a obstruction 

    (unless moving along the perimeter of the obstruction is the best possible route... 

     even in that case it isn't technically a collision...)

3. You move along a shorter path

   ( As your strategy is decided in real time, you don't move through longer path wasting some time...

      This is a direct impact of  the absence of "obsolete goals")

4. And can you believe this !!!

    Your motion, in some cases, appear to be curved in nature....

Verdict

What verdict!! 

Don't ask me if the zombies won or lost.... They don't PM me so often...

In case, they ever decide to, I'll surely share it with you ....

Ok, enough is enough !!

In a more serious tone, though, I think this more advanced Motion Planning has its own advantages and disadvantages...

It follows a much shorter path, for sure, but it isn't practical to  make the basic zombies this advanced because, of course,

a) it'll waste a lot of processing power 

(as it has to plan its next step every instant whereas the basic motion planning required such decisions only when it collided against an obstacle)

b) it'll make the game harder for the player...

So, it is usually better to use this motion planning algorithm only in case of "Boss zombies" or a army of "elite zombies"...

Whatever it is, in the end, always remember to keep the number of such zombies as low as possible....

The END ??

So, here ends my second post on Motion Planning 

And as I can feel, I will have a "overdose of motion planning" if I continue to post on this topic...

To be true, I don't have any more views to offer on this topic at the moment...

Though if I ever come across any fresh idea on this topic, I'll be sure to post theme here ..

So, there will be a change of taste in the next blog post:

The next post is going to be on one of those platforming tutorials I mentioned here ...

So, still tomorrow, good bye...