Last modified on 1 March 2014, at 05:57

Aros/Developer/Games Programming/Basics

Navbar for the Aros wikibook
Aros User Docs
Aros User Docs
Aros User FAQs
Aros User Applications
Aros User DOS Shell
Aros/User/AmigaLegacy
Aros Dev Docs
Aros Developer Docs
Porting Software from AmigaOS/SDL
For Zune Beginners
Zune .MUI Classes
For SDL Beginners
Aros Developer BuildSystem
Specific platforms
68k Support
PPC Power Architecture Support
Arm Raspberry Pi Support
Android support
Linux and FreeBSD Support
Windows Mingw and MacOSX Support
Aros x86 Installing
Aros x86 Audio/Video Support
Aros x86 Network Support
Aros x86 Complete System HCL
Aros Storage Support IDE SATA etc
Aros Poseidon USB Support
x86-64 Support
misc
Aros Public License


IntroductionEdit

  1. learn to think like a programmer
  2. learn C
  3. learn how the AROS (Amiga) works


The first basically is about algorithm designs and things to avoid. Do you know what spaghetti code means? Structured programming? How about OO design? Big "O" notation? Recursion? Quick Sort? These are important concepts regardless of what language you use or platform you're on.



Simpler Language IntroductionsEdit



C and companyEdit

Learning C isn't that hard, learning how to use it properly can be. The syntax for C although terse, is very simple. You could describe the entire C language on a couple of sheets of paper, there's little too it. However, like my prof always told me, C gives you enough rope to hang yourself (and everyone around you actually). Basically, C trusts that you know what you are doing and if you tell it to trash memory it will happily do it for you. C will not hold your hand like Basic, but it gives you more power and flexibility then just about any other language. Anyways, my best advice to anyone who's new with C is to study your pointers. And when you think you understand pointers, study them some more. That's the one part of C that gives people major headaches.

Read more at C or C++

c value
&c address of c 
*c pointed to by c 
.c should contains functions 
.h usually contain #define #include typedef enum struct extern 


C++ 
BASIC
types and variables
conditionals and loops
i/o
structures

MEDIUM
class
constructor
destructor
methods
instance variables

the underlying semantics of C++ ( e.g. when to use virtual, what a copy constructor does ) Even without data-hiding inheritance, references, polymorphism you have a powerful structure. Very handy features, such as function name overloading (used with care and sparingly), declarations as statements, references to name but a few... Data and methods put together called a class. OO language is classes & objects. OO means objects that have data and methods. Methods are sent from object to object and the object manipulates it's data. It has its share of problems too: the syntax is complex (although not unbearably so), it has no garbage collection and still has you managing memory by yourself, and quite a number of others, which may not directly affect a programmer working on his own, but will when working in a team.

Tetris, , etc



AlgorithmsEdit

Algorithms with youtube videos but start with small WB games first. 

Read more here


Algorithm theory involves thinking about the growth rates (Space and Time) and providing a breakdown of the issue into pseudo code and big O notation which taught what items to think about when choosing and optimizing algorithms



QuicksortEdit

# A is the array, p is the start position and r the end position 
# i is the pivot value, p the start position value and r the end position value 
#
# Randomised-Partition(A,p,r)
# i <- Random(p,r)
# exchange A(r) with A(i)
# return Partition(A,p,r)
#
# Randomised-QuickSort(A,p,r)
# if p< r then
#     q <- Randomised-Partition(A,p,r)
#     Randomised-QuickSort(A,p,q)
#     Randomised-QuickSort(A,q+1,r)
#
#
void quickSort(int numbers[], int array_size)
{
  q_sort(numbers, 0, array_size - 1);
}
 
# choose (random?) pivot number and partition numbers into lower and greater around pivot 
void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;
 
  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}

Youtube video here and


Merge SortEdit

void mergeSort(int numbers[], int temp[], int array_size)
{
  m_sort(numbers, temp, 0, array_size - 1);
}
 
 
void m_sort(int numbers[], int temp[], int left, int right)
{
  int mid;
 
  if (right > left)
  {
    mid = (right + left) / 2;
    m_sort(numbers, temp, left, mid);
    m_sort(numbers, temp, mid+1, right);
 
    merge(numbers, temp, left, mid+1, right);
  }
}
 
