文档章节

游戏编程中的人工智能(Python改编)

crazyskady
 crazyskady
发布于 2017/03/26 00:17
字数 3248
阅读 132
收藏 2

本文改编自Mat Buckland的游戏开发中的人工智能技术中的Chapter 3帮助Bob回家,C++代码重新用python来实现(本文所有遗传算法相关代码均改编值Mat的C++代码,如有雷同,纯属巧合)。

Mat在本章节中详细的描述了如何利用遗传算法来帮助Bob从迷宫的起始点走到终点。具体效果如下图,红色是起点,绿色是终点,蓝色是寻找的路径: BobsMap

#遗传算法 遗传算法是一种经典的进化算法,本文不再讲解遗传算法的概念,基本运算过程的介绍从百度百科拷贝如下: a)初始化:设置进化代数计数器t=0,设置最大进化代数T,随机生成M个个体作为初始群体P(0)。

b)个体评价:计算群体P(t)中各个个体的适应度。

c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

d)交叉运算:将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。

e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。 群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出,终止计算。

本文会通过Python来一步一步实现如何利用遗传算法帮助Bob回家。

#数学建模 首先我们需要对地图进行建模,地图有四种情况:起点,终点,障碍物,通路。我们利用一个二维数组来表示Bob需要穿越的地图,1代表障碍,0代表通路,5是起点,8是终点:

BobsMap = [
[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]
]

然后我们需要对Bob的行走方式进行编码,因为只有四个方向,所以我们可以用0-3来代表Bob的行走方向:0-北, 1-南,2-东,3-西。 然后将0-3转化成2进制00,01,10,11,这样我们就可以生成一串随机长度(需要可以被2整除)的字符串来代表Bob的行进路线了。比如 1111000010100101就可以解码成11-11-00-00-10-10-01-01,也就是3-3-0-0-2-2-1-1(西-西-北-北-东-东-南-南)。

def BinToInt(self, bins):
	val = 0
	multiplier = 1
	for bin in bins[::-1]:
		val += bin * multiplier
		multiplier *= 2
	return val

def Decode(self, bits):
	directions = []
	for i in range(0, len(bits), self.GeneLength):
		ThisGene = []
		for j in range(self.GeneLength):
			ThisGene.append(bits[i+j])
		directions.append(self.BinToInt(ThisGene))
	return directions

染色体

根据数学建模的分析,我们可以随机生成一串二进制数据来表示该算法中的染色体,在遗传算法的初始,我们会随机生成一系列随机的该染色体来表示Bob可能进行尝试的回家路径。

class Genome(object):
	def __init__(self, num_bits): #check num_bits length
		self.Fitness = 0.0
		self.Bits    = []
		for i in xrange(num_bits):
			self.Bits.append(random.randint(0, 1))   # 这个循环可以用map来代替  map(lambda _:random.randint(0,1), xrange(num_bits))

种群初始化

定义好染色体之后,我们就可以进行种群的初始化了,种群的初始化就是生成一系列随机的染色体,在初始化种群时,我们同时将算法中需要用的的几个参数全部初始化,FittestGenome表示的是该种群中最佳的Bob行走路径的索引,BestFitnessScore表示的是该种群中最佳行走路径的适应度,TotalFitnessScore表示的是种群的总适应度(该适应度用于个体选择),Generation表示的进化代数:

def CreateStartPopulation(self):
	self.Genomes = []

	for i in xrange(self.PopSize):
		self.Genomes.append(Genome(self.ChromoLength))

	self.FittestGenome     = 0
	self.BestFitnessScore  = 0.0
	self.TotalFitnessScore = 0.0
	self.Generation        = 0
	return

选择运算

赌轮盘的选择方式(商场里经常会出现这样的活动,一个大轮盘,越贵重的奖项在轮盘中占有的比例越小),适应度越高的路径(越接近终点的路径)越容易被选择运算选中而遗传到下一代: 幸运大轮盘

  1. 随机生成一个在0到总适应度之间的值
  2. 遍历种群,对每个染色体的适应度进行累加
  3. 当遇到第一个大于1中生成的适应度的染色体时,停止累加,返回该染色体 适应度越大的染色体被选中的概率越大
def RouletteWheelSelection(self):
	fSlice  = random.random() * self.TotalFitnessScore
	cfTotal = 0.0
	SelectedGenome = 0

	for i in xrange(self.PopSize):
		cfTotal += self.Genomes[i].Fitness
		if cfTotal > fSlice:
			SelectedGenome = i
			break
	return self.Genomes[SelectedGenome]

