This project is a practical application and helps beginners to learn about Artificial Intelligence, Neural Network and Genetic Algorithm.
Introduction
Artificial Intelligence impacts human life in many ways nowadays. An example is in the auto industry; many companies are trying to make their cars smarter. The cars can self-drive, avoid obstacles, find destinations … without controls from human. This paper is about a car simulation program in which the car itself will move without any controls from outside. The approach uses a Neural Network and a Genetic Algorithm to train the car by making the car learn after each time it fails to finish the track.
Using the Code
1) FPS
Every computer has different speeds so we need a mechanism to normalize that to make the game run at the same speed in any computer. We have two main methods: update and render. Usually, the game runs at 60 fps so the update method will be called 60 times per second and the render method will be called as fast as the computer’s speed.
package com.auto.car;
import java.awt.BasicStroke;
import java.awt.Canvas;
import java.awt.Dimension;
import java.awt.Graphics2D;
import java.awt.event.KeyEvent;
import java.awt.image.BufferStrategy;
import java.awt.image.BufferedImage;
import java.awt.image.DataBufferInt;
import javax.swing.JFrame;
import com.auto.algorithm.HelperFunction;
import com.auto.car.entity.EntityManager;
import com.auto.graphics.Screen;
import com.auto.input.Keyboard;
import com.auto.input.Mouse;
public class CarDemo extends Canvas implements Runnable {
private static final long serialVersionUID = 1L;
private static int width = 600;
private static int height = width * 9 / 16;
public static int scale = 2;
private Thread thread;
private JFrame frame;
private boolean running = false;
private BufferedImage image = new BufferedImage(width, height,
BufferedImage.TYPE_INT_RGB);
private int[] pixels = ((DataBufferInt) image.getRaster().getDataBuffer())
.getData();
private Screen screen;
private Keyboard keyboard;
private EntityManager entityManager;
public CarDemo() {
Dimension size = new Dimension(width * scale, height * scale);
setPreferredSize(size);
screen = new Screen(width, height);
frame = new JFrame();
Mouse mouse = new Mouse();
addMouseListener(mouse);
addMouseMotionListener(mouse);
keyboard = new Keyboard();
addKeyListener(keyboard);
entityManager = new EntityManager();
}
public synchronized void start() {
thread = new Thread(this, "Auto Car");
running = true;
thread.start();
}
public synchronized void stop() {
running = false;
try {
System.out.println("Goodbye");
thread.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public static int fps = 60;
@Override
public void run() {
long lastTime = System.nanoTime();
long timer = System.currentTimeMillis();
double deltaTime = 0;
int frameCount = 0;
int updateCount = 0;
requestFocus();
while (running) {
double nanoSecondsPerCount = 1000000000.0 / fps;
long now = System.nanoTime();
deltaTime += (now - lastTime) / nanoSecondsPerCount;
lastTime = now;
while (deltaTime >= 1) {
update();
updateCount++;
deltaTime--;
}
render();
frameCount++;
if (System.currentTimeMillis() - timer > 1000) {
timer += 1000;
frame.setTitle(updateCount + "ups, " + frameCount + " frames");
updateCount = 0;
frameCount = 0;
}
}
stop();
}
private void update() {
keyboard.update();
if (keyboard.getKeys()[KeyEvent.VK_ESCAPE]) {
stop();
} else if (keyboard.getKeys()[KeyEvent.VK_R]) {
restartSimulation();
} else if (keyboard.getKeys()[KeyEvent.VK_DOWN]) {
fps -= 1;
fps = (int) HelperFunction
.getValueInRange(fps, 30, 300);
} else if (keyboard.getKeys()[KeyEvent.VK_UP]) {
fps += 1;
fps = (int) HelperFunction
.getValueInRange(fps, 30, 300);
} else if (keyboard.getKeys()[KeyEvent.VK_N]) {
entityManager.nextMapIndex();
} else {
if (keyboard.getKeys()[KeyEvent.VK_SPACE]) {
entityManager.forceToNextAgent();
}
}
entityManager.update();
}
private void restartSimulation() {
entityManager = new EntityManager();
}
private void render() {
BufferStrategy bs = getBufferStrategy();
if (bs == null) {
createBufferStrategy(3);
return;
}
Graphics2D g = (Graphics2D) bs.getDrawGraphics();
screen.setGraphic(g);
entityManager.renderByPixels(screen);
for (int i = 0; i < pixels.length; i++) {
pixels[i] = screen.getPixels()[i];
}
g.setStroke(new BasicStroke(2));
g.drawImage(image, 0, 0, getWidth(), getHeight(), null);
entityManager.renderByGraphics(screen);
screen.dispose();
bs.show();
}
public static int getWindowWidth() {
return width * scale;
}
public static int getWindowHeight() {
return height * scale;
}
public static void main(String[] args) {
CarDemo car = new CarDemo();
car.frame.setResizable(false);
car.frame.setTitle("Auto Car");
car.frame.add(car);
car.frame.pack();
car.frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
car.frame.setLocationRelativeTo(null);
car.frame.setVisible(true);
car.start();
}
}
2) Graphics
The Screen class handles all graphic rendering for the program. There are two ways to render in this program: by manipulating individual pixels or by using built-in functions of the Java library. For the map, manipulating individual pixels is used and for the other objects such as the Car Sprite, the Sensor Line and the Sensor Circle, built-in functions of Java are used to gain better graphics. This class has these main fields: width, height, pixels, xOffset, yOffset and graphics. If we want to manipulate an individual pixel, we will change data in this pixels array. Two values, xOffset and yOffset change when the Car moves around. Because we always need to see the Car on the screen, the Car will stand at a fixed position on the screen; we just need to adjust the offset of the screen to make us feel like the Car is moving. There are five main functions in this class:
renderTile
The renderTile method renders a Tile on screen. It requires as arguments the x, y coordinates of the Tile and the Tile itself.
renderCar
The renderCar method renders the Car object. It requires as arguments the x, y coordinates of the Car, the angle which the Car is heading and the Sprite for the image of the Car.
renderLine
The method renderLine requires the arguments color and x, y for start point and end point to render the line between these points with a specific color.
renderCircle
The method renderCircle requires arguments x, y coordinates for the center of circle, the radius r and the color for this Circle.
dispose
The dispose method is used to dispose the object graphics to release the resource after rendering.
package com.auto.graphics;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.geom.AffineTransform;
import java.awt.image.BufferedImage;
import java.util.ArrayList;
import com.auto.car.CarDemo;
import com.auto.car.level.tile.Tile;
public class Screen {
private int width;
private int height;
private int[] pixels;
private int xOffset, yOffset;
private Graphics2D graphics;
private int scale = CarDemo.scale;
public Screen() {
}
public Screen(int w, int h) {
width = w;
height = h;
pixels = new int[w * h];
}
public int[] getPixels() {
return pixels;
}
public void renderTile(int xPosition, int yPosition, Tile tile) {
xPosition -= xOffset;
yPosition -= yOffset;
for (int yTile = 0; yTile < tile.size; yTile++) {
int yScreen = yTile + yPosition;
for (int xTile = 0; xTile < tile.size; xTile++) {
int xScreen = xTile + xPosition;
if (xScreen < -tile.size || xScreen >= width || yScreen < 0
|| yScreen >= height) {
break;
}
if (xScreen < 0) {
xScreen = 0;
}
pixels[xScreen + yScreen * width] = tile.sprite.getPixels()[xTile
+ yTile * tile.size];
}
}
}
public void renderCar(int xPosition, int yPosition, double angle,
Sprite sprite) {
xPosition -= xOffset;
yPosition -= yOffset;
BufferedImage img = new BufferedImage(Sprite.SIZE, Sprite.SIZE,
BufferedImage.TYPE_INT_ARGB);
for (int ySprite = 0; ySprite < Sprite.SIZE; ySprite++) {
for (int xSprite = 0; xSprite < Sprite.SIZE; xSprite++) {
int color = sprite.getPixels()[(xSprite + ySprite * Sprite.SIZE)];
if (color != 0xffffffff) {
img.setRGB(xSprite, ySprite, color);
}
}
}
AffineTransform reset = new AffineTransform();
reset.rotate(0, 0, 0);
graphics.rotate(angle, (xPosition + Sprite.SIZE / 2) * scale,
(yPosition + Sprite.SIZE / 2) * scale);
graphics.drawImage(img, xPosition * scale, yPosition * scale,
Sprite.SIZE * scale, Sprite.SIZE * scale, null);
graphics.setTransform(reset);
}
public void renderLine(double x, double y, double x2, double y2, Color color) {
graphics.setColor(color);
graphics.drawLine(((int) (x - xOffset + Sprite.SIZE / 2)) * scale,
((int) (y - yOffset + Sprite.SIZE / 2)) * scale, ((int) (x2
- xOffset + Sprite.SIZE / 2))
* scale, ((int) (y2 - yOffset + Sprite.SIZE / 2))
* scale);
}
public void renderCircle(double x, double y, double r, Color color) {
graphics.setColor(color);
graphics.drawOval((int) (x - xOffset - r + Sprite.SIZE / 2) * scale,
(int) (y - r - yOffset + Sprite.SIZE / 2) * scale,
(int) (2 * r * scale), (int) (2 * r * scale));
}
public void setGraphic(Graphics2D g) {
this.graphics = g;
}
public void renderStatistics(ArrayList<String> info) {
graphics.setColor(Color.black);
graphics.setFont(graphics.getFont().deriveFont(20f));
graphics.drawString(info.get(0), 700, 20);
graphics.drawString(info.get(1), 700, 40);
graphics.drawString(info.get(2), 700, 60);
graphics.drawString(info.get(3), 700, 80);
}
public void dispose() {
graphics.dispose();
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
public int getWidth() {
return width;
}
public void setWidth(int width) {
this.width = width;
}
public void setOffset(int xOffset, int yOffset) {
this.xOffset = xOffset;
this.yOffset = yOffset;
}
public int getXOffset() {
return xOffset;
}
public int getYOffset() {
return yOffset;
}
}
The map uses 16x16 tiles to tile the screen. There are three kind of tiles in this program: GrassTile, BrickTile and VoidTile and they are all inherited from the Tile class. The GrassTile and the VoidTile are non-collided tiles; meanwhile, the BrickTile is collided. The BrickTile is used to build the track’s wall so the Car can detect the collision. The VoidTile will be used to cover the places where there is nothing to render on the screen.
package com.auto.car.level.tile;
import com.auto.graphics.Screen;
import com.auto.graphics.Sprite;
public class Tile {
public int x, y;
public Sprite sprite;
public int size;
public static Tile grass = new GrassTile(Sprite.grass,16);
public static Tile brick = new BrickTile(Sprite.brick,16);
public static Tile voidTile = new VoidTile(Sprite.voidSprite,16);
public static final int grassColor = 0xff00ff00;
public static final int brickColor = 0xffFFD800;
public Tile(Sprite sprite, int size) {
this.sprite = sprite;
this.size = size;
}
public void render(int x, int y, Screen screen) {
}
public boolean solid() {
return false;
}
}
package com.auto.car.level.tile;
import com.auto.graphics.Screen;
import com.auto.graphics.Sprite;
public class BrickTile extends Tile {
public BrickTile(Sprite sprite, int size) {
super(sprite, size);
}
public void render(int x, int y, Screen screen) {
screen.renderTile(x, y, this);
}
public boolean solid() {
return true;
}
}
package com.auto.car.level.tile;
import com.auto.graphics.Screen;
import com.auto.graphics.Sprite;
public class GrassTile extends Tile {
public GrassTile(Sprite sprite, int size) {
super(sprite, size);
}
public void render(int x, int y, Screen screen) {
screen.renderTile(x, y, this);
}
}
package com.auto.car.level.tile;
import com.auto.graphics.Screen;
import com.auto.graphics.Sprite;
public class VoidTile extends Tile {
public VoidTile(Sprite sprite, int size) {
super(sprite, size);
}
public void render(int x, int y, Screen screen) {
screen.renderTile(x, y, this);
}
}
(Sprite Sheet)
A Sprite object holds the pixels of a 16x16 image located in the Sprite Sheet. A Sprite is used to design for objects in the program such as Car, Brick or Grass. The Tile class can either load a Sprite image or just simply fill in itself by color. In this program, the VoidTile is just simply filled in by a color meanwhile the Brick, the Grass and the Car Sprite will load images from the SpriteSheet. The background of the Sprite, which is WHITE color, will not be rendered.
package com.auto.graphics;
public class Sprite {
public static final int SIZE = 16;
public static final int SIZE_2BASED = 4;
private int x, y;
private int[] pixels;
private SpriteSheet sheet;
public static Sprite grass = new Sprite(0, 0, SpriteSheet.tiles16x16);
public static Sprite brick = new Sprite(2, 0, SpriteSheet.tiles16x16);
public static Sprite voidSprite = new Sprite(0xE6FFA3);
public static Sprite carSprite = new Sprite(4, 0, SpriteSheet.tiles16x16);
public Sprite(int x, int y, SpriteSheet sheet) {
pixels = new int[SIZE * SIZE];
this.x = x * SIZE;
this.y = y * SIZE;
this.sheet = sheet;
load();
}
public Sprite(int colour) {
pixels = new int[SIZE * SIZE];
setColour(colour);
}
private void setColour(int colour) {
for (int i = 0; i < SIZE * SIZE; i++) {
pixels[i] = colour;
}
}
private void load() {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
pixels[j + i * SIZE] = sheet.pixels[(j + this.x) + (i + this.y)
* sheet.getSize()];
}
}
}
public int[] getPixels() {
return pixels;
}
}
(Level)
Level is a mini map of the tiles. A level loads an image file then based on the color of each individual pixel, it will determine which Tile should be rendered. One pixel in the image will be replaced by 16 pixels of Tile in the program when it is rendered on screen. In this program, the color 0x00FF00 (Green) will represent the GrassTile and the color 0xFFD800 (Dark Yellow) will represent the BrickTile; any other colors that are not defined will be replaced by the VoidTile. The SpawnLevel class is inherited from the Level class and it overrides the method loadLevel. This method will load an image from the path and store data in the array pixels. After that, the colors on the image will be replaced by the Tile to render on the screen. The following picture is a sample of a Level.
package com.auto.car.level;
import com.auto.car.level.tile.Tile;
import com.auto.graphics.Screen;
import com.auto.graphics.Sprite;
public class Level {
protected int width, height;
protected int[] pixels;
public Level(String path) {
loadLevel(path);
}
protected void loadLevel(String path) {
}
public void update() {
}
public void render(int xScroll, int yScroll, Screen screen) {
screen.setOffset(xScroll, yScroll);
int xMostLeft = xScroll >> Sprite.SIZE_2BASED;
int xMostRight = (xScroll + screen.getWidth() + Sprite.SIZE) >> Sprite.SIZE_2BASED;
int yMostTop = yScroll >> Sprite.SIZE_2BASED;
int yMostBottom = (yScroll + screen.getHeight() + Sprite.SIZE) >> Sprite.SIZE_2BASED;
for (int y = yMostTop; y < yMostBottom; y++) {
for (int x = xMostLeft; x < xMostRight; x++) {
if (x < 0 || y < 0 || x >= width || y >= height) {
Tile.voidTile.render(x << Sprite.SIZE_2BASED,
y << Sprite.SIZE_2BASED, screen);
continue;
}
getTile(x, y).render(x << Sprite.SIZE_2BASED,
y << Sprite.SIZE_2BASED, screen);
}
}
}
public Tile getTile(int x, int y) {
int index = x + y * width;
if (index >= 0 && index < pixels.length) {
switch (pixels[index]) {
case Tile.grassColor:
return Tile.grass;
case Tile.brickColor:
return Tile.brick;
}
}
return Tile.voidTile;
}
}
The Entity class is the parent class of the Car and the Mob classes (Figure 9) (the Mob class stands for Mobile class which creates objects that are movable on the Screen). It has 2 fields for x, y coordinates and getters and setters for x and y.
The Mob class is inherited from the Entity class and it has two functions which are move and isCollided. The Mob object can only move to a new position when there is no collision at that position. To detect a collision, we will detect the Tile at that position. If the Tile is solid, then there is collision; if not, then there is no collision. A Mob object also has a Sprite to render on the screen.
The Car class is inherited from the Mob class. It has information about angle of where the car is heading. Its deltaDistance field is the distance that the car has just moved. And its 5 sensors, EAST, NORTH EAST, NORTH, WEST, NORTH WEST are used to detect the distances from the car to the wall while the Car is moving around the track. The intersections are the intersected points between the 5 sensors and the track. The intersected points will be represented by small yellow circles in this program. After the distances are detected, they will be normalized and sent to the Neural Network to make decisions. The main methods of the Car entity are:
buildFeelers
This method will calculate the coordinates of the head and tail of each feeler. All the feelers’ tails will have the same coordinates with the car’s current position. Other feelers’ heads will be calculated based on the current heading angle of the car.
detectFeelerIntersection
To detect the intersection between a feeler and the wall, first we build a line going through the head and the tail of that feeler. After computing the line’s information, we will iterate from the tail to the head of that feeler to determine the collision point. Here, we need help from function getTile of the Level object. We will pass the coordinates of the points on the line to this function to get out a Tile object. If the Tile object is not null and it is solid, then we have found an intersection between the feeler and the wall right at this point.
update
The car will constantly build the feelers, detect the intersections with the wall, then send data to the Neural Network. The Neural Network will call its update method, then give out the information about left force and right force which help the car turn right or left. The car uses this data to calculate the angle that it will turn and the deltaDistance that it will move then it sends this information to its move method.
render
After two methods, buildFeelers and detectFeelerIntersection are called, this method will use the output of these two methods to draw the Car itself, its sensors’ lines and the intersection circles.
package com.auto.car.entity;
import com.auto.car.level.Level;
import com.auto.graphics.Screen;
public abstract class Entity {
protected int x, y;
protected Level level;
public void update() {
}
public void render(Screen screen) {
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
}
package com.auto.car.entity.mob;
import com.auto.car.entity.Entity;
import com.auto.graphics.Sprite;
public abstract class Mob extends Entity {
protected Sprite sprite;
protected boolean collided = false;
public void move(int xPosition, int yPosition) {
if (xPosition != 0 && yPosition != 0) {
move(xPosition, 0);
move(0, yPosition);
return;
}
if (!isCollided(xPosition, yPosition)) {
x += xPosition;
y += yPosition;
}
}
public void update() {
}
private boolean isCollided(int xPosition, int yPosition) {
for (int corner = 0; corner < 4; corner++) {
int xt = ((x + xPosition) + (corner % 2) * 7 + 5) >> 4;
int yt = ((y + yPosition) + (corner / 2) * 12 + 3) >> 4;
if (level.getTile(xt, yt).solid()) {
collided = true;
}
}
return collided;
}
public void render() {
}
}
package com.auto.car.entity.mob;
import java.awt.Color;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import com.auto.algorithm.NeuralNetwork;
import com.auto.car.entity.EntityManager;
import com.auto.car.level.Level;
import com.auto.car.level.tile.Tile;
import com.auto.graphics.Screen;
import com.auto.graphics.Sprite;
public class Car extends Mob {
public static int FEELER_COUNT = 5;
public static enum SensorFeelers {
FEELER_EAST, FEELER_NORTH_EAST, FEELER_NORTH, FEELER_NORTH_WEST, FEELER_WEST,
};
public static float FEELER_LENGTH = 32.0f;
private double angle;
private double deltaDistance;
private Sensor sensor;
private NeuralNetwork neural;
private Point2D[] intersections;
private double[] normalizedIntersectionDepths;
public int eastIdx = SensorFeelers.FEELER_EAST.ordinal();
public int northEastIdx = SensorFeelers.FEELER_NORTH_EAST.ordinal();
public int northIdx = SensorFeelers.FEELER_NORTH.ordinal();
public int northWestIdx = SensorFeelers.FEELER_NORTH_WEST.ordinal();
public int westIdx = SensorFeelers.FEELER_WEST.ordinal();
public static final float MAX_ROTATION_PER_SECOND = 30.0f / 180;
public class Sensor {
public Point2D[] feelerTails;
public Point2D[] feelerHeads;
public Sensor() {
feelerTails = new Point2D[FEELER_COUNT];
feelerHeads = new Point2D[FEELER_COUNT];
}
}
public Car(int x, int y, double angle, Level lv) {
this.x = x;
this.y = y;
this.angle = angle;
sensor = new Sensor();
level = lv;
buildFeelers();
detectFeelerIntersection();
}
public void setLevel(Level lv) {
level = lv;
}
public void update() {
if (!this.collided) {
buildFeelers();
detectFeelerIntersection();
neural.setInput(normalizedIntersectionDepths);
neural.update();
double leftForce = neural
.getOutput(EntityManager.NeuralNetOuputs.NN_OUTPUT_LEFT_FORCE
.ordinal());
double rightForce = neural
.getOutput(EntityManager.NeuralNetOuputs.NN_OUTPUT_RIGHT_FORCE
.ordinal());
System.out.println("left force: " + leftForce + "-right force: "
+ rightForce);
double leftTheta = MAX_ROTATION_PER_SECOND * leftForce;
double rightTheta = MAX_ROTATION_PER_SECOND * rightForce;
angle += (leftTheta - rightTheta) * 2;
double movingX = Math.sin(angle) * 2;
double movingY = -Math.cos(angle) * 2;
deltaDistance = Math.sqrt(movingX * movingX + movingY * movingY);
move((int) movingX, (int) movingY);
}
}
public Rectangle2D getCarBound() {
return new Rectangle2D.Double(x - Sprite.SIZE / 2, y - Sprite.SIZE / 2,
Sprite.SIZE, Sprite.SIZE);
}
private void buildFeelers() {
for (int i = 0; i < FEELER_COUNT; i++) {
sensor.feelerHeads[i] = new Point2D.Float();
sensor.feelerTails[i] = new Point2D.Float();
sensor.feelerTails[i].setLocation(x, y);
}
sensor.feelerHeads[eastIdx].setLocation(
x + Math.sin(Math.PI - (angle + Math.PI / 2)) * FEELER_LENGTH,
y + Math.cos(Math.PI - (angle + Math.PI / 2)) * FEELER_LENGTH);
sensor.feelerHeads[northEastIdx].setLocation(
x + Math.sin(Math.PI - (angle + Math.PI / 4)) * FEELER_LENGTH,
y + Math.cos(Math.PI - (angle + Math.PI / 4)) * FEELER_LENGTH);
sensor.feelerHeads[northIdx].setLocation(x + Math.sin(Math.PI - angle)
* FEELER_LENGTH, y + Math.cos(Math.PI - angle) * FEELER_LENGTH);
sensor.feelerHeads[northWestIdx].setLocation(
x + Math.sin(Math.PI - (angle - Math.PI / 4)) * FEELER_LENGTH,
y + Math.cos(Math.PI - (angle - Math.PI / 4)) * FEELER_LENGTH);
sensor.feelerHeads[westIdx].setLocation(
x + Math.sin(Math.PI - (angle - Math.PI / 2)) * FEELER_LENGTH,
y + Math.cos(Math.PI - (angle - Math.PI / 2)) * FEELER_LENGTH);
}
public void detectFeelerIntersection() {
intersections = new Point2D[FEELER_COUNT];
normalizedIntersectionDepths = new double[FEELER_COUNT];
for (int k = 0; k < FEELER_COUNT; k++) {
double xStart = sensor.feelerHeads[k].getX();
double xEnd = sensor.feelerTails[k].getX();
double yStart = sensor.feelerHeads[k].getY();
double yEnd = sensor.feelerTails[k].getY();
Line2D line = new Line2D.Double();
line.setLine(sensor.feelerHeads[k], sensor.feelerTails[k]);
double step = 0.001;
double slope = (yStart - yEnd) / (xStart - xEnd);
if (!java.lang.Double.isInfinite(slope)) {
for (double i = xStart; i < xEnd; i += step) {
double j = slope * (i - xEnd) + yEnd;
Tile tile = level.getTile((int) (i + Sprite.SIZE / 2)
/ Sprite.SIZE, (int) (j + Sprite.SIZE / 2)
/ Sprite.SIZE);
if (tile != null) {
if (tile.solid()) {
intersections[k] = new Point2D.Float();
intersections[k].setLocation(i, j);
}
}
}
for (double i = xStart; i > xEnd; i -= step) {
double j = slope * (i - xEnd) + yEnd;
Tile tile = level.getTile((int) (i + Sprite.SIZE / 2)
/ Sprite.SIZE, (int) (j + Sprite.SIZE / 2)
/ Sprite.SIZE);
if (tile != null) {
if (tile.solid()) {
intersections[k] = new Point2D.Float();
intersections[k].setLocation(i, j);
}
}
}
} else {
for (double j = yStart; j < yEnd; j += step) {
Tile tile = level.getTile((int) (xStart + Sprite.SIZE / 2)
/ Sprite.SIZE, (int) (j + Sprite.SIZE / 2)
/ Sprite.SIZE);
if (tile != null) {
if (tile.solid()) {
intersections[k] = new Point2D.Float();
intersections[k].setLocation(xStart, j);
}
}
}
for (double j = yStart; j > yEnd; j -= step) {
Tile tile = level.getTile((int) (xStart + Sprite.SIZE / 2)
/ Sprite.SIZE, (int) (j + Sprite.SIZE / 2)
/ Sprite.SIZE);
if (tile != null) {
if (tile.solid()) {
intersections[k] = new Point2D.Float();
intersections[k].setLocation(xStart, j);
}
}
}
}
if (intersections[k] != null) {
normalizedIntersectionDepths[k] = 1 - (Math.sqrt(Math.pow(x
- intersections[k].getX(), 2)
+ Math.pow(y - intersections[k].getY(), 2)) / FEELER_LENGTH);
} else {
normalizedIntersectionDepths[k] = 0;
}
}
}
public void attach(NeuralNetwork neuralNet) {
this.neural = neuralNet;
}
public void setPosition(Point2D defaultPosition) {
x = (int) defaultPosition.getX();
y = (int) defaultPosition.getY();
}
public void clearFailure() {
collided = false;
}
public boolean hasFailed() {
return collided;
}
public double getDistanceDelta() {
return deltaDistance;
}
public void render(Screen screen) {
screen.renderCar(x, y, angle, Sprite.carSprite);
screen.renderLine(sensor.feelerHeads[eastIdx].getX(),
sensor.feelerHeads[eastIdx].getY(),
sensor.feelerTails[eastIdx].getX(),
sensor.feelerTails[eastIdx].getY(), Color.YELLOW);
screen.renderLine(sensor.feelerHeads[northEastIdx].getX(),
sensor.feelerHeads[northEastIdx].getY(),
sensor.feelerTails[northEastIdx].getX(),
sensor.feelerTails[northEastIdx].getY(), Color.YELLOW);
screen.renderLine(sensor.feelerHeads[northIdx].getX(),
sensor.feelerHeads[northIdx].getY(),
sensor.feelerTails[northIdx].getX(),
sensor.feelerTails[northIdx].getY(), Color.black);
screen.renderLine(sensor.feelerHeads[northWestIdx].getX(),
sensor.feelerHeads[northWestIdx].getY(),
sensor.feelerTails[northWestIdx].getX(),
sensor.feelerTails[northWestIdx].getY(), Color.YELLOW);
screen.renderLine(sensor.feelerHeads[westIdx].getX(),
sensor.feelerHeads[westIdx].getY(),
sensor.feelerTails[westIdx].getX(),
sensor.feelerTails[westIdx].getY(), Color.YELLOW);
screen.renderCircle(x, y, FEELER_LENGTH, Color.YELLOW);
for (int k = 0; k < FEELER_COUNT; k++) {
if (intersections[k] != null) {
screen.renderCircle(intersections[k].getX(),
intersections[k].getY(), 3, Color.YELLOW);
}
}
}
public void setPosition(int x, int y) {
setX(x);
setY(y);
}
3) Genetic Algorithm
A Genetic Algorithm is used to train the Neural Network; it helps the Neural Network give a better decision.
Genome Class
A genome (Figure 10) has 3 pieces of information: ID, fitness and weights. The fitness information is the distance that the car has been able to move without collision and the weights information is the list of random Sigmoid values which are from -1 to 1.
GeneticAlgorithm Class
The GeneticAlgorithm class has a list of Genomes called population. Each population has good genomes with high fitness. Those genomes will be mixed up and mutated to create a new population of genomes. This class has the following main methods:
generateNewPopulation
This function will generate a new population of genomes. The genomes’ weights will be randomly assigned a Sigmoid value; the ID and the fitness values will be assigned to 0.
breedPopulation
This function will generate a new population using old population. First, 4 genomes with high fitness will be chosen from the old population. After that, we will mutate and cross over 4 of them together and add to new population. The left positions of new population will be filled up by a new random Genome.
crossOver
The crossOver function is a function that mixes up 2 genomes and creates 2 other new genomes. To mix them, first we randomly choose the cross over point then split 2 genomes into 4 parts from that point, then mix 4 parts together.
mutate
The mutate function is a function that randomly picks up a gene in a genome and assigns a new value which is the sum of a random Sigmoid value multiplied by the constant MAX_PERMUTATION = 0.3 plus weight of that gene if the Sigmoid value is smaller than MUTATION_RATE = 0.15.
package com.auto.algorithm;
import java.util.ArrayList;
public class Genome {
public int ID;
public double fitness;
public ArrayList<Double> weights;
}
package com.auto.algorithm;
import java.util.ArrayList;
import java.util.Random;
public class GeneticAlgorithm {
public static final float MAX_PERMUTATION = 0.3f;
public static final float MUTATION_RATE = 0.15f;
private int currentGenome;
private int totalPopulation;
private int genomeID;
private int generation;
private ArrayList<Genome> population;
public GeneticAlgorithm() {
currentGenome = -1;
totalPopulation = 0;
genomeID = 0;
generation = 1;
population = new ArrayList<Genome>();
}
public void generateNewPopulation(int totalPop, int totalWeights) {
generation = 1;
clearPopulation();
currentGenome = -1;
totalPopulation = totalPop;
for (int i = 0; i < totalPopulation; i++) {
Genome genome = new Genome();
genome.ID = genomeID;
genome.fitness = 0.0;
genome.weights = new ArrayList<Double>();
for (int j = 0; j < totalWeights; j++) {
genome.weights.add(HelperFunction.RandomSigmoid());
}
genomeID++;
population.add(genome);
}
}
public void setGenomeFitness(double fitness, int index) {
if (index >= population.size() || index < 0)
return;
population.get(index).fitness = fitness;
}
public Genome getNextGenome() {
currentGenome++;
if (currentGenome >= population.size())
return null;
return population.get(currentGenome);
}
public void clearPopulation() {
population.clear();
}
public void breedPopulation() {
ArrayList<Genome> bestGenomes = new ArrayList<Genome>();
bestGenomes = getBestGenomes(4);
ArrayList<Genome> children = new ArrayList<Genome>();
Genome bestGenome = new Genome();
bestGenome.fitness = 0.0;
bestGenome.ID = bestGenomes.get(0).ID;
bestGenome.weights = bestGenomes.get(0).weights;
mutate(bestGenome);
children.add(bestGenome);
ArrayList<Genome> crossedOverGenomes;
crossedOverGenomes = crossOver(bestGenomes.get(0), bestGenomes.get(1));
mutate(crossedOverGenomes.get(0));
mutate(crossedOverGenomes.get(1));
children.add(crossedOverGenomes.get(0));
children.add(crossedOverGenomes.get(1));
crossedOverGenomes = crossOver(bestGenomes.get(0), bestGenomes.get(2));
mutate(crossedOverGenomes.get(0));
mutate(crossedOverGenomes.get(1));
children.add(crossedOverGenomes.get(0));
children.add(crossedOverGenomes.get(1));
crossedOverGenomes = crossOver(bestGenomes.get(0), bestGenomes.get(3));
mutate(crossedOverGenomes.get(0));
mutate(crossedOverGenomes.get(1));
children.add(crossedOverGenomes.get(0));
children.add(crossedOverGenomes.get(1));
crossedOverGenomes = crossOver(bestGenomes.get(1), bestGenomes.get(2));
mutate(crossedOverGenomes.get(0));
mutate(crossedOverGenomes.get(1));
children.add(crossedOverGenomes.get(0));
children.add(crossedOverGenomes.get(1));
crossedOverGenomes = crossOver(bestGenomes.get(1), bestGenomes.get(3));
mutate(crossedOverGenomes.get(0));
mutate(crossedOverGenomes.get(1));
children.add(crossedOverGenomes.get(0));
children.add(crossedOverGenomes.get(1));
int remainingChildren = (totalPopulation - children.size());
for (int i = 0; i < remainingChildren; i++) {
children.add(this.createNewGenome(bestGenomes.get(0).weights.size()));
}
clearPopulation();
population = children;
currentGenome = -1;
generation++;
}
private Genome createNewGenome(int totalWeights) {
Genome genome = new Genome();
genome.ID = genomeID;
genome.fitness = 0.0f;
genome.weights = new ArrayList<Double>();
for (int j = 0; j < totalWeights; j++) {
genome.weights.add(HelperFunction.RandomSigmoid());
}
genomeID++;
return genome;
}
private ArrayList<Genome> crossOver(Genome g1, Genome g2) {
Random random = new Random(System.nanoTime());
int totalWeights = g1.weights.size();
int crossover = Math.abs(random.nextInt()) % totalWeights;
ArrayList<Genome> genomes = new ArrayList<Genome>();
Genome genome1 = new Genome();
genome1.ID = genomeID;
genome1.weights = new ArrayList<Double>();
genomeID++;
Genome genome2 = new Genome();
genome2.ID = genomeID;
genome2.weights = new ArrayList<Double>();
genomeID++;
for (int i = 0; i < crossover; i++) {
genome1.weights.add(g1.weights.get(i));
genome2.weights.add(g2.weights.get(i));
}
for (int i = crossover; i < totalWeights; i++) {
genome1.weights.add(g2.weights.get(i));
genome2.weights.add(g1.weights.get(i));
}
genomes.add(genome1);
genomes.add(genome2);
return genomes;
}
private void mutate(Genome genome) {
for (int i = 0; i < genome.weights.size(); ++i) {
double randomSigmoid = HelperFunction.RandomSigmoid();
if (randomSigmoid < MUTATION_RATE) {
genome.weights.set(i, genome.weights.get(i)
+ (randomSigmoid * MAX_PERMUTATION));
}
}
}
private ArrayList<Genome> getBestGenomes(int totalGenomes) {
int genomeCount = 0;
int runCount = 0;
ArrayList<Genome> bestGenomes = new ArrayList<Genome>();
while (genomeCount < totalGenomes) {
if (runCount > 10) {
break;
}
runCount++;
double bestFitness = 0;
int bestIndex = -1;
for (int i = 0; i < this.totalPopulation; i++) {
if (population.get(i).fitness > bestFitness) {
boolean isUsed = false;
for (int j = 0; j < bestGenomes.size(); j++) {
if (bestGenomes.get(j).ID == population.get(i).ID) {
isUsed = true;
}
}
if (isUsed == false) {
bestIndex = i;
bestFitness = population.get(bestIndex).fitness;
}
}
}
if (bestIndex != -1) {
genomeCount++;
bestGenomes.add(population.get(bestIndex));
}
}
return bestGenomes;
}
public int getCurrentGeneration() {
return generation;
}
public int getCurrentGenomeIndex() {
return currentGenome;
}
}
4) Neural Network
Neuron Class
Neuron is the basic element in the Neural Network. It has two fields which are the numberOfInputs coming to a neuron and values of those inputs which are called weights. In this program, neuron will receive data from the genomes and stores into its weights. These weights will be used by the neuron layers to evaluate output.
Neuronslayer Class
The NeuronsLayer class (Figure 13) contains a list of neurons. It will use those neurons’ weights to evaluate and give out the outputs. There are two types of neurons layer. One is the Hidden Layer and one is the Output Layer. These layers will be managed by the Neural Network. The main method of this class is evaluate method. In this method, we will sum up the value of inputs multiplied by neuron’s weights and add the value of last weight multiplied by a constant BIAS = -1. The purpose of BIAS value is to make sure the output is not 0. After that, the sum will be normalized by Sigmoid function and stored in the outputs.
NeuralNetwork Class
NeuralNetwork class (Figure 14) contains 1 Output Layer and 1 or many Hidden Layers. These are the main methods of this class:
setInput
This method receives the inputs from car’s sensors and stores them.
getOutput
This method receives the index and give out the data at that index.
update
The NeuralNetwork constantly receives data from the sensors of the car, passes that data to Hidden Layer to process, then transfers output to the Output Layer for second processing. After that, the Output Layer will give out the decision back to the car to make a turn.
fromGenome
This function will get weights from genome of GeneticAlgorithm to store in Neurons Layers.
package com.auto.algorithm;
import java.util.ArrayList;
public class Neuron {
protected int numberOfInputs;
protected ArrayList<Double> weights;
public void init(ArrayList<Double> weightsIn, int numOfInputs) {
this.numberOfInputs = numOfInputs;
weights = weightsIn;
}
}
package com.auto.algorithm;
import java.util.ArrayList;
public class NeuronsLayer {
public static final float BIAS = -1.0f;
private int totalNeurons;
private ArrayList<Neuron> neurons;
public void evaluate(ArrayList<Double> inputs, ArrayList<Double> outputs) {
int inputIndex = 0;
for (int i = 0; i < totalNeurons; i++) {
float activation = 0.0f;
int numOfInputs = neurons.get(i).numberOfInputs;
Neuron neuron = neurons.get(i);
for (int j = 0; j < numOfInputs - 1; j++) {
if (inputIndex < inputs.size()) {
activation += inputs.get(inputIndex)
* neuron.weights.get(j);
inputIndex++;
}
}
activation += neuron.weights.get(numOfInputs) * BIAS;
outputs.add(HelperFunction.Sigmoid(activation, 1.0f));
inputIndex = 0;
}
}
public ArrayList<Double> getWeights() {
ArrayList<Double> out = new ArrayList<Double>();
for (int i = 0; i < this.totalNeurons; i++) {
Neuron n = neurons.get(i);
for (int j = 0; j < n.weights.size(); j++) {
out.add(n.weights.get(j));
}
}
return out;
}
public void loadLayer(ArrayList<Neuron> neurons) {
totalNeurons = neurons.size();
this.neurons = neurons;
}
}
package com.auto.algorithm;
import java.util.ArrayList;
public class NeuralNetwork {
private int inputAmount;
private int outputAmount;
private ArrayList<Double> outputs;
private ArrayList<Double> inputs;
private ArrayList<NeuronsLayer> hiddenLayers;
private NeuronsLayer outputLayer;
public NeuralNetwork() {
outputs = new ArrayList<Double>();
inputs = new ArrayList<Double>();
}
public void setInput(double[] normalizedDepths) {
inputs.clear();
for (int i = 0; i < normalizedDepths.length; i++) {
inputs.add(normalizedDepths[i]);
}
}
@SuppressWarnings("unchecked")
public void update() {
outputs.clear();
for (int i = 0; i < hiddenLayers.size(); i++) {
if (i > 0) {
inputs = outputs;
}
hiddenLayers.get(i).evaluate(inputs, outputs);
System.out.println("Output of hidden layers: "
+ outputs.toString());
}
inputs = (ArrayList<Double>) outputs.clone();
outputLayer.evaluate(inputs, outputs);
}
public double getOutput(int index) {
if (index >= outputAmount)
return 0.0f;
return outputs.get(index);
}
public void releaseNet() {
outputLayer = null;
hiddenLayers = null;
}
public void fromGenome(Genome genome, int numOfInputs,
int neuronsPerHidden, int numOfOutputs) {
if (genome == null)
return;
releaseNet();
hiddenLayers = new ArrayList<NeuronsLayer>();
outputAmount = numOfOutputs;
inputAmount = numOfInputs;
NeuronsLayer hidden = new NeuronsLayer();
ArrayList<Neuron> neurons = new ArrayList<Neuron>();
for (int i = 0; i < neuronsPerHidden; i++) {
ArrayList<Double> weights = new ArrayList<Double>();
for (int j = 0; j < numOfInputs + 1; j++) {
weights.add(genome.weights.get(i * neuronsPerHidden + j));
}
Neuron n = new Neuron();
n.init(weights, numOfInputs);
neurons.add(n);
}
hidden.loadLayer(neurons);
hiddenLayers.add(hidden);
ArrayList<Neuron> neuronsOut = new ArrayList<Neuron>();
for (int i = 0; i < numOfOutputs; i++) {
ArrayList<Double> weights = new ArrayList<Double>();
for (int j = 0; j < neuronsPerHidden + 1; j++) {
weights.add(genome.weights.get(i * neuronsPerHidden + j));
}
Neuron n = new Neuron();
n.init(weights, neuronsPerHidden);
neuronsOut.add(n);
}
outputLayer = new NeuronsLayer();
outputLayer.loadLayer(neuronsOut);
}
}
package com.auto.algorithm;
import java.util.Random;
public class HelperFunction {
public static double Sigmoid(float a, float p) {
float ap = (-a) / p;
return (1 / (1 + Math.exp(ap)));
}
public static double RandomSigmoid() {
Random ran = new Random(System.nanoTime());
double r = ran.nextDouble() - ran.nextDouble();
return r;
}
public static double getValueInRange(double a, double b, double c) {
if (a < b) {
return b;
} else if (a > c) {
return c;
}
return a;
}
}
Points of Interest
I felt so good when finish this project. It's my capstone project for Master Degree from Marshall University. The project is a practical application. It helps beginners to learn about Artificial Intelligence, Neural Network and Genetic Algorithm.
References
I'm sorry that I forgot to mention the references in the previous version. The idea and code I learnt from this author https://github.com/matthewrdev/Neural-Network written in C++. The graphics I learnt from this Youtube channel https://www.youtube.com/user/TheChernoProject. :)
History
- 15th December, 2016: Initial version
