WebGraph Generator

This page is about webgraph generation out of collision map images.

You can force WaspLib’s graph generator to always run even if there’s already cached graphs by adding the following compiler directive at the top of your script BEFORE INCLUDING WASPLIB:

{$DEFINE WL_GENERATE_GRAPH_ALWAYS}

TWebGraphGenerator type

Record responsible for generating webgraphs from collision map images.

WebGraphGenerator.Setup

procedure TWebGraphGenerator.Setup(spacing: Int32);

Sets up the TWebGraphGenerator with the following settings which are the defaults:

WebGraphGenerator.Setup(16, 16);

Parameters explanation

  • spacing: Just the spacing between the nodes. Larger spacing means the graph faster to generate with some resolution loss.

  • minSpace: if a the space where a node is is lower than this value, the node won’t be added.

Feel free to change the settings to suit your need and use the Map Debugger to see what the results look like.

To do so you MUST DO IT BEFORE setting up your Map.

Webgraph Generation

If you do wish to understand the technical details a little bit more, the following is a simplified explanation with images of more or less how it works.

First of all, you need to have a collision map. WaspLib’s webgraph generator assumes the walking space is white, other than that, it doesn’t really matter what colors your collision map, for this explanation I’m going to use a small piece of varrock with a bit of the wilderness:

_images/graphgen0.png

We start off by extracting all the white:

_images/graphgen1.png

Then, we cluster the white, grouping each white pixel that is within any other white pixel horizontal or vertically in the same cluster. It’s important to not include diagonal pixels or your clusters will cross certain walls, at least in WaspLib’s collision maps. We also sort our clusters by size as we can have some performance improvements by having the clusters sorted.

Doing this will look something like this:

_images/graphgen2.png

We also need to find all the red to know where the doors are, in this image I’ve expanded the color a little so it’s visble but you should only get the door:

_images/graphgen3.png

While doing this, you also want to get and store for later the point in front and behind the door and map those points to each of your clusters.

The next step is to start processing our clusters. Because we sorted them by size we start by skipping very small ones, usually clusters that are less than the size of a tile.

Clusters that are less than WebGraphGenerator.MinimumTiles we add a single node in the middle, it’s a cluster too small to be worth extra processing. Which would be the red nodes on the image below:

_images/graphgen4.png

We also check our mapped doors to see if any of the points in front or behind each door belongs to our cluster, if it does, we connect it to our node.

Then we start processing bigger clusters if you have WebGraphGenerator.Skeletonize set to True which is the default, we will sekeletonize the cluster which should look something like this:

_images/graphgen5.png

And then we partition it with WebGraphGenerator.Spacing:

_images/graphgen6.png

If you have WebGraphGenerator.Skeletonize set to False, we simply parition the cluster as it is, again with WebGraphGenerator.Spacing.

It’s hard to see much difference here but it’s much denser than the above and later on you will see the actual difference when paths are added:

_images/graphgen7.png

Whichever case your settings followed, those will be your nodes for that cluster.

Then next step is to try and connect the nodes we just created by proximity. We check WebGraphGenerator.MaxConnections*2 closest nodes to each node and connect up to WebGraphGenerator.MaxConnections if:

  • We have a straight path between the 2 nodes

  • If we can have a path using AStar

It should look something like this:

_images/graphgen8.png

For AStar path finding we use the original skeleton/cluster and this is an example of a connection where AStar was used:

_images/graphgen9.png

As you can see that crossing over the wilderness river crossing black, it’s connected because AStar has found a path around it. That’s also what’s happening on those nodes around trees with lines crossing the trees, there’s a valid path because AStar found a way around.

If you were to have WebGraphGenerator.Skeletonize set to False, this is what the same thing would look like:

_images/graphgen10.png

Lastly, we our mapped doors that has their front or behind point within our cluster and connect that door to the closest WebGraphGenerator.MaxDoorConnections amount of nodes:

_images/graphgen11.png

And that’s about it. The final graph should look like this if you WebGraphGenerator.Skeletonize set to True, which again, is the default:

_images/graphgen12.png

And this would be WebGraphGenerator.Skeletonize set to False:

_images/graphgen13.png

WebGraphGenerator variable

Global TWebGraphGenerator variable.