交叉运算

生成一个随机数,如果该随机数大于交叉概率,则不进行交叉,如果随机数小于交叉概率,则在染色体上随机选择一个点,将父亲与母亲的染色体进行交叉,生成新的子代染色体

def Crossover(self, mum, dad):
	if random.random() > self.CrossoverRate or mum == dad:
		return mum, dad

	cp = random.randint(0, self.ChromoLength - 1)
	return mum[:cp]+dad[cp:], dad[:cp]+mum[cp:]

变异运算

顾名思义,对染色体上的每个bit进行概率性的变异操作(0-1),变异运算在遗传算法中有利于算法走出局部最优。

def Mutate(self, bits):  #bits is a list
	for i in xrange(len(bits)):
		if random.random() < self.MutationRate:
			if bits[i] == 0:  #if bitArray, it's more easy to reverse
				bits[i] = 1
			if bits[i] == 1:
				bits[i] = 0
	return bits

适应度

适应度的计算很简单,越靠近终点的行走方式适应度越高,注意在计算路径的时候,如果碰到路障或者是走出了边界,Bob的位置不会移动。

def TestRoute(Path):
	posX = startPos[0]
	posY = startPos[1]

	for direction in Path:
		if direction == 0: #North
			if posY - 1 > 0 and BobsMap[posY - 1][posX] != 1:
				posY -= 1

		elif direction == 1: #South
			if posY + 1 < MapHeight and BobsMap[posY + 1][posX] != 1:
				posY += 1

		elif direction == 2: #East
			if posX + 1 < MapWidth and BobsMap[posY][posX + 1] != 1:
				posX += 1

		elif direction == 3: #West
			if posX - 1 >= 0 and BobsMap[posY][posX - 1] != 1:
				posX -= 1

		else:
			print "Unknown direction: ", direction

	DiffX = abs(posX - endPos[0])
	DiffY = abs(posY - endPos[1])

	return 1.0/(DiffX + DiffY + 1)

进化吧, Bob

在每次进化的Epoch中,我们都会更新本次进化的适应度,并根据适应度来判断是否Bob是否已经到达了终点,如果没有到达终点,则对种群进行选择操作,直到选择出来的染色体已经达到了我们需要的数量:

def UpdateFitnessScores(self):
	self.FittestGenome     = 0
	self.BestFitnessScore  = 0.0
	self.TotalFitnessScore = 0.0

	for i in xrange(self.PopSize):
		directions = self.Decode(self.Genomes[i].Bits)
		self.Genomes[i].Fitness = TestRoute(directions)
		#print directions, self.Genomes[i].Fitness
		self.TotalFitnessScore += self.Genomes[i].Fitness

		if self.Genomes[i].Fitness > self.BestFitnessScore:
			self.BestFitnessScore = self.Genomes[i].Fitness
			self.FittestGenome = i
			if self.Genomes[i].Fitness == 1:
				#Bob已经找到回家的路啦~~~~
				print "Found Path"
				print "Path is :", self.ShowPath(self.Decode(self.Genomes[i].Bits))
				self.Busy = False

	return

def Epoch(self):
	self.UpdateFitnessScores()
	if not self.Busy:
		return
	NewBabies = 0
	BabyGenomes = []

	while NewBabies < self.PopSize:
		mum = self.RouletteWheelSelection()
		dad = self.RouletteWheelSelection()
		#print mum.Bits, dad.Bits
		baby1 = Genome(0)
		baby2 = Genome(0)
		baby1.Bits, baby2.Bits = self.Crossover(mum.Bits, dad.Bits)
		baby1.Bits = self.Mutate(baby1.Bits)
		baby2.Bits = self.Mutate(baby2.Bits)

		BabyGenomes.append(baby1)
		BabyGenomes.append(baby2)

		NewBabies += 2

	self.Genomes = BabyGenomes
	self.Generation += 1
	#print self.Generation, self.BestFitnessScore
	return

整合

最后,我们将上面的代码整合起来,就可以形成一个完整的自动寻找Bob回家的遗传算法。当然,仅有这些没有办法显示的看到Bob是如何尝试寻找回家的方法的,我们需要一个GUI来对每次进化的最优路径进行显示,本文采用的是pygame,如何使用本文不再赘述,请参考用 Python 和 Pygame 写游戏 - 从入门到精通

