Processing java path finder

Processing
8

The PathFinder library was incorperated into my AI for Games library so I didn’t give it the attention it deserved when it came to documentation.

There are two stages to using the library
Stage 1 - Creating the graph
The graph structure comprises of nodes (destinations) and edges (routes between 2 nodes). The edges can be uni or bidirectional so you can create one-way roads if you want. Each edge can be weighted so could represent different terrain e.g. pasture, swamp, mountain etc.
Stage 2 - Search the graph.
Start with creating a search object for this graph based on the path finding algorithm you want to use. Then use this object to search the graph for a given start and end node.

The example below shows the basic code needed to do an A* path search. Note all edges are bidirectional with weights proportional to their lengths.

Hope this helps.

/**
 An exaample of using the PathFinder library to find a route using the
 A* algorithm.
 In this example all edges are bidirectional and have weights proportional
 to their lengths. The A* algorithm uses the 'As the Crow Flies' distance
 between nodes as its heuristic.
 
 Created by Peter Lager 2018
 */
import pathfinder.*;

// PathFinding_01
Graph graph;
// These next 2 are only needed to display 
// the nodes and edges.
GraphEdge[] edges;
GraphNode[] nodes;
GraphNode[] route;
// Pathfinder algorithm
IGraphSearch pathFinder;

// Used to indicate the start and end nodes as selected by the user.
GraphNode startNode, endNode;

void setup() {
  size(800, 300);
  textSize(20);
  // Create graph
  createGraph();
  // Get nodes and edges
  nodes = graph.getNodeArray();
  edges = graph.getAllEdgeArray();
  // Now get a path finder object
  pathFinder = new GraphSearch_Astar(graph);
  // Now get a route between 2 nodes
  // You can change the parameter values but they must be valid IDs
  pathFinder.search(2, 8);
  route = pathFinder.getRoute();
}

void draw() {
  background(0);
  drawGraph();
  drawPath();
  noLoop();
}

void drawGraph() {
  // Edges first
  strokeWeight(2);
  stroke(180, 180, 200);
  for (int i = 0; i < edges.length; i++) {
    GraphNode from = edges[i].from();
    GraphNode to = edges[i].to();
    line(from.xf(), from.yf(), to.xf(), to.yf());
  }
  // Nodes next
  noStroke();
  fill(255, 180, 180);
  for (int i = 0; i < nodes.length; i++) {
    GraphNode node = nodes[i];
    ellipse(node.xf(), node.yf(), 20, 20);
    text(node.id(), node.xf() - 24, node.yf() - 10);
  }
}

void drawPath() {
  strokeWeight(10);
  stroke(200, 255, 200, 160);
  for (int i = 1; i < route.length; i++) {
    GraphNode from = route[i-1];
    GraphNode to = route[i];
    line(from.xf(), from.yf(), to.xf(), to.yf());
  }
}

public void createGraph() {
  graph = new Graph();
  // Create and add node
  GraphNode node;
  //                   ID   X    Y
  node = new GraphNode(0, 40, 45);
  graph.addNode(node);
  node = new GraphNode(1, 395, 30);
  graph.addNode(node);
  node = new GraphNode(2, 80, 130);
  graph.addNode(node);
  node = new GraphNode(3, 175, 110);
  graph.addNode(node);
  node = new GraphNode(4, 295, 155);
  graph.addNode(node);
  node = new GraphNode(5, 410, 125);
  graph.addNode(node);
  node = new GraphNode(6, 530, 65);
  graph.addNode(node);
  node = new GraphNode(6, 600, 115);
  graph.addNode(node);
  node = new GraphNode(7, 60, 265);
  graph.addNode(node);
  node = new GraphNode(8, 330, 255);
  graph.addNode(node);
  node = new GraphNode(9, 510, 260);
  graph.addNode(node);

  // Edges for node 0
  graph.addEdge(0, 1, 0, 0);
  graph.addEdge(0, 2, 0, 0);
  graph.addEdge(0, 3, 0, 0);
  // Edges for node 1
  graph.addEdge(1, 3, 0, 0);
  graph.addEdge(1, 4, 0, 0);
  graph.addEdge(1, 5, 0, 0);
  graph.addEdge(1, 6, 0, 0);
  // Edges for node 2
  graph.addEdge(2, 3, 0, 0);
  graph.addEdge(2, 7, 0, 0);
  // Edges for node 3
  graph.addEdge(3, 4, 0, 0);
  // Edges for node 4
  graph.addEdge(4, 8, 0, 0);
  // Edges for node 5
  graph.addEdge(5, 6, 0, 0);
  graph.addEdge(5, 8, 0, 0);
  graph.addEdge(5, 9, 0, 0);
  // Edges for node 6
  graph.addEdge(6, 9, 0, 0);
  // Edges for node 7
  graph.addEdge(7, 8, 0, 0);
}
2 Likes