= algorithms
:author: 
:revnumber: 
:revdate: 2016/03/17 20:48
:relfileprefix: ../../../../
:imagesdir: ../../../..
ifdef::env-github,env-browser[:outfilesuffix: .adoc]



== Algorimths for games

Single (or serveral) objective algorimths useful for games.

link:http://en.wikipedia.org/wiki/Algorithm[http://en.wikipedia.org/wiki/Algorithm]

link:http://en.wikipedia.org/wiki/Linear_programming[http://en.wikipedia.org/wiki/Linear_programming]

Algorithm is a step-by-step procedure for calculations. An algorithm is an effective method expressed as a finite list[1] of well-defined instructions[2] for calculating a function.[3] Starting from an initial state and initial input (perhaps empty),[4] the instructions describe a computation that, when executed, proceeds through a finite[5] number of well-defined successive states, eventually producing “output[6] and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.[7]

Linear programming (LP, or linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polyhedron, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such a point exists.


=== Why use this ... for games?

This package provides algorithms common in game developments. More to come but first let's take a look of those problems it trying to solve to distingish the objective and goals of this package compare to collection and others.


==== It's not another Collection (DataStructure) or Pattern package!

Sort, concurrent, packing, data compressing is also partial relate to its processing method (that's algorithm) but first, they are provided as the core of the programming language, second we want to care more about the high level of abstraction, not the details. It use “interface of structure for its explaination and progress.

Also, pattern is the term refered to a popular method in software developmenet. Pattern is also in higher level of abstraction compare to algorimths. So consider pattern is the law and algorimth is the effective way of making the job work effectively obey that law.

Algorithms involve logic, a lot of them. But it higher level than logic. And of course algorithms need math (some physics, philosophy also) to be smart!

Algorithms are used heavily in AI. But this package only provide pure algorithms which can be used also outside of AI topics.

That's said:

*  Datastructure, Pattern, Logic and AI are supported elsewhere!
**  Algorimths depends in Pattern, Logic, Interface of Structure.


==== Each algorithm has a goal (or several) to accomplish!

Developer want to use the algorithm they know to solve one or more goals (problem, requirement, aspect, situation, … what ever you call it). The algorithms provided here are the bricks for you to use and reuse, for different purposes. And you may notice the package also be arranged into purposes instead of implementations - techniques or another structure. That's explained the reason!


==== For games?

Yes, not all of the problems we know are solved by this library…??? You've already know. It not even sotiphicated like the alternatives below but they are extremely useful for average programmers; especially game programmer, who, usually focus in the fun side (Am I right? :) )

The library try to provide useful algorithms (best practices and wisdoms) enough for a wide range of usecases and also used in Atom framework its self. The algorimths them self may use another algorimths to solve sub-problems. Of course, it also come with examples and a lot of applications &amp; suggestion, which its the algorithms use for you to quickly and smartly solve your own problem thank to it.
Support algorithms by purposes

....
 1. Allocation: solve problems about resources.
       1. Allocate resources efficiently on demand and sastify requirements:
             1. in an amount of time (interval, arrangement, progess, budget)
             2. with specific capacities of the network and memory (flow, route, budget)
             3. with dependencies (order)
             4. skip or retry if unsuccess (fault-tolerant)
             5. cache
       2. Skip resources that fault-tolerant: ( aka Reject)
             1. Not affect its dependencies, or skip those dependant
             2. Preseved the continuous, so the flow still smooth
       3. Release resources ( aka Remove)
             1. Determiate which resource are no more needed
             2. Help the gabbage collector, cache to remove it
       4. Update resources
             1. Only what that need to be update
             2. Deffered till the update process not abuse the other pioritied operations
 2. Balance: find a division, equallity equilibrium between inputs of forces (presure).
       1. Exchange: when force interact
       2. Equilibrium: when force include, conccure together and zero total
 3. Energy : more than just physics simulation, its applied physics-math based methods
       1. Static:
       2. Dynamic:
       3. Potential: 
       4. Tension:
 4. Constraint: find a solution that sastify a list of constraints.
       1. Search for sollution in avaiable space (travel)
       2. Generate a sollution base in template
 5. Interval: various problems related to intervals (values a duration of time).
       1. Progress monitoring
       2. Schedule jobs
 6. Optimization: to optimize toward a goal
       1. Maximize - minimize:
       2. Resolution: Find a solution upon a known solution (aka neirghboor search)
       3. Boost: wisdoms  to make higher performance and more efficient algorithms if not saturated (without resolution)
             1. Reactive
             2. Adaptive
             3. Fractal
 7. Relate: solve problems between things relate to other (Very close to abstract aglebra):
       1. Reconfiguration: if one change, others react
       2. Coupling: link-relink-relax link-remove link between two or a group by cateria (aka clustering)
       3. Dependency: direct/ indirect depend on other and how to isolate
       4. Order: study of ordering, very similar to sorting wisdoms but in higher level.
 8. Score: Study the "number","amount" (aka quantity) of things; summarize and judge (aka quality). Wisdoms about: Measuring, scale, approximation, coloring or the alike.
       1. Budget:
       2. Audit: (aka Accounting)
       3. Cardinality:
 9. Travel: Study the step by step "move" between unit of things. This is a fundamental and essential spirit of algorithms.
       1. Search: Study the exploring in space.
       2. Trace: Study the affection (footprint, operations, cost.. ) the algorithms left each step
       3. Track:  Study the  route  (path, track, flow,...)  the algorithms  pass.
10.  Generation: good practises in making new things
       1. Template is the resource of generation
       2. Production is the progress of creating new things
....


== Concepts

First of all this package has some degree similar to JScience and Opt4J… I can't denied I had used them intensively to know what is good and what is not. About the similarity between Ptolemy and Atom, even the two take different approaches and implementation, you can read from the Atom framework introduction.

Algorimths in computing, programming and game programming has grown, based in knowledges and wisdoms from a lot of other sciences: math, physics, philosophy, chemistry, biology… etc. Here and there the concepts are familiar with developer because they've taught in schools. Some may require extra knowledge from mathematics and physics per se… But you know google can have any way.

Here is the part where the concepts which used in algorithms in Atom framework which you can reference and research futher. Almost every part you can also google about them or try to find it in jscience +++<abbr title="Application Programming Interface">API</abbr>+++ javadoc:

link:http://jscience.org/api/index.html[http://jscience.org/api/index.html]

link:http://jscience.org/experimental/javadoc/[http://jscience.org/experimental/javadoc/]


=== From Mathematics


==== Algebra


==== Topo & Graph


=== From Physics


==== Common


==== Kinematic


=== From computing techs


=== Saturation of algorithms:

You may notice that if there is a “pattern or “algorimth to optimize a progress. Can we use them repeatly until processing time toward minimum or even zero????

This sounds totally untrue and also ridiculous but an interesting captious way of thinking. 

link:http://algs4.cs.princeton.edu/66intractability/[http://algs4.cs.princeton.edu/66intractability/]

link:http://en.wikipedia.org/wiki/Time_hierarchy_theorem[http://en.wikipedia.org/wiki/Time_hierarchy_theorem]

link:http://www.npr.org/blogs/13.7/2011/09/19/140599268/minds-and-machines-the-limits-of-turing-complete-machines[http://www.npr.org/blogs/13.7/2011/09/19/140599268/minds-and-machines-the-limits-of-turing-complete-machines]

link:http://en.wikipedia.org/wiki/Turing_machine#Computational_complexity_theory[http://en.wikipedia.org/wiki/Turing_machine#Computational_complexity_theory]

Here i used the term the *saturation of algorithms* to describle the problem from overview.

Let say the algorithm A needs B to compute, and than B needs A to compute. The Recursion will be forever in the turing machine such as our computer, until we out of memory or can even cause a crash in some programming language and computer-small scale ones (pc,console…). In real-life, it's hardly useful for game developing. 

For example: 

In Allocation package, we need to compute the dependencies between resources, si call Dependency package. In computing dependency, we need resource so we call allocation package… This loop is actually fine but its will run forever if there is no saturation point or the end point of the recursion calls. 

So in AtomAA, there is a detection of Recursion and cyclic dependency that can break-out early from the infinite loops. Also if Dependency package call, it tell Allocation not to call it again in the amount of time. Allocation then will chose another path of computing by just allocate directly. This not gaurantee to prevent the problem but ease out the percentage you fall into a dead trap. It work pretty much like concurrent contention resolving in by synchronization in Java. 

This mean the context of computing is affect the algorithms, lead the algorithm to context-depend. So is it conflict with the definition of algorithm and wrong? Well, in real-life, some algorithms actually work upon a data structure and context, if not to say all of them. The abstraction and agnostic of algorithm is limit but higher than data structure, it just depend in the “context of computing but work in various data structure, even a new one. It's also better than normal datastructure in this “loop situation. You may experience the situation that datastructure implementation may cause infinite loop with them self or others. At least algorithms try to prevent that…


[WARNING]
====
*Note:* Actually when the situation happen, there is a way to stop the whole!… but not a clean way to set a flag, clear the flag and continue again, because the next time, the progress can not distingish between the normal processing and the invalid one. At least not a simple way without Tranactional Memeory Model.
====


In development mode, with AtomAA , the programmer will be notified and the progress will stop. A monitoring framework can also help. The determistic of the algorithms over arbitrary data (in real-life) is also quite a challange problem. That's also a caveat in AtomAA its self.


== Implementation details


[TIP]
====
The *[JavaAA]* (Java Atom Algorithms) tags mark what this package support.
====



=== Allocation

solve problems about resources.

....
Allocate resources efficiently on demand and sastify requirements:
  in an amount of time (interval, arrangement, progess, budget)
  with specific capacities of the network and memory (flow, route, budget)
  with dependencies (order)
  skip or retry if unsuccess (fault-tolerant)
  cache
Skip resources that fault-tolerant: ( aka Reject)
  Not affect its dependencies, or skip those dependant
  Preseved the continuous, so the flow still smooth
Release resources ( aka Remove)
  Determiate which resource are no more needed
  Help the gabbage collector, cache to remove it
Update resources
  Only what that need to be update
  Deffered till the update process not abuse the other pioritied operations
....


=== Balance:

....
find a division, distribution for equality, find equilibrium between inputs of forces (presure).
 Exchange: when force interact
 Equilibrium: when force include, concur together and zero total
 
....

higher wisdoms than equality and difference. Its the progress of making two or more things equal by exchanging one by one (local optimal or greedy). It's also a study of distribution to find equilibrium between inputs of forces. This problem araise a lot in classical game theory and later game developing. 

Read: 
link:http://en.wikipedia.org/wiki/Game_theory[http://en.wikipedia.org/wiki/Game_theory]

link:http://en.wikipedia.org/wiki/Solution_concept[http://en.wikipedia.org/wiki/Solution_concept]

link:http://en.wikipedia.org/wiki/Nash_equilibrium[http://en.wikipedia.org/wiki/Nash_equilibrium]

link:http://en.wikipedia.org/wiki/Ultimatum_game[http://en.wikipedia.org/wiki/Ultimatum_game]


=== Energy :

....
more than just physics simulation, its applied physics-math based methods
  Static:
  Dynamic:
  Potential: 
  Tension:
....


=== Constraint:

find a solution that sastify a list of constraints.

....
Search for sollution in avaiable space (travel)
Generate a sollution base in template
  
....


=== Interval:

various problems related to intervals (values a duration of time).
 Progress monitoring
 Schedule jobs


=== Optimization:

to optimize toward a goal

....
 Maximize - minimize:
 Resolution: Find a solution upon a known solution (aka neirghboor search)
 Boost: wisdoms  to make higher performance and more efficient algorithms if not saturated (without resolution)
   Reactive
   Adaptive
   Fractal
 Evolutionary: 
....


=== Relate:

 solve problems between things relate to other (Very close to abstract aglebra):

....
 Reconfiguration: if one change, others react
 Coupling: link-relink-relax link-remove link between two or a group by cateria (aka clustering)
 Dependency: direct/ indirect depend on other and how to isolate
 Order: study of ordering, very similar to sorting wisdoms but in higher level.
....

The relationship between things cause complex problems, this package try to solve a subset of problems which is useful in programming and gamedev in general. Relation is very abstract, but some of  “relationship problems are well-defined like:

*  the cause of declaration of relationships 
*  the dependency between two subject
*  the direction, order of relation or force
*  the configuration need to the relationship

*Dependency*: If one object “declare relationship to another, aka one-direction link:
*Coupling*: If two objects “declare relationship between each other, aka bi-direction link:

*  [Real-life] Imagine the marriage law when two get married :) 
*  [Computing] The dependency between packages, modules, operations, tasks.
*  [JavaAA] 
**  The links can be create or not? 
***  to prevent NullPointException if you invoke an empty link.
***  to prevent IllegalException because of tabboo
***  full satifaction conditions?

**  What need for a link to be create? 
***  load needed assets, classes, modules.. - like what osgi and maven does
***  the first-attempt configuration in the two subjects.



*Reconfiguration*: If two objet “change the relationship and the affections.

*  [Real-life] Imagine a devote, and the fate of the property and children
*  [Computing] Reconfiguration cause computation in the said domain and cause a chains of reaction in the network. The reconfiguration can cause “bigger affection than the first time config, but how to decrease the cost?
*  [JavaAA] 
**  Is there anything i can save?
***  what is still valid and update just the delta?
***  what is properly unchanged and really can not be changed?
***  what will be abandond after reconfig?
***  can the reconfig progress delay or divide-to-conquer?

**  This also envolve in general LOD (LevelOfDetail) problems, which mainly focus in reconfig after changes. Divide-to-conquer is the main wisdom of this class of problems.


*Order*: directions, or the order of travelling when bunch of objects are related.

*  [Real-life] I want to travel in a city by roads. I have to know the map.
*  [Computing] Graph problems and how to change the direction of processing
*  [JavaAA] 
**  Sort in graphs &amp; Order of Nodes
**  Direction of Track
**  Order of Intervals (conccurent progresses)



=== Score:

Study the “number,“amount (aka quantity) of things; summarize and judge (aka quality). Wisdoms about: Measuring, scale, approximation, coloring or the alike.

....
 Budget:
 Audit: (aka Accounting)
 Cardinality:
 
....

This package support the invoke of functions and actions for measurement in single step or a chain of steps. Also it provide the remain of power within a Budget. After serveral of steps, it can invoke audit for examine the progress. For doing this, it has to know detail about Unit by understand Cardinality in the context. 

This package depend in Commons Math and JScience for useful functions.


=== Travel:

Study the step by step “move between unit of things. This is a fundamental and essential spirit of algorithms. <<jme3/advanced/atom_framework/atomcore/algorithms#algorimths_for_games,Read back algorithm definition above>>

....
 Search: Study the exploring in space.
 Trace: Study the affection (footprint, operations, cost.. ) the algorithms left each step
 Track:  Study the  route  (path, track, flow,...)  the algorithms  pass.
 
....

Travel depend in relate. It Explores bunch of things that relate to each others in a space (Data space, time space). The process known as Search. Doing Search, it left Traces. Flowing trace in each step, one can see a Track or a Flow of the progress.

This package support: datastructure-agnostic search, traces and tracks (beside of those already supported in Java, Guava…)

Search:  
DFS, BFS, Traveler 

Trace: 
Visit, Footprint (mark), Cost

Track: 
ForwardTrack, BackwardTrack, Flow (TotalCostTrack-SingleStepCostTrack), FlowCapacity


=== Generation:

 good practises in making new things

....
 Template is the resource of generation
 Production is the progress of creating new things
....

A collections of wisdoms explain what/why/how to generate new things smart and efficiently.

*  [Math] A function from one domain to another domain. 
**  link:http://en.wikipedia.org/wiki/Function_%28mathematics%29[http://en.wikipedia.org/wiki/Function_%28mathematics%29]

*  [Physics] Energy from one form to another. 
**  link:http://en.wikipedia.org/wiki/Conservation_of_energy[http://en.wikipedia.org/wiki/Conservation_of_energy]

*  [Language] Translate sematic from one to another language need a dictionary. 
**  link:http://en.wikipedia.org/wiki/Semantic_similarity[http://en.wikipedia.org/wiki/Semantic_similarity]

*  [Art] Nothing new, just a cover. 
**  link:http://www.brainyquote.com/quotes/quotes/p/pablopicas380469.html[http://www.brainyquote.com/quotes/quotes/p/pablopicas380469.html]
**  link:http://idioms.thefreedictionary.com/There+is+nothing+new+under+the+sun[http://idioms.thefreedictionary.com/There+is+nothing+new+under+the+sun]
**  link:http://thephilthyway.files.wordpress.com/2012/09/boycottapple.png?w=549&h=279[http://thephilthyway.files.wordpress.com/2012/09/boycottapple.png?w=549&amp;h=279]

*  [Computing] Template is a good abstraction of algorimths. 
**  link:http://en.wikipedia.org/wiki/Generic_programming[http://en.wikipedia.org/wiki/Generic_programming]

*  [Programming] DRY , data-driven and open source. 
**  link:http://en.wikipedia.org/wiki/Don%27t_repeat_yourself[http://en.wikipedia.org/wiki/Don%27t_repeat_yourself]
**  link:http://en.wikipedia.org/wiki/Open_source[http://en.wikipedia.org/wiki/Open_source]
**  link:http://en.wikipedia.org/wiki/Data-driven_programming[http://en.wikipedia.org/wiki/Data-driven_programming]

*  [New techs &amp; trends] Topology and well defined network actually a virtue. 
**  link:http://en.wikipedia.org/wiki/Distributed_computing[http://en.wikipedia.org/wiki/Distributed_computing] 
**  link:http://storm.incubator.apache.org/[http://storm.incubator.apache.org/]



=== Limitations and futures

Only simple forms. But External libs can be hooked!

Usage of interface from sg.atom.world.physics package, should be all in sg.atom.utils only!

Lack of unit tests. But in the future

Lack of better documentation and education. Here you are, improve it your self.


== Applications


=== In Atom framework

Used in Asset/Task packages


=== Others

This small library can be used in a wide range of applications especially games and simulations. 


[TIP]
====
Don't limit your imagination
====


link:http://en.wikipedia.org/wiki/Algorithmic_game_theory[http://en.wikipedia.org/wiki/Algorithmic_game_theory]

link:http://en.wikipedia.org/wiki/LP-type_problem[http://en.wikipedia.org/wiki/LP-type_problem]

link:http://en.wikipedia.org/wiki/Multi-agent_systems[http://en.wikipedia.org/wiki/Multi-agent_systems]

link:http://en.wikipedia.org/wiki/Auction_Theory[http://en.wikipedia.org/wiki/Auction_Theory]


== Alternatives

For scientific wisdom in Java:

link:http://jscience.org/[http://jscience.org/]

For full-ledged multi objective meta heristic algorithms, try:

link:http://www.joptimizer.com[http://www.joptimizer.com]

link:http://opt4j.sourceforge.net/[http://opt4j.sourceforge.net/]

link:http://jmetal.sourceforge.net/[http://jmetal.sourceforge.net/]

Constraint programming and solver:

Choco

JACK

JaCop
