0
\$\begingroup\$

I'm working on an algorithm to generate a "graph" like array of points in my game world. See Image Below:

Exhibit A

Here is what i'm working on so far, which will generate the black line.. but this may not be the best route.

var angle = Math.random()*Math.PI*2;
var rx = Math.cos(angle)*radius + lastPointX;
var ry = Math.sin(angle)*radius + lastPointY;
lastPointX = rx; 
lastPointY = ry;
points.push(new GamePoint(0, game, rx, ry));

I'm trying to expand upon this to make various other "branches" to add a randomness to the game but at all times the player has to have at least one option to move forward ( if not more ). Paths can cross but shouldn't get too close / overlap.

I'd eventually want the game to consist of multiple paths ( see image below ). The player will move up but doesn't see the whole "graph".

Exhibit B

\$\endgroup\$
  • \$\begingroup\$ What is the intent of the design? Why do you need this? What's the final objective you're trying to achieve? \$\endgroup\$ – Vaillancourt Jan 24 '16 at 6:54
  • \$\begingroup\$ Are you generating a tree (=the paths cannot meet each other, no circles) or a graph? On the bottom image there is a graph, not a tree. While this might seem irrelevant, many algorithms work only on trees. \$\endgroup\$ – wondra Jan 24 '16 at 10:53
  • \$\begingroup\$ I suppose I am trying to make a graph. \$\endgroup\$ – sirmdawg Jan 24 '16 at 16:54
1
\$\begingroup\$

It looks to me like you can use a variant on a Poisson disc sampling algorithm to achieve this.

Check out Mike Bostock's wonderful visual demonstration of these algorithms, particularly the explanation of Bridson's algorithm about a quarter of the way in.

Diagram of Bridson's algorithm from Mike Bostock's site

Here you store your points in a grid where the cell size is r/sqrt(2) - that way if all your points are a distance of at least r apart, then there is at most one point in each grid cell. This speeds up our neighbour checks.

Start with at least one point, classified as a frontier point (those are the red dots in the diagram above)

In each iteration, select a point on the frontier. Randomly generate candidate points around it, at a range of at least r (the Poisson disc example uses a range from r to 2r but you can tune this). To get an "upward" growth like in your example, you might want to bias this random sample vertically.

As you generate each candidate, check to see if it's out of bounds, or if any other points are within r of it. (Using the grid, you only need to check certain cells)

21 cells that need checking for neighbours

If the candidate is too close to an existing point, reject it and generate a new candidate. If you exceed a maximum number of attempts without success, give up and mark the parent point as no longer part of the frontier. (This will terminate a branch)

If the candidate has no other points within a distance of r, add it to the grid as a new frontier point.

Here's where we'll break from the normal Poisson disc sampling algorithm: instead of leaving the parent point as part of the frontier, we can choose to immediately remove it from the frontier once it's spawned a single child point. This will produce chains of points instead of a dense cloud.

To get branching, we can occasionally allow a point to spawn 2 child points before it's removed from the frontier. (We can balance our tolerance based on the number of branches, ie. the size of the frontier set, to avoid spawning too dense a shrub)

This should get you pointed in a useful direction. Some improvements you can make from here:

  • make your peer repulsion distance larger than your parent-child spawning distance, to keep branches spaced apart

  • refine the branch termination condition - maybe if a candidate point is almost equidistant between the parent point and a point from a different branch, you place it as a non-frontier point to "merge" the two branches back together rather than rejecting it.

| improve this answer | |
\$\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.