Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

Advanced search

1336423 Posts in 60832 Topics- by 52314 Members - Latest Member: oreismatheus

April 26, 2018, 03:22:26 am

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsCommunityDevLogsVoronoid: King of the Fill
Pages: [1]
Author Topic: Voronoid: King of the Fill  (Read 3075 times)
Level 0

View Profile
« on: December 27, 2012, 02:34:47 pm »


Several years ago, I slapped together a competitive multiplayer game in XNA for a vector-graphics prototyping class at uni. I tried to dredge up those archaic childhood feels of playing tag on the playground, with a slightly more sadistic, competitive twist. Enter TagNabIt.

In this top-down 'shooter', up to four players would pilot their Asteroids-inspired spaceship around the playing field. One person was always 'it' and their job was to tag another player, who then became 'it'. Everyone else's job was to avoid getting caught until the game timer runs out.
Holding down one of the triggers on your controller would cause you to boost until you let go of the trigger or ran out of fuel. Fuel was restored at a much a slower rate than it was consumed, making boosting a strategic resource. The end result was a lot of really intense dogfights where players would just barely scrape past each other and avoid getting tagged.

This was my first foray into multiplayer game design and the reaction was much better than I expected. I tested it with some close friends and things got very heated very quickly. If there's not already a unit of measurement for tracking the time it takes for a game to elicit inter-player profanity, there really should be. TagNabIt's zero-to-"FUCK YOU!" time was rather low.

Lacking the time and interest to further develop the game and put it on XBLIG, I shelved the prototype and moved on to other projects. Lately that itch to make a competitive couch play game has returned, so I decided to resurrect key elements of TagNabIt and combine them with a technology that's interested me greatly lately: Voronoi diagrams.

A Voronoi diagram is a collection of cells, each of which contains all of the points in space that are closest to a particular control point in the graph. These sorts of diagrams have a lot of practical applications, especially in the fields of technology that deal with nearest neighbor queries. Surprisingly, I don't think I've ever seen them used prominently in games, with the exception of one of the fantastic visualizers in Q-Games' PixelJunk 4am and this excellent exploration of polygonal map generation.

I have a working C# implementation of Fortune's algorithm, which is used to construct the edges of a Voronoi diagram in a reasonably short amount of time. Voronoi diagrams are aesthetically interesting, to me at least, and even more so when they're set in motion. I really like the way a cell's appearance can change drastically with just a small amount of movement. A non-interactive example of a fluid Voronoi diagram is available here. There's a nearly invisible slider on the left that can be tweaked to increase or decrease the number of points in the diagram.

As an aside, I'm intending to bundle the Voronoi tech and release it as a package on the Unity asset store, so if anyone is interested in previewing and helping test the code before I release it, PM me!

The Game

Work in progress - 01.08.2013

Voronoid: King of the Fill is a fast-paced game of dominance that takes place on an intensely dynamic playing field. The game supports 3-4 players, though at the moment there's nothing specific limiting me from increasing the upper bounds, aside from some possible UI restrictions. Unity claims to support up to 11 joysticks simultaneously...

Player movement is about as simple as it gets, with nothing more than a joystick for controlling your character on a 2D plane and an analog trigger which throttles boosting. I'm thinking of mapping all of the other gamepad buttons to a simple 'action' button that executes the equivalent of a half-second boost.

Each player's ship controls a point in the Voronoi diagram. The size of the cell surrounding your ship determines how quickly you progress towards collecting a point. I'll calculate the area of each polygonal cell and divide it by the total area of the playing field, leaving each player with a percentage that I multiply against some maximum point-accumulation speed. Basically, the more pixels that are closest to you and nobody else, the faster you'll gain a point. If you've ever played that carnival game where ten people fire water guns at a target to make their horse reach the finish line first, it's a lot like that.

Due to the way Voronoi diagrams work, each player's cell will be close to the same size (I estimate ~±5% variance across the board, on average), unless a player gets trapped in a corner or surrounded by other players. The more evenly spaced apart the players are, the more equivalent everyone's cells will be. Because of this, I suspect that each match will be very neck'n'neck, with one player winning the match by only a few seconds or so.

To further add to the intensity of things, players can use their ship to boost into other players, shunting them aside and stunning them for a second or two. Shunting another person also results in the attacker stealing some point progress from the defender. The 'winner' of a collision is determined by whichever player is moving faster. If both players are moving at the same speed, the facing direction of each player is taken into consideration. If two players are boosting head on at each other, they will harmlessly ricochet off each other and suffer no penalty. That means the best thing to do if someone comes flying at you is to either get the hell out of their way or meet them head on, both of which are hard to do if you've already spent your fuel and are waiting for it to come back.

