Last time I talked about de-optimizing mapgen4 so that I could more easily create experiments. I wanted to share one of those experiments. I recently assembled some of my existing ingredients into something that was just plain fun to watch, and I wanted to share this simulation of traders moving around a map:
Conceptually, each dot on this simulation represents a trader following a path between two random points. The first ingredient is a pathfinding algorithm such as A*. Pathfinding works on a graph. So the second ingredient is a graph:
I’m using a Delaunay + Voronoi dual graph. Here’s a random path on this graph:
Each trader follows a path. But I decided it’d be more interesting to animate the points on a graph of edges instead of the regions. Here’s a graph between the edges of the original map. Each node in this pathfinding graph is an edge in the original graph, and each edge in this pathfinding graph is between two edges in the original graph:
That’s quite a bit more dense!
Here’s the path on the new graph — it looks smoother:
The choice if graph is something to keep in mind. There may be many choices of pathfinding graph for a given map. I usually start by making the pathfinding graph the same as the underlying game map, but there are many more choices, and lots of tradeoffs to consider. In this case I chose the graph between edges because it let me create multiple “lanes” of traffic. I separated the traffic going one direction from the traffic going the other direction. That made the visuals nicer.
I can run pathfinding on a graph, but I actually want to create lots of paths. A* finds one path at a time. There are algorithms that can find multiple paths at once. This is another thing to keep in mind. Sometimes we’re so focused on a small part of the problem that we miss out on on simpler or faster solutions that solve the larger problem. There are several classes of pathfinding algorithms:
| Problems | Solutions | ||
|---|---|---|---|
| source | destination | algorithm class | algorithms |
| one | one | single pair shortest path[1] | A* |
| one all |
all one |
single source shortest paths[2] | Dijkstra’s, Bellman-Ford |
| all | all | all pairs shortest path[3] | Floyd-Warshall, Johnson’s |
It could be useful to precompute all the paths here, using Floyd-Warshall. Then all the animated points would move along the already-computed paths. In my previous experiments I found that Johnson’s Algorithm was faster than Floyd-Warshall. Johnson’s Algorithm runs Dijkstra’s Algorithm for each source location and then stores all the outputs.
for each location: run dijkstra's from source location create lots of traders: follow a path between a random source and a random destination
Because the map is changing as the user paints on it, I wanted to avoid an expensive precomputation step. I decided to implement something slightly different. Instead of running Dijkstra’s from all locations, then creating all the traders, I ran Dijkstra to one location, created the traders from that location, then ran Dijkstra to another location, created the traders there, etc.:
for each location:
run dijkstra's from source location
create lots of traders:
follow a path between the known source and a random destination
That’s the third ingredient: I run Dijkstra’s Algorithm to build flow fields for pathfinding :
The fourth and fifth ingredients here were mapgen2’s renderer and mapgen4’s generator. It was fun putting together ingredients into something new. Try out experiment 2515 — simulation of traders in an editable procedurally generated map.