Re-definition of the generator презентация

Содержание


Презентации» Информатика» Re-definition of the generator
Re-Definition of the GeneratorGoals for a Generator
 We have defined the process mechanically, butGoals for a Generator
 Speed
 Ability to have content not slowGoals for a Generator
 Expressivity & Diversity
 The generated assets shouldTaxonomy
 Togelius et al. set a Taxonomy on how a generationTaxonomy
 Online v. Offline
 Location of the generation on the hostTaxonomy
 Generic v. Adaptive
 Does it adapt to the player’s actionsExample Taxa
 Faster than LightQuick And Dirty Summary
 Class is biomodal in their time playingWhy This Course
 Interested/Interesting
 Perspective area of employment
 Understand why thisReturn
 Implementation of skills
 Examples
 Advantages and DisadvantagesPortfolio
 2 Elements @ 20% each
 4 Categories
 Implement a researchTextures and LandscapesSpectrum of Need
 Flight SimulationSpectrum of Need 
 FPSRepresentation
 Intensity and Height Maps
 Grid of ValuesPure Randomness
 For each square – take a number from aForced to be Smooth -Interpolation
 Real terrain is not random -Lattice Size
 Larger Lattice – Places large peaks and valleys
 SmallerBilinear
 Weighted Average coming from the value of both points, interpolateAlso Works for Textures
 This method was originally applied to theBiCubic
 Linear is perhaps not as realistic, we want a smoothBiCubic
 Example x=1
 10% distance of the slope face
 S(.1) =Moving Past Direct Generators
 Idea till now have been to generateAgent GenerationDoran and ParBerry 2010
 Use the definition of an agent as:
