Category: Development

Map Generation, Voronoi Debugging

After a solid week of debugging and reworking a php library I had found that generated a Voronoi diagram, I finally managed to hammer out the last kinks. It turns out that the two itterations of the Lloyds relaxation algorithm I used were sometimes coming up with sites that lay outside of the bounding box, which ended up causing all kinds of trouble. I now finally have a Voronoi polygon generator that a) I understand, and b) is performing fast enough for me to continue with.

Recreating Randomness
In order to properly debug the problem, I had to be able to recreate the problem properly. Initially, I used the PHP rand() function to create 1000 random points within a 1024×768 canvas. Each time the problem came up and I reloaded the script, it would come up with another 1000 random points, different each time. After first coming up with a half-arsed solution whereby I also outputting the coordinates for the 1000 points, I found out that you can set a seed with PHP’s srand() function. This allowed me to either generate a random number based on the system time, or just supply a number of my own. I made a little form that allowed me to generate a diagram based on a supplied number or generate one randomly and display the seed for that diagram. That way I could flip through random diagrams until I found one that was broken and simply keep generating that same diagram with the given seed. That made things much, much easier.

In the meantime, I also incorporated some code that wrote all the relevant information for the diagram into an XML file with which I could also once again recreate the diagram, without having to calculate everything again.

Up Next
Now that I’ve finally been able to find the flaws in the PHP library that I was working with and the code that I was using to call the library, I will continue exploring the finished code a bit, seeing if I can make some tweaks and do some cleaning up. I will also try to post the finish product of what I ended up making, perhaps with some more interactivity (the ability to set the canvas size, adjust the number of random sites, and perhaps also the amount of Lloyd iterations it does) so that people can play with it.

Then I’ll start looking at using a Perlin library to start creating a rudimentary shape for the map that I want to eventually create. Once I’m happy with that, elevation and moisture will come into play, which in turn means we’ll be able to make individual biomes.

I’m sure there’s still much more to do, but I have to say that even though the going was tough the last week — to the point that I was even dreaming about Voronoi polygons — it’s really rewarding to achieve breakthroughs and to persist into success.

Anyway,  I’ll try to get my script up tomorrow.

Shadowrun: Corrosion is Broken

The mechanics of Shadowrun: Corrosion are broken and I don’t know how to fix it and I’m starting to suspect it can’t actually be fixed. Or rather, it can’t be fixed in a way that would still remain somewhat true to the old SR3 system. It rarely happens that in the table-top version of Shadowrun, you end up playing a 1000+ karma character. But it happens rather “quickly” in Corrosion. Currently, you are able to make about 30 karma a day if you really dedicate yourself to it. (I’m not entirely sure how feasible it is, but theoretically, you could do two missions and about 20+ duels, and then I’m not counting what you can make in the arena.)

Once you’ve got your attributes maxed out, which is relatively soon, and you’ve lowered the costs of improving your skills, you could quite quickly and quite easily jack your pistols/smg/unarmed/edged weapons up to around 20 skill points, at which point it becomes a game I’d like to call “D or be D’ed” — essentially, you do deadly damage or you get deadly damage, depending on whether you win the initiative roll or not.

This makes for a fairly boring game. Very few duels or PvP fights last more than one or two rounds. And the game starts to revolve around who can chuck the most drugs and still be effective in combat. I think it’s inherent to the game of Shadowrun. The lethality makes the table top game so great and suspenseful, but if you’re doing it as a browser game, it becomes very boring in my opinion. I’m wondering how Shadowrun Returns is going to deal with that.

A game that revolves around hitpoints, generally, makes it a little more easy. You can scale hit points together with damage resisting qualities, damage dealing qualities and you can even play with critical hit possibilities. Gear will simply scale with your progression through the game. I’ve heard people say that you’ll start out with a weapon that does 4 damage while your enemies have 10 hitpoints and after a year you have a weapon that does 400 damage, while your enemies have 1000 hitpoints. In the end, it all remains the same. I suppose that in a sense that’s true, but when the hitpoints always remain the same; namely the 10 boxes on your stun and physical monitor, things become dull.

