Aros/Developer/Games Programming/Basics

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.

Where game engine systems lie regarding other systems

1st - C, C++ base level
2nd - SDL with OpenGL framework, Raylib with OpenGL
3rd - Godot engines, Ren'Py, GameMaker, Scratch, Unity, Unreal ect (AROS does not have)

Game design document GDD

Top 100 games have over 90% market share

Concept (marketing hook in order of difficulty) - gamestyle with gamestyle but ...

arcade, catch, platformer, endless runner, mazes, tower defense, puzzle, city builder, rhythm, text, visual novel, adventure, party, shoot 'em up, metrovania, bullet hell, beat 'em up, walking sim on rails, card deck builder, cooking, racing, fighter, tactical turn based, real time strategy rts long term, relationships, survival, collectothon, fps, sandbox, management simulator, trading, sports, betting, rogue, roguelite, roguelike, dungeon crawler, rpg, horror, souls, soulslite, soulslike, battle royale, arena,

Similar games - same ... look / feel / genre / scope / target avatar audience

Measurement (Scale) - how the character / enemies interact, like reach, swing, grab, etc

Prototype - ugly grey box version, mock ups, concepts, screenshots, color schemes, logo, fonts, etc

10min demo - vertical slice for funding, getting initial impressions about good bits, poor ideas, missing parts, etc i.e playtesting

Fun like overcoming obstacles challenges, progression (quests logs to do lists) and rewards, sense of wonder

Design Patterns - finite state machines (behaviors through states entities transitions), event bus singleton (manage signals from objects), entity component patterns (building blocks)

Game Play Loop - , extraction, looter shooter,

Mechanics

Walls, Spikes, , etc

Story - Narrative, storyline,

Shipping

game jam to limit scope and allow completion within 1 week with clean code
then expand to 3,4 and 6 month cycles later as you gain experience and knowledge, later 9 or 12 months max to gain experience and stay focused

design process 
- Empathize: Research user needs
- Define: State user needs and problems
- Refine: Challenge assumptions and create ideas
- Prototype: Start to create solutions
- Test: Try out solutions

AROS (Amiga)

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. :-)

2D

Setup Tiles, masking, platform stuff, etc
Double buffering for moving objects sprites (collisions) or scrolling
2D frameworks which take some of the hard work of writing your own routines (like SDL1.2) or raylib5
Make at least one type of game from each of the following board/grid, maze, card, etc for the experience

SDL youtube video

hitbox
rotation
gravity
resistance - spring damper mass model
regioning art assets
lighting / shadows using 2d normal maps
particle effects, fire, embers, smoke, spark, lantern,
collisions

Rotations

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.

/* 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 */
             }
        }
}

2.5D Calculating Distance/Depth

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.

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.

Maze Generation

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

Start at a random cell in the grid
Look for a random neighbor cell you haven't been to yet
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
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

3D

solo route (hard and time consuming) ?? and use OpenGL (Mesa) routines] or raylib
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),

AROS currently does not have these

3d graphics engine (need to add networking, physics, sound, scripting, level editor etc.) like Ogre3D C++, Crystal Space C++, irrlicht C++, 3D voxel etc, Cube C, Luxinia in C BSD, horde 3d, [], [ torque 3d],

2D texture onto 3D object

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);

An OpenGL book you can use a 2D array for monochrome images, so assume you could use a 3D array also.

Collision

Ray with Plane

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.

Pathfinding

grid-based

A star

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

Examples

Minecraft clones OpenGL, Minetest C55, Theory,

Simpler Language Introductions

Javascript - [1], [2], [3], [4], [5], [6], [7],
Lua - Love2D,
HTML5, [8],
PortablE

C and company

C
C++ [9]

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.

Algorithms

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

Quicksort

# 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 Sort

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

[], [],