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[0]) + abs(point[1])
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[0], point[1]+1), n-1)
dn = get_cavex_n(seed, (point[0], point[1]-1), n-1)
lt = get_cavex_n(seed, (point[0]+1, point[1]), n-1)
rt = get_cavex_n(seed, (point[0]-1, point[1]), 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[0] - target_pos[0]) + abs(current_pos[1] - target_pos[1])
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[0], current_pos[1]+1), target_pos, max_dist-1)
dn = dijkstra(seed, (current_pos[0], current_pos[1]-1), target_pos, max_dist-1)
lt = dijkstra(seed, (current_pos[0]+1, current_pos[1]), target_pos, max_dist-1)
rt = dijkstra(seed, (current_pos[0]-1, current_pos[1]), target_pos, max_dist-1)
dist, path = sorted([up, dn, lt, rt])[0]
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[0]) + abs(point[1])
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[0], point[1]+1), n-1)
dn = get_cavex_n(seed, (point[0], point[1]-1), n-1)
lt = get_cavex_n(seed, (point[0]+1, point[1]), n-1)
rt = get_cavex_n(seed, (point[0]-1, point[1]), 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"
[][] [][] [][] [][] [] [] [] []
[] [][] [][] [] [][][] [] [][] [][] [][] [][]
[][] [] [] [] [] [][] [][] []
[][] [][][] [] [] [][] [][]
[][] [][] [][] [][] [] [] [] [][] []
[] [][] [][][] [][] [] [][] [][] []
[] [][][] [] [][][] [][] [][] [] [] [][][]
[][] [][] [] [][] [][][] [] [] [] [][] [][] []
[] [][] [][][] [] [] [] []
[][] [][] [] [] [] [] [] [][]
[][] [] [] [] [] [][] [][] [][] [] [][] [] []
[] [][] [][] [] [] [] [][] [][] [][] [][] [][]
[] [][] [] [] [][] [][][] [] [] [] [] [][][]
[][] [] [][] [][] [] [][] [] [][]
[] [] [] [][] [] [] [] [] [][] [][][]
[] [][][] [][] [] [] [][] [] [] [][] [][][] []
[][][] [][] [] [][] [][] [][] []
[][][] [][] [][] [][] [] [] [][] [][] [][] []
[][] [] [][] [] [] [][][] [] [] [] [][]
[] [] [] [][] [][][] [][] [] [][] [][]
[] [] [][][][] [] [] [][][] [][] []
[][][] [][][] [][] [] [] [][]
[] [][] [][][][] [][] [][] [][] [] []
[] [][] [][] [][] [] [] [][] []
[][] [] [] [][] [] [][] [] [][] [][] []
[] [] [] [][] [][][] [] [][]
[] [] [][] [][] [][] [][] [] [][] []
[][] [] [][] [][] [][][] [] [][] [][][]
[] [][] [][] [] [] [][][][] [][] [][] [][] [][]
[][] [] [][] [] [][] [][] [][] [] []
[][] [][] [][] [] [] [][] [][] [] [] [] [] [][] [][] []
[][] [] [][] [] [] [] [] [] []
[][] [][] [] [][] [] [] [][] []
[] [] [][] [][] [][] [] [] []
[][] [][] [][] [][] [][][] [] [] [][] [] []
[][] [][] [] [][][][] [] [][] [][][] [] []
[] [][][] [][] [] [] [] [][]
[] [][] [] [][] [][][] [][] [][] [][] [] []
[][] [][] [][] [][][] [][] [][] [] [] [][]
[][] [] [][][] [][] [] [] [] [] [] [] [] []
[][] [][] [][] [] [] [] []
[][] [] [] [][] [] [] [][] []
[] [] [][][] [][] [][] [][] [] [] [] [][]
[] [][] [] [] [] [] [][][] [] [][] [] []
[] [][] [][] [][] [][][][] [] [][][] [] [][]
[][] [][] [] [][] [][] [][][] [][] [] [] [] []
[] [][] [] [][] [][][] [][] [] [][] [][] [] []
[] [] [] [][][][] [][] [][][][] [] [] [] [][]
[][] [][] [][] [][][] [][][][][] [] []
[] [][] [][][] [] [] [] [][] [][] []
[][] [] [][][][] [][] [] [] [] []
[][] [][][] [][][][] [][] [][] [][] [][] [][] []
[][] [][][] [] [][] [][] [][] [][]
[] [][] [][][] [] [] [] [] [][] [][]
[][] [][] [] [] [][] [] [] [] [][][] [][]
[][] [][][][][][] [][][] [][] [][][] [] [] [] [][]
[][] [][] [][] [][] [][] [][] [][] [][] [][]
[] [][] [][] [][] [][][] []
[] [] [] [] [][] [][] [] [] [] [][][][] [][] [][]
[] [] [][][][] [][] [] [] [][] [][] [] [][] [][]
[][][] [][] [][] [] [] [] [] [][]
[][] [][] [][] [][] [][] [][] [] []
[] [] [][] [][] [] [] [] [] [][] []
[][][][] [] [] [] [][] [] [][] [] [][] [][] []
[] [][] [][] [][] [] [] [][] [] []
[][][][] [][] [] [][][] [] [] [][] [] [] [] [] [][]
[][] [] [] [] [][] [] [] []
[] [][] [][] [][] [][][] [] [][] [] [] [] [] [][]
[][] [] [][] [][] [][][] [][] [] [][] [][]