Back to the main site


Distributed randomness in a battle arena game

Posted on by Malcolm

The Problem
 
My final year at university has a really fun module: Advance Games Development. It’s a module where students from various games-related disciplines (designers, artists etc) get together and produce a game. The game that my group is doing is a 4 player battle arena that takes inspiration from games such as Crash Bash.
 
The game is set in space and each player controls a spaceship. There is treasure that spawns in the center of the screen and each player does righteous battle for that treasure which scores them points. During all the battling going on there will be various obstacles (e.g. black holes which hold a player in place) that will spawn in the arena. The player with most points at the end of the round wins.
 
All of the obstacles/power-ups etc will be procedurally generated at random and it’s this aspect which is a little bit tricky to implement. Sure, you can just use whatever mechanism your programming language of choice offers to randomly generate numbers but there is an inherent problem with computer randomness: it is not the same as what we humans perceive as random.

As a basic example of this, I went over to random.org and used their handy integer number generator to give me ten numbers ranging from 1 to 10. Here’s what I got:
 

Computer randomness demonstrated by random.org


 
That’s a bit odd. The number 4 has occurred three consecutive times. But this is a good illustration of what computer randomness is: it is being truly random and that means not caring about what number(s) you generated before. But if you ask a human to do the same task you will generally not see consecutive numbers (feel free to test this on your friends/family provided that no one gets hurt) and that is because the human perception of randomness is more along the lines of an even distribution with a layer of distortion. So, this is what I set out to do.
 
Step 1: Be able to assess the game world in a meaningful way.
 
Human randomness is the thing we are trying to emulate and that involves having a some kind of even distribution that has been slightly distorted. The fact that we are trying to distribute things involves being aware of the game world and what obstacles are currently active. After doing some research I decided that the best way to represent this was with a 2D grid based on AI Influence Maps. I found that this article on aigamedev.com by Alex J. Champandard was especially helpful.
 
Creating the grid was easy thanks to parts 1 – 3 of this 5-part Youtube series on implementing Prims Algorithm in Unity3D and, thanks to the article on AI Influence Map mechanics, I had a basic algorithm for influence propagation. After a few days I had this working:
 
Visualization of an Influence Map

Visualization of an Influence Map


 
Great! Half way there. My code is very different from Alex’s article though since I don’t want to know everything in real time, rather I’m only interested in the “slice of time” where I need to spawn obstacles so any computations done outside of that time frame would be a waste of everything. For example, in order to propagate influence, I work out the influence generated by obstacles in the cell and then ask the cell to propagate to its adjacent cells:
 
Code sample
 
Step 2: Identify the best place to spawn the next obstacle
 
I’m not trying to make these titles as vague as possible, honest, but the “correct” implementation is really specific to the game you are working on. So, again after research, I thought that going for the biggest rectangle in the grid that did not contain any obstacles would be the best way forward (or at least as a starting point should the results be unsatisfactory for the game play we want to create).
 
I used this great article on the maximal rectangle problem by David Vandevoorde as the basis for my own algorithm and worked my way on from there. I fooled myself into thinking that this part would be a walk over. 10 hours and several headaches later this is what I have:
 
Visualization of finding the maximal rectangle

Visualization of finding the maximal rectangle


 
Now that I have something fit for purpose my team and I can now go on to playing about with spawning rates etc and tweak it further for our game.

This entry was posted in University Work and tagged , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>