void merge(int numbers[], int temp[], int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;
 
  left_end = mid - 1;
  tmp_pos = left;
  num_elements = right - left + 1;
 
  while ((left <= left_end) && (mid <= right))
  {
    if (numbers[left] <= numbers[mid])
    {
      temp[tmp_pos] = numbers[left];
      tmp_pos = tmp_pos + 1;
      left = left +1;
    }
    else
    {
      temp[tmp_pos] = numbers[mid];
      tmp_pos = tmp_pos + 1;
      mid = mid + 1;
    }
  }
 
  while (left <= left_end)
  {
    temp[tmp_pos] = numbers[left];
    left = left + 1;
    tmp_pos = tmp_pos + 1;
  }
  while (mid <= right)
  {
    temp[tmp_pos] = numbers[mid];
    mid = mid + 1;
    tmp_pos = tmp_pos + 1;
  }
 
  for (i=0; i <= num_elements; i++)
  {
    numbers[right] = temp[right];
    right = right - 1;
  }
}

Youtube video here



AROS (Amiga)Edit

Of course you need to learn programming on the Amiga. Lucky for you, the Amiga is a fun computer to program with a relatively small API. That is to say, you won't be swamped with OS calls, however, there are some ugly parts out there. If you want to just open a window and create some buttons, that's easy. Wanna write a web browser? That is gonna be hard and that is mostly because the OS doesn't provide a lot of the things you would need so you will end up writing it yourself. :-)



2DEdit

  • 2D engines which take out the hard work of writing your own routines (ike SDL)
  • Make at least one type of game from each of the following board/grid, maze, card, etc for the experience

SDL youtube video




RotationsEdit

/* assuming width and height are integers with the image's dimensions */
 
for(int x = 0; x < width; x++) {
    int hwidth = width / 2;
    int hheight = height / 2;
 
    double sinma = sin(-angle);
    double cosma = cos(-angle);
 
    for(int y = 0; y < height; y++) {
 
        int xt = x - hwidth;
        int yt = y - hheight;
 
        int xs = (int)round((cosma * xt - sinma * yt) + hwidth);
        int ys = (int)round((sinma * xt + cosma * yt) + hheight);
 
        if(xs >= 0 && xs < width && ys >= 0 && ys < height) {
             /* set target pixel (x,y) to color at (xs,ys) */
             } else {
             /* set target pixel (x,y) to some default background */
             }
        }
}




UsesEdit

2.5D Calculating Distance/DepthEdit

A perspective transform (perspective projection == divide by Z) amounts to

x = x*d/z+d
y = y*d/z+d

where d is the distance from the viewpoint and x, y, z are (obviously ) your x, y, z coordinates in 3d space If there is no "divide by Z", the depth-wise movement will feel wrong and it will feel like your object is accelerating/braking at the wrong times.


3d Projection

y_screen = (y_world / z) + (screen_height >> 1)

or:

z = y_world / (y_screen - (screen_height >> 1))

This formula takes the x or y world coordinates of an object, the z of the object, and returns the x or y pixel location. Or, alternately, given the world and screen coordinates, returns the z location.


Fast Linear Interpolation

o(x) = y1 + ((d * (y2-y1)) >> 16)

This assumes that all the numbers are in 16.16 fixed point. y1 and y2 are the two values to interpolate between, and d is the 16-bit fractional distance between the two points. For example, if d=$7fff, that would be halfway between the two values. This is useful for finding where between two segments a value is.

Fixed Point Arithmetic Floating point is very expensive for old systems which did not have specialized math hardware. Instead, a system called fixed point was used. This reserved a certain number of bits for the fractional part of the number. For a test case, say you only reserve one bit for the fractional amount, leaving seven bits for the whole number amounts. That fraction bit would represent one half (because a half plus a half equals a whole). To obtain the whole number value stored in that byte, the number is shifted right once. This can be expanded to use any number of bits for the fractional and whole portions of the number.

