go home
It seems just making many random walks until get reached for the goal point, but actually the best path gets better in next generation. interesting.
First algorithm introduced in [Programming Game AI by Example], originally implemented in c++.
/**
* Copyright codeonwort ( http://wonderfl.net/user/codeonwort )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/9J7O
*/
package {
import flash.events.MouseEvent
import flash.text.TextField
import flash.display.Sprite
public class PathFinding extends Sprite {
private var mapData:Array
private var map:Map
private var drunkard:Drunkard
private var info:TextField
public function PathFinding() {
mapData = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1],
[8, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1],
[1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 5],
[1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0 ,0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
map = new Map(mapData)
map.render(graphics, 20)
drunkard = new Drunkard(140, map)
info = new TextField
info.text = "click the screen\ngeneration: 0"
info.y = 200
info.autoSize = "left"
info.selectable = false
addChild(info)
stage.addEventListener("mouseDown", nextGeneration)
}
public function nextGeneration(e:MouseEvent):void {
if(drunkard.arrived){
e.target.removeEventListener(e.type, arguments.callee)
return
}
drunkard.epoch()
info.text = "click the screen\ngeneration: " + drunkard.generation + "\nbest fitness: " + drunkard.bestFitness
var path:Vector.<int> = drunkard.getBestPath()
graphics.clear()
map.render(graphics, 20, path)
}
}
}
////////////////////////
// outside of pacakge //
////////////////////////
import flash.display.Graphics
class Map {
public static const START:int = 5
public static const END:int = 8
public static const BLANK:int = 0
public static const WALL:int = 1
private var data:Array
private var width:uint, height:uint
private var startX:int, startY:int
private var endX:int, endY:int
public function Map(data:Array) {
this.data = data
width = data[0].length
height = data.length
for(var y:int=0; y<height; y++){
for(var x:int=0; x<width; x++){
if(data[y][x] == START){
startX = x
startY = y
}else if(data[y][x] == END){
endX = x
endY = y
}
}
}
}
public function testRoute(path:Vector.<int>):Number {
// 경로의 적응도를 반환한다
var x:int = startX
var y:int = startY
var prevx:int = x, prevy:int = y
var len:int = path.length
var dir:int
for(var i:int=0; i<len; i++){
dir = path[i]
if(dir == 0) y -= 1
else if(dir == 1) y += 1
else if(dir == 2) x -= 1
else if(dir == 3) x += 1
if(x<0 || x>=width || y<0 || y>=height || data[y][x] == WALL){
x = prevx
y = prevy
}
prevx = x
prevy = y
}
return 1 / (1 + Math.abs(endX-x) + Math.abs(endY-y))
}
public function render(g:Graphics, tileSize:Number, path:Vector.<int>=null):void {
var t:int
var c:int
var i:int, j:int
for(i=0; i<height; i++){
for(j=0; j<width; j++){
t = data[i][j]
if(t == BLANK) c = 0xffffff
else if(t == WALL) c = 0x0
else if(t == START) c = 0xff0000
else if(t == END) c = 0xff
g.beginFill(c)
g.drawRect(j*tileSize, i*tileSize, tileSize, tileSize)
g.endFill()
}
}
if(path){
var x:int = startX, y:int = startY
var prevx:int = x, prevy:int = y
var len:int = path.length
var dir:int
for(i=0; i<len; i++){
dir = path[i]
if(dir == 0) y -= 1
else if(dir == 1) y += 1
else if(dir == 2) x -= 1
else if(dir == 3) x += 1
if(x<0 || x>=width || y<0 || y>=height || data[y][x] == WALL){
x = prevx
y = prevy
}
prevx = x
prevy = y
g.beginFill(0x00ff00, .5)
g.drawRect(x * tileSize, y * tileSize, tileSize, tileSize)
g.endFill()
}
}
}
}
class Genome {
public var bits:Vector.<uint>
public var fitness:Number = 0
public function Genome(numBits:uint) {
bits = new Vector.<uint>(numBits)
for(var i:int=0; i<numBits; i++){
bits[i] = Math.random() >= 0.5 ? 1 : 0
}
}
}
class Drunkard {
public var genomes:Vector.<Genome>
public var map:Map
public const crossoverRate:Number = 0.7
public const mutationRate:Number = 0.001
public const numWalks:uint = 35 * 2
public var generation:uint = 0
public var arrived:Boolean = false
public var bestFitness:Number = 0
public function Drunkard(population:uint, map:Map) {
genomes = new Vector.<Genome>(population)
for(var i:int=0; i<genomes.length; i++){
genomes[i] = new Genome(numWalks)
}
this.map = map
}
public function epoch():void {
if(arrived) return
updateFitness()
if(bestFitness == 1){
arrived = true
return
}
var babies:Vector.<Genome> = new Vector.<Genome>
var dad:Genome, mom:Genome
var roy:Genome, sam:Genome
while(babies.length < genomes.length){
dad = roulettewheelSelection()
mom = roulettewheelSelection()
roy = new Genome(numWalks)
roy.bits = dad.bits.concat()
sam = new Genome(numWalks)
sam.bits = mom.bits.concat()
if(Math.random() < crossoverRate){
crossover(roy, sam)
}
if(Math.random() < mutationRate){
mutate(roy)
}
if(Math.random() < mutationRate){
mutate(sam)
}
babies.push(roy, sam)
}
genomes = babies
generation++
}
private function crossover(baby1:Genome, baby2:Genome):void {
var len:int = baby1.bits.length
var x:int = Math.random() * len
var temp:uint
for(var i:int=x; i<len; i++){
temp = baby1.bits[i]
baby1.bits[i] = baby2.bits[i]
baby2.bits[i] = temp
}
}
private function mutate(baby:Genome):void {
var len:int = baby.bits.length
for(var i:int=0; i<len; i++){
baby.bits[i] = 1 - baby.bits[i]
}
}
public function updateFitness():void {
var gene:Genome
bestFitness = 0
for(var i:int=0; i<genomes.length; i++){
gene = genomes[i]
gene.fitness = map.testRoute(decode(gene.bits))
if(gene.fitness > bestFitness) bestFitness = gene.fitness
}
}
public function decode(bits:Vector.<uint>):Vector.<int> {
var dir:Vector.<int> = new Vector.<int>
for(var i:int=0; i<bits.length; i+=2){
dir.push(bits[i]*2 + bits[i+1])
}
return dir
}
public function roulettewheelSelection():Genome {
var fit_sum:Number = 0
var len:int = genomes.length
for(var i:int=0; i<len; i++){
fit_sum += genomes[i].fitness
}
var slice:Number = Math.random() * fit_sum
var f:Number = 0
for(i=0; i<len; i++){
f += genomes[i].fitness
if(f > slice){
return genomes[i]
}
}
return genomes[0]
}
public function getBestPath():Vector.<int> {
var idx:int = 0
var len:int = genomes.length
for(var i:int=1; i<len; i++){
if(genomes[i].fitness > genomes[idx].fitness) idx = i
}
return decode(genomes[idx].bits)
}
}