[Contenido] 1. Intro 2. Rutas 3. Grupos 4. Apuntando 5.Juego
Índice de Contenidos :.
Introducción :: 1
Arquitectura:: 1.1
Máquina de Estados Finitos:: 1.2
Sistemas de Reglas :: 1.3
Búsqueda de Rutas:: 2
Algoritmo A*:: 2.1
Movimiento de Grupos :: 3
Boids :: 3.1
Apuntando al objetivo :: 4
Propuesta de trabajo :: 5
Sesión 5 :: Transp. 2
Contenido [1. Intro] 2. Rutas 3. Grupos 4. Apuntando 5.Juego
Inteligencia Artificial en los juegos :.
Indivíduos, Actitudes
Movimiento de masa
Búsqueda de rutas
Acciones Simples
Razonamiento
Sesión 5 :: Transp. 3
Contenido [1. Intro] 2. Rutas 3. Grupos 4. Apuntando 5.Juego
Estructura del Sistema de IA :.
Sistema de Sensores
INPUT
Memoria de Trabajo
Núcleo de Razonamiento
y Análisis
Sistema de Actuadores
OUTPUT
Sesión 5 :: Transp. 4
Contenido [1. Intro] 2. Rutas 3. Grupos 4. Apuntando 5.Juego
Ténicas más habituales :.
Máquina de Estados Finitos
(FSM)
a0/oO
Q0
a1/o2
Q1
Q2
a0/o1
Estado Transición Entrada
Acción
Componentes
Sesión 5 :: Transp. 5
Contenido [1. Intro] 2. Rutas 3. Grupos 4. Apuntando 5.Juego
Máquina de Estados Finitos :.
A={Conjunto de Estado Q,
Alfabeto Entrada A,
Estado inicial Q0 ,
Función de Transición F:QxA->Q ,
Funcion de Accion S:QxA->O}
● Bucle principal:
● La actualización de la
situación
● Captación de los ls
sensores.
ESTADO=ID_INICIAL
ENTRADA=Sensores()
While not TERMINAR:
[ACTUALIZACION]
ENTRADA=Sensores()
Sesión 5 :: Transp. 6
Contenido [1. Intro] 2. Rutas 3. Grupos 4. Apuntando 5.Juego
Máquina de Estados Finitos:.
if ESTADO==ID_ESTADO:
elsif ENTRADA==ID_ENTRADA1:
[ACCIONES POR DEFECTO]
if ENTRADA==ID_ENTRADA0:
[ACCIONES ESPECIFICAS]
ESTADO=ID_SIGUIENTE
[ACCIONES ESPECIFICAS]
ESTADO=ID_SIGUIENTE
elsif ...
.....................
elsif ESTADO==ID_ESTADO:
[ACCIONES POR DEFECTO]
if ENTRADA==ID_ENTRADA0:
[ACCIONES ESPECIFICAS]
ESTADO=ID_SIGUIENTE
[ACCIONES ESPECIFICAS]
ESTADO=ID_SIGUIENTE
elsif ...
.....................
elsif ENTRADA==ID_ENTRADA1:
● Una posible
implementación de la
fase de
[ACTUALIZACION]
● Entrada será la
salida de nuestro
sistema de sensores
●ESTADO, En un
principio tendrá el
valor del estado
inicial.
Sesión 5 :: Transp. 7
Contenido [1. Intro] 2. Rutas 3. Grupos 4. Apuntando 5.Juego
FSM Ejemplo :.
● Un enemigo está fuera en un espacio abierto y sin obstáculos.
● Tiene definidas unas localizaciones que patrulla cíclicamente.
● El enemigo se activa si cuando entras en línea de visión.
● Si te ve, cambia su forma de actuar.
● Lleva una espada.
● Si se estable un contacto , te exortará a pararte y te atacará
Sesión 5 :: Transp. 8
?
o
d
a
e
n
i
l
A
Contenido [1. Intro] 2. Rutas 3. Grupos 4. Apuntando 5.Juego
FSM Ejemplo :.
L
o
c
a
l
i
z
a
c
i
ó
n
a
l
c
a
n
z
a
d
a
Estar
Loc
Buscar
Loc
Visto
Preparado
Batalla
Dist<2
Dist>2
Lucha
El jugador a muerto o no lo ve
El jugador a muerto o no lo ve
Sesión 5 :: Transp. 9
Contenido [1. Intro] 2. Rutas 3. Grupos 4. Apuntando 5.Juego
Sistemas de Reglas :.
Sistemas de Reglas (RS)
SI
[...]
se puede verificar que
ENTONCES
se hace [...]
HECHOS
Y
SENSORES
REGLAS
RAZONAMIENTO
Sesión 5 :: Transp. 10
Contenido [1. Intro] 2. Rutas 3. Grupos 4. Apuntando 5.Juego
Entornos simbólicos de reglas :.
Ver Clips
Entorno para Sistemas Expertos
Interprete empotrado
Lenguaje de Script
(defrule <Nombre>
(<antecedente 1>)
.................
(<antecedente n>)
=>
(<consecuente 1>)
.................
(<consecuente m>)
)
Age of Empires
Sesión 5 :: Transp. 11
Contenido 1. Intro [2. Rutas] 3. Grupos 4. Apuntando 5.Juego
Búsqueda de Rutas:.
B
A
¿ Co
m
o ir de A a B ?
Sesión 5 :: Transp. 12
Contenido 1. Intro [2. Rutas] 3. Grupos 4. Apuntando 5.Juego
0
1
32
654
x
o
0
1
2
3
4
5
6
7
Búsqueda de rutas A* :.
Ir de la casilla O
(5,3)
a la casilla x (1,6)
Objetivo
7
¿Como conseguirlo ?
Con movimientos válidos
6
7
5
0
4
1
2
3
¿Vale cualquier solución?
N
O
Sesión 5 :: Transp. 13
Contenido 1. Intro [2. Rutas] 3. Grupos 4. Apuntando 5.Juego
Algoritmo A* :.
Bolsa de casillas Visitadas vacia
Bolsa de casillas No Visitadas con la posición inicial
Mientras no este vacia la Bolsa de No Visitados y no hemos llegado
Ordenar las casillas de No Visitadas según la valoración
Tomo la mejor casilla
La quito de No Visitadas
Si final entornces ya hemos terminado
Para todas las casillas a donde puedo llegar desde ésta
Si no están en visitados
Calcular su valor, indicar su ancestro
introducirlo en la Bolsa de No Visitadas
Sesión 5 :: Transp. 14
Contenido 1. Intro [2. Rutas] 3. Grupos 4. Apuntando 5.Juego
Construir una ruta:.
(x ,y )
i
i
Inicio
....
n'
(x ,y -1 )
n'
n 0
Acció
n'
camino
8,63cm
...
n
A
c
c
i
ó
n
7
Meta
(x ,y )
m m
(x -1,y -1 )
n'
n'
Sesión 5 :: Transp. 15
Inicio
n'
Contenido 1. Intro [2. Rutas] 3. Grupos 4. Apuntando 5.Juego
Valorar una ruta:.
f(n)
20,19cm
....
g(n)
9,77cm
c(n',n)
8,83cm
Meta
n
h(n)
1 0 , 0 7 c m
n
g(n)
=
g(n')
+
c(n',n)
Sesión 5 :: Transp. 16
Contenido 1. Intro [2. Rutas] 3. Grupos 4. Apuntando 5.Juego
Ejemplo:.
hx1,y1,x2,y2=∣x1−x2∣∣y1−y2∣
X
f=g+h , g ,h
O
gx1,y1,x2,y2=x1−x22y1−y22
Sesión 5 :: Transp. 17
Contenido 1. Intro [2. Rutas] 3. Grupos 4. Apuntando 5.Juego
Ejemplo:.
X
7,0,7
Sesión 5 :: Transp. 18
Contenido 1. Intro [2. Rutas] 3. Grupos 4. Apuntando 5.Juego
Ejemplo:.
8'8,7'8,1 7'4,7'4,0 8'8,7'8,1
8'8,6'8,2 7'4,6'4,1 8'8,6'8,2
7'4,5'4,2 8'8,5'8,3
7'4,4'4,3 9'4,5'4,4
8'4,1'4,7
9,1,8
7,0,7
7,1,6
8,3,5
10'8,5'8,5
10'4,1'4,9
9,1,8
8'4,1'4,7 9'4,3'4,6 10'4,5'4,5
Sesión 5 :: Transp. 19
Contenido 1. Intro [2. Rutas] 3. Grupos 4. Apuntando 5.Juego
Ejemplo de implementación :.
Ver Busqueda.py
Algoritmo de Búsqueda de Rutas
● Nos centraremos primero en los
Nodos que compondrán el árbol
de búsqueda.
Class Nodo:
def __init__(self,punto,g,h,f,padre=None):
self.pos=punto
self.g=g
self.h=h
self.f=f
self.padre=padre
self.id=self.genNum(self.pos)
Sesión 5 :: Transp. 20
Contenido 1. Intro [2. Rutas] 3. Grupos 4. Apuntando 5.Juego
Ejemplo de implementación :.
class Nodo:
def __init__(self,punto,g,h,f,padre=None):
def genNum(self,pos): # Genera un
def __cmp__(self,dat): # Establece un orden
def strVal(self):
def strPos(self):
def __str__(self):
def __repr__(self):
def opciones(self,terreno,inicio,final):
def ancestros(self):
Sesión 5 :: Transp. 21
Contenido 1. Intro [2. Rutas] 3. Grupos 4. Apuntando 5.Juego
Ejemplo de implementación :.
def opciones(self,terreno,inicio,final):
LResult=[]
for dx,dy in VectMov:
x,y=(self.pos[0]+dx),(self.pos[1]+dy)
if not (x,y) in terreno:
g1=FuncG(inicio,(x,y))
h1=FuncH((x,y),final)
f1=FuncF(g1,h1)
n=Nodo((x,y),g1,h1,f1,self)
LResult.append(n)
return LResult
def menor(dic):
m=dic.keys()[0]
for (key,n) in dic.iteritems():
if n.f<dic[m].f:
m=key
return m
Sesión 5 :: Transp. 22
Contenido 1. Intro [2. Rutas] 3. Grupos 4. Apuntando 5.Juego
Ejemplo de implementación :.
Def BusquedaAEstrella(terreno,ini,fin):
Visitados,NoVisitados={},{}
n=Nodo(ini,0,FuncH(ini,fin),FuncH(ini,fin),None)
NoVisitados[ini]=n
terminado=0
while (len(NoVisitados.keys())>0) and (not terminado):
casilla=menor(NoVisitados)
n=NoVisitados[casilla]
del(NoVisitados[casilla])
if n.pos==fin:
terminado=1
break
Visitados[n.pos]=n
lOpciones=n.opciones(terreno,ini,fin)
for m in lOpciones:
if not Visitados.has_key(m.pos):
NoVisitados[m.pos]=m
.......................
Sesión 5 :: Transp. 23
Contenido 1. Intro 2. Rutas [3. Grupos] 4. Apuntando 5.Juego
Movimiento de Grupos :.
Boids
Craig W.Reynolds (1990)
http://www.red3d.com/cwr/boids
http://www.cse.unsw.edu.au/~conradp/boids/pseudocode.html
Sesión 5 :: Transp. 24
Contenido 1. Intro 2. Rutas [3. Grupos] 4. Apuntando 5.Juego
Las tres reglas:.
Separación
Cohesión
Alineamiento
Sesión 5 :: Transp. 25
Contenido 1. Intro 2. Rutas [3. Grupos] 4. Apuntando 5.Juego
Ejemplo de codificación :.
Lista de individuos con [ pt, vel, objNum ]
objNum
pt=[ x, y, z ]
vel=[ dx, dy, dz ]
Codigo de Todd Warner:
[email protected]
Sesión 5 :: Transp. 26
Contenido 1. Intro 2. Rutas [3. Grupos] 4. Apuntando 5.Juego
Ejemplo de codificación de las reglas:.
def Rule1(self, b):
pc = [0.0, 0.0, 0.0]
for each in self.theList:
if b != each:
pc = translate(pc, each[0])
fact = float(len(self.theList)) - 1.0
fact = 1.0/fact
pc = scale(pc, fact)
pc = subVec(pc, b[0])
fact = 1.0/100.0 # Proportion
pc = scale(pc, fact)
return pc
Codigo de Todd Warner:
[email protected]
Cohesión
Sesión 5 :: Transp. 27
Contenido 1. Intro 2. Rutas [3. Grupos] 4. Apuntando 5.Juego
Ejemplo de codificación de las reglas:.
def Rule2(self, b):
c = [0.0, 0.0, 0.0]
for each in self.theList:
if b != each:
diffPos = subVec(b[0], each[0])
dist = calcMagnitude(diffPos)
if dist < NEIGHBOR_THRESH:
c = subVec(c, diffPos)
return c
Codigo de Todd Warner:
[email protected]
Separación
Sesión 5 :: Transp. 28
Contenido 1. Intro 2. Rutas [3. Grupos] 4. Apuntando 5.Juego
Ejemplo de codificación de las reglas:.
def Rule3(self, b):
pv = [0.0, 0.0, 0.0]
for each in self.theList:
if b != each:
pv = translate(pv, each[1])
fact = float(len(self.theList)) - 1.0
fact = 1.0/fact
pv = scale(pv, fact)
fact = 1.0/8.0
Comentarios de: sesión 5 - Inteligencia Artificial (0)
No hay comentarios