Fixed point multiplication is trickier than addition. In this operation, you would multiply the two numbers and then shift right by however many bits are reserved for fractions. Due to overflow, sometimes you may need to shift before multiplication instead of after. See "Fast Linear Interpolation" for an example of fixed point multiplcation.

Point Rotation

x' = x*cos(a) - y*sin(a) 
y' = x*sin(a) + y*cos(a) 

Mentioned briefly in the tutorial as being an expensive operation, here is the basic point rotation formula. As you can see, it's at least 2 table lookups, 4 multiplications, and two additions, but the sine and cosine values can be reused for each point. Rotating for the purpose of hills would mean rotating the Z and Y coordinates, not the X and Y coordinates. To find the derivation of this formula, look up Rotation of Axes.

Avoid Division Instead of dividing by the z of an object in the standard projection formulas, you can take advantage of some properties of the road to speed up calculations. Say you have a 3d segment z position and a y position, and you want to find which line of the screen it belongs on. First, read through the z-map until you get to the 3d segment's z position. Then, multiply the height of the segment by the corresponding scaling value. The result is the number of pixels above the road that the segment belongs.

Use Z as Scaling Value Scaling routines work by slowing or speeding up the speed at which a draw routine reads through graphics data. For example, if you were to set the read speed to half, this would draw a sprite double the size. This is because for each time a pixel is drawn, the read position in the sprite data is only incremented by half, causing the read position to only increment by a whole number every two pixels.

Usually, a scaling routine has parameters like x, y, and scaling factor. But since a scaling factor is just 1/z, we can just reuse the Z value of that sprite! We will still need the scaling factor though to determine the boundaries of the sprite so that we can keep it centered as it scales.

Read more about 2.5D here



Maze GenerationEdit

Binary Tree (simple but has limitations) Sidewinder (better Binary tree) Depth First Search (DFS) (good simple mazes - traces route and backtracks to fill in missing) Growing Tree

Recursive Subdivision (wall adding - fractal like)

Aldous-Broeder (inefficient uniform spanning tree based) Wilson's (better spanning tree) Prim's (another spanning tree) Kruskal's (good but complex tree spanning)



Solving Algorithms

Dead-end retrace



a perfect maze, there is one and only one path from any point in the maze to any other point. That is, there are no inaccessible sections, no circular paths, and no open regions. A perfect maze can be generated easily with a computer using a depth first search algorithm.

A two dimensional maze can be represented as a rectangular array of square cells. Each cell has four walls. The state of each wall (north, south, east, and west) of each cell is maintained in a data structure consisting of an array of records. Each record stores a bit value that represents the state of each wall in a cell. To create a path between adjacent cells, the exit wall from the current cell and the entry wall to the next cell are removed. For example, if the next cell is to the right (east) of the current cell, remove the right (east) wall of the current cell and the left (west) wall of the next cell.


Depth-First Search - simplest maze generation algorithm

  1. Start at a random cell in the grid
  2. Look for a random neighbor cell you haven't been to yet
  3. If you find one, move there, knocking down the wall between the cells. If you don't find one, back up to the previous cell
  4. Repeat steps 2 and 3 until you've been to every cell in the grid


PSEUDOCODE

create a CellStack (LIFO) to hold a list of cell locations
set TotalCells = number of cells in grid
choose a cell at random and call it CurrentCell
set VisitedCells = 1
 
while VisitedCells < TotalCells

      find all neighbors of CurrentCell with all walls intact
      if one or more found
            choose one at random
            knock down the wall between it and CurrentCell
            push CurrentCell location on the CellStack
            make the new cell CurrentCell
            add 1 to VisitedCells 
      else
            pop the most recent cell entry off the CellStack
            make it CurrentCell 
      endIf
 
endWhile

assumed u have a x b size of maze, u need a + 1 and b + 1 of walls, so size of array should be (size * 2 + 1)


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>
 
#define MAX 61  // 30 * 2 + 1
#define CELL 900  // 30 * 30
#define WALL 1
#define PATH 0
 