完整的代码如下,注意本文仅使用了最基本的遗传算法操作,所以会经常陷入局部最优而难以达到终点,我们会在后续的文章中来对遗传算法进行优化。

原创作品,转载请注明出处。

# -*- coding: utf-8 -*-
import random
import pygame
from pygame.locals import *
from sys import exit

BobsMap = [
[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]
]

MapHeight = len(BobsMap)
MapWidth  = len(BobsMap[0])
startPos  = [14, 7]
endPos    = [0, 2]

# 15 * 40 = 600, 10 * 40 = 400
block_size = 40

def TestRoute(Path):
	posX = startPos[0]
	posY = startPos[1]

	for direction in Path:
		if direction == 0: #North
			if posY - 1 > 0 and BobsMap[posY - 1][posX] != 1:
				posY -= 1

		elif direction == 1: #South
			if posY + 1 < MapHeight and BobsMap[posY + 1][posX] != 1:
				posY += 1

		elif direction == 2: #East
			if posX + 1 < MapWidth and BobsMap[posY][posX + 1] != 1:
				posX += 1

		elif direction == 3: #West
			if posX - 1 >= 0 and BobsMap[posY][posX - 1] != 1:
				posX -= 1

		else:
			print "Unknown direction: ", direction

	DiffX = abs(posX - endPos[0])
	DiffY = abs(posY - endPos[1])

	return 1.0/(DiffX + DiffY + 1)

class Genome(object):
	def __init__(self, num_bits): #check num_bits length
		self.Fitness = 0.0
		self.Bits    = []
		for i in xrange(num_bits):
			self.Bits.append(random.randint(0, 1))   # This loop can be replaced by:       map(lambda _:random.randint(0,1), xrange(num_bits))

	def _show(self):
		print self.Bits, self.Fitness

class GaBob(object):
	def __init__(self, cross_rat, mut_rate, pop_size, num_bits, gene_len):
		self.Genomes           = []
		self.PopSize           = pop_size
		self.CrossoverRate     = cross_rat
		self.MutationRate      = mut_rate
		self.ChromoLength      = num_bits
		self.GeneLength        = gene_len
		self.FittestGenome     = 0
		self.BestFitnessScore  = 0.0
		self.TotalFitnessScore = 0.0
		self.Generation        = 0
		self.Busy              = False
		pass

	def Run(self):
		self.CreateStartPopulation()
		self.Busy = True

	def _showPopulation(self):
		for i in xrange(self.PopSize):
			print self.Genomes[i].Bits

	def CreateStartPopulation(self):
		self.Genomes = []

		for i in xrange(self.PopSize):
			self.Genomes.append(Genome(self.ChromoLength))

		self.FittestGenome     = 0
		self.BestFitnessScore  = 0.0
		self.TotalFitnessScore = 0.0
		self.Generation        = 0
		return

	# 赌轮盘的选择方式:
	# 1. 随机生成一个在0到总适应度之间的值
	# 2. 遍历种群,对每个染色体的适应度进行累加
	# 3. 当遇到第一个大于1中生成的适应度的染色体时,停止累加,返回该染色体
	# 适应度越大的染色体被选中的概率越大 
	def RouletteWheelSelection(self):
		fSlice  = random.random() * self.TotalFitnessScore
		cfTotal = 0.0
		SelectedGenome = 0

		for i in xrange(self.PopSize):
			cfTotal += self.Genomes[i].Fitness
			if cfTotal > fSlice:
				SelectedGenome = i
				break
		return self.Genomes[SelectedGenome]

	def Mutate(self, bits):  #bits is a list
		for i in xrange(len(bits)):
			if random.random() < self.MutationRate:
				if bits[i] == 0:  #if bitArray, it's more easy to reverse
					bits[i] = 1
				if bits[i] == 1:
					bits[i] = 0
		return bits

	def Crossover(self, mum, dad):
		if random.random() > self.CrossoverRate or mum == dad:
			return mum, dad

		cp = random.randint(0, self.ChromoLength - 1)
		return mum[:cp]+dad[cp:], dad[:cp]+mum[cp:]

	def BinToInt(self, bins):
		val = 0
		multiplier = 1
		for bin in bins[::-1]:
			val += bin * multiplier
			multiplier *= 2
		return val

	def Decode(self, bits):
		directions = []
		for i in range(0, len(bits), self.GeneLength):
			ThisGene = []
			for j in range(self.GeneLength):
				ThisGene.append(bits[i+j])
			directions.append(self.BinToInt(ThisGene))
		return directions

	def UpdateFitnessScores(self):
		self.FittestGenome     = 0
		self.BestFitnessScore  = 0.0
		self.TotalFitnessScore = 0.0

		for i in xrange(self.PopSize):
			directions = self.Decode(self.Genomes[i].Bits)
			self.Genomes[i].Fitness = TestRoute(directions)
			#print directions, self.Genomes[i].Fitness
			self.TotalFitnessScore += self.Genomes[i].Fitness

			if self.Genomes[i].Fitness > self.BestFitnessScore:
				self.BestFitnessScore = self.Genomes[i].Fitness
				self.FittestGenome = i
				if self.Genomes[i].Fitness == 1:
					#we found, stop
					print "Found Path"
					print "Path is :", self.ShowPath(self.Decode(self.Genomes[i].Bits))
					self.Busy = False

		return

	def Epoch(self):
		self.UpdateFitnessScores()
		if not self.Busy:
			return
		NewBabies = 0
		BabyGenomes = []

		while NewBabies < self.PopSize:
			mum = self.RouletteWheelSelection()
			dad = self.RouletteWheelSelection()
			#print mum.Bits, dad.Bits
			baby1 = Genome(0)
			baby2 = Genome(0)
			baby1.Bits, baby2.Bits = self.Crossover(mum.Bits, dad.Bits)
			baby1.Bits = self.Mutate(baby1.Bits)
			baby2.Bits = self.Mutate(baby2.Bits)

			BabyGenomes.append(baby1)
			BabyGenomes.append(baby2)

			NewBabies += 2

		self.Genomes = BabyGenomes
		self.Generation += 1
		#print self.Generation, self.BestFitnessScore
		return

	def ShowPath(self, Path):
		pathStr = ""
		for direction in Path:
			if direction == 0: #North
				pathStr += "-North"

			elif direction == 1: #South
				pathStr += "-South"

			elif direction == 2: #East
				pathStr += "-East"

			elif direction == 3:
				pathStr += "-West"	

			else:
				pathStr += "-Unknown direction: ", direction

		return pathStr


	def Started(self):
		return self.Busy

	def Stop(self):
		self.Busy = False
		return

	def GetFittestDirection(self):
		return self.Decode(self.Genomes[self.FittestGenome].Bits)

