Memory Allocation and Linked Lists

Memory Allocation


Memory allocation allows the programmer to allocate a block of memory of a desired size, and then store data into the block, along with initializing a pointer pointing to this block of memory. In order to do so, I'll explain the use of malloc(), realloc(), free(), and calloc().


malloc() will allocate a block of memory, although it will not initialize it, and returns a pointer to the block of memory allocated. The prototype of malloc() looks like: void malloc(size_t size);. size_t is an integer type defined in the C library, which is an unsigned integer. So, size is just an integer and represents the amount of bytes to be allocated. Since malloc() will return a pointer to a block of allocated memory, you need a pointer in order to make use of a call to malloc(), like so:

//Memory allocation for a character array of n number of elements

char *p;
p = malloc(n + 1);

//you could also do:

p = (char *) malloc(n + 1);

Since a character in C is one byte the, numerical argument for malloc() ends up just being a simple integer. However, if you were allocating memory for any other type of data you would need to use the sizeof() function to determine how much memory to allocate.

int *p;
p = malloc(sizeof(int));

//you could also do:

p = (char *) malloc(sizeof(int));

Just as a reminder, if you ever need to figure out how many elements an array has, use the following idiom: num_Elements = (sizeof(array) / sizeof(array[0])). That will take the size of all the elements divided by the size of a single element, giving you an integer resultant.


realloc() will change the size of a previously allocated block of memory. The prototype for realloc() is: void *realloc(void *ptr, size_t size);. ptr must point to a block of memory that was previously used in a call to malloc() or realloc(). The size parameter can be either larger or smaller than the original block.


calloc() is similar to malloc() in all ways except in that it initializes the bytes to 0 within the block.


free() is very easy to use; simply pass a pointer that points to a memory block we no longer need, and it will be available for reuse later on.


Linked Lists


A linked list is a chain of structures (called nodes), where each node contains a pointer to the next node in the chain. The last node in the list would contain a null pointer. The advantages of using a linked list over an array, is that you can add in nodes anywhere in the list you want, and you can delete nodes anywhere you want. You can also create many types of data structures like graphs and trees using linked lists.


Here are the barebones of a basic node:

struct node {
  //... here would be the node's data
  struct node *next;
};

To access a member of a structure through a pointer to a structure there is a "shortcut" operator called the right arrow selection operator ->. The right arrow selection operator allows you to access the member of a value pointed by a pointer. The following are equal:

(*node).data = 10;

//this is the same as:

node->data = 10;

In order to add a node to the beginning of the linked list, all you need to do is create a temporary variable to hold your new node, assign the value of your new node to the variable, and modify your new node to point to the old first node. Since adding a new node to the beginning of a list is such a common task, I'll show a sample function on how to do so. In order for a function to directly add a new node to a list, you need to be able to pass a pointer to the function and make it point elsewhere. Since arguments are passed by value, you can't simply pass a pointer to a function, since the function will then only be able to modify a copy of the pointer passed to it. Instead, you would need to pass a pointer to a pointer, then, you can make the pointer point elsewhere.

void add(struct node **list, int n)
{
  struct node *new_node;

  new_node = malloc(sizeof(struct node));
  if (new_node == NULL) //the macro NULL is defined in stdlib.h
  {
    printf("Error: Malloc failed to allocate necessary space.");
    exit(EXIT_FAILURE);
  }
  new_node->value = n;
  new_node->mext = *list;
  *list = new_node; //modifies the value pointed by list, which is a pointer
}

In the above example, list is a pointer to the first node in a linked list. Since we pass a pointer to a pointer (when we call this function we would use &first in the first argument, being the address of the first node), we are able to update the list pointer to point to our newly added node.


In order to search through a list, from beginning to end, you would usually use a for loop. The idiom is actually very simple. You scan the value and make your comparison on the first node, then make your iteration point to the next node:

for (p = first; p != NULL; p -> next)
  ... //whatever code you want to loop

Remember how I mentioned that the last node in the list contains a null pointer? The NULL macro defined in stdlib.h has the value of a NULL pointer, and as such the loop will stop on the last node of the list.


