MPI: Hide’n Seek

Over the last few weeks, more and more information has been released regarding a feature called multiplayer instances. Since those are quite long and boring words, we internally go with MPIs. Yeah, that’s not really creative, but for now, function over form has to suffice.

Today I’ll add to the information already available. As mentioned, the MPIs are derived from the current fort battle system and are, in the first iteration, PvE content. Unlike fort battles, you can undertake a MPI whenever you want (as long as your character is not busy doing something else) with either your friends or random players. Right now, we’re working on the first playable prototype which will have one main character besides the players: The Bear(tm). Short and sweet, you and a handful of other players are sleeping in a forest when suddenly a bear shows up! As you have been a bad boy scout (otherwise you’d have realized that there’s a cave just next to your resting place) you have to protect yourself and fight the bear. Luckily, the bear is not the smartest bear you could’ve faced and only attacks the closest player – but it makes up for its lack of cleverness with some very strong attacks and boy, it’s fast, too!

The Art of Drawing

Although I completely made this story up, the scenario in fact is not and covers a couple of features (AI, anyone?), none of which I will talk about today though. A feature which is not mentioned in the story but I do want to talk about is the bear’s and the players’ eyes. Sure you have beautiful ones, but the most important job of your eyes is to actually see what is going on. Fort battles do already have lines of sight, but these are actually pre-compiled for every map as the sight-blocking objects are known in advance and other players don’t block each other’s sight.

This is different for the upcoming MPIs. Every actual object will block your view. There’s a tree? You won’t know what’s behind it. There’s a big fat bear standing on his hind legs in front of you? You should get comfortable with his furry belly (or just get crushed) because you’ll see nothing else. Besides some static objects (e.g. walls, trees), there’s a lot of movement going on which means that what you see changes almost every turn – everything has to be calculated in real time.

So what we need is an algorithm that calculates what the players see and don’t see, and that’s what I’ve been working on for the last couple of days. It first started with an art class as we had drawn nice lines and circles to get used to the actual problem. Here’s what it looks like when non-artistic software developers go on a drawing-spree:

Nice, isn’t it? I’m thinking of starting a more artsy career – or at least I am now aware that I’ll always have an alternative available. What’s actually more interesting is the meaning of all those lines and boxes. Since I’m a good guy and not your art teacher, I’ll tell you directly. You might not be able to see it, but there are several ideas hidden within the picture. At first we dug up our geometric skills and drew some straight lines at a couple of angles to each other (you’ll have different view radii, so far: 90, 180 and 360 degrees). Our first approach was to project the lines from a specific point (the player’s eyes) in the direction they are facing. This is also known as ray tracing. If a line (or ray) hits a blocking object, the stuff behind that object is hidden. That is one approach, but from the beginning we have also been working on another one which you can see in the upper right corner.

Instead of sending out rays, another way is to iterate over the player’s field of view and, if you hit a blocking object, calculate the shadow of this object. Finally, add the resulting squares to a list that contains all of the hidden squares. When displaying the grid, just check if a square is in the hidden list or not and show its content accordingly. The algorithm to calculate an object’s shadow is the interesting part. It was quite easy to start with, and still somewhat is, but there have been quite a number of edge cases and there are still some bugs left.

After the implementation, we started on a ray tracing algorithm. Since a ray doesn’t fit one-to-one on a square grid, we have to convert that information using the Bresenham Algorithm to match the straight ray to the underlying squares. The code is easier, shorter and more efficient but yields different results. How can we check if the results are appropriate though? Quite early on I was not keen on writing tests for such a visual feature, so I decided on writing a simple, quick and dirty standalone visualizer to test it. Now to the fun part: it’s available online! Before you head over there, please keep in mind that it’s not at all optimized but is just a proof of concept (as the code you can look at is seriously bad). It’s also very slow when not opened with a decent computer and a decent browser (Firefox does not count as decent here, unfortunately; Chrome should run well enough).

Space Invaders Incoming!

A quick explanation of what is shown and what you can do:

When hovering over the grid, there’s a red square beneath your mouse cursor. This is you, the player, whose position is used to calculate what you can see from that point and what you cannot see. Hidden stuff is either dark green or grey (have a look at the legend to the right), light green squares are objects which will block the red square’s view, thus having a shadow. The rest, the white squares, are things the player can see. You can add / remove blocking objects by clicking on a grid square.

To the right of the grid, there are a couple of settings you can change: a different direction (it defaults to a 360 degrees view) and a different view angle, which itself results in a different raw field of view. You can also customize how far the player can see. Next on the list, Show Shadows, only works when the other one, Use Ray tracing, is not active and shows the actual calculated shadows. If you tick “Use Raytracing”, the ray tracing algorithm described above is used. If it’s off, the algorithm we started out with comes into play.

So, here you go: http://map.the-west.de/view.html

I found myself building quite a number of labyrinth maps, wandering through them.
What did you build?