# pos = (x, y), top left position of the rect
def set_block(screen, color, pos):
	top_side_rect   = Rect(pos[0], pos[1], block_size, 1)
	right_side_rect = Rect(pos[0] + block_size, pos[1], 1, block_size)
	bottom_side_rect= Rect(pos[0], pos[1] + block_size, block_size, 1)
	left_side_rect  = Rect(pos[0], pos[1], 1, block_size)
	center_rect     = Rect(pos[0]+1, pos[1]+1, block_size-1, block_size-1)
	pygame.draw.rect(screen, (255, 255, 255), top_side_rect)
	pygame.draw.rect(screen, (255, 255, 255), right_side_rect)
	pygame.draw.rect(screen, (255, 255, 255), bottom_side_rect)
	pygame.draw.rect(screen, (255, 255, 255), left_side_rect)
	pygame.draw.rect(screen, color, center_rect)

def set_path(screen, color, path):
	posX = startPos[0]
	posY = startPos[1]

	for direction in path:
		if direction == 0: #North
			if posY - 1 > 0 and BobsMap[posY - 1][posX] != 1:
				posY -= 1

		elif direction == 1: #South
			if posY + 1 < MapHeight and BobsMap[posY + 1][posX] != 1:
				posY += 1

		elif direction == 2: #East
			if posX + 1 < MapWidth and BobsMap[posY][posX + 1] != 1:
				posX += 1

		elif direction == 3: #West
			if posX - 1 >= 0 and BobsMap[posY][posX - 1] != 1:
				posX -= 1
		else:
			print "Unknown direction: ", direction

		if [posX, posY] == startPos:
			continue
		current_pos = (posX*block_size, posY*block_size)
		set_block(screen, color, current_pos)

if __name__ == "__main__":
	CROSSOVER_RATE = 0.7
	MUTATION_RATE  = 0.015	
	POP_SIZE       = 140
	CHROMO_LENGTH  = 70
	GENE_LENGTH    = 2	

	test_gaBob = GaBob(CROSSOVER_RATE, MUTATION_RATE, POP_SIZE, CHROMO_LENGTH, GENE_LENGTH)	
	test_gaBob.Run()

	pygame.init()	

	screen = pygame.display.set_mode((600, 400), 0, 32)
	while True:
		for event in pygame.event.get():
			if event.type == QUIT:
				exit()

		screen.fill((255, 255, 255))		
		#set_block(screen, (255,0,0), (100, 100))
		for yIdx, rowItem in enumerate(BobsMap):
			for xIdx, blockItem in enumerate(rowItem):
				if blockItem == 1:
					block_pos = (xIdx*block_size, yIdx*block_size)
					set_block(screen, (0, 0, 0), block_pos)
				elif blockItem == 5:
					block_pos = (xIdx*block_size, yIdx*block_size)
					set_block(screen, (255, 0, 0), block_pos)
				elif blockItem == 8:
					block_pos = (xIdx*block_size, yIdx*block_size)
					set_block(screen, (0, 255, 0), block_pos)	

		if test_gaBob.Started():
			test_gaBob.Epoch()

		set_path(screen, (0, 0, 255), test_gaBob.GetFittestDirection())

		pygame.display.update()

© 著作权归作者所有

crazyskady
粉丝 0
博文 5
码字总数 6747
作品 0
南京
程序员
私信 提问
JavaScript能写一切?Python不服:盘它!

几天前,LinkedIn 领英发布了《2019 年职场十大趋势》,其中第一大趋势,便是人工智能赋能未来。人工智能是领英上数量增长最快的技能之一,近几年增幅达 190%。而人工智能领域并不简单,需要...

AI科技大本营
01/24
0
0
人工智能用Python?高考要加入Python?!Python成为微软官方Excel脚本语言?再不学习就OUT了!

Python适合初学者入门最好的语言 人工智能用Python?高考要加入Python?现在连微软官方Excel都要把Python作为官方语言!Python魅力这么大!小伙伴们知道吗?小编只想说,现在不学Python就OUT...

q1622479435
2018/06/08
0
0
JavaScript 能写一切?Python 不服:盘它!

几天前,LinkedIn 领英发布了《2019 年职场十大趋势》,其中第一大趋势,便是人工智能赋能未来。人工智能是领英上数量增长最快的技能之一,近几年增幅达 190%。而人工智能领域并不简单,需要...

CSDN资讯
01/22
0
0
IT届各位大佬告诉你,为什么学习AI之前要学习Python!

在之前的全国高中信息“新课标”出炉!要想报考这些专业,必须得会……中,我们从政策上给大家阐述了为什么要学Python。今天,我们就来听听IT届各位大佬是怎么说的。 编程是一项社交活动。 ...

python达人
2018/04/30
0
0
高薪机会丨Python人才需求缺口高达50万,你还在等什么!

在这个大数据的时代,你要想走在潮流前端,就必须要学习前言有用的只是。而如今人工智能和数据分析爆发,python就是一个冉冉升起的新星。 有人说:Python可能是所有语言里最符合成为人类对编...

C04
2018/08/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Boot 2 实战:使用 Spring Boot Admin 监控你的应用

1. 前言 生产上对 Web 应用 的监控是十分必要的。我们可以近乎实时来对应用的健康、性能等其他指标进行监控来及时应对一些突发情况。避免一些故障的发生。对于 Spring Boot 应用来说我们可以...

码农小胖哥
30分钟前
3
0
ZetCode 教程翻译计划正式启动 | ApacheCN

原文:ZetCode 协议:CC BY-NC-SA 4.0 欢迎任何人参与和完善:一个人可以走的很快,但是一群人却可以走的更远。 ApacheCN 学习资源 贡献指南 本项目需要校对,欢迎大家提交 Pull Request。 ...

ApacheCN_飞龙
41分钟前
3
0
CSS定位

CSS定位 relative相对定位 absolute绝对定位 fixed和sticky及zIndex relative相对定位 position特性:css position属性用于指定一个元素在文档中的定位方式。top、right、bottom、left属性则...

studywin
50分钟前
6
0
从零基础到拿到网易Java实习offer,我做对了哪些事

作为一个非科班小白,我在读研期间基本是自学Java,从一开始几乎零基础,只有一点点数据结构和Java方面的基础,到最终获得网易游戏的Java实习offer,我大概用了半年左右的时间。本文将会讲到...

Java技术江湖
昨天
5
0
程序性能checklist

程序性能checklist

Moks角木
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部