Initial State
 Flat World bellow a waterline
 Representation as a heightCoastline Agent
 Starts with a seed location, a preferred direction (repulsor,Coastline Agent
 When done subdivision will begin to spend tokens
 SelectsSmoothing Agent
 Makes a random walk about the space and changesBeach Agents
 Search the area on the coastline and reduce theirMountain Agents
 Starts at a random location and has a preferredHill Agents
 Similar to Mountain agents
 Expend more tokens for eachRiver Agents
 Begin on the coastline
 Will walk from the coastlineAshlock and McGuiness 2013
 Evolutionary Approach to Landscapes
 Matches a TargetMethod
 Recursive quartering of the map space
 Automation holds a stateAutomation
 Representation is an automation of transitions and actions
 Actions areEA System
 Create a randomized population made up of chromosomes, dataCrossover in a GA on StringsCrossover and Mutation Operations
 Treats the structure as linear about states
Evaluation Against a Target
 Target is the ideal function
 For eachBeyond Squares
 Hex based Games instead of squares
 Height map valuesCiv 5?FactalsFracTals
 Self Similar Mathematical Structures
 Recursive Definitions
 Create structures which haveKoch Curve
 Each line has a triangle placed in the centreMidpoint Displacement Fractal
 Midpoint_Displacement(Startx,Endx,Run)
 Select the midpoint 
 Midx<-Startx + (EndxDiamond Square Algorithm
 Fournier et al. (1982), purposed for terrain byDiamond-SQuare
 Average over the 4 points (3 if on edge)
 AddDSFactal
 DSFractal(startx,starty,endx,endy,run)
 midx<-startx+(endx-startx)/2
 midy<-starty+(endy-starty)/2
 Square(startx,starty,endx,endy,midx,midy)
 Diamonds(startx,starty,endx,endy,midx,midy)
 DSFactal(startx,starty,midx,midy)
 DSFactal(midx,starty,endx,midy)
 DSFactal(startx,midy,midx,endy)
 DSFactal(midx,midy,endx,endy)Torus
 x Mod Xn
 y Mod Yn
 Note in C/C++ thatBrown et al. (2011) 
 Fractal Photomosaic images
 Idea – toMosacs
 Coloured Shards of Pottery, Stone, or Glass plastered to walls
Photo Mosaics
 First algorithmic version by R. Silvers 
 Holds PatentMaking a Photo Mosaic
 Break Images into Blocks
 Take a setLenna Image
 Scanned in from a Playboy Centerfold Lena Söderberg inMandelbrot Set
 Defined on the complex number set
 A point inData Structure
 X,Y values of the location of the start ofColouring
 Colouring based on the escape value of the factal
 ColouringSearch Through Fractals
 Genetic Algorithm
 Image Structure in box and ColourExpanding on These Techniques
 Target v. generation
 Animation of the process?



Слайды и текст этой презентации
Слайд 1
Описание слайда:
Re-Definition of the Generator


Слайд 2
Описание слайда:
Goals for a Generator We have defined the process mechanically, but what are the goals of a generation? In Procedural Content Generation for Games a set of desirable traits for a generator to have are discussed. A good generation must meet with requirements of: Speed Reliability Controllability Expressivity & Diversity Creativity & Believability

Слайд 3
Описание слайда:
Goals for a Generator Speed Ability to have content not slow the game content usage Reliability The Generator must meet with the constraints placed upon it, not introduce game breaking aspects Level without an exit v. Flower with lopsided petals Controllability Ability of a human designer or algorithmic method to specify aspects of the generation This level must have 5 enemies which are suitable to be faced by a level 10 Wizard or a level 4 Barbarian

Слайд 4
Описание слайда:
Goals for a Generator Expressivity & Diversity The generated assets should not be direct cloned copies A number of different but equally relevant content Hard to Measure (Defined Objective Measure) Creativity & Believability The generation should not feel `different` from one produced by a designer Again Hard to Measure Objectively

Слайд 5
Описание слайда:
Taxonomy Togelius et al. set a Taxonomy on how a generation can be classed: Online v. Offline Necessary v. Optional Degree and Dimensions of Control Generic v. Adaptive Stochastic v. Deterministic Constructive v. Generate and Test Automatic v. Mixed Construction

Слайд 6
Описание слайда:
Taxonomy Online v. Offline Location of the generation on the host machine during gameplay or by the game developers/host machine before the start of the game Necessary v. Optional Generator builds key mechanical parts of the game or is it to increase the functionality Degree and Dimensions of Control The level to which a developer or player has input into the generation method

Слайд 7
Описание слайда:
Taxonomy Generic v. Adaptive Does it adapt to the player’s actions or will it progress without intervention Stochastic v. Deterministic The generated content uses a random element in it’s creation or not Constructive v. Generate and Test The algorithm creates a or uses a search based approach Automatic v. Mixed Construction Does the generator act as the only designer or does a human designer use it as a tool

Слайд 8
Описание слайда:
Example Taxa Faster than Light

Слайд 9
Описание слайда:

Слайд 10
Описание слайда:

Слайд 11
Описание слайда:
Quick And Dirty Summary Class is biomodal in their time playing games Large spikes at the casual end and the hardcore end PC gamers and cellphone games Low usage of Consoles

Слайд 12
Описание слайда:
Why This Course Interested/Interesting Perspective area of employment Understand why this technique is not more widespread

Слайд 13
Описание слайда:
Return Implementation of skills Examples Advantages and Disadvantages

Слайд 14
Описание слайда:
Portfolio 2 Elements @ 20% each 4 Categories Implement a research paper Implement a small new design Implement a PCG method for a new creative domain outside of games Implement basic Maze/Texture generations and make comparisons Both Elements due on May 1 Can ask for an examination before with no penalty in order to know what to improve upon

Слайд 15
Описание слайда:
Textures and Landscapes

Слайд 16
Описание слайда:

Слайд 17
Описание слайда:
Spectrum of Need Flight Simulation

Слайд 18
Описание слайда:
Spectrum of Need FPS

Слайд 19
Описание слайда:
Representation Intensity and Height Maps Grid of Values

Слайд 20
Описание слайда:
Pure Randomness For each square – take a number from a random distribution Problems You get spikes in all the wrong places Doesn’t hold with reality Unplayable for games

Слайд 21
Описание слайда:
Forced to be Smooth -Interpolation Real terrain is not random - smoother Idea – randomize a set of critical locations, e.g. grid/lattice, which are placed apart by some distance Calculate the intermediary points to fit with the grid Loss of some features We cannot make shear rock faces easily

Слайд 22
Описание слайда:

Слайд 23
Описание слайда:
Lattice Size Larger Lattice – Places large peaks and valleys Smaller Lattice – Defines local peaks Hybrid – A larger lattice which determines the location of smaller lattices Assume for the next set that our Lattice contains a 11x11 square of the total map Ex. Between Height[0,0] to Height[10,10] Move over the space, vertically or horizontally, and interpolate the other points

Слайд 24
Описание слайда:
Bilinear Weighted Average coming from the value of both points, interpolate the y values on the top and bottom of the search area Height[0,y] = (10-y)/10 Height[0,0] + (y)/10 Height[0,10] Height[10,y] = (10-y)/10 Height[10,0] + (y)/10 Height[10,10] We now have the linear interpolation for the Y direction, we now make a second linear interpolation for the X for the remainder Height[x,y] = (10-x)/10 Height[0,y] + (x)/10 Height[10,y]

Слайд 25
Описание слайда:
Also Works for Textures This method was originally applied to the creation of texture maps Conversion from height space into colour space RGB values Verison of the mathematics which can be done with linear algebra – perfect for the GPU archatextures ]

Слайд 26
Описание слайда:
BiCubic Linear is perhaps not as realistic, we want a smooth transition between valley and hill, but we want something more Transition equation was a linear calculation, keep the same basic method but edit the equation Slope Function in Bilinear is S(x)=x Common slope function S(x)=-2x3+3x2

Слайд 27
Описание слайда:
BiCubic Example x=1 10% distance of the slope face S(.1) = .028 2.8% up the slope Height[0,y] = S(.1)y Height[0,0] + (1-S(.1))y Height[0,10] Height[0,y] = (.972)y Height[0,0] + (.028)y Height[0,10]

Слайд 28
Описание слайда:
Moving Past Direct Generators Idea till now have been to generate the points then figure out the slopes Alternative – place slopes directly Interpolation leads to breaks along the lines of the lattice – the lattice becomes visible The lattice can be formed to meet with the gradients

Слайд 29
Описание слайда:
Agent Generation

Слайд 30
Описание слайда:
Doran and ParBerry 2010 Use the definition of an agent as: Agents perceives its environment through sensors and acts via effectors Number of types of agents with different effector goals Coastline Agents Smoothing Agents Beech Agents Mountain Agents River Agents Each of these agents is given a number of tokens which they expend to change the environment An agent without tokens dies

Слайд 31
Описание слайда:
Initial State Flat World bellow a waterline Representation as a height map A single coastline agent on the boarder of the map

Слайд 32
Описание слайда:
Coastline Agent Starts with a seed location, a preferred direction (repulsor, attactor points), a set of tokens, and a number of points it is responsible for rising from the seas Capable of Producing Other Agents Bifocates Hands them a set of tokens (reducing its own) New agent is given a different repulsor and attactor Scores a point in the map P by dr(P)-da(P)+3de(P) Dr – square of the distance to the repulsor Da – square of the distance to the attractor De – square of the distance to the edges Wants to move close to the center

Слайд 33
Описание слайда:
Coastline Agent When done subdivision will begin to spend tokens Selects a random point in the space it is working within and evaluates the adjacent points The point with the highest score is filled in as part of the island Process continues till all tokens are spent

Слайд 34
Описание слайда:
Smoothing Agent Makes a random walk about the space and changes a point to the weighted height of its neighbours in a Moore Neighbourhood (i.e. the 8 cells about the midpoint

Слайд 35
Описание слайда:
Beach Agents Search the area on the coastline and reduce their height Has a limit on how high it will climb Mountains beside the water will form cliffs Makes random walks inland and will not progress father than a limit Beaches should not extend in too deep

Слайд 36
Описание слайда:

Слайд 37
Описание слайда:
Mountain Agents Starts at a random location and has a preferred direction of travel Will move toward that point rising the land like a V to either side of the walk Will continue on their path unless blocked by water

Слайд 38
Описание слайда:
Hill Agents Similar to Mountain agents Expend more tokens for each increase in height than Mountains

Слайд 39
Описание слайда:
River Agents Begin on the coastline Will walk from the coastline to a selected mountain point Will stop their walk if the mountain is too far away If the mountain is too close If there is no uphill or equal point ahead

Слайд 40
Описание слайда:

Слайд 41
Описание слайда:
Ashlock and McGuiness 2013 Evolutionary Approach to Landscapes Matches a Target functions – an ideal landscape Allows for variation about this idea Limited Application unless there is a placement of landscape ideals Create a number of functions with desired properties (craters, mountains, rivers) Merge these functions via some method F=Max(f1,f2,f3,…,fn) Use the evolution to ensure a ‘interesting skinning’ Huge space savings – hold an agent not the texture

Слайд 42
Описание слайда:
Method Recursive quartering of the map space Automation holds a state for each quarter and a multiplier The automation recusively calls itself in each location applying first an increase to the affected area equal to the automation value times the current multipliers Multipliers are <1, it will progressively make smaller changes to smaller areas Final height map is then interpolated

Слайд 43
Описание слайда:
Automation Representation is an automation of transitions and actions Actions are dependant upon which quarter the machine is resting within, each quadrant taking a different Completely deterministic

Слайд 44
Описание слайда:
EA System Create a randomized population made up of chromosomes, data structures which encode a potential solution Until <Done>, based on a stopping criteria Find an objective/fitness score for each member of the population Select members to act upon using some variation operators Apply operations on the members Crossover Mutations Replace some members of the population with these children from the variation operators Keep some members from the previous population in the new population, i.e. elitism/inheritance

Слайд 45
Описание слайда:
Crossover in a GA on Strings

Слайд 46
Описание слайда:
Crossover and Mutation Operations Treats the structure as linear about states Two point crossover on states in the machine Mutations change state transitions and make small changes to the multiplier in the range [-0.1,0.1]

Слайд 47
Описание слайда:
Evaluation Against a Target Target is the ideal function For each of the points it is measured against the ideal Root Mean Squared Error (RMS-error) Holds all errors at equal value on the scale Residuals Measure was used in the NETFLIX prediction prize as the evaluator between the method and the

Слайд 48
Описание слайда:

Слайд 49
Описание слайда:
Beyond Squares Hex based Games instead of squares Height map values -> biomes

Слайд 50
Описание слайда:
Civ 5?

Слайд 51
Описание слайда:
Factals

Слайд 52
Описание слайда:
FracTals Self Similar Mathematical Structures Recursive Definitions Create structures which have interesting complexity from simple rules

Слайд 53
Описание слайда:
Koch Curve Each line has a triangle placed in the centre recursively Length tends to infinity

Слайд 54
Описание слайда:
Midpoint Displacement Fractal Midpoint_Displacement(Startx,Endx,Run) Select the midpoint Midx<-Startx + (Endx – StartX)/2 Add to the height of the midpoint a random value which is controlled by the number of runs (higher = less) Midx.height = Midx.height+RandD(Run); Recuse over the two halves of the space Midpoint_Displacement(Midx,Endx,Run+1) Midpoint_Displacement(Startx,Midx,Run+1) Can be made Iterative – pregen the run values

Слайд 55
Описание слайда:

Слайд 56
Описание слайда:
Diamond Square Algorithm Fournier et al. (1982), purposed for terrain by Gavin (1986) Four Seeding Values - one on each corner of the generation space Extension of the ideas from the midpoint displacement moving it into 3 dimensions

Слайд 57
Описание слайда:
Diamond-SQuare Average over the 4 points (3 if on edge) Add a random value Square-step Find the midpoint of a square of points Add a random value Diamond Step Find the midpoint of a diamond of points Add a random value Alternate between Diamonds and Squares

Слайд 58
Описание слайда:
DSFactal DSFractal(startx,starty,endx,endy,run) midx<-startx+(endx-startx)/2 midy<-starty+(endy-starty)/2 Square(startx,starty,endx,endy,midx,midy) Diamonds(startx,starty,endx,endy,midx,midy) DSFactal(startx,starty,midx,midy) DSFactal(midx,starty,endx,midy) DSFactal(startx,midy,midx,endy) DSFactal(midx,midy,endx,endy)

Слайд 59
Описание слайда:

Слайд 60
Описание слайда:
Torus x Mod Xn y Mod Yn Note in C/C++ that mod is defined to allow for negative values, so rolling over the side onto the negatives will return something which cannot be used to index our array (v-1)+n Mod n

Слайд 61
Описание слайда:
Brown et al. (2011) Fractal Photomosaic images Idea – to tile an image with ‘photos’ made from fractals Computer Art

Слайд 62
Описание слайда:

Слайд 63
Описание слайда:
Mosacs Coloured Shards of Pottery, Stone, or Glass plastered to walls Mathematical and Geometric Patterns Popular in Islamic Art

Слайд 64
Описание слайда:
Photo Mosaics First algorithmic version by R. Silvers Holds Patent on his process for creation and trademark Thesis is Robert Silvers “Photomosaics: Putting Pictures in Their Place” MIT 1996. Sub-picture Resolution Colour and Semantic Channels

Слайд 65
Описание слайда:
Making a Photo Mosaic Break Images into Blocks Take a set of ‘photos’ This can be ‘generated images’ For each block in the image, search through the set and test against the target for closeness RMS Error Structurally

Слайд 66
Описание слайда:
Lenna Image Scanned in from a Playboy Centerfold Lena Söderberg in 1973 (Nov. 72 issue) photographed by Dwight Hooker Commonly used test image in graphical processing Canonical Test Image 512x512 pixels, human face Has lead to some issues in the field regarding it as sexist Lena attended the 50th Anniversary of the Society for Imaging Science and Technology

Слайд 67
Описание слайда:

Слайд 68
Описание слайда:

Слайд 69
Описание слайда:
Mandelbrot Set Defined on the complex number set A point in the complex set, , is considered part of the Mandelbrot set if the walk defined by does not approach infinity If any point on this walk >2, then we know it is going to escape Keep a record of this point – it is the escape point (we will use this to colour.

Слайд 70
Описание слайда:

Слайд 71
Описание слайда:
Data Structure X,Y values of the location of the start of the window on the fractal L defining the length of the window – zoom Two Values for each of the 3 colour channels to define the colouring algorithm Multiplier Adder

Слайд 72
Описание слайда:
Colouring Colouring based on the escape value of the factal Colouring is defined per channel Red Green Blue 0-255 128*cos(S*n*P)+127

Слайд 73
Описание слайда:
Search Through Fractals Genetic Algorithm Image Structure in box and Colour – Defined by Fractal RMS error between pixel colour and Each Box searched on separately Builds the image box by box

Слайд 74
Описание слайда:
Expanding on These Techniques Target v. generation Animation of the process? Growth into final form? Cell Shaded Games Alternative technique other than realistic


Скачать презентацию на тему Re-definition of the generator можно ниже:

Похожие презентации