map with nodes for route finder

Jai

can someone point out to me HOW can i assign a node across the entire image? as in not i follow the instructions as stated in the below setup BUT hmmmmm not really working out, i mean i did one just to check it out so i did something like 1 5 5 which means id #1 x5 y5 so this translates into one node in the top right corner but here is where i come in trying to get that advise from the community, when i get that node and i try to link one node with the current made node "ID1"and i get a error msg saying "No route found" - (this msg was copy from the processing window)

# map.txt

# Declare the node positions between tags <nodes></nodes>.

# 1st = the unique id number for the node it should be >= 0
#       but the id numbers do not need to start with zero or
#       be sequential
# 2nd = the horizontal location of the node
# 3nd = the vertical location of the node

# although the locations are expressed as integers in this
# file they are interpreted as floats.


<nodes>
1 10 10
100 40 100
101 124 105
102 171 102
103 210 99
104 271 96
105 266 67
106 139 161
107 163 162
108 210 140
109 106 203
110 184 179
111 219 170
112 110 240
113 133 247
114 132 229
115 219 243
116 267 259
117 247 299
118 269 298
119 291 285
120 166 211
130 163 263
131 152 297
132 235 339
</nodes>



# Declare the edges between tags <edges></edges>.
# 1st = the node id for the 'from' node
# 2nd = the node id for the 'to' node
# 3rd = the cost of traveling 'from' >> 'to'
# 4th = the cost of traveling 'to' >> 'from'
# If either cost is 0 (zero) then the demo program
# calculates the Euclidean (shortest) distance between
# them and uses that as the cost.
# If either cost is <0.0 then that edge will not be
# created.
# The fourth value is optional and if missing then the 
# edge will not be created (equivalent to -1)
#
# although the costs are expressed as integers in this
# file they are interpreted as floats by the program
#

<edges>
100 101 84 84
101 102 46 46
101 109 98 98
102 103 37 37
102 106 68 68
103 104 61 61
103 108 39 39
104 105 29 29
106 107 40 40
106 109 55 55
107 108 50 50
107 110 27 27
108 111 45 45
109 112 37 37
110 111 48 48
110 115 73 73
110 120 37 37
112 113 36 36
113 114 18 18
113 120 41 41
113 130 38 38
115 116 52 52
116 118 39 39 
116 119 57 38
117 118 21 21
117 130 92 92
117 132 39 39
118 119 42 28
120 130 48 48
130 131 40 40
131 132 94 94
</edges>

well as you can see of where im going with this i would like to upload a map "depending on the situation" and simply calculate the best shortest route following the vector from start point "street" and stay on the street because as in now what ends up happening is that i start here and when i specify the end point it appears that the best trajectory to follow is cutting thru my neighbors property lol and thats no good lol.

What is it that i should be tuning in this txt? i feel like it has something todo with

# 2nd = the node id for the 'to' node
# 3rd = the cost of traveling 'from' >> 'to'
# 4th = the cost of traveling 'to' >> 'from'

but im not sure? i hope someone slick enough can break this down for me.

Chrisir

is this a library example ? where from ? post the link.

Which library is it?

post your entire code.

if it is a library you can adress the creator directly here in the forum

write his name with an @ sign like @Chrisir

Chrisir

you know the difference between edge and node, right?

node is a spot / point like your house.

edge is a connection between two nodes.

now, when you want to go from A to B without cutting through the neighborhood I guess what you have to do is to declare all crossings as nodes manually and connect all crossings / nodes where possible.

only then the library knows the layout of the map and can calculate the route.

I guess you basically have to rewrite the whole list of nodes and edges first

you can start with those edges and nodes that are necessary for the example you want to experiment with first

Jai

right i understand what i dont understand is in this

<edges>
100 101 84 84

what is those 84 84 for ? "the cost of traveling, WHAT COST? " ic a pattern but dont see any association with the whole why double number, and yes this is the pathfinder i think is called ? i try to get info on this but when i try to get reference processing dont redirect me to the site for more info

Chrisir

Link = ?

Chrisir

https://forum.processing.org/one/topic/understanding-the-pathfinder-library.html

Chrisir

as said you can ask the author directly by using @ and his name quark here

he will get notified then

for cost I quote :