The idea behind deleting a node is to search for your desired deletion and make the previous node point to the node directly ahead of your node to be deleted. One method of doing so, is to keep a "trailing pointer". You scan through each node and keep a pointer to the node previously scanned, so that you can delete the current node and make the previous node point the next one in the list. Here is a sample function that searches for a node with a value inside of it (this value could be the node's ID, or whatever you are searching for) and deletes the node using free().

struct node *delete(struct node *list, val)
{
  struct node *current, *previous;

  for (current = list, previous = NULL;
       current != NULL && current -> data_Member != val;
       previous = current, current = current -> next)
    ;

  if (current == NULL)  //val was not found, end of list reached
    return list
  if (previous == NULL) //val was in the first node
    list = list -> next;
  else                  //val was found within a node
    prev -> next;
  
  free(current);
  return list;
}

The for loop in this function actually just has a null statement, because all the actions are done in the iteration portion of the for loop; the previous node is set to the currently being scanned, and the currently being scanned is set to the next node. The for loop stops once the value you are searching for is found, or if the end of the list is found. The two if and the else statements catch all the possible outcomes of the for loop. If the first node in the list is going to be deleted (if previous equals NULL), you need to make your list pointer point to the second node.

Structures Unions and Enumerations

Structures


Out of the three data types structures are the most important, so I'll start by going over them. Structures are similar to arrays in that they hold data. However, a structure's data is referenced by name rather than numerical index. The data inside structures is private; each new structure provides a new scope. Here is an example of how to declare a structure with a couple variables of that structure type:

struct {
  int ident;
  char name[LEN + 1];
  int val;
} part1, part2;

part1 and part2 are now both the exact same data-type, and each have the same members as each other. A structure can also be initialized while it is declared, like so:

struct {
  int ident;
  char name[LEN + 1];
  int val;
} part1 = {1, "Mobo", 200},
  part2 = {2, "PSU", 75};

Alternatively you can use the designator operator "." to assign values to structure members, like so:

struct {
  int ident;
  char name[LEN + 1];
  int val;
} part1 = {.ident = 1, .name = "Mobo", .val = 200},
  part2 = {.ident = 2, .name = "PSU", .val = 75};

It doesn't matter where in the initializer that a member is given a value if it is given a value by a designator. However, is there is no designator, then the value will be given to the corresponding member in the order from top to bottom of the structure, and from left to right of the initializer. LEN is just a constant defined in a preprocessor directive, and could be whatever the coder chose. You must add one to compensate for an end of line null character.

Structures of the same type can be copied with the = operator. Although, you cannot use the == or != whether or not structures are of the same type. part1 and part2 from the above example are both the exact same structure type. However, in the following example, part1 and part2 are not the exact same, and cannot be used with the = operator:

struct {
  int ident;
  char name[LEN + 1];
  int val;
} part1;

struct {
  int ident;
  char name[LEN + 1];
  int val;
} part2;

Since you can use the assignment operator with structures it is a slight surprise that arrays within structures will be copied from one to another. This can be useful for creating "dummy" structures that are used just for the purpose of copying one array to another.


So far I've shown two examples of declaring structures without using a structure tag. Once you've created a tag for a structure, you can treat a structure as a data type, like so:

struct pc_Hardware{
  int ident;
  char name[LEN + 1];
  int val;
};

struct pc_Hardware part1 =  {.ident = 1, .name = "Mobo", .val = 200};

It is also possible for a function to use a structure as an argument. However, using a structure as an argument can cause a lot of overhead. It's actually usually better to pass a pointer to a structure to a function, and then use the pointer to modify the members as needed. Functions can also return structures. Similarly, you might have a function return a pointer to a structure instead of an actual structure.

A structure can also be nested within another structure, as a data member. This is useful to create "categories" of members within a structure. Suppose you have a structure that holds data about computer hardware, and there are a total of four different brands of hardware. You could have each member of the structure represent a type of hardware, and within each structure you could hold information about the hardware brand.


Unions


A union is similar to a structure in all ways, except in that the compiler will allocate enough space for only the largest of all the union members. This means that all members of a union will all share the same space in memory. Altering one member of a union will overwrite the data of all others. This means that only one member of a union can hold data at any given time. Unions are usually used as a means of saving space. In my last computer hardware example, a union could have been used in place of a structure for holding the names of the brand, as the hardware usually wouldn't be made by two different companies at once (as long as the brand name doesn't go over the LEN limit, which is just a constant that can be defined as any amount you want to specify).


Arrays of unions can also be useful. Suppose you need an array that can hold either integers or floats. You can't simply create an array that can hold either, since an array must be universally one type. You can however create an array of unions rather easily. Consider this example:

union {
  int i;
  float f;
} Number;

Number a[100];

Now the array a can hold in each element either a float or integer type. Here is how one could assign either a float or integer into the array:

a[0].i = 1;
a[1].f = 10.01;

The biggest problem with using unions is that there is no way to tell which data member was last altered, and thus knowing which member actually holds a value. Often times programmers will nest a union within a structure, having the structure have one other data member. This other member within the structure will act as a "tag field" so that the programmer can keep track of which member holds a value.


