2
$\begingroup$

I'm writing software to dynamically create a random, generated world (civ-esque), populate it with settlements, and draw roads between them. It would be relatively easy to draw roads like this:

However, what I really want is a more "efficient" way of building roads. Something like this:

I appreciate that there must be a relationship between the length of line a and the angles at point x, but I just don't see it. Can anybody help?

Edit: I'm thinking we fix angle BxC at an arbitrary value, perhaps even chosen randomly between a range of values at computation-time to give each intersection some variety.

$\endgroup$
7
  • $\begingroup$ Are you saying you want to fix the length of line a and then let the lengths of xB and xC arbitrarily vary? $\endgroup$
    – Lewy
    Apr 12, 2013 at 10:00
  • $\begingroup$ The most effective way to connect cities with roads with respect to total road length can be shown to always have three roads at a time meet at $120$ degrees. It might not be the most effective from a logistical standpoint, though. $\endgroup$
    – Arthur
    Apr 12, 2013 at 10:01
  • $\begingroup$ I was thinking of fixing angle BxC, perhaps at 120 degrees like @Arthur said, thanks for pointing out my omission. $\endgroup$
    – GrumpyTechDude
    Apr 12, 2013 at 10:02
  • $\begingroup$ If you fix the angle $\measuredangle BxC$, the locus of $x$ is a circular arc between $B$ and $C$. The length $a$ is not fixed at all. Perhaps you could look for a $x$ on the circular arc that minimize $a$? $\endgroup$
    – achille hui
    Apr 12, 2013 at 10:22
  • 1
    $\begingroup$ While the optimum for total distance is given by the Fermat point (i.e. $120^\circ$) the "real" optimum wiould also consider how important the various links are. If much more transport occurs between $B$ and $C$ than with $A$, the point $x$ should be moved more and more towards the line $BC$. Similarly, the relative weight of $AB$ versus $AC$ would influence if $x$ should be closer to $B$ or to $C$, possibly $x$ might not be needed at all, and only roads e.g. $AB$ and $BC$ make the optimal solution. $\endgroup$
    – Hagen von Eitzen
    Apr 12, 2013 at 10:49

1 Answer 1

Reset to default
0
$\begingroup$

I'm guessing you care more about giving some variety to road layout than absolute shortest distance (in which case use Arthur's answer), so how about this:

Connect BC, then connect A to midpoint(BC). Let the length of line $a = A/2 \pm 20\%$, this will give you point x. Then randomly vary the angle of a $\pm 20$ degrees or so, and create lines xC and xB.

This might prove simpler than your idea of fixing BxC, depending on how you are coding things up.

$\endgroup$

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.