El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algoritmes de Cerca de Camins

Següent ►
►

En aquest tema, explorarem els algoritmes de cerca de camins, una part fonamental de la navegació en videojocs. Aquests algoritmes permeten als personatges del joc trobar el camí més eficient des d'un punt d'origen fins a una destinació, evitant obstacles i optimitzant el recorregut.

Conceptes Clau

  1. Grafs

Els grafs són estructures de dades que representen xarxes de nodes (punts) i arestes (connexions entre punts). En el context de la cerca de camins, els nodes representen posicions en el món del joc, i les arestes representen els camins possibles entre aquestes posicions.

  1. Algoritmes de Cerca

Hi ha diversos algoritmes de cerca que es poden utilitzar per trobar camins en un graf. Alguns dels més comuns són:

  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)
  • Dijkstra's Algorithm
  • A (A Estrella)*

  1. Heurística

En els algoritmes de cerca informada com A*, la heurística és una funció que estima el cost de moure's des d'un node fins a la destinació. Aquesta estimació ajuda a guiar l'algoritme cap a la solució de manera més eficient.

Algoritmes de Cerca Comuns

Breadth-First Search (BFS)

BFS és un algoritme de cerca no informada que explora tots els nodes a la mateixa distància del node inicial abans de passar a la següent distància. És útil per trobar el camí més curt en grafs no ponderats.

Exemple de Codi en Python

from collections import deque

def bfs(graph, start, goal):
    queue = deque([start])
    visited = set()
    parent = {start: None}

    while queue:
        node = queue.popleft()
        if node == goal:
            break
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                queue.append(neighbor)

    path = []
    while goal is not None:
        path.append(goal)
        goal = parent[goal]
    return path[::-1]

# Exemple d'ús
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print(bfs(graph, 'A', 'F'))  # Output: ['A', 'C', 'F']

Depth-First Search (DFS)

DFS és un altre algoritme de cerca no informada que explora tan profundament com sigui possible al llarg de cada branca abans de retrocedir. És útil per explorar totes les possibles solucions, però no garanteix trobar el camí més curt.

Exemple de Codi en Python

def dfs(graph, start, goal):
    stack = [start]
    visited = set()
    parent = {start: None}

    while stack:
        node = stack.pop()
        if node == goal:
            break
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                stack.append(neighbor)

    path = []
    while goal is not None:
        path.append(goal)
        goal = parent[goal]
    return path[::-1]

# Exemple d'ús
print(dfs(graph, 'A', 'F'))  # Output: ['A', 'C', 'F']

Dijkstra's Algorithm

L'algoritme de Dijkstra és un algoritme de cerca informada que troba el camí més curt en grafs ponderats. Utilitza una cua de prioritat per explorar els nodes amb el menor cost acumulat primer.

Exemple de Codi en Python

import heapq

def dijkstra(graph, start, goal):
    queue = [(0, start)]
    visited = set()
    parent = {start: None}
    cost = {start: 0}

    while queue:
        current_cost, node = heapq.heappop(queue)
        if node == goal:
            break
        if node in visited:
            continue
        visited.add(node)

        for neighbor, weight in graph[node].items():
            new_cost = current_cost + weight
            if neighbor not in cost or new_cost < cost[neighbor]:
                cost[neighbor] = new_cost
                parent[neighbor] = node
                heapq.heappush(queue, (new_cost, neighbor))

    path = []
    while goal is not None:
        path.append(goal)
        goal = parent[goal]
    return path[::-1]

# Exemple d'ús
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 2, 'E': 5},
    'C': {'A': 4, 'F': 3},
    'D': {'B': 2},
    'E': {'B': 5, 'F': 1},
    'F': {'C': 3, 'E': 1}
}
print(dijkstra(graph, 'A', 'F'))  # Output: ['A', 'B', 'D', 'E', 'F']

A* (A Estrella)

A* és un algoritme de cerca informada que combina les millors característiques de BFS i Dijkstra. Utilitza una funció heurística per estimar el cost restant fins a la destinació, fent-lo més eficient.

Exemple de Codi en Python

import heapq

def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star(graph, start, goal):
    queue = [(0, start)]
    visited = set()
    parent = {start: None}
    cost = {start: 0}

    while queue:
        current_cost, node = heapq.heappop(queue)
        if node == goal:
            break
        if node in visited:
            continue
        visited.add(node)

        for neighbor, weight in graph[node].items():
            new_cost = cost[node] + weight
            if neighbor not in cost or new_cost < cost[neighbor]:
                cost[neighbor] = new_cost
                priority = new_cost + heuristic(neighbor, goal)
                parent[neighbor] = node
                heapq.heappush(queue, (priority, neighbor))

    path = []
    while goal is not None:
        path.append(goal)
        goal = parent[goal]
    return path[::-1]

# Exemple d'ús
graph = {
    (0, 0): {(0, 1): 1, (1, 0): 1},
    (0, 1): {(0, 0): 1, (1, 1): 1},
    (1, 0): {(0, 0): 1, (1, 1): 1},
    (1, 1): {(0, 1): 1, (1, 0): 1, (2, 2): 1},
    (2, 2): {(1, 1): 1}
}
print(a_star(graph, (0, 0), (2, 2)))  # Output: [(0, 0), (1, 1), (2, 2)]

Exercicis Pràctics

Exercici 1: Implementació de BFS

Implementa l'algoritme BFS per trobar el camí més curt en un graf no ponderat. Prova'l amb diferents grafs i punts d'origen i destinació.

Exercici 2: Implementació de Dijkstra

Implementa l'algoritme de Dijkstra per trobar el camí més curt en un graf ponderat. Prova'l amb diferents grafs i punts d'origen i destinació.

Exercici 3: Implementació d'A*

Implementa l'algoritme A* per trobar el camí més curt en un graf ponderat. Prova'l amb diferents grafs i punts d'origen i destinació, i ajusta la funció heurística per veure com afecta el rendiment.

Resum

En aquesta secció, hem explorat diversos algoritmes de cerca de camins, incloent BFS, DFS, Dijkstra i A*. Hem vist com aquests algoritmes poden ser implementats en Python i hem proporcionat exemples pràctics per ajudar a comprendre el seu funcionament. Els exercicis pràctics proporcionats permeten reforçar els conceptes apresos i aplicar-los en situacions reals.

En el següent tema, ens centrarem en la implementació de l'algoritme A* en un entorn de videojoc, utilitzant eines i tècniques específiques per a la navegació en temps real.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats