The Endless Road

Use the WASD keys to look around. Click on the black road to add or remove cars.

Development

I had two goals for this project. First, I wanted the generation to be stateless and not require preexisting knowledge about the tiles around it. And second, I wanted to generate cities with roads connecting them.

I could think of many ways to generate cities, but connecting them would require mapping a set of cities first and finding paths between them, but this approach would violate my first goal. So instead I realised that generating the roads and placing cities along them would guarantee their connectedness without requiring additional information.

But generating contiguous roads turned out to be a much harder problem than I anticipated. Perlin noise by itself isn't cohesive enough to form a contiguous line, so instead I decided to take a contiguous line and manipulate it using noise. I came up with the idea of using polar coordinates to sample the distance from (0, 0) to any point as input to a Perlin noise function to get a random rotation. Then I could check if that rotation passes through any arbitrary block.

The problem with my method was twofold. First, as the road gets farther away from the origin rotations have a bigger impact on the road, making it rotate erratically. I tried several methods, but ended up taking the log of the distance to reduce variation as distance increases. What I should be doing is finding the arc length between squares, but I couldn't think of a good way to find adjacent squares perpendicular to the origin. My second problem was that if the line passed through one of a square’s corners it wouldn't be detected and would appear on the map as blank spaces with no road. I never found a definite fix, but sampling the distance to each of the square’s edges greatly improved the problem.

Overall I am very happy with the winding roads I was able to generate. Future improvements would be to find a way to guarantee the road was one square wide, and to make its movement more natural.