For simplicity's sake, those are the two primary gameplay mechanics I'm incorporating. TagNabIt's development proved that there's a lot of depth in the boosting ability and my hope is that overlaying the Voronoi diagram on top of things will round it all out and impose a nice balance between seeking out the 'high ground' and smashing your opponents into oblivion.


I keep the web build up to date as often as possible. You can find it here.
Updated 01/08/2013 - 1:15AM

Joystick (Up to 2 players) or WASD - Move your ship
L/R Trigger or Space - Boost


There are still several things I need to do before the game is in a playable, testable state. Right now two players can control their own ships and knock the other two dummy players around on the screen.

  • Ensure Voronoi graph generates stable polygonal cells
  • Add 'CalculateArea' method to the Voronoi cell class
  • Display each player's boost meter
  • Display total area of each player's cell
  • Display each player's point tally, plus progress towards the next point
  • Implement point accumulation over time
  • Improve player-to-player collision
  • Iterate on player ship design
  • Placeholder SFX
  • Particles?

I'm intending to do all, or most, of the art myself for now. I haven't quite settled on the final aesthetic for the game, and this may be something I pass off to somebody else, depending on how things go.
« Last Edit: January 09, 2013, 01:58:00 pm by Kavika » Logged
Level 0


View Profile
« Reply #1 on: December 27, 2012, 02:41:24 pm »

Sounds interesting. I like tactical and intense battles.  Kiss
Level 0

View Profile
« Reply #2 on: December 28, 2012, 01:31:32 am »

Thanks Atrus!

I improved the rendering of cell edges so they're not boring grey lines anymore. I figured it couldn't hurt to throw up a playable build either. Spent some time adding keyboard input (instead of just joystick support) and making a web player. If you have an Xbox controller (or two) handy, definitely use that, otherwise WASD and Space will suffice.

Hitting one of the bottom two ships results in a slowed down version of the shunting reaction; the slow down is only temporary so I can frame-by-frame the feel of the knockback effect. I'll be removing that soon.

You can try out the build here.
Level 0

View Profile
« Reply #3 on: January 02, 2013, 12:23:46 pm »

Holiday update!

Apparently when I ported my Voronoi implementation from openFrameworks to Unity, I didn't fully understand the differences between C# structs and classes, in terms of being stored by value or by reference. This resulted in the algorithm that generates polygons from the edges of the graph becoming totally borked. In the C++ version, polygons simply track a list of pointers to unfinished graph edges; at a later point in time, when the whole graph has been computed and the edges are finalized, polygons are generated from the edge endpoints. In my broken port, edges were structs instead of classes, resulting in each edge getting copied in its current state whenever it was added to a polygon.

Long story short, it's all fixed now. I added a polygon clipping algorithm as well, so that I can clamp the polygon edges to the playing field. I sort of overlooked this step when I made my last tasklist and it definitely ended up taking me more time than I thought it would. With properly formed polygons, I'm able to calculate the area of each cell using this handy formula. You essentially sum the area of a triangle list formed by the edges of the polygon - it works perfectly for convex, regular polygons but I suspect it would fall apart in certain situations.

With polygon generation and area computation behind me, I'm excited to turn my attention to writing actual gameplay! That was my last major technical hurdle to overcome and I'm satisfied that I've sufficiently addressed the hardest parts of the project, aside from making it fun.

I spent some time writing a shader that uses one greyscale texture as a mask for another, intending to create an animated ring for the player's boost meter. Of course, once I had it working, I stumbled upon this much better Dynamic Circles plugin on the asset store. $5? Sold!
I'm not happy with the thickness of the ring or the amount of space it takes up. I think I'll try thinning it out a bit and making it a quarter circle instead of a full one so that I can use the space around the player for other things as well.

I regret having to shrink the playing field to accommodate the HUD at the top. I think it's really important to be able to see each player's progress towards the next point, so it's a sacrifice I'm willing to make. I'm hoping to play around with some other ways of representing that data; maybe putting something in a 3D scene behind the playing field, sort of blurred out so it doesn't steal focus from the game but still makes it easy to tell at a glance who's about to snag the next point.

The art is still very meh, but I'm ignoring it as much as I can until the core gameplay is all there and I'm able to play a match from start to finish with three friends. Most of all, I need a better ship. I'm still on the fence about how it should look, whether or not I should use the same Asteroids style ship I used in TagNabIt or try something a little softer.