Enumerations


Enumerations are good for creating new definitions of data types that have only a few different possible values. An enumeration would be good for creating a boolean variable, or perhaps a variable to represent suit in a deck of cards. The benefits of using an enumeration over preprocessor directives for defining such things is that anyone reading your code can easily see all the possible variants of your variable, and see that each one is of the same type. Enumerations can increase readability and code cleanliness.

enum suit { CLUBS, SPADES, DIAMONDS, HEARTS };

The above example shows how set up an enumeration for the different suits of a deck. This is much better than using #define directives, in that it obeys C's scope rules; an enumeration declared within a function won't affect the rest of the program. The members of this enumeration can be used just the same as #define directives.


The members of an enumeration are actually integers. CLUBS is equivalent to the integer 0, and HEARTS 3. One could use the suits defined in the above enumeration just as if SPADES were the integer 1, and so on. You can also specify exactly the integer amount that a member will equal, like so:

enum suit { CLUBS, SPADES = 7, DIAMONDS, HEARTS = 20 } s;

s = CLUBS;
s++;

CLUBS would default to 0, although DIAMONDS would default to 8, which is one more than the previous member. s was assigned the value of CLUBS (zero), then in the next line was incremented to 1.


Enumerations are perfect creating "tag fields" for unions to determine which of the members of a union were last modified. Here is an example:

struct {
  enum { INT, FLOAT } kind;
  union {
    int i;
    float f;
  } u;
} Number;

The above struct can be used in our original union example where an array of unions was created. This structure has advantages in that the programmer will be able to tell whether or not each array element holds an integer or float with the "tag field" kind.


Sources:  C Programming: A Modern Approach 2nd Ed. (particularly chapter 16)

Pointers: Basics

A pointer in C is a data type that holds the address to a specific block of memory within your computer's memory. The address in the pointer can be used to modify the contents thereof, or to cycle through other addresses in memory adjacent to such. It is also possible to use pointer arithmetic (addition and subtraction), though you cannot multiply or divide pointers. Take a look at the following diagram:

P is a pointer that has been declared and initialized with the value of the address 1884. P points to the block in memory next to the blocks with addresses of 1883 and 1885. C requires that every pointer point to only a specific type. There are no restrictions on what type of referenced data a pointer may reference to; pointers can even point to pointers.

int *p;
double *q;
char *r;


The above shows three ways of declaring a pointer as three different types of data. The only difference between declaring a pointer and a variable, is that a pointer's identifier must be preceded by the asterisk symbol.


Address and Dereference Operators


There are two different operators that are very commonly used with pointers. The first, which you've seen in the form of multiplication and when declaring a pointer, is the asterisk *, which is called the dereference operator (or also known as the indirection operator). You can translate the * literally into "the value pointed by". So, if we take P from our example above, and type *P, then *P means "the value pointed by" P. *P would equal whatever value is within the block of memory 1884. Actually, *P would be another alias for the value within the address 1884. This is because by modifying *P we actually directly modify the value within the address 1884. Suppose *P is an int value:

*p = 76;


This line of code would change the value within the address 1884 into the integer 76.


The second operator is the Address operator &. & can be translated literally into "the address of". This operator is particularly useful for assigning a value to a pointer, like so:

int val = 7;
int *p;
p = &val;

//You could also do:

int *p = &val;


Usually you wouldn't know exactly what the address of val is before assigning it to a pointer, as it could be anywhere within memory while your program is running. What is important, is that you can assign the address to a pointer.

Uses of Pointers

Imagine you need a function that modifies a variable. You cannot simply pass the variable to the function, since you can only pass the value of your variable to the function. This is due to the fact that the data within functions is private. You could however, pass a pointer to the function, and then use the dereference operator to directly modify the value pointed by the address. Consider the following:

#include <stdio.h>

int clear(int *x)
{
  *x = 0;
}

int main(void)
{
  int a = 5;

  clear(a);

  printf("%d", a);

  return 0;
}

You can also have a function return a pointer, like the following:

#include <stdio.h>

int *max( int *a, int *b)
{
  if (*a > *b)
    return a;
  else
    return b;
}

This function, when given pointers to two integers, will return a pointer to whichever integer is larger.


Pointers and arrays are used together all the time. Say we initialize pointer P and make it point to the first element of a[4]:

int a[4], *p;

p = &a[0];

Here is what we have just done graphically:

P now points to the first element of array a[]. Suppose we do the following:

*p = 7;

a[0] now equals 7. Here is what we have just done graphically:

