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, minimumTiles, nodeRadius, maxConnections, maxDoorConnections: Integer);

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

WebGraphGenerator.Setup(18, 4, 50, 6, 3, True);

Parameters explanation

spacing: Lower values have better results but the generation is slower, high values have worse results but geneartion is faster.
minimumTiles: spaces with less tiles than this will be ignored.
nodeRadius: closed spaces that are less than this values in pixels will have a single node in the middle.
maxConnections: max connections per node.
maxDoorConnections: max connections per door node.

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.

WebGraphGenerator.BuildGraph¶

function TWebGraphGenerator._BuildGraph(map: TImage; white, red: TPointArray): TWebGraph;
function TWebGraphGenerator.BuildGraph(name: String; map: TImage): TWebGraph;

Magically builds a webgraph for you for a given collision map passed into map.

The collision map can only have 4 colors:

white ($FFFFFF) for walkable space
black ($000000) for non walkable space
red ($0000FF) for doors (optional)
gray ($333333) for objects (optional)

Note

This is an internal method. Don’t use it if you don’t know what you are doing.

How it works in detail is quite technical but if you want to see the result run this example code:

{$I WaspLib/osrs.simba}
begin
  Map.Setup([Chunk(Box(49,54,50,53), 0)]);
  Map.Debug();
end.

This will setup a map with a small piece of varrock and then open the Map Debugger.

On the Map Debugger change the dropdown to the collision map if you want to see what it looks like, that is what will go through this as the map parameter and it should look something like this:

As a bonus you can also see the resulting webgraph!

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 and that the doors are red, 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:

We start off by extracting all the white:

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:

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:

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:

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:

And then we partition it with WebGraphGenerator.Spacing:

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:

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:

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

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:

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:

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

And this would be WebGraphGenerator.Skeletonize set to False:

WebGraphGenerator variable¶

Global TWebGraphGenerator variable.