Senior Production Week 7

This week myself and the lead systems designer were able to begin testing and tweaking the game in engine.  We spent the majority of the time testing and tweaking the cars, and the first major change we made was to influence the car’s turning ability based upon its current speed.  Thus, the faster a ship moves, the worse its turning capability will be–to an extent.  Though it may not seem it, this change was actually made to improve control and maneuverability of the ships, as previously turning would simply immediately rotate the ship, causing a very high probability of players losing control, or the ship spinning out.  Currently, we have three major vectors around which ships will be balanced, tweaked, and made unique: max speed, acceleration, and turning ability.

In addition, this week we took the game to testing after a fairly lengthy hiatus.  Though the build had bugs and playability issues, the testing period helped display many areas that need improvement and fixing, and will become the focus of future tasks.

Advertisements

2 Week Project on Genetic Algorithms

Genetic Algorithms are a subset of Evolutionary Algorithms, which are a subset of Evolutionary Computing, which is a subset of Artificial Intelligence.  Essentially, Genetic Algorithms are a type of search used to find solutions, or the best result, to optimization problems, such as the backpack and salesman problems.  As its name suggests, these styles of algorithms arrive at their results by using a process that mirrors biological evolution–the members of a population mate, creating a new generation with the better characteristics of the current generation, as well possibly mutating some aspects of the new members.

The structure of Genetic Algorithms is often as follows:

1) Define target and terminators – The target is most often the goal the algorithm is attempting to achieve, such as a particular string, calculation, or result.  Terminators are failsafes, such as a maximum number of population iterations, to assure  the program does not run indefinitely, or derail from the problem at hand.

2) Initialize population – The importance of this step is in choosing the population size most useful for the problem at hand.  In many cases, a larger population size is not always desirable, as it can greatly increase the resources the algorithm requires to run or complete.  Conversely, having too small a population can increase the time required for the data within the algorithm to evolve.

3) Evaluate fitness – This step is often very important in getting ready for the mating stage.  Essentially, this steps rates each member of the population based on some sort of criteria.  For example, in attempting to generate a specific string, each char within the member string is rated based on how close it is to the chars in the target string.  Depending on the goals of the algorithm, the members of the population might be sorted based on their fitness in this stage.

4) Mate (Elitism and Mutation) – This step mates two members of the population together, and produces two children.  Mating is made up of four stages:

  1. Selection – The selection stage determines which two members to mate together.  Examples of how to determine these pairs include: Roulette–members with a higher fitness have a greater chance of being mated–Rank–members are ranked and mated together based on their fitness–Random–randomly select to members that have not yet mated–Steady–the top X percent of the population is mated together–and Elitism–where the top X percent of the population is directly copied into the new generation.
  2. Encoding – The encoding stage determines the type of, and how, data is transferred to children.  Examples include: Binary–each piece of data is represented as a bit–Permutation–data is a sequence of numbers or characters–Value–data is values of various types–and Tree–data is a part of a tree of data and functions.  This type of encoding is often used to evolve functions, rather than data.
  3. Crossover – The crossover stage determines how the parent’s data is presented in its children.  As examples, Single and Multi encoding work by selecting one or multiple, respectively, points where everything before this point will be parent A’s genetic data, and everything after will be parent B’s genetic data.  Other examples include Uniform–where genetic data is randomly selected from parents–and Arithmetic–where a predefined function determines what data is copied from what parent.
  4. Mutation – This is an optional stage.  As in biological evolution, this stage gives new members of a population a random chance to mutate some of their genetic data, either positively or negatively.

6) Assign new population – This step very simply sees the new generation overriding the current generation.  Upon completion the process returns to stage 3, and repeats until either the target or terminator is met.

 

Resources and Helpful Links:

http://www.obitko.com/tutorials/genetic-algorithms/index.php

http://www.generation5.org/content/2003/gahelloworld.asp

http://www.ai-junkie.com/ga/intro/gat3.html

http://www.dreamincode.net/forums/topic/230020-evolutionary-algorithms-genetic-algorithms/

http://en.wikipedia.org/wiki/Genetic_algorithms

Senior Production Week 6

This week was a bit of an interim, as changes were made to the GIT repository in order to streamline the production process and ease of access.  Now that most of the major changes have been made, myself and the lead systems and experience designer were able to get in engine and begin creating a test level, wherein we will be testing everything from overall experience, to hovercar and spectacle experience.  Additionally, we will heavily be test edge cases for all systems and the track itself, as well as experimenting with  track pieces, so as to best advise the level designers as the construct the tracks.v

Senior Production Week 5

