Home

# Infinite Map Generation

Procedural map generation is amazing. It allows a person to generate an infinite number of maps that are similar, but without requiring much manual work beyond tweaking the algorithm.

But all of this is lost in that most approaches don't allow you to generate a truly infinite map. For example, cellula automata requires a map that contains the state of each point such that you can alter these values iteratively to arrive at the final map.

Wouldn't it be nice to be able to generate a truly infinite map? Here I'm going to talk about how I generated an infinite number of infinite tile-based maps

## Step 1: Crypotgraphic RNG

We want our map to be the same each time we return to a point. Otherwise simply moving back and forth changes the location world. To solve this we need to generate a random number based on the position. Because this is a tile based map, we need to generate random boolean values, and a (very) nieve approach may be to add the coordinates together, add a random number, and check if it is even or odd: ``` def get_random_bool(seed, point): return (seed + point.x + point.y) % 2 ``` Obviously, this doesn't work well because if point.x and point.y switch values, the result will be the same. So what we need is some way of converting similar numbers into very different outputs. Thankfully people have spent years researching this for crypography and error-checking purposes. A hash (eg md5) is designed that a small difference in input results in a large difference in output. Thus some 'good' random number generators are: ``` import hashlib def get_rand_float(seed): '''Returns a random float (0 - 1) from a seed. Nice little hack of hashing algorithms''' array = hashlib.md5(seed).digest() s = 0 for e in array: s += e return s/(len(array)*256) def get_raw_point(seed, point): '''Returns a random bool at a certain location.''' seed = (str(seed)+str(point)).encode('UTF-8') radius = abs(point) + abs(point) return 1 if get_rand_float(seed) > 0.5 else 0 ```

## Step 2: Cellula Automata

Cellula Automata (CA) samples the points on all sides to arrive at a map output. This is often run multiple times. To simplify things, I wrote the CA recursively, and instead of using a neighbour count, I used an algorithm I've designed to remove narrow walls. This algorithm is tuned to generate maps where most of the map is accessable but the terrain is still varied. I call this algorithm "cavex" ``` def get_cavex_n(seed, point, n=0): '''Returns the result of n iterations of the cavex algorithm for a specific point''' if n == 0: return get_raw_point(seed, point) else: up = get_cavex_n(seed, (point, point+1), n-1) dn = get_cavex_n(seed, (point, point-1), n-1) lt = get_cavex_n(seed, (point+1, point), n-1) rt = get_cavex_n(seed, (point-1, point), n-1) # TWIDDLE THIS PART for different automata if (up == dn) and (lt == rt):# and (up != lt): return 0 else: return get_cavex_n(seed, point, n-1) ``` See how it works? If you ask it to do no layers of automata, it returns the point, otherwise it does a layer of cellula automata on the layer below.

### Performance and Caching

At some stage you'll notice that sampling the map is not as fast as you want. This is because applying one layers of CA requires sampling the map 4 times(9 for normal CA) , but for two layers it requires 16. In other words it's O(n^2). This isn't helped by the md5 sum being relitively slow (after all it is designed for cryptography)

Normally the map prevents lower layers being sampled. Wouldn't it be nice if we could do something similar? Turns out we can. A cache stores data such that it does not need to be calculated. We can do this in python using functtools. A nice small example is: ``` import time from functools import lru_cache MAX_CACHE_SIZE = 1024 @lru_cache(maxsize=MAX_CACHE_SIZE) def long_function(a, b): time.sleep(1) return a + b print(long_function(5, 4)) print(long_function(4, 4)) print(long_function(5, 4)) print(long_function(5, 4)) print(long_function(5, 4)) ``` You'll notice that it only takes ~2 seconds to run, despite calling a function with sleep(1) in it 5 times. This is because the function is run with the same arguments lots of times.

The best place to apply caching to is the recursive cellula automata. If the cellula automata is cached, then it won't need to sample the raw points nearly as often.

## Pathfinding

Once you have a method of sampling the map down, it's easy to add any algorithm on top of it. Because we are treating caches a little like map, we can create a recursive dijkstra's implementation just like: ``` @lru_cache(maxsize=MAX_CACHE_SIZE) def dijkstra(seed, current_pos, target_pos, max_dist): '''Returns the shortest path between target and destination using dijkstra's algorithm. Yes, it is really slow, but it's fast enough Returns (distance, points)''' dist = abs(current_pos - target_pos) + abs(current_pos - target_pos) if dist > max_dist or get_cavex_n(seed, current_pos, 2) != 0: # Too far from target that even if we went straight there it # would be beyond max_dist. Or the current brick is blocked return (max_dist + 1, [(None, None)]) if dist == 0: # We have arrived, so the distance is zero return (0, [current_pos]) else: # Check in every possible direction, and pick the shortest up = dijkstra(seed, (current_pos, current_pos+1), target_pos, max_dist-1) dn = dijkstra(seed, (current_pos, current_pos-1), target_pos, max_dist-1) lt = dijkstra(seed, (current_pos+1, current_pos), target_pos, max_dist-1) rt = dijkstra(seed, (current_pos-1, current_pos), target_pos, max_dist-1) dist, path = sorted([up, dn, lt, rt]) dist += 1 path.append(current_pos) return (dist, path) ```

## Where to from here?

I need to figure out how to place objects. Some things (like monsters) can be placed anywhere, but some objects (such as keys, treasure and exits) need to be accessible. One approach is a random walk from a starting location. This would mean that the objects are always reachable, but does not gaurentee thhe distance. The other approach is to pick random points and check the path to the player. I suspect this would be much more computationally heavy though.

## Full Code:

Run in python3

``` import hashlib import time from functools import lru_cache BIAS = 0.47 # How likely source noise is to be full/empty MAX_CACHE_SIZE = 1024 @lru_cache(maxsize=MAX_CACHE_SIZE) def get_rand_float(seed): '''Returns a random float (0 - 1) from a seed. Nice little hack of hashing algorithms''' array = hashlib.md5(seed).digest() s = 0 for e in array: s += e return s/(len(array)*256) @lru_cache(maxsize=MAX_CACHE_SIZE) def get_raw_point(seed, point): '''Returns a random point at a certain location. This gets run ~100,000 times for a 40x40 map, so performance is rather important''' seed = (str(seed)+str(point)).encode('UTF-8') radius = abs(point) + abs(point) return 1 if get_rand_float(seed) > BIAS else 0 @lru_cache(maxsize=MAX_CACHE_SIZE) def get_cavex_n(seed, point, n=0): '''Returns the result of n iterations of the cavex algorithm for a specific point''' if n == 0: return get_raw_point(seed, point) else: up = get_cavex_n(seed, (point, point+1), n-1) dn = get_cavex_n(seed, (point, point-1), n-1) lt = get_cavex_n(seed, (point+1, point), n-1) rt = get_cavex_n(seed, (point-1, point), n-1) # TWIDDLE THIS PART if (up == dn) and (lt == rt):# and (up != lt): return 0 else: return get_cavex_n(seed, point, n-1) print("Note that there is a delay of 0.1 seconds between lines") seed = input("enter seed: ") x = 0 while(1): x += 1 for y in range(40): res = get_cavex_n(seed, (x, y), 2) if res == 0: print(" ", end="") else: print("[]", end="") print('\n', end='') time.sleep(0.1) ```

### Sample Map:

This is a sample of the map with seed "1" ``` [][] [][] [][] [][] [] [] [] [] [] [][] [][] [] [][][] [] [][] [][] [][] [][] [][] [] [] [] [] [][] [][] [] [][] [][][] [] [] [][] [][] [][] [][] [][] [][] [] [] [] [][] [] [] [][] [][][] [][] [] [][] [][] [] [] [][][] [] [][][] [][] [][] [] [] [][][] [][] [][] [] [][] [][][] [] [] [] [][] [][] [] [] [][] [][][] [] [] [] [] [][] [][] [] [] [] [] [] [][] [][] [] [] [] [] [][] [][] [][] [] [][] [] [] [] [][] [][] [] [] [] [][] [][] [][] [][] [][] [] [][] [] [] [][] [][][] [] [] [] [] [][][] [][] [] [][] [][] [] [][] [] [][] [] [] [] [][] [] [] [] [] [][] [][][] [] [][][] [][] [] [] [][] [] [] [][] [][][] [] [][][] [][] [] [][] [][] [][] [] [][][] [][] [][] [][] [] [] [][] [][] [][] [] [][] [] [][] [] [] [][][] [] [] [] [][] [] [] [] [][] [][][] [][] [] [][] [][] [] [] [][][][] [] [] [][][] [][] [] [][][] [][][] [][] [] [] [][] [] [][] [][][][] [][] [][] [][] [] [] [] [][] [][] [][] [] [] [][] [] [][] [] [] [][] [] [][] [] [][] [][] [] [] [] [] [][] [][][] [] [][] [] [] [][] [][] [][] [][] [] [][] [] [][] [] [][] [][] [][][] [] [][] [][][] [] [][] [][] [] [] [][][][] [][] [][] [][] [][] [][] [] [][] [] [][] [][] [][] [] [] [][] [][] [][] [] [] [][] [][] [] [] [] [] [][] [][] [] [][] [] [][] [] [] [] [] [] [] [][] [][] [] [][] [] [] [][] [] [] [] [][] [][] [][] [] [] [] [][] [][] [][] [][] [][][] [] [] [][] [] [] [][] [][] [] [][][][] [] [][] [][][] [] [] [] [][][] [][] [] [] [] [][] [] [][] [] [][] [][][] [][] [][] [][] [] [] [][] [][] [][] [][][] [][] [][] [] [] [][] [][] [] [][][] [][] [] [] [] [] [] [] [] [] [][] [][] [][] [] [] [] [] [][] [] [] [][] [] [] [][] [] [] [] [][][] [][] [][] [][] [] [] [] [][] [] [][] [] [] [] [] [][][] [] [][] [] [] [] [][] [][] [][] [][][][] [] [][][] [] [][] [][] [][] [] [][] [][] [][][] [][] [] [] [] [] [] [][] [] [][] [][][] [][] [] [][] [][] [] [] [] [] [] [][][][] [][] [][][][] [] [] [] [][] [][] [][] [][] [][][] [][][][][] [] [] [] [][] [][][] [] [] [] [][] [][] [] [][] [] [][][][] [][] [] [] [] [] [][] [][][] [][][][] [][] [][] [][] [][] [][] [] [][] [][][] [] [][] [][] [][] [][] [] [][] [][][] [] [] [] [] [][] [][] [][] [][] [] [] [][] [] [] [] [][][] [][] [][] [][][][][][] [][][] [][] [][][] [] [] [] [][] [][] [][] [][] [][] [][] [][] [][] [][] [][] [] [][] [][] [][] [][][] [] [] [] [] [] [][] [][] [] [] [] [][][][] [][] [][] [] [] [][][][] [][] [] [] [][] [][] [] [][] [][] [][][] [][] [][] [] [] [] [] [][] [][] [][] [][] [][] [][] [][] [] [] [] [] [][] [][] [] [] [] [] [][] [] [][][][] [] [] [] [][] [] [][] [] [][] [][] [] [] [][] [][] [][] [] [] [][] [] [] [][][][] [][] [] [][][] [] [] [][] [] [] [] [] [][] [][] [] [] [] [][] [] [] [] [] [][] [][] [][] [][][] [] [][] [] [] [] [] [][] [][] [] [][] [][] [][][] [][] [] [][] [][] ```