I've updated the WIP picture in the first post and also updated the web build. Joystick controls work best, but WASD / Space will do in a pinch if you don't have one handy.
Kris with a K
Level 1

It's a good day to die.

View Profile
« Reply #4 on: January 02, 2013, 11:49:49 pm »

This is kind of awesome. First time I've heard of Voronoids; you're right, they are cool.

Few problems though -

1. May just be me, but I can't control more than one player. WASD and my USB gamepad (standard xbox model) both move orange.

2) Terrible art. Sorry, but it's true. It's not really distinct from other games, or unified within itself to be compelling or interesting. You've got some vaguely industrial borders, dividing lines that don't match said borders, and worst of all a weird range of player colors (purple, blue, and that lime color are all cools that are too similar to each other, but then there's an orange that, while distinct, totally doesn't match the theme. And they all look too similar to differentiate them - a problem exacerbated by the fuel color being the same for every player, and the sprites being so small). It's still a prototype, I know, and maybe you have no art skill (or you do and you're holding off until the game itself is finished), but it needs more style.

3) This is more subjective, but is the stealing mechanic even necessary? I have no idea as I haven't actually played it to win (broken controls) but a totally non-combat-oriented game is kind of a cool concept. Just throwing out a random suggestion, but assuming you keep it, I would increase the collision area slightly to make it easier to hit each other.

4.Playing area, I think the rectangle leaves too many undesirable areas.  Seems to me your position relative to other players, not the map, should be the prime factor, as in a circle or hexagon. Or hell, a roughly circular voronoi diagram as shown in that map generation link of yours.

Anyways, hope I didn't go overboard on the suggestions. Not trying to co-opt your game, just trying to help.

One last idea, re your UI problem: the score meter could be expressed as increasing opacity of each player's color in their area. Helps to solve the art style problem, focuses the player's attention on the field (and makes it very obvious to see who has the most points) instead of divided between it and the UI, and frees up screen space to increase the size of the map. Since you share these concerns, about UI/art style, I think you should try it, I believe it would help a lot.

Anyways, sweet game. I'd like to see it on XBLIG but I guess that can't happen if you're working in Unity. :/ Maybe Arcade.
« Last Edit: January 02, 2013, 11:55:58 pm by 7heSama » Logged

Level 0

View Profile
« Reply #5 on: January 03, 2013, 01:10:51 am »

Hey, thanks for taking the time to reply! These are exactly the kinds of discussions I'd love to have about the game, so I can either defend my choices or re-examine a particular part of the game Smiley

1.) No, that's by 'design'. WASD and the controller both go to player 1 at the moment. I wasn't trying to solicit feedback for character collision yet, so I left it all disabled. I actually don't even have the other two players mapped in yet since I only have two controllers. Getting some help from a friend to test that tomorrow night!

2.) Yes, it's abysmal. Actually, it's gotten slightly better as of tonight, I think. Part of my problem is that I don't have a strong sense of character design in my head right now, apart from how movement should feel. Appearance wise, it's pretty blank. Maybe I could render each player as a smaller voronoi diagram, with their own little bounding cells inside...ohmygod, yes, that is happening. Fractal levels, each one taking place inside the winning player's body...

On a more pertinent note, yes, the colors were semi-randomly picked. I just wanted something different from RGBY and those were the first moderately hue separated values I landed on. My plan is for the character customization screen to have a palette full of colors that players can choose from so they can be as ugly or as color coordinated as they all care to be.
Art is definitely one of those things I'm considering outsourcing, but I'd like to give it a shot over the course of development to see how well I can do on my own. As a programmer by day, I'm almost never responsible for the look of things and that's a skill I'd like to develop.

3.) The stealing mechanic isn't strictly necessary, but I felt like there should be some way to hamper other player's progress with a well-time, skill-based maneuver. The playing field is moderately unpredictable (I suspect, having only tried it with two controllers at once, I can only imagine four...), so I wanted to add something more technical to counteract it.

If ignoring the diagram and focusing all of your time on bashing other players is the most effective way to play, then I'll tone down the amount of progress you gain/lose when you're involved in a shunt.

4.) Alternate level shapes is actually a great idea that I hadn't yet considered. I was wondering if I would do a map selection mode at all and now I think I have my answer. I picked a rectangle because it makes the best use of the screen space, and the game is all about maximizing space, so it seemed like a natural choice. I suppose I could make playing fields that are larger than the screen and just pull back the camera as the players drift apart.
One difference is that the bigger the total area, the less likely you are to get into a dogfight with another player. It would become a much more strategic game, I think.

[5].) Yes, I'm intending to use the opacity of each player's cell to my advantage in representing data. I was thinking the greater their ownership of the field, the more vibrant the color of their cell becomes, or something. I had hoped to avoid shrinking the playing field to fit the UI, but I didn't have a good idea of how to represent everything on the player - in large part because I'm still lacking a decisive ship design.

Thanks for your input! XBLIG is unlikely to happen, unless they start supporting Unity. I think that it's going to be more of a showcase game that pops up at indie meetups and LAN parties. I hope it's that catchy, anyway! There's not a huge market for couchplay mutliplayer games, although SPORTSFRIENDS looks to be setting a trend of their own.

I just updated the build again with a bunch of HUD changes.

« Last Edit: January 09, 2013, 12:32:33 pm by Kavika » Logged
Level 0

View Profile
« Reply #6 on: January 09, 2013, 01:57:43 pm »

It's been almost a week since my last update. I'm a little sad that most of the pertinent elements are all up on screen now, since that's always one of the most exciting parts of making a new game, when you see everything starting to take form.

Last week I added in the input mappings for Players 3 and 4, which was mostly busy work.
I'm designing the game to be playable on both PC and Mac OSX, since those are the two machines I'm developing on. Because the game is controller driven, I needed to install the Tattiebogle Xbox gamepad drivers for OSX, which unfortunately specifies a completely different mapping for almost all of the buttons and joysticks. Horizontal and vertical thumbstick input is the same between platforms, but each trigger requires a separate entry in Unity's input mapping list, one for PC and one for OSX.

It looks a bit gross, because each player requires a minimum of seven inputs (Vertical, Horizontal, L Trigger, R Trigger, L Trigger (OSX), R Trigger (OSX), A button), expanding the input list to 28 entries for four players, plus some others for controlling Player 1 with the keyboard.

I really shouldn't be complaining. It works perfectly and didn't take that long to set up; I just wish there was a cleaner way to edit the mappings. The collapsible list view doesn't hold up that well when you have this many entries.

I didn't intend to, but I wound up taking the weekend off from working on the game. I realized later that it was because I was procrastinating working on the one thing I most dreaded: player collisions.

For me, this is one of the most important mechanics in the game, along with basic movement. Fortunately, Unity's physics make the actual collision itself trivial to detect. Then, with a mixture of a really, really simple FSM and coroutines I'm able to split the effect into a series of linear instructions, which is so, so much easier than controlling everything in a single Update function with a complicated switch statement.

In the event of a shunt, each player gets pushed backwards. The attacker only experiences a slight amount of recoil, during which time they cannot move, while the defender slides back quite a bit further. At the same time, the victor's Voronoi cell pulses while the line segment separating the space between the players flashes brightly (not yet implemented). Later I'll be adding some sparks to the collision and SFX to make it a bit more visceral.

I added the center point of every Voronoi cell to its corresponding mesh that I construct each frame. I also changed the UV mapping so that the new center point is (0,0) while the outer points are all (1,1), which allowed me to pull off some neat effects with a custom shader.
Specifically, I take the player's color and multiply it by the product of the UV coordinates at each pixel, which ends up creating this trippy perspective effect, almost like you're staring down a pit.
Then I scale the brightness by an 'intensity' shader property which corresponds to the percentage of screen space controlled. When one player hits another, I ramp up a 'surge' parameter on the player, which gets added into the intensity, creating that flare. I'm thinking of cranking the maximum surge value up again, because it creates this awesome bloom when the colors get blown out.

Basically, the brighter the cell, the better you're doing. This also creates a really cool effect when two players are fighting over a spot in one of the corners, due to the sudden flashes of alternating colors. Try ramming the blue guy down towards the bottom of the screen til your cell is super bright, then fly around him in a circle!

This was unintentional, but I really like how the darkness at the center surrounds the player, making sure he/she stands out and doesn't get lost in all of the mess. Because of the way the Voronoi diagram works, everyone is always going to be compartmentalized within their cell, and I think this effect reinforces that concept.

Here is a screencap of the game in its present state, though I have to say those cells look a whole lot better in motion. As usual, you can check out the latest version in your browser using the link at the bottom of the top post. Or here, for the lazy.

As always, feedback is greatly appreciated! I've stated this numerous times before, but yes, the art is all WIP. What I'm focused on now is perfecting the gameplay and experimenting with effects that take advantage of the Voronoi diagram's unique aesthetic. Texturing is very, very low on my priority list right now, though opinions on things such as contrast and scale are definitely welcome.

Pages: [1]
Jump to:  

Theme orange-lt created by panic