This week was spent working on the attract screen, as well as preparing to begin fully diving in to refine the experience of the game.  We decided we will eventually make use of a variety of fonts, colors, and lighting effects, as well as on screen visual effects, such as mirror or making reflected shapes on the screen.  Our audio direction has, for some time, been a combination rock/metal and electronic, and the attract screen will follow this principle, though it will play with a much more with dynamic range.  For example, there will be great difference between slow, quiet and fast, loud sections.  Finally, once the code for controlling the wheel and pedals has been re-added, we will begin to spend a great amount of time testing the game, looking for all the edge cases we possibly can, as well as refining the numbers controlling the various cars, traveling through rifts, and experiencing the track and its spectacles.

Senior Production Week 4

This week was largely spent documenting, tweaking, and analyzing the current rift systems, as well as some initial exploration into the balancing of the hovercars.  Additionally, the team as a whole began to prepare to challenge the greenlight stage during Week 5’s class.

Though the rift system hasn’t gone under any heavy experience testing yet, we have already analyzed some possible usability issues, such as players being mid turn when entering a rift and immediately hitting an obstacle or driving out of the sub-space area, and have put forward initial solutions.  In preparing for the greenlight challenge, we documented and discussed both the rift systems themselves, as well as any possible ‘what-if’ situations, such as what would occur if player 2 was able to enter a necessary rift intended for player 3.  In this example, then, the exit rift would still be tied to player 1, as the rift was originally intended for player 2.

Senior Production Week 3

This week was largely spent defining the rules of what are now being  called “Unnecessary Rifts”, as well as some general documenting and presentation preparation.  As opposed to “Necessary Rifts”, the purpose of which is to act as a rubberbanding system to keep all players in the competition, Unnecessary Rifts are intended to act as a speed boost, throwing a wrench into a group of tightly packed players.

The rules for unnecessary rifts  begin with a check to see if all players have been within a short distance of the player ahead of them, for a period of time.  Afterwards, it randomly generates a rift for one of the players, granting a higher chance for those players furthest back.  Unlike Necessary Rifts, which disappear immediately if they are missed by their intended players, Unnecessary Rifts disappear after 1 second, allowing for the possibility of another player being able to use the rift instead.

The rules and goals within the rift remain the same across both types of rifts, though Unnecessary rifts are a degree more difficult than their Necessary Rift counterparts.  Finally, rather than tying the exit points to the ahead player’s most recently passed waypoints, Unnecessary Rifts transport players forward a number of waypoints equal to the number of sections they progressed through in the rift.  For example, a player that makes it to the third section of a rift will be transported forward three waypoints.

2 Week Project on Big O Notation

Big O Notation is a means of theoretically measuring the resources needed to perform an algorithm of ‘n’ inputs.  Resources can be a variety of measurements, but most often is time, space, or memory.  Essentially, Big O Notation is an algorithm’s efficiency as its input approaches infinity.  It is not, however, a means of exactly measuring an algorithm given a specific input.  The levels of efficiency,  from most to least efficient, are:

  • O(1) – Constant
  • O(log n) – Logarithmic
  • O(n) – Linear
  • O(n log n) – “n log n”
  • O(n ^ 2) – Quadratic
  • O(a ^ n)(a > 1) – Exponential

To find the Big O of an algorithm, count the number of touches, simplify the resulting polynomial, and discard any constants.  The answer will then be the fastest growing ‘n’.

Examples:

for(int i = 0; i < n; i++) //touches ‘n’ times

{

}

F(n) = O(1 + n) //1 is the constant for engaging the for loop, ‘n’ is the number of times the loop is ‘touched’

F(n) = O(n) //Drop the constant.  The Big O of this loop is n, or linear.

for(int i = 0; i < n; i++)

{

}

for(int i = 0; i < n; i++) //touches ‘n’ times

{

for(int j = 0; j < n; j++) //touches ‘n’ times

{

}

}

F(n) = O(1 + n + n * n) //1 is the constant, the first ‘n’ is the solitary loop, nested loops cause ‘n’s to be multiplied together

F(n) = O(1 + n + n ^ 2) //Simplify

F(n) = O(n + n ^ 2) //Drop the constant

F(n) = O(n ^ 2) //The answer is the fastest growing ‘n’.  The Big O of this algorithm is n2, or quadratic.

Helpful Links:

http://www.dreamincode.net/forums/topic/125427-determining-big-o-notation/

http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it

http://www.apcomputerscience.com/apcs/misc/BIG-O.pdf

http://www.cprogramming.com/tutorial/computersciencetheory/algorithmicefficiency3.html

http://en.wikipedia.org/wiki/Big_O_Notation