Creating a Road Network with A* - how to start?

#1

Heyhey!
so i got inspired by this post which explains how to generate roads/paths on a random generated terrain.:

i always used A* for single navigations, so going from point A to B but never created a path network and to be honest i dont know how to start.
this is how the path looks at the moment. nothing complicated.

but how do i create a big path network with junctions and all that stuff?
do you have any examples somewhere or a hint what i have to look up?

thanks!

#2

Hi

You probably want to use a point graph for this. In the point graph example scene you can see how one can be set up. You might want to only use manual links for every connection (there are a few examples of that as well in that scene).

#3

Hm. I checked out that blog post and I think I misunderstood your question.
What you want is probably to first increase the resolution of that grid graph a bit (it looks too low resolution to capture any relevant detail) and then you want to add penalties to the nodes. If you have the pro version there is an option to use the slope as a penalty (check the ‘Advanced’ section of the grid graph settings) and if the result of that is unsatisfactory you can always control the penalty yourself using scripts or use a texture where each pixel decides the penalty for a node (also an option in the pro version).

Now, this will not actually be exactly what they did in the blog post as these penalties are only per node, not per connections (a higher resolution will fix this though), and grid nodes will only use their 8 adjacent nodes (which I think is better solved using post processing, maybe using the funnel modifier and the simple smooth modifier).

#4

hey, thanks for the answer
point graph! thank you, that was what i was looking for :slight_smile:

do you maybe have also have an idea how i could “paint” under the connections?
for example lets imagine the PointGraphExample.unity scene would be complete black, and the white stuff would get painted as soon as i hit play. would this even possible?

#5

Hi

That depends on what you want to use to paint. What you can get from the point graph are all connections (lines) between the nodes, then you will have to use some painting library.

#6

hey, sorry, had to be more precise with my question.
so painting on a terrain at runtime is no problem.
i think all i need know now is how to get the world coordinates… or whatever coordinates - of the connections/lines so i can hand that over to the terrain painting stuff

#7

Ok.
You can use something like this.

var graph = AstarPath.active.astarData.pointGraph;
// Alternatively use the graph.nodes array
graph.GetNodes(node => {
       // Alternatively use the node.connections array
       node.GetConnections(otherNode => {
              // We will find each connection *twice* since connections go in both directions
              // so use the node index as a tie breaker to only paint each connection once
              if (otherNode.NodeIndex < node.NodeIndex) {
                   Vector3 p1 = (Vector3)node.position;
                   Vector3 p2 = (Vector3)otherNode.position;
                   // Paint from p1 to p2
              }
       });
});
1 Like
#8

awesome! that will help me a lot! thanks again,
okay, i got one last question. promised :smiley:
this is how my beautiful terrain looks now :smiley:

astar.jpg1918×754 176 KB

so i want to achieve two things now:
if the mountain is to high, go around (red)
if the mountain is not to high, align the path to the height

#9

Hi

Well. To get those red paths you will either have to manually add it to the point graph or you will have to create a grid graph with a relatively high resolution, there is no way the pathfinding can know how to “go around” a mountain otherwise.

#10

ok, understand. thanks.
so this is how it looks now:

astar2.jpg1450×975 487 KB

i have a grid graph and a point graph.
when i send now a seeker from the start node to the node in the middle, he is calculating actually the right right path and “draws” it how i wanted it.
the thing now is, how do i sent a seeker from all nodes to next node? - so that i have this green line between all nodes. or is this a stupid idea what i am doing there?

#11

ok, got it working now.
i gave every village a seeker and a AiPath.cs and the target is the nearest village. that works for me

now i only need a list of all waypoints as Vector 3 from a path so i can paint on the terrain

#12

Hi

Ok.
You can also request paths directly like described on this page: http://arongranberg.com/astar/docs/calling-pathfinding.php#calling-directly
The points are stored in the vectorPath list on the path object.

1 Like