ok, I was looking at several tutorials for writing a path finder most where in the wrong language. After failing at that I decided to check if processing has a path finder library which it does but I can’t find a tutorial to tell me how to use it. So far I found it has 4 path finders in it & I decided I want to use A*. Can anyone send me a link of how to use the library or a java tutorial on pathfinding.
If you skip to the end you might even find a link to the working code.
that is in the wrong language. I just watched it. That uses java script not java
It’s in p5.js, which is literally based of Processing and is therefore very similar despite being a Javascript library rather than a Java one.
If you need some help converting then don’t be afraid to ask!
Here is even a thread on it:
If you are referring to this Path Finder, it comes with a working example. It is quite long but there are many different options. If you are interesting only in the A* path finder algorithm, you can narrow the code down to the line that concern only that particular algorithm, get rid of all the GUI elements, deal with only 1 map and then you will have the basic on how to use it.
I tried pulling up the example only got a page that said the library has 4 different path finding functions
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
ty, for that. I so love it. Is there a fast way to create one that covers the screen like a 600,600 where each 25 X 25 square is a node? Or do I need to do node = new graphicnode for the thousands of them? Are you edges the lines? between the nodes?
You can easily do this in a double loop.
Yes - an edge is a connection between two nodes
I tried double loop with i and j inside it but didn’t come out right
There are several ways to do this but the double loop makes it easier when calculating the x,y coordinates of the node. You also need to work out how you are going to allocate node IDs because you need this information to add the edges.
So you want a 600x600 pixel screen with a node at the centre of cells in a 24x24 grid. This means that you are going to have 578 nodes. Starting from the top left corner we will number the cells starting from 0 and go left-to-right and top-to-bottom
So in the top row the nodes are numbered 0-23, the next row 24-47 and the bottom row 552-575.
For each horizontal row we need to connect adjacent nodes so
1 <-> 0
2 <-> 1
3 <-> 2
…
23 <-> 22
The next row would be
25 <-> 24
24 <-> 23
23 <-> 22
…
47 <-> 46
Notice that they are the same as the numbers for the first row with 24 added. Continue this for each row.
The vertical edges are similar if we consider the first 2 rows we need to connect
24 <-> 0
25 <-> 1
26 <-> 2
…
47 <-> 23
I have modified the example above to demonstrate how this works.
/**
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(600, 600);
textSize(8);
// 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, 517);
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(240, 255, 240);
for (int i = 0; i < nodes.length; i++) {
GraphNode node = nodes[i];
ellipse(node.xf(), node.yf(), 6, 6);
text(node.id(), node.xf() + 4, node.yf() - 2);
}
}
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;
int node_id = 0;
for (int v = 0; v < 24; v++) {
for (int h = 0; h < 24; h++) {
node = new GraphNode(node_id, 12 + h * 25, 12 + v * 24);
graph.addNode(node);
node_id++;
}
}
// Create horizontal edges
for (int v = 0; v < 24; v++) {
for (int h = 1; h < 24; h++) {
graph.addEdge(v * 24 + h-1, v * 24 + h, 0, 0);
}
}
// Create vertical edges
for (int h = 0; h < 24; h++) {
for (int v = 1; v < 24; v++) {
graph.addEdge(v * 24 - 24 + h, v * 24 + h, 0, 0);
}
}
}
1 Like
i didn’t mean 24 X 24 i meant i want each node to be 24.
I am not sure how to interpret this in any other way than I did in the sketch.
That doesn’t make sense - 24 what???
Why not include a drawing of what you mean.
Sorry didn’t read whole thing or did the math. I’ll try your ideas and see if it get me what I want. TY that code was what I meant. How would I get the path to an enemy now? & also place walls in for the enemy to go around. I’ll send pic in second of what I’m asking. OK, this picture is what I’m asking in this question not the last one. The grid is in the back not seen I need it to draw the white line to the target and then tranfer that data to the enemy so he can move.
I never did understand how coding train made his avoid stuff. Here is the grid showing.The red is where the wall should be at 24 through like 45 or something like that.
As you can see the path just goes straight down as all the nodes are free to travel through.