It’s really bugging me. To the point where I don’t see any reason to continue expanding upon anything else in the game until I’ve figured it out. If I don’t figure it out, and I continue adding new content or fixing bugs, I just have the feeling I’m decorating a cabin on the Titanic; a little pointless in the end.

In the mean time, I’ve had some ideas for other games that might work much better and I’m wondering if it’s not better to cut the game loose and move on.

Map Generation, Cont’d

While my voronoi generation still displays some problems, I’ve moved on for the time being to determining land from sea. I’m using a perlin class that I previously created, but it’s really not cluttering the way I had hoped it would. I’m playing around with it, but this is what I have so far.

Voronoi polygons run through a Perlin noise generator. 1000 polygons on a 1024×768 field.

Map Generation

A while back, my brother told me about a guy in his class who was busy with a random map generator. I started to play around with the idea as well and I took a careful look at different Perlin libraries in order to come up with some random shapes. After coding around for a while, I ended up with some disappointing results. While Perlin allowed me to generate noise that wasn’t completely random, but in which each coordinate had some relation to the coordinates adjacent to it, the results were made little sense to me, despite them looking quite organic. I basically used the noise to determine elevation. Each negative value meant water, each positive value meant land. Using some simple math I could also assign different colours to different depths and altitudes. Looked kind of neat, but took an awful lot of processing power. I was playing around with this on a twelve hour flight from Amsterdam to San Francisco, and my little netbook felt like it would melt through my tray table.

A random map generated using a Perlin noise library.

What killed the performance was the sheer amount of data points to calculate and display. I rendered it in HTML, using DIVs, later using an SVG, but it really didn’t matter. The Perlin performance was poor and the amount of data points required to get anything fun was gigantic. I dropped the project for a few months, until I discovered a post on polygonal map generation written by Amit Patel and it really opened my eyes. The organic feel that I was trying to achieve using Perlin could also be achieved using a Voronoi diagram and the amount of actual datapoints would be much less. The relationships between bordering polygons was also built into the concept of the diagram and on top of that, the input needed was relatively small (depending on how many polygons you want to generate); just a bunch of coordinates for the polygon sites.

I found several libraries generating Voronoi diagrams, but the one PHP library that I found was a messy port of brilliant Javascript library done by Raymond Hill, who showed me the power of HTML5 and Javascript as a tool for data presentation! (For example; take a look at these mind boggling examples of data visualisation!) I ended up porting the Javascript library myself and creating raw PNG output. It took me a while to really figure out how all of it worked, but tonight I had somewhat of a breakthrough and I managed to solve some persistent bugs in my code. Below is an example of an 1920×1200 image with 1000 randomly generated polygon sites. One of the things to keep in mind is that the randomly generated points have been adjusted with two passes of the Lloyd relaxation to make the points a little more evenly spaced apart.

An automatically generated 1920×1200 image with 1000 random polygon sites.

The next step will be to start figuring out land from water, assigning elevation and creating some sensible colours for the polygon cells. I’ll let my new best friend Amit Patel lead the way in logic; immitation, emulatio, creatio. I don’t quite understand all the logic behind everything yet, but if I take it one step at a time and tenaciously plug away, I’m sure that eventually my brain (made of obsidian, coated in teflon and impervious to the uptake of knowledge!) will eventually make this information his.

Shadowrun: Corrosion – Boom!

Yeah, I’m not really sure what happened over the last week, but we doubled the amount of registered players. And as if that wasn’t enough, the number of actively logged in players probably quintupled. It’s really very exciting and it also puts a nice amount of pressure on my brother and I. We’ve been working on and off for a while now, but it’s always been a bit laissez-faire, without any real sense of urgency. Now, people are equally enthusiastic at the promise of the game as they are dissatisfied that it’s not fully playable yet.

Most people are pretty good about it, and then there are a select few — of course, they have to be the most vocal ones, don’t they? — whose abrasive style rubs me the wrong way. Luckily, I am pretty good at ignoring all the insults and jabs and still manage to concede the point if they have one. (I’m looking at you, ShadowDragon8685.)