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\$
  • 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 Jul 8 at 9:50
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\$
  • \$\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 Jul 8 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 Jul 8 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 Jul 8 at 11:36
  • 1
    \$\begingroup\$ @PaulReed you can generate the nodes and edges as needed \$\endgroup\$ – ratchet freak Jul 8 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.