void init_maze(int maze[MAX][MAX]);
void maze_generator(int indeks, int maze[MAX][MAX], int backtrack_x[CELL], int bactrack_y[CELL], int x, int y, int n, int visited);
void print_maze(int maze[MAX][MAX], int maze_size);
int is_closed(int maze[MAX][MAX], int x, int y);
 
int main(void)
{
    srand((unsigned)time(NULL));
 
    int size;
    int indeks = 0;
    printf("MAZE CREATOR\n\n");
    printf("input  (0 ~ 30): ");
    scanf("%d", &size);
    printf("\n");
    int maze[MAX][MAX];
    int backtrack_x[CELL];
    int backtrack_y[CELL];
 
    init_maze(maze);
 
    backtrack_x[indeks] = 1;
    backtrack_y[indeks] = 1;
 
    maze_generator(indeks, maze, backtrack_x, backtrack_y, 1, 1, size, 1);
    print_maze(maze, size);
 
    getch();
    return 0;
}
 
void init_maze(int maze[MAX][MAX])
{
     for(int a = 0; a < MAX; a++)
     {
         for(int b = 0; b < MAX; b++)
         {
             if(a % 2 == 0 || b % 2 == 0)
                 maze[a][b] = 1;
             else
                 maze[a][b] = PATH;
         }
     }
}
 
void maze_generator(int indeks, int maze[MAX][MAX], int backtrack_x[CELL], int backtrack_y[CELL], int x, int y, int n, int visited)
{
    if(visited < n * n)
    {
        int neighbour_valid = -1;
        int neighbour_x[4];
        int neighbour_y[4];
        int step[4];
 
        int x_next;
        int y_next;
 
        if(x - 2 > 0 && is_closed(maze, x - 2, y))  // upside
        {
            neighbour_valid++;
            neighbour_x[neighbour_valid]=x - 2;;
            neighbour_y[neighbour_valid]=y;
            step[neighbour_valid]=1;
        }
 
        if(y - 2 > 0 && is_closed(maze, x, y - 2))  // leftside
        {
            neighbour_valid++;
            neighbour_x[neighbour_valid]=x;
            neighbour_y[neighbour_valid]=y - 2;
            step[neighbour_valid]=2;
        }
 
        if(y + 2 < n * 2 + 1 && is_closed(maze, x, y + 2))  // rightside
        {
            neighbour_valid++;
            neighbour_x[neighbour_valid]=x;
            neighbour_y[neighbour_valid]=y + 2;
            step[neighbour_valid]=3;
 
        }
 
        if(x + 2 < n * 2 + 1 && is_closed(maze, x + 2, y))  // downside
        {
            neighbour_valid++;
            neighbour_x[neighbour_valid]=x+2;
            neighbour_y[neighbour_valid]=y;
            step[neighbour_valid]=4;
        }
 
        if(neighbour_valid == -1)
        {
            // backtrack
            x_next = backtrack_x[indeks];
            y_next = backtrack_y[indeks];
            indeks--;
        }
 
        if(neighbour_valid!=-1)
        {
            int randomization = neighbour_valid + 1;
            int random = rand()%randomization;
            x_next = neighbour_x[random];
            y_next = neighbour_y[random];
            indeks++;
            backtrack_x[indeks] = x_next;
            backtrack_y[indeks] = y_next;
 
            int rstep = step[random];
 
            if(rstep == 1)
                maze[x_next+1][y_next] = PATH;
            else if(rstep == 2)
                maze[x_next][y_next + 1] = PATH;
            else if(rstep == 3)
                maze[x_next][y_next - 1] = PATH;
            else if(rstep == 4)
                maze[x_next - 1][y_next] = PATH;
            visited++;
        }
 
        maze_generator(indeks, maze, backtrack_x, backtrack_y, x_next, y_next, n, visited);
    }
}
 
void print_maze(int maze[MAX][MAX], int maze_size)
{
     for(int a = 0; a < maze_size * 2 + 1; a++)
     {
         for(int b = 0; b < maze_size * 2 + 1; b++)
         {
             if(maze[a][b] == WALL)
                 printf("#");
             else
                 printf(" ");
         }
         printf("\n");
     }
}
 
int is_closed(int maze[MAX][MAX], int x, int y)
{
    if(maze[x - 1][y]  == WALL
       && maze[x][y - 1] == WALL
       && maze[x][y + 1] == WALL
       && maze[x + 1][y] == WALL
    )
    return 1;
 
    return 0;
}



Growing Tree

It starts by selecting a random cell and adding it to the list

x, y = rand(width), rand(height)
cells << [x, y]

The program them simply loops until the list is empty 

until cells.empty?
  # ...
end

Within the loop, we first select the cell to operate on. I’m going to mask my own program’s complexity here behind a simple “choose_index” method; it takes a number and returns a number less than that.

index = choose_index(cells.length)
x, y = cells[index]

Next, we iterate over a randomized list of directions, looking for an unvisited neighbor. If no such neighbor is found, we delete the given cell from the list before continuing.

[N, S, E, W].shuffle.each do |dir|
  nx, ny = x + DX[dir], y + DY[dir]
  if nx >= 0 && ny >= 0 && nx < width && ny < height && grid[ny][nx] == 0
    # ...
  end
end

cells.delete_at(index) if index

When a valid, unvisited neighbor is located, we carve a passage between the current cell and that neighbor, add the neighbor to the list, set index to nil (to indicate that an unvisited neighbor was found), and then break out of the innermost loop.

grid[y][x] |= dir
grid[ny][nx] |= OPPOSITE[dir]
cells << [nx, ny]
index = nil
break

And that’s really all there is to it. Some possible implementations of the choose_index method might be:

def choose_index(ceil)
  return ceil-1 if choose_newest?
  return 0 if choose_oldest?
  return rand(ceil) if choose_random?
  # or implement your own!
end



Edit

