git链接如下 https://github.com/xviniette/FlappyLearn
是一个教电脑自己玩游戏的算法
因为是跨考来的所以包括基础语法在内的很多东西都不懂，请尽可能多的注释、解释一下，或者给出可以参考的材料，谢谢！
/** 以下是Neuroevolution.js
* Provides a set of classes and methods for handling Neuroevolution and
* genetic algorithms.
*
* @param {options} An object of options for Neuroevolution.
*/
var Neuroevolution = function (options) {
var self = this; // reference to the top scope of this module
// Declaration of module parameters (options) and default values
self.options = {
/**
* Logistic activation function.
*
* @param {a} Input value.
* @return Logistic function output.
*/
activation: function (a) {
ap = (-a) / 1;
return (1 / (1 + Math.exp(ap)))
},
/**
* Returns a random value between -1 and 1.
*
* @return Random value.
*/
randomClamped: function () {
return Math.random() * 2 - 1;
},
// various factors and parameters (along with default values).
network: [1, [1], 1], // Perceptron network structure (1 hidden
// layer).
population: 50, // Population by generation.
elitism: 0.2, // Best networks kepts unchanged for the next
// generation (rate).
randomBehaviour: 0.2, // New random networks for the next generation
// (rate).
mutationRate: 0.1, // Mutation rate on the weights of synapses.
mutationRange: 0.5, // Interval of the mutation changes on the
// synapse weight.
historic: 0, // Latest generations saved.
lowHistoric: false, // Only save score (not the network).
scoreSort: -1, // Sort order (-1 = desc, 1 = asc).
nbChild: 1 // Number of children by breeding.
}
/**
* Override default options.
*
* @param {options} An object of Neuroevolution options.
* @return void
*/
self.set = function (options) {
for (var i in options) {
if (this.options[i] != undefined) { // Only override if the passed in value
// is actually defined.
self.options[i] = options[i];
}
}
}
// Overriding default options with the pass in options
self.set(options);
/*NEURON**********************************************************************/
/**
* Artificial Neuron class
*
* @constructor
*/
var Neuron = function () {
this.value = 0;
this.weights = [];
}
/**
* Initialize number of neuron weights to random clamped values.
*
* @param {nb} Number of neuron weights (number of inputs).
* @return void
*/
Neuron.prototype.populate = function (nb) {
this.weights = [];
for (var i = 0; i < nb; i++) {
this.weights.push(self.options.randomClamped());
}
}
/*LAYER***********************************************************************/
/**
* Neural Network Layer class.
*
* @constructor
* @param {index} Index of this Layer in the Network.
*/
var Layer = function (index) {
this.id = index || 0;
this.neurons = [];
}
/**
* Populate the Layer with a set of randomly weighted Neurons.
*
* Each Neuron be initialied with nbInputs inputs with a random clamped
* value.
*
* @param {nbNeurons} Number of neurons.
* @param {nbInputs} Number of inputs.
* @return void
*/
Layer.prototype.populate = function (nbNeurons, nbInputs) {
this.neurons = [];
for (var i = 0; i < nbNeurons; i++) {
var n = new Neuron();
n.populate(nbInputs);
this.neurons.push(n);
}
}
/*NEURAL NETWORK**************************************************************/
/**
* Neural Network class
*
* Composed of Neuron Layers.
*
* @constructor
*/
var Network = function () {
this.layers = [];
}
/**
* Generate the Network layers.
*
* @param {input} Number of Neurons in Input layer.
* @param {hidden} Number of Neurons per Hidden layer.
* @param {output} Number of Neurons in Output layer.
* @return void
*/
Network.prototype.perceptronGeneration = function (input, hiddens, output) {
var index = 0;
var previousNeurons = 0;
var layer = new Layer(index);
layer.populate(input, previousNeurons); // Number of Inputs will be set to
// 0 since it is an input layer.
previousNeurons = input; // number of input is size of previous layer.
this.layers.push(layer);
index++;
for (var i in hiddens) {
// Repeat same process as first layer for each hidden layer.
var layer = new Layer(index);
layer.populate(hiddens[i], previousNeurons);
previousNeurons = hiddens[i];
this.layers.push(layer);
index++;
}
var layer = new Layer(index);
layer.populate(output, previousNeurons); // Number of input is equal to
// the size of the last hidden
// layer.
this.layers.push(layer);
}
/**
* Create a copy of the Network (neurons and weights).
*
* Returns number of neurons per layer and a flat array of all weights.
*
* @return Network data.
*/
Network.prototype.getSave = function () {
var datas = {
neurons: [], // Number of Neurons per layer.
weights: [] // Weights of each Neuron's inputs.
};
for (var i in this.layers) {
datas.neurons.push(this.layers[i].neurons.length);
for (var j in this.layers[i].neurons) {
for (var k in this.layers[i].neurons[j].weights) {
// push all input weights of each Neuron of each Layer into a flat
// array.
datas.weights.push(this.layers[i].neurons[j].weights[k]);
}
}
}
return datas;
}
/**
* Apply network data (neurons and weights).
*
* @param {save} Copy of network data (neurons and weights).
* @return void
*/
Network.prototype.setSave = function (save) {
var previousNeurons = 0;
var index = 0;
var indexWeights = 0;
this.layers = [];
for (var i in save.neurons) {
// Create and populate layers.
var layer = new Layer(index);
layer.populate(save.neurons[i], previousNeurons);
for (var j in layer.neurons) {
for (var k in layer.neurons[j].weights) {
// Apply neurons weights to each Neuron.
layer.neurons[j].weights[k] = save.weights[indexWeights];
indexWeights++; // Increment index of flat array.
}
}
previousNeurons = save.neurons[i];
index++;
this.layers.push(layer);
}
}
/**
* Compute the output of an input.
*
* @param {inputs} Set of inputs.
* @return Network output.
*/
Network.prototype.compute = function (inputs) {
// Set the value of each Neuron in the input layer.
for (var i in inputs) {
if (this.layers[0] && this.layers[0].neurons[i]) {
this.layers[0].neurons[i].value = inputs[i];
}
}
var prevLayer = this.layers[0]; // Previous layer is input layer.
for (var i = 1; i < this.layers.length; i++) {
for (var j in this.layers[i].neurons) {
// For each Neuron in each layer.
var sum = 0;
for (var k in prevLayer.neurons) {
// Every Neuron in the previous layer is an input to each Neuron in
// the next layer.
sum += prevLayer.neurons[k].value *
this.layers[i].neurons[j].weights[k];
}
// Compute the activation of the Neuron.
this.layers[i].neurons[j].value = self.options.activation(sum);
}
prevLayer = this.layers[i];
}
// All outputs of the Network.
var out = [];
var lastLayer = this.layers[this.layers.length - 1];
for (var i in lastLayer.neurons) {
out.push(lastLayer.neurons[i].value);
}
return out;
}
/*GENOME**********************************************************************/
/**
* Genome class.
*
* Composed of a score and a Neural Network.
*
* @constructor
*
* @param {score}
* @param {network}
*/
var Genome = function (score, network) {
this.score = score || 0;
this.network = network || null;
}
/*GENERATION******************************************************************/
/**
* Generation class.
*
* Composed of a set of Genomes.
*
* @constructor
*/
var Generation = function () {
this.genomes = [];
}
/**
* Add a genome to the generation.
*
* @param {genome} Genome to add.
* @return void.
*/
Generation.prototype.addGenome = function (genome) {
// Locate position to insert Genome into.
// The gnomes should remain sorted.
for (var i = 0; i < this.genomes.length; i++) {
// Sort in descending order.
if (self.options.scoreSort < 0) {
if (genome.score > this.genomes[i].score) {
break;
}
// Sort in ascending order.
} else {
if (genome.score < this.genomes[i].score) {
break;
}
}
}
// Insert genome into correct position.
this.genomes.splice(i, 0, genome);
}
/**
* Breed to genomes to produce offspring(s).
*
* @param {g1} Genome 1.
* @param {g2} Genome 2.
* @param {nbChilds} Number of offspring (children).
*/
Generation.prototype.breed = function (g1, g2, nbChilds) {
var datas = [];
for (var nb = 0; nb < nbChilds; nb++) {
// Deep clone of genome 1.
var data = JSON.parse(JSON.stringify(g1));
for (var i in g2.network.weights) {
// Genetic crossover
// 0.5 is the crossover factor.
// FIXME Really should be a predefined constant.
if (Math.random() <= 0.5) {
data.network.weights[i] = g2.network.weights[i];
}
}
// Perform mutation on some weights.
for (var i in data.network.weights) {
if (Math.random() <= self.options.mutationRate) {
data.network.weights[i] += Math.random() *
self.options.mutationRange *
2 -
self.options.mutationRange;
}
}
datas.push(data);
}
return datas;
}
/**
* Generate the next generation.
*
* @return Next generation data array.
*/
Generation.prototype.generateNextGeneration = function () {
var nexts = [];
for (var i = 0; i < Math.round(self.options.elitism *
self.options.population); i++) {
if (nexts.length < self.options.population) {
// Push a deep copy of ith Genome's Nethwork.
nexts.push(JSON.parse(JSON.stringify(this.genomes[i].network)));
}
}
for (var i = 0; i < Math.round(self.options.randomBehaviour *
self.options.population); i++) {
var n = JSON.parse(JSON.stringify(this.genomes[0].network));
for (var k in n.weights) {
n.weights[k] = self.options.randomClamped();
}
if (nexts.length < self.options.population) {
nexts.push(n);
}
}
var max = 0;
while (true) {
for (var i = 0; i < max; i++) {
// Create the children and push them to the nexts array.
var childs = this.breed(this.genomes[i], this.genomes[max],
(self.options.nbChild > 0 ? self.options.nbChild : 1));
for (var c in childs) {
nexts.push(childs[c].network);
if (nexts.length >= self.options.population) {
// Return once number of children is equal to the
// population by generatino value.
return nexts;
}
}
}
max++;
if (max >= this.genomes.length - 1) {
max = 0;
}
}
}
/*GENERATIONS*****************************************************************/
/**
* Generations class.
*
* Hold's previous Generations and current Generation.
*
* @constructor
*/
var Generations = function () {
this.generations = [];
var currentGeneration = new Generation();
}
/**
* Create the first generation.
*
* @param {input} Input layer.
* @param {input} Hidden layer(s).
* @param {output} Output layer.
* @return First Generation.
*/
Generations.prototype.firstGeneration = function (input, hiddens, output) {
// FIXME input, hiddens, output unused.
var out = [];
for (var i = 0; i < self.options.population; i++) {
// Generate the Network and save it.
var nn = new Network();
nn.perceptronGeneration(self.options.network[0],
self.options.network[1],
self.options.network[2]);
out.push(nn.getSave());
}
this.generations.push(new Generation());
return out;
}
/**
* Create the next Generation.
*
* @return Next Generation.
*/
Generations.prototype.nextGeneration = function () {
if (this.generations.length == 0) {
// Need to create first generation.
return false;
}
var gen = this.generations[this.generations.length - 1]
.generateNextGeneration();
this.generations.push(new Generation());
return gen;
}
/**
* Add a genome to the Generations.
*
* @param {genome}
* @return False if no Generations to add to.
*/
Generations.prototype.addGenome = function (genome) {
// Can't add to a Generation if there are no Generations.
if (this.generations.length == 0) return false;
// FIXME addGenome returns void.
return this.generations[this.generations.length - 1].addGenome(genome);
}
/*SELF************************************************************************/
self.generations = new Generations();
/**
* Reset and create a new Generations object.
*
* @return void.
*/
self.restart = function () {
self.generations = new Generations();
}
/**
* Create the next generation.
*
* @return Neural Network array for next Generation.
*/
self.nextGeneration = function () {
var networks = [];
if (self.generations.generations.length == 0) {
// If no Generations, create first.
networks = self.generations.firstGeneration();
} else {
// Otherwise, create next one.
networks = self.generations.nextGeneration();
}
// Create Networks from the current Generation.
var nns = [];
for (var i in networks) {
var nn = new Network();
nn.setSave(networks[i]);
nns.push(nn);
}
if (self.options.lowHistoric) {
// Remove old Networks.
if (self.generations.generations.length >= 2) {
var genomes =
self.generations
.generations[self.generations.generations.length - 2]
.genomes;
for (var i in genomes) {
delete genomes[i].network;
}
}
}
if (self.options.historic != -1) {
// Remove older generations.
if (self.generations.generations.length > self.options.historic + 1) {
self.generations.generations.splice(0,
self.generations.generations.length - (self.options.historic + 1));
}
}
return nns;
}
/**
* Adds a new Genome with specified Neural Network and score.
*
* @param {network} Neural Network.
* @param {score} Score value.
* @return void.
*/
self.networkScore = function (network, score) {
self.generations.addGenome(new Genome(score, network.getSave()));
}
}
/*以下是game.js*/
(function() {
var timeouts = [];
var messageName = "zero-timeout-message";
function setZeroTimeout(fn) {
timeouts.push(fn);
window.postMessage(messageName, "*");
}
function handleMessage(event) {
if (event.source == window && event.data == messageName) {
event.stopPropagation();
if (timeouts.length > 0) {
var fn = timeouts.shift();
fn();
}
}
}
window.addEventListener("message", handleMessage, true);
window.setZeroTimeout = setZeroTimeout;
})();
var Neuvol;
var game;
var FPS = 60;
var maxScore=0;
var images = {};
var speed = function(fps){
FPS = parseInt(fps);
}
var loadImages = function(sources, callback){
var nb = 0;
var loaded = 0;
var imgs = {};
for(var i in sources){
nb++;
imgs[i] = new Image();
imgs[i].src = sources[i];
imgs[i].onload = function(){
loaded++;
if(loaded == nb){
callback(imgs);
}
}
}
}
var Bird = function(json){
this.x = 80;
this.y = 250;
this.width = 40;
this.height = 30;
this.alive = true;
this.gravity = 0;
this.velocity = 0.3;
this.jump = -6;
this.init(json);
}
Bird.prototype.init = function(json){
for(var i in json){
this[i] = json[i];
}
}
Bird.prototype.flap = function(){
this.gravity = this.jump;
}
Bird.prototype.update = function(){
this.gravity += this.velocity;
this.y += this.gravity;
}
Bird.prototype.isDead = function(height, pipes){
if(this.y >= height || this.y + this.height <= 0){
return true;
}
for(var i in pipes){
if(!(
this.x > pipes[i].x + pipes[i].width ||
this.x + this.width < pipes[i].x ||
this.y > pipes[i].y + pipes[i].height ||
this.y + this.height < pipes[i].y
)){
return true;
}
}
}
var Pipe = function(json){
this.x = 0;
this.y = 0;
this.width = 50;
this.height = 40;
this.speed = 3;
this.init(json);
}
Pipe.prototype.init = function(json){
for(var i in json){
this[i] = json[i];
}
}
Pipe.prototype.update = function(){
this.x -= this.speed;
}
Pipe.prototype.isOut = function(){
if(this.x + this.width < 0){
return true;
}
}
var Game = function(){
this.pipes = [];
this.birds = [];
this.score = 0;
this.canvas = document.querySelector("#flappy");
this.ctx = this.canvas.getContext("2d");
this.width = this.canvas.width;
this.height = this.canvas.height;
this.spawnInterval = 90;
this.interval = 0;
this.gen = [];
this.alives = 0;
this.generation = 0;
this.backgroundSpeed = 0.5;
this.backgroundx = 0;
this.maxScore = 0;
}
Game.prototype.start = function(){
this.interval = 0;
this.score = 0;
this.pipes = [];
this.birds = [];
this.gen = Neuvol.nextGeneration();
for(var i in this.gen){
var b = new Bird();
this.birds.push(b)
}
this.generation++;
this.alives = this.birds.length;
}
Game.prototype.update = function(){
this.backgroundx += this.backgroundSpeed;
var nextHoll = 0;
if(this.birds.length > 0){
for(var i = 0; i < this.pipes.length; i+=2){
if(this.pipes[i].x + this.pipes[i].width > this.birds[0].x){
nextHoll = this.pipes[i].height/this.height;
break;
}
}
}
for(var i in this.birds){
if(this.birds[i].alive){
var inputs = [
this.birds[i].y / this.height,
nextHoll
];
var res = this.gen[i].compute(inputs);
if(res > 0.5){
this.birds[i].flap();
}
this.birds[i].update();
if(this.birds[i].isDead(this.height, this.pipes)){
this.birds[i].alive = false;
this.alives--;
//console.log(this.alives);
Neuvol.networkScore(this.gen[i], this.score);
if(this.isItEnd()){
this.start();
}
}
}
}
for(var i = 0; i < this.pipes.length; i++){
this.pipes[i].update();
if(this.pipes[i].isOut()){
this.pipes.splice(i, 1);
i--;
}
}
if(this.interval == 0){
var deltaBord = 50;
var pipeHoll = 120;
var hollPosition = Math.round(Math.random() * (this.height - deltaBord * 2 - pipeHoll)) + deltaBord;
this.pipes.push(new Pipe({x:this.width, y:0, height:hollPosition}));
this.pipes.push(new Pipe({x:this.width, y:hollPosition+pipeHoll, height:this.height}));
}
this.interval++;
if(this.interval == this.spawnInterval){
this.interval = 0;
}
this.score++;
this.maxScore = (this.score > this.maxScore) ? this.score : this.maxScore;
var self = this;
if(FPS == 0){
setZeroTimeout(function(){
self.update();
});
}else{
setTimeout(function(){
self.update();
}, 1000/FPS);
}
}
Game.prototype.isItEnd = function(){
for(var i in this.birds){
if(this.birds[i].alive){
return false;
}
}
return true;
}
Game.prototype.display = function(){
this.ctx.clearRect(0, 0, this.width, this.height);
for(var i = 0; i < Math.ceil(this.width / images.background.width) + 1; i++){
this.ctx.drawImage(images.background, i * images.background.width - Math.floor(this.backgroundx%images.background.width), 0)
}
for(var i in this.pipes){
if(i%2 == 0){
this.ctx.drawImage(images.pipetop, this.pipes[i].x, this.pipes[i].y + this.pipes[i].height - images.pipetop.height, this.pipes[i].width, images.pipetop.height);
}else{
this.ctx.drawImage(images.pipebottom, this.pipes[i].x, this.pipes[i].y, this.pipes[i].width, images.pipetop.height);
}
}
this.ctx.fillStyle = "#FFC600";
this.ctx.strokeStyle = "#CE9E00";
for(var i in this.birds){
if(this.birds[i].alive){
this.ctx.save();
this.ctx.translate(this.birds[i].x + this.birds[i].width/2, this.birds[i].y + this.birds[i].height/2);
this.ctx.rotate(Math.PI/2 * this.birds[i].gravity/20);
this.ctx.drawImage(images.bird, -this.birds[i].width/2, -this.birds[i].height/2, this.birds[i].width, this.birds[i].height);
this.ctx.restore();
}
}
this.ctx.fillStyle = "white";
this.ctx.font="20px Oswald, sans-serif";
this.ctx.fillText("Score : "+ this.score, 10, 25);
this.ctx.fillText("Max Score : "+this.maxScore, 10, 50);
this.ctx.fillText("Generation : "+this.generation, 10, 75);
this.ctx.fillText("Alive : "+this.alives+" / "+Neuvol.options.population, 10, 100);
var self = this;
requestAnimationFrame(function(){
self.display();
});
}
window.onload = function(){
var sprites = {
bird:"./img/bird.png",
background:"./img/background.png",
pipetop:"./img/pipetop.png",
pipebottom:"./img/pipebottom.png"
}
var start = function(){
Neuvol = new Neuroevolution({
population:50,
network:[2, [2], 1],
});
game = new Game();
game.start();
game.update();
game.display();
}
loadImages(sprites, function(imgs){
images = imgs;
start();
})
}
<!DOCTYPE html>
<html>
<head>
<title>NeuroEvolution : Flappy Bird</title>
<link href='https://fonts.googleapis.com/css?family=Oswald' rel='stylesheet' type='text/css'>
</head>
<body>
<canvas id="flappy" width="500" height="512"></canvas> <br/>
<button onclick="speed(60)">x1</button>
<button onclick="speed(120)">x2</button>
<button onclick="speed(180)">x3</button>
<button onclick="speed(300)">x5</button>
<button onclick="speed(0)">MAX</button>
<br/>
<a href="http://github.com/xviniette/FlappyLearning">GitHub Repository</a>
<script src = "Neuroevolution.js"></script>
<script src = "game.js"></script>
</body>
</html>