So far this whole process doesn't seem too useful, but, where things start getting really useful is when you use pointer arithmetic to cycle through each element of the array using a pointer. C allows the following combinations of pointer arithmetic, and only these combination:

Adding an integer to a pointer

Subtracting an integer from a pointer

Subtracting one pointer from another pointer

Adding integer i to pointer P will cause P to point i elements ahead from where P originally pointed to. Similarly, if P points to a[x], then P + i points to a[x + i] (assuming a[x + i] even exists).

If P points to element a[x], then P - i points to a[x - i].

When one pointer is subtracted from another, the result is the distance in array elements from the two pointers.

It is also valid to compare pointers with the comparisons ==, !=, <=, and >=. However, in order for these comparisons to actually have meaning the two pointers being compared would need to point within the same array.

Pointers are also good for processing arrays, since you can apply addition and subtraction upon pointers. Though one could just as easily use array subscripting for such a task, pointers can be faster and less resource intensive (depending on the compiler; some compilers have no efficiency discrepancy between array subscripting and array processing via pointers).

#define VAL 10

int a[VAL], *p;

sum = 0;
for (p = &a[0]; p < &a[VAL]; p++)
  sum += *p;

The above code fragment shows how to sum all elements of an array with p. Note that this loop will not fire once p equals a[VAL], due to the properties of a for loop, thus the address a[VAL] won't actually be analyzed and the program will not produce an error during compilation.


A very important thing to note, is that the name of an array can be used as a pointer to the first element of an array.

int a[5];

*a = 7; //stores 7 in a[0]

*(a + 1) = 12; //stores 12 in a[1]

In general, a + i is the same as &a[i]. Also, *(a + i) is equivalent to a[i]. Also, the fact that an array name can serve as a pointer makes it easier to process them with for loops.

for (p = &a[0]; p < &a[VAL]; p++)
  sum += *p;

//this is the same as the following:

for (p =a; p < a + VAL; p++)
  sum += *p;

When passing an array to a function, the compiler passes a pointer to the first element in the array to the function. This is important to know.


Using all that I've explained so far, you can write loops to process both rows or columns of 2D arrays using pointers, like so (processing a row):

//loop that clears a row of a 2D array

int a[rows][cols], *p, row;

row = x; //x is an integer that represents our selected row 

for (p = a[row]; p < a[i] + cols; p++)
  *p = 0;

Processing a column isn't as simple, since a 2D array has the first array be an array of arrays, meaning it's an array of rows.

//loop that clears a column of a 2D array

int a[rows][cols], (*p)[cols], col;

col = x; //x is an integer that represents our selected column

for (p = a; p < a[rows]; p++)
  (*p)[col] = 0;

I have declared p to be a pointer to an array of integers, which will be used as a row in the loop. The parentheses are necessary to be around the *p, otherwise p would be an array of pointers rather than a pointer to an array. In the expression p = a, a is equal to the address of a[0]. We know this from recalling the earlier quote:

In general, a + i is the same as &a[i]. Also, *(a + i) is equivalent to a[i].

Sources for this post:
* C Programming: A Modern Approach 2nd Ed. (particularly chapter 12)

2D Array Practice

In the book C Programming a Moder Approach Second Edition there is a programming project at the end of chapter 8 that asks you to write a program that creates a randomized walk across a 10x10 field, where each step is shown as a letter from the alphabet, and each blank space is shown as a period. The end result should look something like this:

a . . . . . . . . .
b c . . . . . . . .
e d . . . p q r . .
f . . . . o . s . .
g h i j . n u t . .
. . . k l m v . . .
. . . . . . w . . .
. . . . z y x . . .
. . . . . . . . . .
. . . . . . . . . .


