NavMesh + path-finding + obstáculos dinâmicos em JS/WASM
npm install mesh-pilotgetBoundingBox(): Retorna o retângulo mínimo que envolve o polígono.
getEdges(): Lista de arestas (segmentos) do polígono.
getCenter(): Centro geométrico (média das coordenadas).
containsPoint(point): Verifica se um ponto (x,y) está dentro do polígono.
getWidth(): Retorna a largura do polígono com base na bounding box.
allowedLayers e layer: Define em qual camada o polígono se encontra e quais camadas ele permite.
addPolygon(poly): Adiciona um polígono à malha.
buildGraph(): Constrói o grafo de adjacências sem considerar obstáculos.
buildGraphConsideringObstacles(obstacles): Constrói o grafo considerando uma lista de obstáculos (bloqueios).
enableDynamicObstacles(): Habilita o sistema de obstáculos dinâmicos.
cloneGraph(): Retorna uma cópia do grafo atual.
addObstacle(obstacle: Polygon): Adiciona um novo obstáculo e atualiza o grafo.
removeObstacle(obstacleId): Remove um obstáculo, liberando arestas do grafo.
updateObstacle(obstacleId, newObstacle): Atualiza forma/posição de um obstáculo.
getAdjacencias(nodeId): Retorna as arestas ligadas a um nó (vizinhança).
getNode(nodeId): Acessa o nó pelo ID.
clone(): Gera uma cópia profunda (Deep Clone) do grafo.
js
layerSystem.registerLayer("lava", { color: "#ff0000", traversalCost: 10 });
layerSystem.addFilter(
"lava",
LayerSystem.FILTER_TYPES.EXCLUSION,
(node, ctx) => {
return ctx.agentType !== "fire"; // exclui se o agente não for de fogo
}
);
`
$3
- Fornece métodos estáticos para encontrar caminhos em um grafo.
- Suporta:
- A\* (A_STAR)
- Dijkstra
- BFS
- DFS
- Cada método aceita configurações como:
- heuristic, costFunction, validator (funções callback).
- maxIterations, partialPath, etc.
- Exemplo:
`js
const pathResult = Pathfinder.findPath({
graph,
start: { x: 10, y: 50 },
end: { x: 300, y: 350 },
method: "A*",
heuristic: (a, b) => Math.hypot(a.x - b.x, a.y - b.y),
});
`
$3
- Classe que desenha todo o conteúdo no Canvas:
- Polígonos, arestas, obstáculos, caminho atual, nós, grid, rótulos etc.
- Simplifica o debug, pois exibe em tempo real tudo que acontece.
- Principais métodos:
- draw(): Faz o desenho completo.
- toggle(enabled): Liga/desliga a visualização.
- captureDebugData(): Retorna dados de estado e logs de eventos.
- highlightAccessibleAreas(profile): Demonstra quais áreas são acessíveis a certo tipo de agente.
- drawAllAgentPaths(): Desenha caminhos de todos os agentes ativos.
---
Instalação e Estrutura de Pastas
A estrutura das pastas é:
`
src/
navmesh/
EventEmitter.js
NavMesh.js
Polygon.js
DynamicObstacleManager.js
LayerSystem.js
pathfinding/
Graph.js
Pathfinder.js
AgentManager.js
debug/
DebugVisualizer.js
`
4.1 Instalação
Via npm:
`bash
npm install mesh-pilot
`
Manual/local:
- Baixe ou clone este repositório
- Copie a pasta mesh-pilot para o seu projeto
- Importe diretamente os arquivos de ./src/index.js no seu código.
---
Exemplo Rápido (Quick Start)
Suponha que você tenha um canvas em HTML e queira criar uma malha de navegação simples:
`js
import { NavMesh } from "./navmesh/NavMesh.js";
import { Polygon } from "./navmesh/Polygon.js";
import { DebugVisualizer } from "./debug/DebugVisualizer.js";
import { Pathfinder } from "./pathfinding/Pathfinder.js";
// 1) Crie o NavMesh
const navMesh = new NavMesh(true); // enableLogs = true (opcional)
// 2) Registre camadas (opcional)
navMesh.layerSystem.registerLayer("customLayer", {
color: "#ff00ff",
traversalCost: 2,
});
// 3) Adicione alguns polígonos
const poly1 = new Polygon(
[
{ x: 10, y: 10 },
{ x: 100, y: 10 },
{ x: 100, y: 80 },
{ x: 10, y: 80 },
],
{ layer: "customLayer" }
);
navMesh.addPolygon(poly1);
// 4) Construa o grafo (sem obstáculos inicialmente)
navMesh.buildGraph();
// 5) Exemplo: Encontrar caminho entre 2 pontos
const pathResult = Pathfinder.findPath({
graph: navMesh.graph,
start: { x: 12, y: 12 },
end: { x: 90, y: 70 },
method: "A*",
});
console.log("Path:", pathResult.path, "Distance:", pathResult.distance);
// 6) Visualizar no canvas
const canvas = document.getElementById("myCanvas");
const ctx = canvas.getContext("2d");
const debug = new DebugVisualizer(ctx, navMesh, {
showNodes: true,
});
debug.draw(); // Desenha tudo (polígonos, arestas, etc.)
`
Nesse exemplo, adicionamos um polígono simples, construímos o grafo e buscamos o caminho via A\*. Depois, utilizamos o DebugVisualizer para desenhar tudo em tela.
---
Uso Avançado
$3
Para adicionar obstáculos em tempo real:
`js
// 1) Habilitar o gerenciador de obstáculos
navMesh.enableDynamicObstacles();
// 2) Criar um polígono representando obstáculo
const obstaclePoly = new Polygon([
{ x: 50, y: 50 },
{ x: 60, y: 50 },
{ x: 60, y: 60 },
{ x: 50, y: 60 },
]);
// 3) Adicionar ao gerenciador
const obstacleId = navMesh.dynamicObstacleManager.addObstacle(obstaclePoly);
`
O grafo será automaticamente atualizado (caso autoUpdate esteja habilitado), removendo arestas bloqueadas pelo obstáculo.
$3
`js
// Exemplo de filtro de exclusão
navMesh.layerSystem.addFilter("customLayer", "exclude", (node, context) => {
// Exclui polígonos se...
return node.polygon.getWidth() < 20;
});
`
$3
`js
const dijkstraResult = Pathfinder.findPath({
graph: navMesh.graph,
start: { x: 20, y: 20 },
end: { x: 300, y: 300 },
method: "DIJKSTRA",
});
`
---
API Detalhada
A seguir, listamos as classes e métodos-chave (já documentados no código-fonte):
1. NavMesh
- addPolygon(poly: Polygon): Adiciona polígono.
- buildGraph(): Constrói grafo simples.
- buildGraphConsideringObstacles(obstacles: Polygon[]): Constrói grafo levando em conta bloqueios.
- enableDynamicObstacles(options?): Inicializa o gerenciador de obstáculos.
- cloneGraph(): Retorna cópia do grafo atual.
- ...
2. Polygon
- new Polygon(vertices, options?): Cria polígono.
- getBoundingBox(), getEdges(), getCenter(), getWidth().
- containsPoint(point).
- ...
3. DynamicObstacleManager
- addObstacle(obstacle: Polygon), removeObstacle(id: string), updateObstacle(id: string, newObstacle: Polygon).
- Mantém índice espacial via SpatialGrid.
4. LayerSystem
- registerLayer(name: string, config: Object).
- addFilter(layer: string, type: string, condition: Function, scope?).
- applyFilters(nodes: any[], context?).
5. Graph
- nodes: {id, polygon}[].
- adjList: Map.
- getAdjacencias(nodeId), getNode(nodeId), clone().
6. Pathfinder
- findPath(config): Principal método, aceita A_STAR, DIJKSTRA, BFS, DFS.
- Diversos callbacks de customização (heuristic, costFunction, validator).
7. DebugVisualizer
- draw(), toggle(enabled), captureDebugData().
- highlightAccessibleAreas(profile), drawAllAgentPaths(), etc.
---
Boas Práticas e Dicas
1. Valide sempre seus polígonos: verifique se não há interseções indesejadas ou vértices desalinhados.
2. Use camadas com cautela: As camadas podem aumentar a complexidade, então utilize filtros somente quando necessário.
3. Otimize o Pathfinding: Se possível, defina uma boa heuristic para o A\* e uma costFunction coerente com o custo real de travessia do seu ambiente.
4. Obstáculos Dinâmicos: Gerenciar muitos obstáculos pode impactar o desempenho. Se tiver muitos, considere otimizar o cellSize do SpatialGrid.
5. DebugVisualizer: Em produção, você pode desativar (toggle(false)) para economizar recursos de desenho.
6. Agentes: Se estiver usando AgentManager`, mantenha cada agente com perfil de camada e custo condizentes com seu tipo (por exemplo, “veículo grande” vs. “humano”).