Introducció

L'algoritme A* (A estrella) és un dels més utilitzats en la navegació de personatges en videojocs. Combina les millors característiques de l'algoritme de cerca en amplada i l'algoritme de cerca de cost uniforme, utilitzant una funció heurística per trobar el camí més curt de manera eficient.

Conceptes Clau

Abans de començar amb la implementació, és important entendre alguns conceptes bàsics:

Node: Representa un punt en el mapa.
G-Cost: El cost des del node inicial fins al node actual.
H-Cost: La distància heurística des del node actual fins al node final.
F-Cost: La suma del G-Cost i l'H-Cost. Aquest és el valor que A* utilitza per prioritzar els nodes.

Pseudocodi de l'Algoritme A*

1. Inicialitza l'openList amb el node inicial.
2. Inicialitza la closedList buida.
3. Mentre l'openList no estigui buida:
    a. Agafa el node amb el menor F-Cost de l'openList.
    b. Si aquest node és el node final, has trobat el camí.
    c. Mou aquest node de l'openList a la closedList.
    d. Per a cada veí del node actual:
        i. Si el veí està en la closedList, ignora'l.
        ii. Si el veí no està en l'openList, afegeix-lo i calcula els seus G, H i F.
        iii. Si el veí ja està en l'openList, comprova si aquest camí és millor (menor G-Cost). Si ho és, actualitza els costos.
4. Si l'openList està buida i no has trobat el node final, no hi ha camí possible.

Implementació en Python

A continuació, es presenta una implementació de l'algoritme A* en Python. Aquesta implementació assumeix que el mapa és una graella on cada cel·la pot ser transitable o no.

Codi

import heapq

class Node:
    def __init__(self, position, parent=None):
        self.position = position
        self.parent = parent
        self.g = 0
        self.h = 0
        self.f = 0

    def __eq__(self, other):
        return self.position == other.position

    def __lt__(self, other):
        return self.f < other.f

def heuristic(node, end_node):
    # Utilitzem la distància de Manhattan com a heurística
    return abs(node.position[0] - end_node.position[0]) + abs(node.position[1] - end_node.position[1])

def a_star(map, start, end):
    start_node = Node(start)
    end_node = Node(end)

    open_list = []
    closed_list = []

    heapq.heappush(open_list, start_node)

    while open_list:
        current_node = heapq.heappop(open_list)
        closed_list.append(current_node)

        if current_node == end_node:
            path = []
            while current_node:
                path.append(current_node.position)
                current_node = current_node.parent
            return path[::-1]

        neighbors = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        for new_position in neighbors:
            node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])

            if node_position[0] > (len(map) - 1) or node_position[0] < 0 or node_position[1] > (len(map[len(map)-1]) - 1) or node_position[1] < 0:
                continue

            if map[node_position[0]][node_position[1]] != 0:
                continue

            neighbor = Node(node_position, current_node)

            if neighbor in closed_list:
                continue

            neighbor.g = current_node.g + 1
            neighbor.h = heuristic(neighbor, end_node)
            neighbor.f = neighbor.g + neighbor.h

            if add_to_open(open_list, neighbor):
                heapq.heappush(open_list, neighbor)

    return None

def add_to_open(open_list, neighbor):
    for node in open_list:
        if neighbor == node and neighbor.g > node.g:
            return False
    return True

# Exemple d'ús
map = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

start = (0, 0)
end = (4, 4)

path = a_star(map, start, end)
print(path)

Explicació del Codi

Node Class: Defineix la classe Node per representar cada punt en el mapa. Cada node té una posició, un pare, i els costos G, H i F.
Heuristic Function: La funció heuristic calcula la distància heurística entre dos nodes utilitzant la distància de Manhattan.
A Function*: La funció a_star implementa l'algoritme A*. Utilitza una llista oberta (open_list) per mantenir els nodes que s'han de processar i una llista tancada (closed_list) per mantenir els nodes ja processats.
Add to Open Function: La funció add_to_open comprova si un node ja està en la llista oberta amb un menor G-Cost.

Exercici Pràctic

Enunciat

Implementa una funció que permeti visualitzar el camí trobat per l'algoritme A* en un mapa de graella. La funció ha de mostrar la graella amb el camí representat per un caràcter especial (per exemple, *).

Solució

def print_path(map, path):
    for position in path:
        map[position[0]][position[1]] = '*'
    
    for row in map:
        print(' '.join(str(cell) for cell in row))

# Exemple d'ús
map = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

start = (0, 0)
end = (4, 4)

path = a_star(map, start, end)
print_path(map, path)

Explicació

La funció print_path modifica el mapa original per incloure el camí trobat per l'algoritme A*. Després, imprimeix la graella amb el camí representat per *.

Conclusió

L'algoritme A* és una eina poderosa per a la navegació en videojocs, permetent trobar camins òptims de manera eficient. La seva implementació requereix una comprensió clara dels conceptes de nodes, costos i heurístiques. Amb la pràctica, es pot adaptar i optimitzar per a diferents tipus de jocs i entorns.

Implementació de A*

Introducció

Conceptes Clau

Pseudocodi de l'Algoritme A*

Implementació en Python

Codi

Explicació del Codi

Exercici Pràctic

Enunciat

Solució

Explicació

Conclusió

IA per a Videojocs

Mòdul 1: Introducció a la IA en Videojocs

Mòdul 2: Navegació en Videojocs

Mòdul 3: Presa de Decisions

Mòdul 4: Aprenentatge Automàtic

Mòdul 5: Integració i Optimització

Mòdul 6: Projectes Pràctics

Mòdul 7: Recursos Addicionals