In order to do this, you initialize a 2D array, fill it with periods, randomly choose a number between 0-3 to represent a direction to move, detect if the move was a valid move (and re-randomize the move if it wasn't), then make the move chosen. Each time a move is chosen, use a new letter from the alphabet.


Overall, this was extremely simple. If I were writing this program without such specific rules as the programming book gave me, I would have made the array 12x12 instead of 10x10. This would allow me to line the edges with a value other than ".", and I could use that value on the edges to detect collision. This is a lot simpler than detecting if it is the edge of the array, since I can't simply use if board[y][x + 1] != '.', as a period can't exist out of the edge of the arrays.


I'll post the source code the most interesting part of the program:

for (column = 0; column < 10; column++)
{
  for (row = 0; row < 10; row++)
  {
    printf("%c ", board[column][row]);
  }
  printf("\n");
}

This cycles through the first row, and prints out all the contents. It does this by adding one to column during each iteration, and printing out a piece of the board using the token column as a coordinate. The same thing happens with the row token as well. Then, the next row, and the next row. Just before these two for loops I modify the current field and place a letter in wherever the current coordinates are, so that these two loops print out the move that just occurred as a letter.


Overall I didn't learn anything new, but I still needed to write this program in order to get used to the syntax of C. Here is the source and .exe for the full program.


PRNGs (Pseudo-Random Number Generator)

Computers cannot truly generate random numbers, as computers are simply mechanisms that react to actions that are enacted upon them. In order to compensate for this, to generate a random number computers use a PRNG (pseudo random number generator). PRNGs can generate seemingly random numbers rather effectively.

One way to generate a random number in C is to use the rand() function, which is lies within the standard library of C. Here is an example:

#include <stdio.h> /* included for printf */
#include <stdlib.h> /* included for rand */

int main(void)
{
  int i;

  for (i = 0; i < 10; i++)
    printf("%i\n", rand());

  return 0;
}

Depending on your compiler, the output of this program will output ten numbers. However, this program will always output the same ten numbers in the same order. I've learned that the GCC compiler will have the rand() function return a value with an upper bound of 2,147,483,647 (2³²-1), compared to upper bounds of 32,767 (2¹⁶-1) from most other compilers.


In order to have this program output different numbers each time it is run, you need to do what is called seeding the PRNG. Seeding will affect the sequence in which the rand() function begins outputting numbers. In order to seed the rand() function, you use srand(). Here is an example:

#include <stdio.h> /* included for printf */
#include <stdlib.h> /* included for rand */

int main(void)
{
  int i;

  srand(1)
  for (i = 0; i < 10; i++)
    printf("%i\n", rand());

  return 0;
}

This seeded the PRNG with the integer 1, and will now output ten different numbers than the last program. Although, this still doesn't solve our problem; how do we randomly seed the PRNG? In order to do so, you can use the time() function. The time() function will return the number of seconds elapsed since Jan 1st 1970. This is the method of randomly seeding that DigiPen has shown their Freshman incoming students. Example:

#include <stdio.h> /* included for printf */
#include <stdlib.h> /* included for rand */

int main(void)
{
  int i;

  srand(time(0));
  for (i = 0; i < 10; i++)
    printf("%i\n", rand());

  return 0;
}

Now this program will produce a different set of numbers every time it is run. Although, what if you wanted to produce a random number within a specific range? You could use the modulo operator, like so:

#include <stdio.h> /* included for printf */
#include <stdlib.h> /* included for rand */

int main(void)
{
  int i;

  srand(time(0));
  for (i = 0; i < 10; i++)
    printf("%i\n", rand() % 10 + 1); //Random int from 1-10

  return 0;
}

Although I've been told this is error-prone and tedious, and it is much preferred to create your own wrapper function around rand().

int randomInt(int low, int high)
{
  return (rand() % (high - low + 1) + low);
}

Linear Algebra: Rotation Matrices

A day or so ago I looked up the topic of using rotation matrices to modify the angle of a vector by an arbitrary amount. I visited none other than the WikiPedia page for rotation matrices.


The idea behind rotation matrices is to solve for the x and y coordinates after the rotation by using two separate equations. Here is a rotation matrix for 2 dimensions:

That matrix will rotate the 2D plane counterclockwise by angle θ. Using this knowledge, the new x and y coordinates for a point on a rotated vector would be solved for using these two equations:

Very simple! So here is an example problem: Say you have vector AB. AB = (2, 3).

To solve for a rotated counterclockwise version of this vector you input your desired angle of rotation in for θ, 2 for x and 3 for y. This rotation matrix rotates a 2D plane clockwise:

Rotation in 3 dimensions is basically the same process. All that is different is the z coordinate and modified rotation matrices. You simply solve for each individual coordinate with the rotation matrices for the z, x, and y axis. These three rotation matrices and more are found at the WikiPedia page for rotation matrices.

Mini RPG

Today I worked on my Mini RPG. I added about 75 lines of code. I added a monster class, almost finished the battle function, modified and updated the main loop, and made some minor changes to the character class to allow for holding weapons and having hit points. I am really loving object orientation for this little program; things are super organized and simplified. I can't imagine creating this program without using any classes D:


I haven't had time to actually test the source file for bugs and errors, but I believe it is working.


Here is a link to my source: http://www.mediafire.com/download.php?mgmzmwnnwdg

Linear Algebra: Basics

Today with my math teacher I went over some of the basics of linear algebra. The two topics I went over included solving for the intersection of two lines in 3D space, and finding the angle between two vectors. The rest of the mathematical topics I'll try to cover in the near future include: finding a vector orthogonal to two other vectors in 3D space; finding the time T during the intersection of ray between a circle of sphere; using a matrix to rotate a vector by an arbitrary angle. I found these topics, as well as an entire survival guide for DigiPen students, at this site here. Hopefully by explaining the math I went over today I can solidify my own understanding.

First off: solving for the intersection of two lines in 3D space. I know how to do this in matrix form, as it is easiest and simplest in matrix form. Here is a matrix of the x y and z coordinates for a point in 3D space: [x, y, z]. An equation for a vector in 3D space consists of a point on a line, and the direction vector of a line multiplied by a magnitude. This magnitude represents the length of the line, whereas the timestep, or t, represents a constant.

Here is an equation for a line in 3D space: L1 = [2, 4, -1] + t[-1, 2, 3]. I just chose these numbers at random because they really don't matter. The first matrix is a point on the line. The second matrix is the rise, run, and the z equivalent to rise or run (just like two dimensional lines). You need a point on the line, otherwise the direction vector (rise//run//zrun) could sit anywhere in space. Without the direction vector for your line, you line could be facing in any direction as long as it sits on your point. The t is the magnitude of the direction vector, and these could be used as something to define the distance something traveled over time of t. t is just a constant.

In order to solve for the intersection of two lines, I'll quickly show the process with some variables. Here are the two lines: L1 = [a, b, c] + t[d, e, f]; L2 = [g, h, i] + r[j, k, l]. Now since these two equations each represent a line, the point of intersection is going to be a point that can be used to satisfy either of the equations. You just set both of the equations equal to each other, one variable at a time (x, y and z) and solve for each one. To solve for the x coordinate of the intersection you would use a + td = g + rj. You do this for variable a through c corresponding to d through f. Then using substitution, if need be, you can solve for t and then solve for the rest of the variables, thus getting a final matrix of [x, y, z].

The second thing I learned today was finding the angle between two vectors. Luckily, you only need the direction vectors of the line equations. This makes sense because no matter where the lines are in space, they will have the same angle of intersection as long as the direction of the lines face in stays constant. To do this, you use the equation of:

Theta, the zero thingy on the left, is the angle you are solving for. a and b both represent matrices that represent direction vectors, like the direction vectors in the line equations earlier in this post. Arccos is cos^-1. The a and b on the top half of the right side of the equation is pronounced as a dot b. The dot is the operator for the dot product. The dot product is used to find the scalar projection of a onto b, and vise versa. I honestly don't fully understand what exactly the dot product does yet (read last paragraph, I understand it now), but for now I just need it for equations like this one, and it returns a scalar value. To use the dot product on two 1x3 matrices, you would do this: [a, b, c] dot [d, e, f] = ((a x d) + (b x e) + (c x f). The |a| represents the magnitude of a, which is the length of a. If the direction vector of a line is representing velocity vectors, then the magnitude of a would be the speed of the direction vector. To find the magnitude of a 1x3 matrix you do this: |M| = |[a, b, c]| = sqrt(a^(2) + b^(2) + c^(2)). Does that look familiar? It should; it's basically the Pythagorean Theorem in 3D. It takes the rise, run, and zrun and converts the three into a length value, just like the Pythagorean Theorem does with two lines, except this is with three.


Now once you find a dot b, and magnitude of a times magnitude of b, you then divide a dot by magnitude of a times magnitude of b, then arccos that value which results in your angle!


Dot product explained: Okay! I so I did a bit of research and asked a couple people some questions and now I understand what the value returned by the dot product does. It projects a vector onto another vector and returns the length. A dot B also equals B dot A, which makes sense because multiplication itself is commutative, and the formula for the dot product is just multiplication of three values. Here is a picture to help visualize this:

The blue line would be the dot product of A and B. This is very useful for collision in programming, and transforming vectors from one grid space to another. Here is a good example of using the dot product for 2D collision detection of convex polygons:

The red and blue are both one dimensional projections of the objects onto a line. The dotted line is perpendicular one side length of one of the objects. In the diagram is looks like it is perpendicular to both, which is fine, but it is important to understand that the dotted line is normal to one of the sides of one of the polygons. Once you find a dotted line that is perpendicular to a side of one of the shapes, you use the dot product on a two dimensional matrix and project both of the shapes onto the normal to the dotted line. You can then compare the two projections to see if they overlap. If the two projections overlap, you then try the entire process over for a different side of one of the polygons. Once you try this algorithm over each of the sides of each object and no collision vector was detected (a collision vector would be the length of overlap formed by overlapping projections) in at least one of the iterations, then the two objects are not colliding with one another.


Sources:
http://www.mvps.org/directx/articles/math/dot/index.htm
http://en.wikipedia.org/wiki/Dot_product
http://www.gamedev.net/reference/programming/features/verletPhys/page2.asp

Game Design: Positive and Negative Feedback; Flow Control

 As I've said a few times in the past, I have been reading Rules of Play: Game Design Fundamentals. Lately I have also been applying what I've learned into judging StarCraft mapping contests, like this one, and weaving them into my own map like this one. I've decided to take some of the knowledge and tools I've gained and write a post here about them. First, I want to talk about positive and negative feedback back loops in two different contexts.


The first context I want to talk about them in, is in the study of cybernetics.

Cybernetics deals with the ways a system gauges its effect and makes necessary adjustments. The simplest cybernetic device consists of a sensor, a comparator, and an activator. The sensor provides feedback to the comparator, which determines whether the machine is deviating from its established norm. The comparator then provides guidance to the activator, which produces an output that affects the environment in some way. This fundamental process of output-feedback-adjust-ment is the basis of cybernetics.—Stephen Littlejohn, Theories of Human Communication

 As this quote explains, cybernetics is a study of how a system reacts and makes adjustments to the current state of the system. This should sound rather relevant to video games. This type of automated reaction is used all the time; have you ever played a game that automatically tiers to the user's level of skill? There are two primary types of adjustments that are made upon a system, these two are positive and negative feedback reactions, usually used within a loop.

For example, take a room with a thermostat and a heater. When this room's sensor, the thermostat, reads a certain temperature it can trigger the heater to react. This system can be rigged to perform a negative feedback reaction in which the heater heats the room when the temperature is less than or equal to a certain amount. Assuming the room naturally cools, the room's temperate will oscillate between a few degrees and stay that way, all the while the room's specific state is constantly changing. A positive feedback loop would be if the heater turns on when the temperate is equal to or greater than a specific temperature. In a positive feedback loop, the temperature of the room will spiral up and up once it hits a certain activation point. Both positive and negative feedback loops are essential tools to be used in game design.

Too often I see games designed in StarCraft maps that are too hard or too easy, or too hard or too easy once the player reaches a certain point. I also see games made in which the leader has no way of letting the other players catch up to him, because he has such a great advantage over the other players. I also see the losers in a game have no means of catching up to the leaders. What's the point of continuing play if the outcome of the match has already been determined in the middle of the game because the leading player has a tremendous advantage over the rest of the players? These types of design flaws can be controlled with positive and negative feedback loops. Usually positive feedback loops are harmful to a game's flow (flow will be explained more in depth soon), and should be switched out for negative feedback loops. If a leading player seems to be constantly destroying all the other players in an unfair way, create a negative feedback response in which the system (the game) reacts and hinders the leading player. Similarly, you can give advantages to the players in last place to encourage and help them catch up to the leaders.

A great example of a negative feedback response is in the game Super Mario Cart. In Super Mario Cart there are weapons you gain from running into question marked boxes with your cart. Once you hit one you obtain a random weapon. You have a much greater chance to obtain a powerful weapon when you are near last place in the race, and you have a much greater chance to obtain a weak weapon when you are in first place. This sort of automated reaction the system generates creates a much more compelling form of gameplay, in which all the racers are usually closely pitted against each other neck to neck until the very end of the race. This generates an exciting play in which the outcome of the overall match remains uncertain till the very end.

The second meaning of positive and negative feedback would be rewards and punshiments to a player. Simply put, rewards are great to use to encourage players to make certain choices, and punishments are used to deter certain behavior. There is also a third category known as negative feedback. Negative feedback is not necessarily a punishment, but is used to deter a player from making specific choices. For example say you do not want your game to be focused on fighting, although you want to have an occasional enemy in your game. It turns out that too many players are focusing on finding and fighting enemies rather than experiencing your game how you designed it to be experienced. You do not want to punish the player as to deter them from playing at all, so what you could do instead is implement a clever negative feedback mechanism. You might be thinking that you could just make enemies stronger and therefore make the player want to avoid them -this might just make finding and killing enemies an interesting challenge for the player. Instead you could give the player absolutely no reward for killing the enemy (no points or anything), you could also make enemy encounters not worth the risk (as in making the player restart the level if an enemy kills them, or have enemies be "thieves" where if they hit you you lose items). If your goal is to make enemies something the player wants to avoid, give the player a reason to avoid them. If you find that fighting these enemies is truly fun for the players, you could also switch your game to a fighting one; it's your design, you decide.

Flow; flow would be the fine balance between difficulty in a game and the player's skills. Skills do not just include physical coordination; skills also include knowledge of the game's workings, knowledge of the other player's skill level, physical coordination, intelligence level, and response time. There are more than likely many many more forms of skill which I did not mention, but these should give a general idea. The difficulty of the game is pretty self-explanatory. The flow channel of a game is a narrow isle where the difficulty of the game is perfectly balanced and matched to the skill level of the player. Here is a diagram of the flow channel graphed with challenge over skill level:

 As you can see, it can be hard to create a flow in gameplay for all different types of players. One way that game designers achieve balanced flow is to apply positive and/or negative feedback loops to a game's processes.


Here is an interesting excerpt from the book Rules of Play that talks about the design process for a game made by two designers:

In a wonderful essay published on Gamasutra.com, Jesse Schell and Joe Shochet of Disney Imagineering write about the process of designing Pirates of the Caribbean-Battle for the Buccaneer Gold, a game "ride" where a group of players stands on a motion-platform pirate ship surrounded by video projections. During the game, one player steers the ship while the other players operate a number of cannons, firing at monsters, forts, and enemy vessels. Pirates of the Caribbean is designed as a condensed five-minute experience, and it was essential that players feel properly challenged at every moment of the game.

In their design analysis, Schell and Shochet detail a number of design problems that had to be overcome in order to maximize player enjoyment. For example, during playtesting they identified as a problem the fact that the player steering the ship could take the ship to what they call "dull places," leading to a less engaging experience for all of the players. In the selected quotes below, Schell and Shochet outline some solutions to this problem:

Architectural Weenies: "Weenie" is a phrase coined by Walt Disney himself. It refers to the technique used on movie sets of guiding stage dogs by holding up part of a sausage… In the case of Pirates, [there are] three main "weenies," one for each island: a volcano, an enormous fort, and a plume of smoke coming from a burning town. No matter which way the boat is facing, at least one of these "weenies" is in view. Since the coolest action takes place at the islands, [we wanted] to guide the captains to go there.

Guide Ships: Since the short-term goal of the game is to fire on other pirate ships, captains strive to get near these ships so that their gunners can get a clear shot. Many of the ships in the Pirates world are "on their way" to the islands mentioned above. Many captains, in just trying to stay near these ships find that just as they have destroyed the ship, they have arrived at one of the islands, without even trying to get there.

Sneak attacks: What if the captain ignores the guide ships? Even if he heads toward one of the "weenies" it might mean as long as a minute during which the gunners have little to shoot at. For this reason, [we] created special "sneak attack" ships that "magically" appear behind the players' ship, and quickly pull up alongside, when no other boats are in range.

The Waterspout: This was [a] nickname for [a] "last ditch" forcefield that surrounds the game play area.If a captain tries to sail out of the main game play area and out to open sea, they hit the forcefield, and the ship is "magically" pointed back to where the action is. The few guests who see this don't even realize that anything unusual has happened. They are just pleased to have their boat going somewhere cool.

Schell and Shochet are thinking in very experiential terms, using clever techniques to subtly guide player action in meaningful directions. At the time of its release, Pirates was a very high-tech production, featuring real-time 3D graphics, physically engaging cannon-firing interfaces, and a large motion platform to simulate a pirate ship rocking on the waves. Often in these instances, a desire to "properly" simulate a coherent 3D space or "correctly" output logical behavior for computer-controlled characters overshadows the design of the actual play experience. But Schell and Shochet had no hesitation in making pirate ships "magically" appear to guide the player, or abandoning "realistic" physics to have the player's ship turn on a dime to facilitate navigation. As they put it,"By choosing to be less concerned with reality and more concerned with what was fun, we created an experience that…is easier to adapt to, quicker to learn, and is a better show." In game design, player experience should always trump so-called "realism."

Boredom and anxiety, as game design watchwords, are wonderful because they speak directly to player experience. As you shape and sculpt your players' pleasure, you are guiding them between the Scylla and Charybdis of anxiety and boredom.This task is made all the more difficult because, as we know, the experience of play can only be indirectly designed. How do you create a set of rules that maximizes the play of pleasure for your audience?

The designers of this game implement two negative feedback loops. Did you see them? Onewould be the sneak attack ships. These ships react to the players being all alone at seas, and then appear out of nowhere to create an exciting experience. The other would be the water spout; the water spout reacts to the players entering the boundaries of the map, then spins them in the correct direction, thus keeping the game in a specific state. The guideships and weenies would be more a form of positive feedback in which encourage the player to make specific decisions. The guideships encourage the players to travel to the key focul points of the game while the weenies create enticing visual scenes that players are likely to travel to. Both of these provide the players with a reward and a reason to take specific actions.