Procedural FPS Maps V1

I had two main goals with this little mini project.

1. Get to know my way around Jmonkey a little better.

2. Design some heuristics around FPS maps (mainly for deathmatch style games) from scratch.

I definitely feel like this project helped me get a grip on most of the basics JMonkey has to offer.  I was able to set up a small bootstrapping application with an FPS camera, wall and floor collisions, and some bonus visual effects (which might not all be obvious from the screen shots).  It was quite easy to do a lot of this, which I liked because it meant I could get to the meat of my algorithm most quickly.

Did I invent a revolutionary map generation algorithm?  No, it’s quite a simple algorithm.  But I did learn some things, exercised my pseudo-math and came up with some pleasing results (I’ll probably use something similar in a game at some point, when I’m done with all of these one-off experiments).

Once I had the sample application up and running I started brainstorming what key features I’d want in a map to make it interesting.  First couple of things that popped into my head:  We need rooms with multiple exits so players won’t get locked in a single room.  We need hallways and open spaces, to force players to take risks when moving between rooms, and to also allow enough freedom of movement when engaging in a head to head fight.  All rooms need to be accessible, so if a player spawns in a random location they aren’t left out in the middle of nowhere.

With that list of requirements I started working on the generator.  My algorithm is based on a simple 2 dimensional grid, so walls will be at right angles and there are no stairs or elevation changes.  Maybe I’ll add those in V2.

The First calculation I came up with was Room Size.  After some initial experimentation I decided it needed to have a lower bound (7 square boxes) since there needed to be some room to dodge attacks if a player entered.  It also needed to scale with the number of players, but couldn’t scale linearly.  In larger maps it would be unlikely that all players would be in the same room at the same time, unless it were closer to the center of the map.  My final formula was produced rooms of sizes between 7 and “players”x7, chosen randomly but with a weighted distribution towards the smaller rooms the farther you got from the center of the map.  I also allowed rooms to intersect, and just surround them with walls after the floor plan was generated.  This allowed non-square room sizes very easily, and had a nice effect of usually generating a larger common area in the middle.

Using this algorithm I placed randomly sized rooms all over a chosen map size (configurable) until the number of empty squares crossed 50%.  Why did I choose 50%?  I wanted to make sure that roughly half of the map was open room territory, but leaving enough space for hallways between rooms.  I generated roughly 100 levels with these settings and was pleased with the results, it was time to move onto hallways.

The main goal of hallways was to ensure that rooms usually had two entrances and exits.  I decided that rooms near the outside of the map could be left with only single entrances, and if items were being placed these rooms could be chosen for rare items where it would be risky to sit and wait for them to spawn (since you could be trapped).  This actually made the hallway algorithm very easy.  For any given room, I’d draw a hallway (Manhattan grid traversal randomly choosing between X then Y and Y then X) from the current room to the last two rooms generated.  For rooms near the center, this would generate non-overlapping hallways almost all the time as the probability of two rooms being in the same quarter of the map was 0.25 (25% chance).  As you move towards the corners, the probability of overlapping hallways increases.

I’ve attached some screenshots I took of sections of some maps I generated, for V2 I’ll probably end up posting a demo of this for people to play around with.


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>