# Guia de Pathfinding A*
## 🗺️ Visão Geral
O sistema de pathfinding permite que NPCs e inimigos naveguem pelo mundo de forma inteligente, evitando obstáculos e encontrando o caminho mais curto até o destino.
## 🎯 Conceitos Básicos
### GridPos - Posição no Grid
```rust
use sevenx_engine::GridPos;
let start = GridPos::new(5, 5);
let goal = GridPos::new(20, 15);
// Calcular distância
let distance = start.distance(&goal); // Euclidiana
let manhattan = start.manhattan_distance(&goal); // Manhattan
```
### Pathfinder - Sistema de Navegação
```rust
use sevenx_engine::Pathfinder;
// Cria grid 40x30
let mut pathfinder = Pathfinder::new(40, 30);
// Adiciona obstáculos
pathfinder.add_obstacle(10, 10);
pathfinder.add_obstacle(10, 11);
pathfinder.add_obstacle(10, 12);
// Remove obstáculo
pathfinder.remove_obstacle(10, 11);
// Configura movimento diagonal
pathfinder.allow_diagonal = true;
```
## 🚀 Uso Básico
### Encontrar Caminho
```rust
let start = GridPos::new(0, 0);
let goal = GridPos::new(20, 20);
if let Some(path) = pathfinder.find_path(start, goal) {
println!("Caminho encontrado com {} passos", path.len());
for pos in path {
println!("Passo: ({}, {})", pos.x, pos.y);
}
} else {
println!("Nenhum caminho encontrado!");
}
```
### Verificar se Posição é Válida
```rust
let pos = GridPos::new(10, 10);
if pathfinder.is_walkable(&pos) {
println!("Posição válida!");
} else {
println!("Posição bloqueada ou fora do grid");
}
```
## 🎮 Exemplo: NPC que Persegue o Jogador
```rust
use sevenx_engine::*;
struct ChaseGame {
pathfinder: Pathfinder,
player_pos: GridPos,
enemy_pos: GridPos,
enemy_path: Option<Vec<GridPos>>,
cell_size: i32,
path_update_timer: f32,
}
impl GameState for ChaseGame {
fn new() -> Self {
let mut pathfinder = Pathfinder::new(40, 30);
// Cria labirinto
for x in 10..30 {
pathfinder.add_obstacle(x, 15);
}
for y in 5..20 {
pathfinder.add_obstacle(20, y);
}
Self {
pathfinder,
player_pos: GridPos::new(5, 5),
enemy_pos: GridPos::new(35, 25),
enemy_path: None,
cell_size: 20,
path_update_timer: 0.0,
}
}
fn update(&mut self, dt: f32, input: &sevenx_engine::input::InputHandler, _world: &mut World) {
// Move jogador
let mut new_player_pos = self.player_pos;
if input.is_key_just_pressed(KeyCode::ArrowUp) {
new_player_pos.y -= 1;
}
if input.is_key_just_pressed(KeyCode::ArrowDown) {
new_player_pos.y += 1;
}
if input.is_key_just_pressed(KeyCode::ArrowLeft) {
new_player_pos.x -= 1;
}
if input.is_key_just_pressed(KeyCode::ArrowRight) {
new_player_pos.x += 1;
}
if self.pathfinder.is_walkable(&new_player_pos) {
self.player_pos = new_player_pos;
}
// Atualiza caminho do inimigo a cada 0.5 segundos
self.path_update_timer += dt;
if self.path_update_timer > 0.5 {
self.path_update_timer = 0.0;
self.enemy_path = self.pathfinder.find_path(
self.enemy_pos,
self.player_pos
);
}
// Move inimigo ao longo do caminho
if let Some(path) = &self.enemy_path {
if path.len() > 1 {
self.enemy_pos = path[1];
}
}
}
fn draw(&mut self, _world: &World, frame: &mut [u8]) {
let width = 800;
// Desenha grid
for y in 0..self.pathfinder.grid_height {
for x in 0..self.pathfinder.grid_width {
let pos = GridPos::new(x, y);
let px = x * self.cell_size;
let py = y * self.cell_size;
let color = if self.pathfinder.obstacles.contains(&pos) {
[100, 50, 50, 255] // Obstáculo
} else if pos == self.player_pos {
[50, 255, 50, 255] // Jogador
} else if pos == self.enemy_pos {
[255, 50, 50, 255] // Inimigo
} else {
[60, 60, 60, 255] // Vazio
};
draw_rect(frame, width, px, py, self.cell_size - 2, color);
}
}
// Desenha caminho
if let Some(path) = &self.enemy_path {
for pos in path {
let px = pos.x * self.cell_size;
let py = pos.y * self.cell_size;
draw_rect(frame, width, px, py, self.cell_size - 2, [100, 100, 255, 255]);
}
}
}
}
```
## 🎨 Exemplo: Obstáculos Dinâmicos
```rust
impl GameState for DynamicObstacles {
fn update(&mut self, dt: f32, input: &InputHandler, _world: &mut World) {
// Adiciona/remove obstáculos com clique do mouse
if let Some((mx, my)) = input.mouse_position() {
let grid_x = (mx as i32) / self.cell_size;
let grid_y = (my as i32) / self.cell_size;
if input.is_mouse_button_just_pressed(0) {
// Botão esquerdo: adiciona obstáculo
self.pathfinder.add_obstacle(grid_x, grid_y);
// Recalcula caminho
self.path = self.pathfinder.find_path(self.start, self.goal);
} else if input.is_mouse_button_just_pressed(1) {
// Botão direito: remove obstáculo
self.pathfinder.remove_obstacle(grid_x, grid_y);
// Recalcula caminho
self.path = self.pathfinder.find_path(self.start, self.goal);
}
}
}
}
```
## 🌍 Integração com Tilemap
```rust
// Converte tilemap em obstáculos
for y in 0..tilemap.height {
for x in 0..tilemap.width {
if let Some(tile) = tilemap.get_tile(x, y) {
if tile.solid {
pathfinder.add_obstacle(x as i32, y as i32);
}
}
}
}
```
## 🎯 Múltiplos Inimigos
```rust
struct Enemy {
pos: GridPos,
path: Option<Vec<GridPos>>,
speed: f32,
}
struct MultiEnemyGame {
pathfinder: Pathfinder,
player_pos: GridPos,
enemies: Vec<Enemy>,
}
impl GameState for MultiEnemyGame {
fn update(&mut self, dt: f32, input: &InputHandler, _world: &mut World) {
// Atualiza cada inimigo
for enemy in &mut self.enemies {
// Recalcula caminho periodicamente
enemy.path = self.pathfinder.find_path(
enemy.pos,
self.player_pos
);
// Move ao longo do caminho
if let Some(path) = &enemy.path {
if path.len() > 1 {
enemy.pos = path[1];
}
}
}
}
}
```
## ⚡ Otimizações
### Cache de Caminhos
```rust
use std::collections::HashMap;
struct PathCache {
cache: HashMap<(GridPos, GridPos), Vec<GridPos>>,
}
impl PathCache {
fn get_path(&mut self, pathfinder: &Pathfinder, start: GridPos, goal: GridPos) -> Option<Vec<GridPos>> {
let key = (start, goal);
if let Some(path) = self.cache.get(&key) {
return Some(path.clone());
}
if let Some(path) = pathfinder.find_path(start, goal) {
self.cache.insert(key, path.clone());
return Some(path);
}
None
}
fn invalidate(&mut self) {
self.cache.clear();
}
}
```
### Atualização Espaçada
```rust
// Não recalcula todo frame
if self.path_timer > 0.5 {
self.path_timer = 0.0;
self.path = pathfinder.find_path(start, goal);
}
```
### Limitar Distância de Busca
```rust
// Só busca caminho se estiver perto
let distance = start.manhattan_distance(&goal);
if distance < 50 {
self.path = pathfinder.find_path(start, goal);
}
```
## 🎮 Dicas de Design
1. **Movimento Suave**: Interpole entre posições do grid
2. **Antecipação**: Calcule caminho alguns passos à frente
3. **Variação**: Adicione aleatoriedade para NPCs mais naturais
4. **Grupos**: Use formações para múltiplos NPCs
5. **Prioridades**: NPCs diferentes podem ter custos diferentes para terrenos
## 📊 Complexidade
- **Tempo**: O(n log n) onde n é o número de células
- **Espaço**: O(n) para armazenar o caminho
- **Grids recomendados**: Até 100x100 para 60fps
Execute o exemplo:
```bash
cargo run --example pathfinding_demo
```