# Aros/Developer/Games Programming/Basics

* Navbar for the Aros wikibook
* Aros User
* 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
* Aros x86 Complete System HCL
* Aros x86 Audio/Video Support
* Aros x86 Network Support
* Aros Intel AMD x86 Installing
* Aros Storage Support IDE SATA etc
* Aros Poseidon USB Support
* x86-64 Support
* Motorola 68k Amiga Support
* Linux and FreeBSD Support
* Windows Mingw and MacOSX Support
* Android Support
* Arm Raspberry Pi Support
* PPC Power Architecture
* misc
* Aros Public License

## Introduction

* learn to think like a programmer
* learn C C++
* 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.
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

Concept (marketing hook in order of difficulty) - gamestyle with gamestyle but ...
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

## 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
* Sprites Artwork
* Animation Artwork
* 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
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.

### 2.5D Calculating Distance/Depth

A perspective transform (perspective projection == divide by Z) amounts to
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
or:
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
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.
Read more about 2.5D here

#### 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
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)
Growing Tree
It starts by selecting a random cell and adding it to the list
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.
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.
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.
And that’s really all there is to it. Some possible implementations of the choose_index method might be:

## 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 :
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.
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.
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
* Djikstra's with tutorial and close cousin A* star and pseudocode
* flooding algorithm and then sound propagation. 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 neighbours 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 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
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 - , , , , , , ,
* Lua - Love2D,
* HTML5, ,
* PortablE

### C and company

* C
* C++
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++
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

### Algorithms

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
* search trees like: B tree, B+ tree, Red-black tree
* sorting algorithms like quicksort, natural merge sort, bucket bin sort,
* Breadth-first search (http://en.wikipedia.org/wiki/Graph_traversal), Depth-first search (mazes),
* path finding like Hill Climb, A-star,
* Vectors,

#### Quicksort

Youtube video here and

#### Merge Sort

Youtube video here