0
\$\begingroup\$

I'm building a sort of city building sim and would like the ability for people to automatically place roads (or rail) based on a start and end point and for the sim to calculate the optimal route. I thought this would be relatively easy to do with normal path finding but I'm finding it challenging to deal with impassable obstacles and areas where you really wouldn't want a road/rail unless there was no other option!

See an example below - the difficult terrain might be a swamp or a park which we'd like to preserve if possible and the impassable might be really bad terrain, or something protected - for example a National Park.

Problem space - varying terrain

I thought about using Dijkstra's algorithm but there is no real set of routes/nodes - as you can see the possible routes are quite open, same with A*. The areas covered would also be quite large so I'm trying to avoid a grid based system - I'm wondering if there is a vector based path finding algorithm? I found this https://faculty.nps.edu/ncrowe/opmpaper2.htm which creates a grid of vectors which looks halfway to what I want, but again could be quite expensive on a large area.

Possible, but expensive solution

Any suggestions would be appreciated!

Thanks,

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Typical solutions here include A* on a nav mesh, where you can represent large convex areas with consistent pathing attributes as a single polygon, cutting down on the number of graph nodes needed. Have you tried applying something like this to your case? There's also Theta* which you may find useful, particularly if your route has limits on its turning radius. \$\endgroup\$
    – DMGregory ♦
    Commented Jul 8, 2019 at 9:50

1 Answer 1

Reset to default
2
\$\begingroup\$

A* and Dijkstra work based on a graph of nodes. They don't need to be grid based.

So you can create a node for each section and then generate next options based on that.

Given a node you have a position and a direction (and a curve if you want to generate smooth curves), From that you can create several candidates by adjusting the length and new curve. Each of those candidates would have a cost based on the terrain the section goes through.

The A* heuristic can be a simple distance from endpoint to the goal.

The trick bit would be limiting the candidate generation Which you can do by keeping the distance per segment large in a first generation per node then allow shorter segments to be generated.

\$\endgroup\$
4
  • \$\begingroup\$ Ok - So I can work with graphs. But generating graph nodes for each section, what do you mean by this? Generate a node for each vertex for each zone in the first drawing above? \$\endgroup\$
    – Paul Reed
    Commented Jul 8, 2019 at 11:10
  • 1
    \$\begingroup\$ The track is created in sections, This can be a curve or a straight section, Each node is placed at the end points of each section, connected sections share an endpoint. To keep A* correctness you need to ensure that direction is part of the node data you use to differentiate, so you can avoid generating right angles. \$\endgroup\$
    – ratchet freak
    Commented Jul 8, 2019 at 11:20
  • \$\begingroup\$ Yeah, I'm not getting this - don't you need a full graph in place before undertaking A*? \$\endgroup\$
    – Paul Reed
    Commented Jul 8, 2019 at 11:36
  • 1
    \$\begingroup\$ @PaulReed you can generate the nodes and edges as needed \$\endgroup\$
    – ratchet freak
    Commented Jul 8, 2019 at 12:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .