6
\$\begingroup\$

Got a procedurally generated world. It's succinctly described as an undirected acyclic graph where vertices are junctions and edges weights/length note the amount of time/effort guesstimated to be needed by the current player to traverse between vertices.

Now, the thing is that I'm not a big fan of permadeath as a feature to be forced on the player. It is a great thing for gamers that enjoy the added challenge but a deterrent to casual players. So now I'd like to add checkpoints evenly distributed across an existing game world.

My rule is that I don't want any spot (vertex) on the map to be more than T distance away from the nearest checkpoint with the added constraint that I want the smallest number k of checkpoints possible.

enter image description here

So brute force is not going to work cause the real graph has thousands of vertices. Now I'm wondering if there is a heuristic that can get a pretty good equivalent of the optimal result. Given k or T, I'd like to find the best setup.

\$\endgroup\$
  • \$\begingroup\$ Is the distance to nearest checkpoint calculated with respect to edge lengths, or hop count? And are checkpoints constrained to always lie on vertices, or can I encounter a checkpoint partway along an edge I'm traversing? \$\endgroup\$ – DMGregory May 20 '15 at 23:29
  • \$\begingroup\$ @DMGregory Good questions! In this case, the distance is computed with respect to edge length. The vertices are the only spots where the checkpoint can be added but knowing the exact point is interesting as well. \$\endgroup\$ – wolfdawn May 21 '15 at 12:54
  • \$\begingroup\$ I think there's an efficient dynamic programming option to get the optimal solution, but I'm still sorting out the details. Do you have any estimates of the size of T relative to your smallest/typical edges? ie. is a distance of T going to encompass at most say 3 edges end-to-end, or could I traverse dozens or hundreds of edges before accumulating a total length of T? \$\endgroup\$ – DMGregory May 21 '15 at 15:50
  • \$\begingroup\$ It is likely going to be around a hundred edges tops. \$\endgroup\$ – wolfdawn May 22 '15 at 5:01
  • \$\begingroup\$ You can decide check points while you are building the tree or you must/want to parse it later? \$\endgroup\$ – dnk drone.vs.drones May 22 '15 at 7:14
4
\$\begingroup\$

Looking at your image gives an idea of how this should work. Two points are apparent:

  1. Endpoint nodes (those with only one connected neighbour) are the least likely to have checkpoints, since they share with the fewest other nodes; endpoint nodes will in fact only contain a checkpoint iff they are isolated as a degenerate DAG, i.e. they have no neighbours in which case they must serve as their own checkpoint.
  2. Highest-order intersections, i.e. those providing a concourse to the most "arms" & "sub-arms" , are most likely to have checkpoints.

So... I would suggest a weight-based approach (this is a very rough answer as I'm pressed for time): assign a value of 1 to all end nodes. Walk "inward" from the end node. Now for the node you have walked to, look at all of it's neighbours that have already had a value assigned (at the start, just 1's) and make this node's value the sum of all of those. Repeat and continue. At each step, check whether you have met or exceeded T; if you have, cap the value at T (i.e. never allow any node's value to exceed T). As you get to intersections like the top left one marked in purple, you should start to get rather high values (if your graph is to be taken as a working result, then these would already have met or exceeded the value of T). Iterating further, ultimately those nodes directly between the purple nodes (four of them) will also be T. Thus your resultant graph is the purple intersections A & B, the two nodes between them, and B & C and the 2 nodes between those, or a linear graph of 7 nodes. This is a kind of "straight skeleton" or "watershed" as it is known in computational geometry or GIS, respectively. You are quite literally creating a watershed network out of the graph, that is, those edges closer in to the centre of the (mountain) network are highest up, whilst outlying ridges sit at a minimal height of 1 (sea level).

At this point, I suspect that selecting nodes off this skeleton in order to provide the best-spaced checkpoints should be a reasonably trivial exercise. Thousands of nodes or not (though hopefully down to hundreds by this point), graph operations are by their nature iterative and so the best you can do is O(n) in the number of nodes.

Of course the "skeleton" will not always be "straight", it may indeed branch. And that is as it should be if you want a workable solution for your game.**

EDIT I missed your comment about distance being computer by sum of edge lengths. You can factor this into the above calculation: Endpoint nodes must then be represented as zero (which is the distance from edge) while inner node weights are distance to nearest endpoint.

\$\endgroup\$
1
\$\begingroup\$

There are two questions here:

  1. How to assign the fewest number of checkpoints, so that every vertex is within at most T distance from some checkpoint.

  2. How to spread those checkpoints as evenly as possible.

Question 1 turns out to have a linear-time solution:

First, fix some root node arbitrarily. If this is a level, then some start/spawn point makes a natural choice. Next we define...

UncoveredDistance(node)
{
  greatest = 0

  // Initialize least > 0. If least drops to/below 0, it tells us
  // this node is covered by a checkpoint deeper in its descendant tree.
  least = 1

  foreach (child of node)
  {
    distance = UncoveredDistance(node)

    // We'll use NaN as a special value to indictate this branch should be ignored.
    if(isNaN(UncoveredDistance(node)))
       continue;

    // Greatest represents the depth of the deepest node descended from
    // this one that is still not covered by any checkpoint.
    greatest = max(greatest, distance)

    // least represents the most "spillover" coverage from a checkpoint
    // placed deeper in the tree. (Represented as negative uncovered distance)
    least = min(least, distance)
  }

  // If the spillover completely covers the uncovered nodes in our descendant tree, 
  // then this whole subtree is covered, with additional coverage to pass upward
  if(greatest + least <= 0) 
     greatest = least

  // Include depth from node's parent, so we know whether to place a checkpoint
  // before the next hop takes us too far away.
  // (Treat the root as having a rootwardEdgeLength of 0)      
  myDepth = greatest + node.rootwardEdgeLength      

  // If no later checkpoint could cover this whole subtree, add one now.
  if(myDepth > T)
  { 
     AddCheckpoint(node)
     myDepth = node.rootwardEdgeLength - T
  }

  // This whole subtree is already covered but without surplus,
  // so signal parent node to ignore this branch.
  if(myDepth > 0 && greatest <= 0 && least <= 0)
     return NaN

  // Pass upward any coverage surplus or shortfall we have.
  return myDepth
}

// Finally, kick off the process at the root:
if(UncoveredDistance(rootNode) > 0)
   AddCheckpoint(root)

I've shown a recursive version, but this can also be done in one linear scan by first sorting the nodes in topological order (depending on how you generate your graph, they might already be in such an order)

The trick is that this doesn't necessarily solve question 2, of spreading out the checkpoints equally. It puts off adding a checkpoint for as long as it can, which tends to pull all the checkpoints as close to the root as they can go. So some checkpoints may be arbitrarily close together, and intermediate nodes may be within T range of multiple checkpoints, even though the set of checkpoints is still minimal.

If this is a problem, there may be a post-process we can apply, given a minimal checkpoint set, to jiggle those checkpoints around the topology to a more even spacing.

\$\endgroup\$
1
\$\begingroup\$

Assuming we wish to have N checkpoints:

  1. we being by randomly picking sqrt(N) vertices on the graph (possibly a tree).
  2. We now pick N random distinct vertices. We compute the Dijkstra distances of each such randomly picked vertex from the closest existing checkpoint.
  3. We then proceed to declare the winner as the one furthest away from any other existing checkpoint and add it to the set.
  4. We now pick a "bad" checkpoint to remove by looking for the checkpoint closest to another checkpoint (there is a pair) and then compare by closeness to the second closest checkpoint.
  5. We remove the "bad" checkpoint.
  6. We repeat step (2) twice.
  7. We go back to (4) until we have enough checkpoints.
\$\endgroup\$
  • \$\begingroup\$ Would this not have a tendency to put checkpoints at the leaf nodes, since that maximizes their expected distance from any randomly-chosen other node? This method also assumes that we have a good heuristic for determining a priori how many checkpoints will be "enough" \$\endgroup\$ – DMGregory Jul 2 '15 at 21:35
  • \$\begingroup\$ @DMGregory Thanks! That is actually a great point to anyone (who has this question). You could place dummy checkpoints in the leaves if you need to keep them unused. Forgot about it cause we ended up using cyclic graphs instead. And yes, this helps when you have k as input. Just thought I'd share this in case it helps anyone. \$\endgroup\$ – wolfdawn Jul 4 '15 at 13:30
0
\$\begingroup\$

I propose a recursive pseudo code aproach to use while creating the tree

Keep track of placed check points in a listlike structure:

stacked_check_point_collection 

here comes the recursive method:

create_node(last_check_point_distance, current_node) //recursive method
add current_node to tree;
if last_chec_point_distance > T {
    /*check other checks point distance using stacked_check_point_collection */
    FOR_EACH check_point in stacked_check_point_collection 
    {
        IF check_point distance from current_node < T {
            last_chec_point_distance = check_point distance from current_node
            found = true
            break //exit foreach loop
        }
    }
    if not found {
        /*place check point here*/
        SET CHECK POINT IN current_node
        last_chec_point_distance=0
        stacked_check_point_collection.ADD(current_node)
    }
}
foreach outgoing arc{
        create_node(last_chec_point_distance + arc.lenght, new node)
}   
\$\endgroup\$
  • \$\begingroup\$ You shouldn't need to search through the previous checkpoints. If the closest checkpoint to the node's parent is too far away, every other checkpoint will be at least that far (since distances are measured along edges, and we're in a tree, so the only path to any previously-placed checkpoint is through the parent). \$\endgroup\$ – DMGregory May 24 '15 at 4:24
  • \$\begingroup\$ Moreover, this method can produce results arbitrarily far from optimum. Imagine we come to a node V with last_check_point_distance = T - epsilon. We don't include a checkpoint here because it's covered by the previous one. Now we proceed to the node's children, which turn out to be 1000 leaf nodes, epsilon + 1 distance away. We could have covered all 1000 with a single checkpoint at V, but instead this algorithm will place a checkpoint at each of those 1000 leaves. \$\endgroup\$ – DMGregory May 24 '15 at 4:28

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.