3DEdit

  • solo route (hard and time consuming) ?? and use OpenGL (Mesa) routines]
  • 3d game engines like Antiryad Gx, panda 3d, [Quake Doom id Tech 1 to 3 in C], [id Tech 4 in C plus plus], Urho3d, [Terathon C4 (Commercial),




2D texture onto 3D objectEdit

You need to create a separate context per class object instance and keep it alive as long as instance is alive. The context is bound to executing task and you can only have one context bound at a time. Opening the library itself does nothing - all actions are executed in relation to the context.

To get access to the right mouse button in an subclass I've added this in the setup method :

set(_win(obj), MUIA_Window_NoMenus, TRUE);

f the square you are drawing to is 2 dimensional and not rotated, you may be looking for glDrawPixels. It allows you to draw a rectangular region of pixels directly to the buffer without using any polygons.

glTexImage2D. This is the call that loads the image in OpenGL for a 2D Texture. glTexImage2D actually takes a raw pointer to the pixel data in the image. You can allocate memory yourself, and set the image data directly (however you want), then call this function to pass the image to OpenGL. Once you've created the texture, you can bind it to the state so that your triangles use that texture. If the texture needs to change, you will need to either re-do the glTexImage2D() call, or use something like glTexSubImage2D() to do a partial update.

just pass an array of GLubyte to the glTexImage2D function (as well as all the functions needed to bind the texture, etc). Haven't tried this exact snippet of code, but it should work fine. The array elements represent a serial version of the rows, columns and channels.


int pixelIndex = 0;
GLubyte pixels[400];

for (int x = 0; x < 10; x++)
{
    for (int y = 0; y < 10; x++)
    {
         for (int channel = 0; channel < 4; channel++)
         {
             // 0 = black, 255 = white
             pixels[pixelIndex++] = 255;
         }
    }
}

glTexImage2D(
    GL_TEXTURE_2D, 0, GL_RGBA, SIZE, SIZE, 0,
    GL_RGBA, GL_UNSIGNED_BYTE, pixels);

I've read in the OpenGL book you can use a 2D array for monochrome images, so I assume you could use a 3D array also.



CollisionEdit

Ray with PlaneEdit

  • about a sphere intersecting triangles, and something called the "2PI summation method" to determine if a ray strikes a triangle.
  • create a plane from your wall and do a ray to plane intersection test. A very simple test is a dot product test. If the result of the vector based scalar 'dot' product is >0, or the vectors are pointing in somewhat the same direction, then you know you are on the near side of the wall. If its <0, or the vectors are nearly pointing in the opposite directions then you are on the far side of the wall
  • test for pixel perfect, you must find the point at which your camera ray intersected the plane in question. Back the camera up to that point, compute the collision response, and move on
  • does a ray to triangle test and then computes the barycentric coords of the ray inside of the triangle. It will also bail on NAN's which can cause problems. It only uses dot products as well


The equation for intersection of ray and plane. This is easier to do in a maze because we know that all walls will form a plane so there is no need to do an expensive ray to triangle test.

    Ray: p(t)=p0+td
    Plane: p dot n=d

    Equation: t=(d-p0 dot n)/(d dot n)

    If ray is parallel to plane or (d dot n)=0 then there is no intersection.
    If (d dot n)<0 then intersection during interval.

Solve for p0 which is actually p0.x and p0.y in this equation as well. This has been solved for t to test for intersection in this time interval. The nice thing about this is the dot product test and point test are rolled up in one algorithm. If the first time interval test passes, you can then solve for p0.



PathfindingEdit

  • grid-based


  • Djikstra's with tutorial and close cousin A* star and pseudocode
  • flooding algorithm and then sound propagation. [http://sourceforge.net/projects/argorha/ placing a virtual version of my character at a given position (usually a spawn point). I do an initial ray cast to place him flush against the ground and then add that single occupy-able cell to my "unprocessed list". I then check the four neighbors of that cell to see if a virtual player could step there with out being impeded/falling-climbing too much. I add the successful cells to the unprocessed list, and take my initial cell and put it in the processed list. repeat until the unprocessed list is empty.

The cells in my algorithm also store a position of the ground, and this can go up or down depending on if stairs or a ramp were encountered. When a sector is created from a list of related cells, it uses a axis aligned bounding box that encompass all these points (+ the width and height of each cell)]

  • D* being a dynamic A*
  • 3D mesh navigation


A starEdit

A* (A star) algorithm moves through the grid from the given starting point to the given destination. Each "step" it makes it stores in a node. In this node data structure is stored three values

  • the coordinates of the current block from the start
  • the distance to the finish position from this block (different methods manhattan, diagonal, euclidian (optional squared version)
  • and this block's parent block (for a later backtrack mode)

As the algorithm moves towards the destination, it stores these nodes into two stacks: the open and the closed stack. Once the destination block is reached, we go back through the nodes (using the pointer to the parent nodes) and we have our path described

Youtube video here and here



Insert the start point onto the open stack

while( nodes left on open stack ) {

    //Pop first (closest) node off of open stack

    node = openstack.pop

    if( node.bDestination == 1 ) {

        Loop upwards through data structure to generate path

        exit function

    }

    //If we get here, this node isn't the destination

    for( up, down, forward, backward, left, right in grid ) {

        //GetNewNode returns null if block is occupied or in //closed stack

        newnode = GetNewNode( currentDirection )

        if( newnode ) {

        //This InsertSorted function inserts the node //sorted based on the block's distance from the //destination

            openstack.InsertSorted(newnode);

        }

    }

    //Once a node is on the closedstack it is no longer used //(unless one of its children is the destination)

    closedstack.push( node );

}

In this algorithm the tricky part is actually in the InsertSorted() method of the openstack. You sort the nodes by their distance to the destination. This is the most important part of the algorithm, because the order in which the algorithm picks nodes to search is based on this sorting. Traditionally, (at least in the examples I've seen) you use the Manhattan Distance, which is the distance in grid blocks from the destination. I tweaked this distance function, and instead used the 3D distance of the centerpoint of the current block to the destination (using BlockDistance3D). For whatever reason this made the algorithm work better in my case...it consistantly searched less nodes than using the manhattan distance.

Read more here and here


ExamplesEdit

Minecraft clones OpenGL, Minetest C55, Theory,