A weighted graph is a graph in which a number (the weight) is assigned to each edge.[9] Such weights might represent for example costs, lengths or capacities, depending on the problem at hand. Some authors call such a graph a network.[10] Weighted correlation networks can be defined by soft-thresholding the pairwise correlations among variables (e.g. gene measurements). Such graphs arise in many contexts, for example in shortest path problems such as the traveling salesman problem.

https://en.wikipedia.org/wiki/Graph_(mathematics)

Hence I guess it's OK to assign all the value 1 or a value proportional to its length. I guess.

Or ask quark.

WHY don't you just read his links...?

http://www.lagers.org.uk/pfind/index.html

quark

The links in the library download got messed up when I was upgrading for PS3. They were fixed on 29-11-2015 so you could delete the library and reinstall it through the PDE.

Nodes can be thought of as places to visit and edges the routes between places to visit.

In the example code you posted you added a node (place to visit) with

<nodes>
1 10 10
...

BUT you didn't added a route to it. Try adding an edge between node 1 and 100 with

<edges>
1 100 80 80
100 101 84 84
101 102 46 46
101 109 98 98
...

So now we come to the weighting which is the cost of traveling along an edge.

The easiest way is to think of it as a 'toll' and the edge then becomes a 'toll road'. Now imagine that you have a bag of gold coins and to travel along an edge you have to pay the weighting in gold coins. Now assume you want to travel from node 1 to node 102 how much will it cost?

  1 > 100  80
100 > 101  84
101 > 102  46

The cost is 80+84+46 = 210

The point of path finding is to find the least expensive route.

Notice that we have two weightings - that is because the cost of traveling the edge maybe different depending on the direction traveled.

The simplest weighting is the distance between nodes and the library will calculate this for you. Assume you have two nodes

<nodes>
500 20 20
510 50 60
...

The distance between these nodes is 50 (using Pythagoras) so we could have the edge as

500 510 50 50

but if we have a lot of nodes that is a lot of calculator work so if you use this

500 510 0 0

the library will calculate the distance (and hence the cost) for you.

Lets take this further. Assume that we are creating an adventure game and node 500 is at the top of a cliff and 510 a river at the bottom of the cliff. Now the weighting represent the amount of energy a player uses to travel between nodes. We might express the edge as

500 510 2 3000

So we use 2 energy units to jump into the river but 3000 units to climb the cliff.

That makes sense but what if it is impossible to climb the cliff? We can change the edge to

500 510 2 -1

a negative weighting means there is no route it that direction.

Hope this helps :)

Chrisir

thanks for jumping in here, dear @quark

Best, Chrisir ;-)

Jai

thanks guys and by the way i guess based on your explanation i guess what i was trying to do was make everywhere a point of interest except the shaded or black areas on the map 'this being any map i import in from a 2d hud view ' and in regards to the toll i think it be best to just use 0 and "library will calculate the distance (and hence the cost) for me." and when i say shaded or dark areas i means as in the (maze) section, and these areas might be cars homes green grass water and all these are off limits for the "cost"

maybe im thinking i should do a nodeX[nodeX.array] [cost][cost] and a nodeY[nodeY.array] [cost][cost] and make this array xxxXxxxX pixel of the window screen, draw's width and height ? void Collision(PImage.Shapes) "PImage is the rectangles or squares aka dark or shaded buildings from the imported map"????

something like this maybe?

Xnode[] Y.height;
Ynode[] X.width;
Edges[]
int Cost = 0;
int Array X,Y;


void setup()
{
  size(640,480);
}

void draw()
{

}

i dont know what im doing but i do understand the language a bit, so i know theirs some syntax issues but just an idea

nthomasvan

Dear @quark,

I am trying to use your pathfinder library, and I was wondering if you can return an array of the Nodes used in the route as node IDs? Because when I am printing out the rNodes "node route", it gives me stuff like pathfinder.GraphNode@18d54229.

Thanks, Thomas

quark

@nthomasvan

The simple answer is no, but you can create a function to do it for you

// This function accepts an array of GraphNode objects
// and returns an array of their IDs
int [] nodeIDs (GraphNode [] nodes){
  int[] ids = new int [nodes.length];
  for (int i = 0; i < ids.length; i++)
    ids [i] = nodes [i];
  return ids;
}